library/core/tests/slice.rs

   1 use core::cell::Cell;
   2 use core::cmp::Ordering;
   3 use core::result::Result::{Err, Ok};
   4
   5 #[test]
   6 fn test_position() {
   7     let b = [1, 2, 3, 5, 5];
   8     assert_eq!(b.iter().position(|&v| v == 9), None);
   9     assert_eq!(b.iter().position(|&v| v == 5), Some(3));
  10     assert_eq!(b.iter().position(|&v| v == 3), Some(2));
  11     assert_eq!(b.iter().position(|&v| v == 0), None);
  12 }
  13
  14 #[test]
  15 fn test_rposition() {
  16     let b = [1, 2, 3, 5, 5];
  17     assert_eq!(b.iter().rposition(|&v| v == 9), None);
  18     assert_eq!(b.iter().rposition(|&v| v == 5), Some(4));
  19     assert_eq!(b.iter().rposition(|&v| v == 3), Some(2));
  20     assert_eq!(b.iter().rposition(|&v| v == 0), None);
  21 }
  22
  23 #[test]
  24 fn test_binary_search() {
  25     let b: [i32; 0] = [];
  26     assert_eq!(b.binary_search(&5), Err(0));
  27
  28     let b = [4];
  29     assert_eq!(b.binary_search(&3), Err(0));
  30     assert_eq!(b.binary_search(&4), Ok(0));
  31     assert_eq!(b.binary_search(&5), Err(1));
  32
  33     let b = [1, 2, 4, 6, 8, 9];
  34     assert_eq!(b.binary_search(&5), Err(3));
  35     assert_eq!(b.binary_search(&6), Ok(3));
  36     assert_eq!(b.binary_search(&7), Err(4));
  37     assert_eq!(b.binary_search(&8), Ok(4));
  38
  39     let b = [1, 2, 4, 5, 6, 8];
  40     assert_eq!(b.binary_search(&9), Err(6));
  41
  42     let b = [1, 2, 4, 6, 7, 8, 9];
  43     assert_eq!(b.binary_search(&6), Ok(3));
  44     assert_eq!(b.binary_search(&5), Err(3));
  45     assert_eq!(b.binary_search(&8), Ok(5));
  46
  47     let b = [1, 2, 4, 5, 6, 8, 9];
  48     assert_eq!(b.binary_search(&7), Err(5));
  49     assert_eq!(b.binary_search(&0), Err(0));
  50
  51     let b = [1, 3, 3, 3, 7];
  52     assert_eq!(b.binary_search(&0), Err(0));
  53     assert_eq!(b.binary_search(&1), Ok(0));
  54     assert_eq!(b.binary_search(&2), Err(1));
  55     assert!(match b.binary_search(&3) {
  56         Ok(1..=3) => true,
  57         _ => false,
  58     });
  59     assert!(match b.binary_search(&3) {
  60         Ok(1..=3) => true,
  61         _ => false,
  62     });
  63     assert_eq!(b.binary_search(&4), Err(4));
  64     assert_eq!(b.binary_search(&5), Err(4));
  65     assert_eq!(b.binary_search(&6), Err(4));
  66     assert_eq!(b.binary_search(&7), Ok(4));
  67     assert_eq!(b.binary_search(&8), Err(5));
  68
  69     let b = [(); usize::MAX];
  70     assert_eq!(b.binary_search(&()), Ok(usize::MAX / 2));
  71 }
  72
  73 #[test]
  74 fn test_binary_search_by_overflow() {
  75     let b = [(); usize::MAX];
  76     assert_eq!(b.binary_search_by(|_| Ordering::Equal), Ok(usize::MAX / 2));
  77     assert_eq!(b.binary_search_by(|_| Ordering::Greater), Err(0));
  78     assert_eq!(b.binary_search_by(|_| Ordering::Less), Err(usize::MAX));
  79 }
  80
  81 #[test]
  82 // Test implementation specific behavior when finding equivalent elements.
  83 // It is ok to break this test but when you do a crater run is highly advisable.
  84 fn test_binary_search_implementation_details() {
  85     let b = [1, 1, 2, 2, 3, 3, 3];
  86     assert_eq!(b.binary_search(&1), Ok(1));
  87     assert_eq!(b.binary_search(&2), Ok(3));
  88     assert_eq!(b.binary_search(&3), Ok(5));
  89     let b = [1, 1, 1, 1, 1, 3, 3, 3, 3];
  90     assert_eq!(b.binary_search(&1), Ok(4));
  91     assert_eq!(b.binary_search(&3), Ok(7));
  92     let b = [1, 1, 1, 1, 3, 3, 3, 3, 3];
  93     assert_eq!(b.binary_search(&1), Ok(2));
  94     assert_eq!(b.binary_search(&3), Ok(4));
  95 }
  96
  97 #[test]
  98 fn test_partition_point() {
  99     let b: [i32; 0] = [];
 100     assert_eq!(b.partition_point(|&x| x < 5), 0);
 101
 102     let b = [4];
 103     assert_eq!(b.partition_point(|&x| x < 3), 0);
 104     assert_eq!(b.partition_point(|&x| x < 4), 0);
 105     assert_eq!(b.partition_point(|&x| x < 5), 1);
 106
 107     let b = [1, 2, 4, 6, 8, 9];
 108     assert_eq!(b.partition_point(|&x| x < 5), 3);
 109     assert_eq!(b.partition_point(|&x| x < 6), 3);
 110     assert_eq!(b.partition_point(|&x| x < 7), 4);
 111     assert_eq!(b.partition_point(|&x| x < 8), 4);
 112
 113     let b = [1, 2, 4, 5, 6, 8];
 114     assert_eq!(b.partition_point(|&x| x < 9), 6);
 115
 116     let b = [1, 2, 4, 6, 7, 8, 9];
 117     assert_eq!(b.partition_point(|&x| x < 6), 3);
 118     assert_eq!(b.partition_point(|&x| x < 5), 3);
 119     assert_eq!(b.partition_point(|&x| x < 8), 5);
 120
 121     let b = [1, 2, 4, 5, 6, 8, 9];
 122     assert_eq!(b.partition_point(|&x| x < 7), 5);
 123     assert_eq!(b.partition_point(|&x| x < 0), 0);
 124
 125     let b = [1, 3, 3, 3, 7];
 126     assert_eq!(b.partition_point(|&x| x < 0), 0);
 127     assert_eq!(b.partition_point(|&x| x < 1), 0);
 128     assert_eq!(b.partition_point(|&x| x < 2), 1);
 129     assert_eq!(b.partition_point(|&x| x < 3), 1);
 130     assert_eq!(b.partition_point(|&x| x < 4), 4);
 131     assert_eq!(b.partition_point(|&x| x < 5), 4);
 132     assert_eq!(b.partition_point(|&x| x < 6), 4);
 133     assert_eq!(b.partition_point(|&x| x < 7), 4);
 134     assert_eq!(b.partition_point(|&x| x < 8), 5);
 135 }
 136
 137 #[test]
 138 fn test_iterator_advance_by() {
 139     let v = &[0, 1, 2, 3, 4];
 140
 141     for i in 0..=v.len() {
 142         let mut iter = v.iter();
 143         iter.advance_by(i).unwrap();
 144         assert_eq!(iter.as_slice(), &v[i..]);
 145     }
 146
 147     let mut iter = v.iter();
 148     assert_eq!(iter.advance_by(v.len() + 1), Err(v.len()));
 149     assert_eq!(iter.as_slice(), &[]);
 150
 151     let mut iter = v.iter();
 152     iter.advance_by(3).unwrap();
 153     assert_eq!(iter.as_slice(), &v[3..]);
 154     iter.advance_by(2).unwrap();
 155     assert_eq!(iter.as_slice(), &[]);
 156 }
 157
 158 #[test]
 159 fn test_iterator_advance_back_by() {
 160     let v = &[0, 1, 2, 3, 4];
 161
 162     for i in 0..=v.len() {
 163         let mut iter = v.iter();
 164         iter.advance_back_by(i).unwrap();
 165         assert_eq!(iter.as_slice(), &v[..v.len() - i]);
 166     }
 167
 168     let mut iter = v.iter();
 169     assert_eq!(iter.advance_back_by(v.len() + 1), Err(v.len()));
 170     assert_eq!(iter.as_slice(), &[]);
 171
 172     let mut iter = v.iter();
 173     iter.advance_back_by(3).unwrap();
 174     assert_eq!(iter.as_slice(), &v[..v.len() - 3]);
 175     iter.advance_back_by(2).unwrap();
 176     assert_eq!(iter.as_slice(), &[]);
 177 }
 178
 179 #[test]
 180 fn test_iterator_nth() {
 181     let v: &[_] = &[0, 1, 2, 3, 4];
 182     for i in 0..v.len() {
 183         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
 184     }
 185     assert_eq!(v.iter().nth(v.len()), None);
 186
 187     let mut iter = v.iter();
 188     assert_eq!(iter.nth(2).unwrap(), &v[2]);
 189     assert_eq!(iter.nth(1).unwrap(), &v[4]);
 190 }
 191
 192 #[test]
 193 fn test_iterator_nth_back() {
 194     let v: &[_] = &[0, 1, 2, 3, 4];
 195     for i in 0..v.len() {
 196         assert_eq!(v.iter().nth_back(i).unwrap(), &v[v.len() - i - 1]);
 197     }
 198     assert_eq!(v.iter().nth_back(v.len()), None);
 199
 200     let mut iter = v.iter();
 201     assert_eq!(iter.nth_back(2).unwrap(), &v[2]);
 202     assert_eq!(iter.nth_back(1).unwrap(), &v[0]);
 203 }
 204
 205 #[test]
 206 fn test_iterator_last() {
 207     let v: &[_] = &[0, 1, 2, 3, 4];
 208     assert_eq!(v.iter().last().unwrap(), &4);
 209     assert_eq!(v[..1].iter().last().unwrap(), &0);
 210 }
 211
 212 #[test]
 213 fn test_iterator_count() {
 214     let v: &[_] = &[0, 1, 2, 3, 4];
 215     assert_eq!(v.iter().count(), 5);
 216
 217     let mut iter2 = v.iter();
 218     iter2.next();
 219     iter2.next();
 220     assert_eq!(iter2.count(), 3);
 221 }
 222
 223 #[test]
 224 fn test_chunks_count() {
 225     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 226     let c = v.chunks(3);
 227     assert_eq!(c.count(), 2);
 228
 229     let v2: &[i32] = &[0, 1, 2, 3, 4];
 230     let c2 = v2.chunks(2);
 231     assert_eq!(c2.count(), 3);
 232
 233     let v3: &[i32] = &[];
 234     let c3 = v3.chunks(2);
 235     assert_eq!(c3.count(), 0);
 236 }
 237
 238 #[test]
 239 fn test_chunks_nth() {
 240     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 241     let mut c = v.chunks(2);
 242     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 243     assert_eq!(c.next().unwrap(), &[4, 5]);
 244
 245     let v2: &[i32] = &[0, 1, 2, 3, 4];
 246     let mut c2 = v2.chunks(3);
 247     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 248     assert_eq!(c2.next(), None);
 249 }
 250
 251 #[test]
 252 fn test_chunks_nth_back() {
 253     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 254     let mut c = v.chunks(2);
 255     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 256     assert_eq!(c.next().unwrap(), &[0, 1]);
 257     assert_eq!(c.next(), None);
 258
 259     let v2: &[i32] = &[0, 1, 2, 3, 4];
 260     let mut c2 = v2.chunks(3);
 261     assert_eq!(c2.nth_back(1).unwrap(), &[0, 1, 2]);
 262     assert_eq!(c2.next(), None);
 263     assert_eq!(c2.next_back(), None);
 264
 265     let v3: &[i32] = &[0, 1, 2, 3, 4];
 266     let mut c3 = v3.chunks(10);
 267     assert_eq!(c3.nth_back(0).unwrap(), &[0, 1, 2, 3, 4]);
 268     assert_eq!(c3.next(), None);
 269
 270     let v4: &[i32] = &[0, 1, 2];
 271     let mut c4 = v4.chunks(10);
 272     assert_eq!(c4.nth_back(1_000_000_000usize), None);
 273 }
 274
 275 #[test]
 276 fn test_chunks_last() {
 277     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 278     let c = v.chunks(2);
 279     assert_eq!(c.last().unwrap()[1], 5);
 280
 281     let v2: &[i32] = &[0, 1, 2, 3, 4];
 282     let c2 = v2.chunks(2);
 283     assert_eq!(c2.last().unwrap()[0], 4);
 284 }
 285
 286 #[test]
 287 fn test_chunks_zip() {
 288     let v1: &[i32] = &[0, 1, 2, 3, 4];
 289     let v2: &[i32] = &[6, 7, 8, 9, 10];
 290
 291     let res = v1
 292         .chunks(2)
 293         .zip(v2.chunks(2))
 294         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 295         .collect::<Vec<_>>();
 296     assert_eq!(res, vec![14, 22, 14]);
 297 }
 298
 299 #[test]
 300 fn test_chunks_mut_count() {
 301     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 302     let c = v.chunks_mut(3);
 303     assert_eq!(c.count(), 2);
 304
 305     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 306     let c2 = v2.chunks_mut(2);
 307     assert_eq!(c2.count(), 3);
 308
 309     let v3: &mut [i32] = &mut [];
 310     let c3 = v3.chunks_mut(2);
 311     assert_eq!(c3.count(), 0);
 312 }
 313
 314 #[test]
 315 fn test_chunks_mut_nth() {
 316     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 317     let mut c = v.chunks_mut(2);
 318     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 319     assert_eq!(c.next().unwrap(), &[4, 5]);
 320
 321     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 322     let mut c2 = v2.chunks_mut(3);
 323     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 324     assert_eq!(c2.next(), None);
 325 }
 326
 327 #[test]
 328 fn test_chunks_mut_nth_back() {
 329     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 330     let mut c = v.chunks_mut(2);
 331     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 332     assert_eq!(c.next().unwrap(), &[0, 1]);
 333
 334     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 335     let mut c1 = v1.chunks_mut(3);
 336     assert_eq!(c1.nth_back(1).unwrap(), &[0, 1, 2]);
 337     assert_eq!(c1.next(), None);
 338
 339     let v3: &mut [i32] = &mut [0, 1, 2, 3, 4];
 340     let mut c3 = v3.chunks_mut(10);
 341     assert_eq!(c3.nth_back(0).unwrap(), &[0, 1, 2, 3, 4]);
 342     assert_eq!(c3.next(), None);
 343
 344     let v4: &mut [i32] = &mut [0, 1, 2];
 345     let mut c4 = v4.chunks_mut(10);
 346     assert_eq!(c4.nth_back(1_000_000_000usize), None);
 347 }
 348
 349 #[test]
 350 fn test_chunks_mut_last() {
 351     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 352     let c = v.chunks_mut(2);
 353     assert_eq!(c.last().unwrap(), &[4, 5]);
 354
 355     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 356     let c2 = v2.chunks_mut(2);
 357     assert_eq!(c2.last().unwrap(), &[4]);
 358 }
 359
 360 #[test]
 361 fn test_chunks_mut_zip() {
 362     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 363     let v2: &[i32] = &[6, 7, 8, 9, 10];
 364
 365     for (a, b) in v1.chunks_mut(2).zip(v2.chunks(2)) {
 366         let sum = b.iter().sum::<i32>();
 367         for v in a {
 368             *v += sum;
 369         }
 370     }
 371     assert_eq!(v1, [13, 14, 19, 20, 14]);
 372 }
 373
 374 #[test]
 375 fn test_chunks_exact_count() {
 376     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 377     let c = v.chunks_exact(3);
 378     assert_eq!(c.count(), 2);
 379
 380     let v2: &[i32] = &[0, 1, 2, 3, 4];
 381     let c2 = v2.chunks_exact(2);
 382     assert_eq!(c2.count(), 2);
 383
 384     let v3: &[i32] = &[];
 385     let c3 = v3.chunks_exact(2);
 386     assert_eq!(c3.count(), 0);
 387 }
 388
 389 #[test]
 390 fn test_chunks_exact_nth() {
 391     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 392     let mut c = v.chunks_exact(2);
 393     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 394     assert_eq!(c.next().unwrap(), &[4, 5]);
 395
 396     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 397     let mut c2 = v2.chunks_exact(3);
 398     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 399     assert_eq!(c2.next(), None);
 400 }
 401
 402 #[test]
 403 fn test_chunks_exact_nth_back() {
 404     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 405     let mut c = v.chunks_exact(2);
 406     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 407     assert_eq!(c.next().unwrap(), &[0, 1]);
 408     assert_eq!(c.next(), None);
 409
 410     let v2: &[i32] = &[0, 1, 2, 3, 4];
 411     let mut c2 = v2.chunks_exact(3);
 412     assert_eq!(c2.nth_back(0).unwrap(), &[0, 1, 2]);
 413     assert_eq!(c2.next(), None);
 414     assert_eq!(c2.next_back(), None);
 415
 416     let v3: &[i32] = &[0, 1, 2, 3, 4];
 417     let mut c3 = v3.chunks_exact(10);
 418     assert_eq!(c3.nth_back(0), None);
 419 }
 420
 421 #[test]
 422 fn test_chunks_exact_last() {
 423     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 424     let c = v.chunks_exact(2);
 425     assert_eq!(c.last().unwrap(), &[4, 5]);
 426
 427     let v2: &[i32] = &[0, 1, 2, 3, 4];
 428     let c2 = v2.chunks_exact(2);
 429     assert_eq!(c2.last().unwrap(), &[2, 3]);
 430 }
 431
 432 #[test]
 433 fn test_chunks_exact_remainder() {
 434     let v: &[i32] = &[0, 1, 2, 3, 4];
 435     let c = v.chunks_exact(2);
 436     assert_eq!(c.remainder(), &[4]);
 437 }
 438
 439 #[test]
 440 fn test_chunks_exact_zip() {
 441     let v1: &[i32] = &[0, 1, 2, 3, 4];
 442     let v2: &[i32] = &[6, 7, 8, 9, 10];
 443
 444     let res = v1
 445         .chunks_exact(2)
 446         .zip(v2.chunks_exact(2))
 447         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 448         .collect::<Vec<_>>();
 449     assert_eq!(res, vec![14, 22]);
 450 }
 451
 452 #[test]
 453 fn test_chunks_exact_mut_count() {
 454     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 455     let c = v.chunks_exact_mut(3);
 456     assert_eq!(c.count(), 2);
 457
 458     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 459     let c2 = v2.chunks_exact_mut(2);
 460     assert_eq!(c2.count(), 2);
 461
 462     let v3: &mut [i32] = &mut [];
 463     let c3 = v3.chunks_exact_mut(2);
 464     assert_eq!(c3.count(), 0);
 465 }
 466
 467 #[test]
 468 fn test_chunks_exact_mut_nth() {
 469     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 470     let mut c = v.chunks_exact_mut(2);
 471     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 472     assert_eq!(c.next().unwrap(), &[4, 5]);
 473
 474     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 475     let mut c2 = v2.chunks_exact_mut(3);
 476     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 477     assert_eq!(c2.next(), None);
 478 }
 479
 480 #[test]
 481 fn test_chunks_exact_mut_nth_back() {
 482     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 483     let mut c = v.chunks_exact_mut(2);
 484     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 485     assert_eq!(c.next().unwrap(), &[0, 1]);
 486     assert_eq!(c.next(), None);
 487
 488     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 489     let mut c2 = v2.chunks_exact_mut(3);
 490     assert_eq!(c2.nth_back(0).unwrap(), &[0, 1, 2]);
 491     assert_eq!(c2.next(), None);
 492     assert_eq!(c2.next_back(), None);
 493
 494     let v3: &mut [i32] = &mut [0, 1, 2, 3, 4];
 495     let mut c3 = v3.chunks_exact_mut(10);
 496     assert_eq!(c3.nth_back(0), None);
 497 }
 498
 499 #[test]
 500 fn test_chunks_exact_mut_last() {
 501     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 502     let c = v.chunks_exact_mut(2);
 503     assert_eq!(c.last().unwrap(), &[4, 5]);
 504
 505     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 506     let c2 = v2.chunks_exact_mut(2);
 507     assert_eq!(c2.last().unwrap(), &[2, 3]);
 508 }
 509
 510 #[test]
 511 fn test_chunks_exact_mut_remainder() {
 512     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 513     let c = v.chunks_exact_mut(2);
 514     assert_eq!(c.into_remainder(), &[4]);
 515 }
 516
 517 #[test]
 518 fn test_chunks_exact_mut_zip() {
 519     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 520     let v2: &[i32] = &[6, 7, 8, 9, 10];
 521
 522     for (a, b) in v1.chunks_exact_mut(2).zip(v2.chunks_exact(2)) {
 523         let sum = b.iter().sum::<i32>();
 524         for v in a {
 525             *v += sum;
 526         }
 527     }
 528     assert_eq!(v1, [13, 14, 19, 20, 4]);
 529 }
 530
 531 #[test]
 532 fn test_array_chunks_infer() {
 533     let v: &[i32] = &[0, 1, 2, 3, 4, -4];
 534     let c = v.array_chunks();
 535     for &[a, b, c] in c {
 536         assert_eq!(a + b + c, 3);
 537     }
 538
 539     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 540     let total = v2.array_chunks().map(|&[a, b]| a * b).sum::<i32>();
 541     assert_eq!(total, 2 * 3 + 4 * 5);
 542 }
 543
 544 #[test]
 545 fn test_array_chunks_count() {
 546     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 547     let c = v.array_chunks::<3>();
 548     assert_eq!(c.count(), 2);
 549
 550     let v2: &[i32] = &[0, 1, 2, 3, 4];
 551     let c2 = v2.array_chunks::<2>();
 552     assert_eq!(c2.count(), 2);
 553
 554     let v3: &[i32] = &[];
 555     let c3 = v3.array_chunks::<2>();
 556     assert_eq!(c3.count(), 0);
 557 }
 558
 559 #[test]
 560 fn test_array_chunks_nth() {
 561     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 562     let mut c = v.array_chunks::<2>();
 563     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 564     assert_eq!(c.next().unwrap(), &[4, 5]);
 565
 566     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 567     let mut c2 = v2.array_chunks::<3>();
 568     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 569     assert_eq!(c2.next(), None);
 570 }
 571
 572 #[test]
 573 fn test_array_chunks_nth_back() {
 574     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 575     let mut c = v.array_chunks::<2>();
 576     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 577     assert_eq!(c.next().unwrap(), &[0, 1]);
 578     assert_eq!(c.next(), None);
 579
 580     let v2: &[i32] = &[0, 1, 2, 3, 4];
 581     let mut c2 = v2.array_chunks::<3>();
 582     assert_eq!(c2.nth_back(0).unwrap(), &[0, 1, 2]);
 583     assert_eq!(c2.next(), None);
 584     assert_eq!(c2.next_back(), None);
 585
 586     let v3: &[i32] = &[0, 1, 2, 3, 4];
 587     let mut c3 = v3.array_chunks::<10>();
 588     assert_eq!(c3.nth_back(0), None);
 589 }
 590
 591 #[test]
 592 fn test_array_chunks_last() {
 593     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 594     let c = v.array_chunks::<2>();
 595     assert_eq!(c.last().unwrap(), &[4, 5]);
 596
 597     let v2: &[i32] = &[0, 1, 2, 3, 4];
 598     let c2 = v2.array_chunks::<2>();
 599     assert_eq!(c2.last().unwrap(), &[2, 3]);
 600 }
 601
 602 #[test]
 603 fn test_array_chunks_remainder() {
 604     let v: &[i32] = &[0, 1, 2, 3, 4];
 605     let c = v.array_chunks::<2>();
 606     assert_eq!(c.remainder(), &[4]);
 607 }
 608
 609 #[test]
 610 fn test_array_chunks_zip() {
 611     let v1: &[i32] = &[0, 1, 2, 3, 4];
 612     let v2: &[i32] = &[6, 7, 8, 9, 10];
 613
 614     let res = v1
 615         .array_chunks::<2>()
 616         .zip(v2.array_chunks::<2>())
 617         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 618         .collect::<Vec<_>>();
 619     assert_eq!(res, vec![14, 22]);
 620 }
 621
 622 #[test]
 623 fn test_array_chunks_mut_infer() {
 624     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 625     for a in v.array_chunks_mut() {
 626         let sum = a.iter().sum::<i32>();
 627         *a = [sum; 3];
 628     }
 629     assert_eq!(v, &[3, 3, 3, 12, 12, 12, 6]);
 630
 631     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 632     v2.array_chunks_mut().for_each(|[a, b]| core::mem::swap(a, b));
 633     assert_eq!(v2, &[1, 0, 3, 2, 5, 4, 6]);
 634 }
 635
 636 #[test]
 637 fn test_array_chunks_mut_count() {
 638     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 639     let c = v.array_chunks_mut::<3>();
 640     assert_eq!(c.count(), 2);
 641
 642     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 643     let c2 = v2.array_chunks_mut::<2>();
 644     assert_eq!(c2.count(), 2);
 645
 646     let v3: &mut [i32] = &mut [];
 647     let c3 = v3.array_chunks_mut::<2>();
 648     assert_eq!(c3.count(), 0);
 649 }
 650
 651 #[test]
 652 fn test_array_chunks_mut_nth() {
 653     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 654     let mut c = v.array_chunks_mut::<2>();
 655     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 656     assert_eq!(c.next().unwrap(), &[4, 5]);
 657
 658     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 659     let mut c2 = v2.array_chunks_mut::<3>();
 660     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 661     assert_eq!(c2.next(), None);
 662 }
 663
 664 #[test]
 665 fn test_array_chunks_mut_nth_back() {
 666     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 667     let mut c = v.array_chunks_mut::<2>();
 668     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 669     assert_eq!(c.next().unwrap(), &[0, 1]);
 670     assert_eq!(c.next(), None);
 671
 672     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 673     let mut c2 = v2.array_chunks_mut::<3>();
 674     assert_eq!(c2.nth_back(0).unwrap(), &[0, 1, 2]);
 675     assert_eq!(c2.next(), None);
 676     assert_eq!(c2.next_back(), None);
 677
 678     let v3: &mut [i32] = &mut [0, 1, 2, 3, 4];
 679     let mut c3 = v3.array_chunks_mut::<10>();
 680     assert_eq!(c3.nth_back(0), None);
 681 }
 682
 683 #[test]
 684 fn test_array_chunks_mut_last() {
 685     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 686     let c = v.array_chunks_mut::<2>();
 687     assert_eq!(c.last().unwrap(), &[4, 5]);
 688
 689     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 690     let c2 = v2.array_chunks_mut::<2>();
 691     assert_eq!(c2.last().unwrap(), &[2, 3]);
 692 }
 693
 694 #[test]
 695 fn test_array_chunks_mut_remainder() {
 696     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 697     let c = v.array_chunks_mut::<2>();
 698     assert_eq!(c.into_remainder(), &[4]);
 699 }
 700
 701 #[test]
 702 fn test_array_chunks_mut_zip() {
 703     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 704     let v2: &[i32] = &[6, 7, 8, 9, 10];
 705
 706     for (a, b) in v1.array_chunks_mut::<2>().zip(v2.array_chunks::<2>()) {
 707         let sum = b.iter().sum::<i32>();
 708         for v in a {
 709             *v += sum;
 710         }
 711     }
 712     assert_eq!(v1, [13, 14, 19, 20, 4]);
 713 }
 714
 715 #[test]
 716 fn test_array_windows_infer() {
 717     let v: &[i32] = &[0, 1, 0, 1];
 718     assert_eq!(v.array_windows::<2>().count(), 3);
 719     let c = v.array_windows();
 720     for &[a, b] in c {
 721         assert_eq!(a + b, 1);
 722     }
 723
 724     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 725     let total = v2.array_windows().map(|&[a, b, c]| a + b + c).sum::<i32>();
 726     assert_eq!(total, 3 + 6 + 9 + 12 + 15);
 727 }
 728
 729 #[test]
 730 fn test_array_windows_count() {
 731     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 732     let c = v.array_windows::<3>();
 733     assert_eq!(c.count(), 4);
 734
 735     let v2: &[i32] = &[0, 1, 2, 3, 4];
 736     let c2 = v2.array_windows::<6>();
 737     assert_eq!(c2.count(), 0);
 738
 739     let v3: &[i32] = &[];
 740     let c3 = v3.array_windows::<2>();
 741     assert_eq!(c3.count(), 0);
 742
 743     let v4: &[()] = &[(); usize::MAX];
 744     let c4 = v4.array_windows::<1>();
 745     assert_eq!(c4.count(), usize::MAX);
 746 }
 747
 748 #[test]
 749 fn test_array_windows_nth() {
 750     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 751     let snd = v.array_windows::<4>().nth(1);
 752     assert_eq!(snd, Some(&[1, 2, 3, 4]));
 753     let mut arr_windows = v.array_windows::<2>();
 754     assert_ne!(arr_windows.nth(0), arr_windows.nth(0));
 755     let last = v.array_windows::<3>().last();
 756     assert_eq!(last, Some(&[3, 4, 5]));
 757 }
 758
 759 #[test]
 760 fn test_array_windows_nth_back() {
 761     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 762     let snd = v.array_windows::<4>().nth_back(1);
 763     assert_eq!(snd, Some(&[1, 2, 3, 4]));
 764     let mut arr_windows = v.array_windows::<2>();
 765     assert_ne!(arr_windows.nth_back(0), arr_windows.nth_back(0));
 766 }
 767
 768 #[test]
 769 fn test_rchunks_count() {
 770     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 771     let c = v.rchunks(3);
 772     assert_eq!(c.count(), 2);
 773
 774     let v2: &[i32] = &[0, 1, 2, 3, 4];
 775     let c2 = v2.rchunks(2);
 776     assert_eq!(c2.count(), 3);
 777
 778     let v3: &[i32] = &[];
 779     let c3 = v3.rchunks(2);
 780     assert_eq!(c3.count(), 0);
 781 }
 782
 783 #[test]
 784 fn test_rchunks_nth() {
 785     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 786     let mut c = v.rchunks(2);
 787     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 788     assert_eq!(c.next().unwrap(), &[0, 1]);
 789
 790     let v2: &[i32] = &[0, 1, 2, 3, 4];
 791     let mut c2 = v2.rchunks(3);
 792     assert_eq!(c2.nth(1).unwrap(), &[0, 1]);
 793     assert_eq!(c2.next(), None);
 794 }
 795
 796 #[test]
 797 fn test_rchunks_nth_back() {
 798     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 799     let mut c = v.rchunks(2);
 800     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 801     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 802
 803     let v2: &[i32] = &[0, 1, 2, 3, 4];
 804     let mut c2 = v2.rchunks(3);
 805     assert_eq!(c2.nth_back(1).unwrap(), &[2, 3, 4]);
 806     assert_eq!(c2.next_back(), None);
 807 }
 808
 809 #[test]
 810 fn test_rchunks_last() {
 811     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 812     let c = v.rchunks(2);
 813     assert_eq!(c.last().unwrap()[1], 1);
 814
 815     let v2: &[i32] = &[0, 1, 2, 3, 4];
 816     let c2 = v2.rchunks(2);
 817     assert_eq!(c2.last().unwrap()[0], 0);
 818 }
 819
 820 #[test]
 821 fn test_rchunks_zip() {
 822     let v1: &[i32] = &[0, 1, 2, 3, 4];
 823     let v2: &[i32] = &[6, 7, 8, 9, 10];
 824
 825     let res = v1
 826         .rchunks(2)
 827         .zip(v2.rchunks(2))
 828         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 829         .collect::<Vec<_>>();
 830     assert_eq!(res, vec![26, 18, 6]);
 831 }
 832
 833 #[test]
 834 fn test_rchunks_mut_count() {
 835     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 836     let c = v.rchunks_mut(3);
 837     assert_eq!(c.count(), 2);
 838
 839     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 840     let c2 = v2.rchunks_mut(2);
 841     assert_eq!(c2.count(), 3);
 842
 843     let v3: &mut [i32] = &mut [];
 844     let c3 = v3.rchunks_mut(2);
 845     assert_eq!(c3.count(), 0);
 846 }
 847
 848 #[test]
 849 fn test_rchunks_mut_nth() {
 850     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 851     let mut c = v.rchunks_mut(2);
 852     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 853     assert_eq!(c.next().unwrap(), &[0, 1]);
 854
 855     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 856     let mut c2 = v2.rchunks_mut(3);
 857     assert_eq!(c2.nth(1).unwrap(), &[0, 1]);
 858     assert_eq!(c2.next(), None);
 859 }
 860
 861 #[test]
 862 fn test_rchunks_mut_nth_back() {
 863     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 864     let mut c = v.rchunks_mut(2);
 865     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 866     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 867
 868     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 869     let mut c2 = v2.rchunks_mut(3);
 870     assert_eq!(c2.nth_back(1).unwrap(), &[2, 3, 4]);
 871     assert_eq!(c2.next_back(), None);
 872 }
 873
 874 #[test]
 875 fn test_rchunks_mut_last() {
 876     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 877     let c = v.rchunks_mut(2);
 878     assert_eq!(c.last().unwrap(), &[0, 1]);
 879
 880     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 881     let c2 = v2.rchunks_mut(2);
 882     assert_eq!(c2.last().unwrap(), &[0]);
 883 }
 884
 885 #[test]
 886 fn test_rchunks_mut_zip() {
 887     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 888     let v2: &[i32] = &[6, 7, 8, 9, 10];
 889
 890     for (a, b) in v1.rchunks_mut(2).zip(v2.rchunks(2)) {
 891         let sum = b.iter().sum::<i32>();
 892         for v in a {
 893             *v += sum;
 894         }
 895     }
 896     assert_eq!(v1, [6, 16, 17, 22, 23]);
 897 }
 898
 899 #[test]
 900 fn test_rchunks_exact_count() {
 901     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 902     let c = v.rchunks_exact(3);
 903     assert_eq!(c.count(), 2);
 904
 905     let v2: &[i32] = &[0, 1, 2, 3, 4];
 906     let c2 = v2.rchunks_exact(2);
 907     assert_eq!(c2.count(), 2);
 908
 909     let v3: &[i32] = &[];
 910     let c3 = v3.rchunks_exact(2);
 911     assert_eq!(c3.count(), 0);
 912 }
 913
 914 #[test]
 915 fn test_rchunks_exact_nth() {
 916     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 917     let mut c = v.rchunks_exact(2);
 918     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 919     assert_eq!(c.next().unwrap(), &[0, 1]);
 920
 921     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 922     let mut c2 = v2.rchunks_exact(3);
 923     assert_eq!(c2.nth(1).unwrap(), &[1, 2, 3]);
 924     assert_eq!(c2.next(), None);
 925 }
 926
 927 #[test]
 928 fn test_rchunks_exact_nth_back() {
 929     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 930     let mut c = v.rchunks_exact(2);
 931     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 932     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 933
 934     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 935     let mut c2 = v2.rchunks_exact(3);
 936     assert_eq!(c2.nth_back(1).unwrap(), &[4, 5, 6]);
 937     assert_eq!(c2.next(), None);
 938 }
 939
 940 #[test]
 941 fn test_rchunks_exact_last() {
 942     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 943     let c = v.rchunks_exact(2);
 944     assert_eq!(c.last().unwrap(), &[0, 1]);
 945
 946     let v2: &[i32] = &[0, 1, 2, 3, 4];
 947     let c2 = v2.rchunks_exact(2);
 948     assert_eq!(c2.last().unwrap(), &[1, 2]);
 949 }
 950
 951 #[test]
 952 fn test_rchunks_exact_remainder() {
 953     let v: &[i32] = &[0, 1, 2, 3, 4];
 954     let c = v.rchunks_exact(2);
 955     assert_eq!(c.remainder(), &[0]);
 956 }
 957
 958 #[test]
 959 fn test_rchunks_exact_zip() {
 960     let v1: &[i32] = &[0, 1, 2, 3, 4];
 961     let v2: &[i32] = &[6, 7, 8, 9, 10];
 962
 963     let res = v1
 964         .rchunks_exact(2)
 965         .zip(v2.rchunks_exact(2))
 966         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 967         .collect::<Vec<_>>();
 968     assert_eq!(res, vec![26, 18]);
 969 }
 970
 971 #[test]
 972 fn test_rchunks_exact_mut_count() {
 973     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 974     let c = v.rchunks_exact_mut(3);
 975     assert_eq!(c.count(), 2);
 976
 977     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 978     let c2 = v2.rchunks_exact_mut(2);
 979     assert_eq!(c2.count(), 2);
 980
 981     let v3: &mut [i32] = &mut [];
 982     let c3 = v3.rchunks_exact_mut(2);
 983     assert_eq!(c3.count(), 0);
 984 }
 985
 986 #[test]
 987 fn test_rchunks_exact_mut_nth() {
 988     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 989     let mut c = v.rchunks_exact_mut(2);
 990     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 991     assert_eq!(c.next().unwrap(), &[0, 1]);
 992
 993     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 994     let mut c2 = v2.rchunks_exact_mut(3);
 995     assert_eq!(c2.nth(1).unwrap(), &[1, 2, 3]);
 996     assert_eq!(c2.next(), None);
 997 }
 998
 999 #[test]
1000 fn test_rchunks_exact_mut_nth_back() {
1001     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
1002     let mut c = v.rchunks_exact_mut(2);
1003     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
1004     assert_eq!(c.next_back().unwrap(), &[4, 5]);
1005
1006     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
1007     let mut c2 = v2.rchunks_exact_mut(3);
1008     assert_eq!(c2.nth_back(1).unwrap(), &[4, 5, 6]);
1009     assert_eq!(c2.next(), None);
1010 }
1011
1012 #[test]
1013 fn test_rchunks_exact_mut_last() {
1014     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
1015     let c = v.rchunks_exact_mut(2);
1016     assert_eq!(c.last().unwrap(), &[0, 1]);
1017
1018     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
1019     let c2 = v2.rchunks_exact_mut(2);
1020     assert_eq!(c2.last().unwrap(), &[1, 2]);
1021 }
1022
1023 #[test]
1024 fn test_rchunks_exact_mut_remainder() {
1025     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
1026     let c = v.rchunks_exact_mut(2);
1027     assert_eq!(c.into_remainder(), &[0]);
1028 }
1029
1030 #[test]
1031 fn test_rchunks_exact_mut_zip() {
1032     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
1033     let v2: &[i32] = &[6, 7, 8, 9, 10];
1034
1035     for (a, b) in v1.rchunks_exact_mut(2).zip(v2.rchunks_exact(2)) {
1036         let sum = b.iter().sum::<i32>();
1037         for v in a {
1038             *v += sum;
1039         }
1040     }
1041     assert_eq!(v1, [0, 16, 17, 22, 23]);
1042 }
1043
1044 #[test]
1045 fn test_windows_count() {
1046     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
1047     let c = v.windows(3);
1048     assert_eq!(c.count(), 4);
1049
1050     let v2: &[i32] = &[0, 1, 2, 3, 4];
1051     let c2 = v2.windows(6);
1052     assert_eq!(c2.count(), 0);
1053
1054     let v3: &[i32] = &[];
1055     let c3 = v3.windows(2);
1056     assert_eq!(c3.count(), 0);
1057
1058     let v4 = &[(); usize::MAX];
1059     let c4 = v4.windows(1);
1060     assert_eq!(c4.count(), usize::MAX);
1061 }
1062
1063 #[test]
1064 fn test_windows_nth() {
1065     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
1066     let mut c = v.windows(2);
1067     assert_eq!(c.nth(2).unwrap()[1], 3);
1068     assert_eq!(c.next().unwrap()[0], 3);
1069
1070     let v2: &[i32] = &[0, 1, 2, 3, 4];
1071     let mut c2 = v2.windows(4);
1072     assert_eq!(c2.nth(1).unwrap()[1], 2);
1073     assert_eq!(c2.next(), None);
1074 }
1075
1076 #[test]
1077 fn test_windows_nth_back() {
1078     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
1079     let mut c = v.windows(2);
1080     assert_eq!(c.nth_back(2).unwrap()[0], 2);
1081     assert_eq!(c.next_back().unwrap()[1], 2);
1082
1083     let v2: &[i32] = &[0, 1, 2, 3, 4];
1084     let mut c2 = v2.windows(4);
1085     assert_eq!(c2.nth_back(1).unwrap()[1], 1);
1086     assert_eq!(c2.next_back(), None);
1087 }
1088
1089 #[test]
1090 fn test_windows_last() {
1091     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
1092     let c = v.windows(2);
1093     assert_eq!(c.last().unwrap()[1], 5);
1094
1095     let v2: &[i32] = &[0, 1, 2, 3, 4];
1096     let c2 = v2.windows(2);
1097     assert_eq!(c2.last().unwrap()[0], 3);
1098 }
1099
1100 #[test]
1101 fn test_windows_zip() {
1102     let v1: &[i32] = &[0, 1, 2, 3, 4];
1103     let v2: &[i32] = &[6, 7, 8, 9, 10];
1104
1105     let res = v1
1106         .windows(2)
1107         .zip(v2.windows(2))
1108         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
1109         .collect::<Vec<_>>();
1110
1111     assert_eq!(res, [14, 18, 22, 26]);
1112 }
1113
1114 #[test]
1115 #[allow(const_err)]
1116 fn test_iter_ref_consistency() {
1117     use std::fmt::Debug;
1118
1119     fn test<T: Copy + Debug + PartialEq>(x: T) {
1120         let v: &[T] = &[x, x, x];
1121         let v_ptrs: [*const T; 3] = match v {
1122             [ref v1, ref v2, ref v3] => [v1 as *const _, v2 as *const _, v3 as *const _],
1123             _ => unreachable!(),
1124         };
1125         let len = v.len();
1126
1127         // nth(i)
1128         for i in 0..len {
1129             assert_eq!(&v[i] as *const _, v_ptrs[i]); // check the v_ptrs array, just to be sure
1130             let nth = v.iter().nth(i).unwrap();
1131             assert_eq!(nth as *const _, v_ptrs[i]);
1132         }
1133         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
1134
1135         // stepping through with nth(0)
1136         {
1137             let mut it = v.iter();
1138             for i in 0..len {
1139                 let next = it.nth(0).unwrap();
1140                 assert_eq!(next as *const _, v_ptrs[i]);
1141             }
1142             assert_eq!(it.nth(0), None);
1143         }
1144
1145         // next()
1146         {
1147             let mut it = v.iter();
1148             for i in 0..len {
1149                 let remaining = len - i;
1150                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
1151
1152                 let next = it.next().unwrap();
1153                 assert_eq!(next as *const _, v_ptrs[i]);
1154             }
1155             assert_eq!(it.size_hint(), (0, Some(0)));
1156             assert_eq!(it.next(), None, "The final call to next() should return None");
1157         }
1158
1159         // next_back()
1160         {
1161             let mut it = v.iter();
1162             for i in 0..len {
1163                 let remaining = len - i;
1164                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
1165
1166                 let prev = it.next_back().unwrap();
1167                 assert_eq!(prev as *const _, v_ptrs[remaining - 1]);
1168             }
1169             assert_eq!(it.size_hint(), (0, Some(0)));
1170             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
1171         }
1172     }
1173
1174     fn test_mut<T: Copy + Debug + PartialEq>(x: T) {
1175         let v: &mut [T] = &mut [x, x, x];
1176         let v_ptrs: [*mut T; 3] = match v {
1177             [ref v1, ref v2, ref v3] => {
1178                 [v1 as *const _ as *mut _, v2 as *const _ as *mut _, v3 as *const _ as *mut _]
1179             }
1180             _ => unreachable!(),
1181         };
1182         let len = v.len();
1183
1184         // nth(i)
1185         for i in 0..len {
1186             assert_eq!(&mut v[i] as *mut _, v_ptrs[i]); // check the v_ptrs array, just to be sure
1187             let nth = v.iter_mut().nth(i).unwrap();
1188             assert_eq!(nth as *mut _, v_ptrs[i]);
1189         }
1190         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
1191
1192         // stepping through with nth(0)
1193         {
1194             let mut it = v.iter();
1195             for i in 0..len {
1196                 let next = it.nth(0).unwrap();
1197                 assert_eq!(next as *const _, v_ptrs[i]);
1198             }
1199             assert_eq!(it.nth(0), None);
1200         }
1201
1202         // next()
1203         {
1204             let mut it = v.iter_mut();
1205             for i in 0..len {
1206                 let remaining = len - i;
1207                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
1208
1209                 let next = it.next().unwrap();
1210                 assert_eq!(next as *mut _, v_ptrs[i]);
1211             }
1212             assert_eq!(it.size_hint(), (0, Some(0)));
1213             assert_eq!(it.next(), None, "The final call to next() should return None");
1214         }
1215
1216         // next_back()
1217         {
1218             let mut it = v.iter_mut();
1219             for i in 0..len {
1220                 let remaining = len - i;
1221                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
1222
1223                 let prev = it.next_back().unwrap();
1224                 assert_eq!(prev as *mut _, v_ptrs[remaining - 1]);
1225             }
1226             assert_eq!(it.size_hint(), (0, Some(0)));
1227             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
1228         }
1229     }
1230
1231     // Make sure iterators and slice patterns yield consistent addresses for various types,
1232     // including ZSTs.
1233     test(0u32);
1234     test(());
1235     test([0u32; 0]); // ZST with alignment > 0
1236     test_mut(0u32);
1237     test_mut(());
1238     test_mut([0u32; 0]); // ZST with alignment > 0
1239 }
1240
1241 // The current implementation of SliceIndex fails to handle methods
1242 // orthogonally from range types; therefore, it is worth testing
1243 // all of the indexing operations on each input.
1244 mod slice_index {
1245     // This checks all six indexing methods, given an input range that
1246     // should succeed. (it is NOT suitable for testing invalid inputs)
1247     macro_rules! assert_range_eq {
1248         ($arr:expr, $range:expr, $expected:expr) => {
1249             let mut arr = $arr;
1250             let mut expected = $expected;
1251             {
1252                 let s: &[_] = &arr;
1253                 let expected: &[_] = &expected;
1254
1255                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
1256                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
1257                 unsafe {
1258                     assert_eq!(
1259                         s.get_unchecked($range),
1260                         expected,
1261                         "(in assertion for: get_unchecked)",
1262                     );
1263                 }
1264             }
1265             {
1266                 let s: &mut [_] = &mut arr;
1267                 let expected: &mut [_] = &mut expected;
1268
1269                 assert_eq!(&mut s[$range], expected, "(in assertion for: index_mut)",);
1270                 assert_eq!(
1271                     s.get_mut($range),
1272                     Some(&mut expected[..]),
1273                     "(in assertion for: get_mut)",
1274                 );
1275                 unsafe {
1276                     assert_eq!(
1277                         s.get_unchecked_mut($range),
1278                         expected,
1279                         "(in assertion for: get_unchecked_mut)",
1280                     );
1281                 }
1282             }
1283         };
1284     }
1285
1286     // Make sure the macro can actually detect bugs,
1287     // because if it can't, then what are we even doing here?
1288     //
1289     // (Be aware this only demonstrates the ability to detect bugs
1290     //  in the FIRST method that panics, as the macro is not designed
1291     //  to be used in `should_panic`)
1292     #[test]
1293     #[should_panic(expected = "out of range")]
1294     fn assert_range_eq_can_fail_by_panic() {
1295         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
1296     }
1297
1298     // (Be aware this only demonstrates the ability to detect bugs
1299     //  in the FIRST method it calls, as the macro is not designed
1300     //  to be used in `should_panic`)
1301     #[test]
1302     #[should_panic(expected = "==")]
1303     fn assert_range_eq_can_fail_by_inequality() {
1304         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
1305     }
1306
1307     // Test cases for bad index operations.
1308     //
1309     // This generates `should_panic` test cases for Index/IndexMut
1310     // and `None` test cases for get/get_mut.
1311     macro_rules! panic_cases {
1312         ($(
1313             // each test case needs a unique name to namespace the tests
1314             in mod $case_name:ident {
1315                 data: $data:expr;
1316
1317                 // optional:
1318                 //
1319                 // one or more similar inputs for which data[input] succeeds,
1320                 // and the corresponding output as an array.  This helps validate
1321                 // "critical points" where an input range straddles the boundary
1322                 // between valid and invalid.
1323                 // (such as the input `len..len`, which is just barely valid)
1324                 $(
1325                     good: data[$good:expr] == $output:expr;
1326                 )*
1327
1328                 bad: data[$bad:expr];
1329                 message: $expect_msg:expr;
1330             }
1331         )*) => {$(
1332             mod $case_name {
1333                 #[allow(unused_imports)]
1334                 use core::ops::Bound;
1335
1336                 #[test]
1337                 fn pass() {
1338                     let mut v = $data;
1339
1340                     $( assert_range_eq!($data, $good, $output); )*
1341
1342                     {
1343                         let v: &[_] = &v;
1344                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
1345                     }
1346
1347                     {
1348                         let v: &mut [_] = &mut v;
1349                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
1350                     }
1351                 }
1352
1353                 #[test]
1354                 #[should_panic(expected = $expect_msg)]
1355                 fn index_fail() {
1356                     let v = $data;
1357                     let v: &[_] = &v;
1358                     let _v = &v[$bad];
1359                 }
1360
1361                 #[test]
1362                 #[should_panic(expected = $expect_msg)]
1363                 fn index_mut_fail() {
1364                     let mut v = $data;
1365                     let v: &mut [_] = &mut v;
1366                     let _v = &mut v[$bad];
1367                 }
1368             }
1369         )*};
1370     }
1371
1372     #[test]
1373     fn simple() {
1374         let v = [0, 1, 2, 3, 4, 5];
1375
1376         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
1377         assert_range_eq!(v, ..2, [0, 1]);
1378         assert_range_eq!(v, ..=1, [0, 1]);
1379         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
1380         assert_range_eq!(v, 1..4, [1, 2, 3]);
1381         assert_range_eq!(v, 1..=3, [1, 2, 3]);
1382     }
1383
1384     panic_cases! {
1385         in mod rangefrom_len {
1386             data: [0, 1, 2, 3, 4, 5];
1387
1388             good: data[6..] == [];
1389             bad: data[7..];
1390             message: "out of range";
1391         }
1392
1393         in mod rangeto_len {
1394             data: [0, 1, 2, 3, 4, 5];
1395
1396             good: data[..6] == [0, 1, 2, 3, 4, 5];
1397             bad: data[..7];
1398             message: "out of range";
1399         }
1400
1401         in mod rangetoinclusive_len {
1402             data: [0, 1, 2, 3, 4, 5];
1403
1404             good: data[..=5] == [0, 1, 2, 3, 4, 5];
1405             bad: data[..=6];
1406             message: "out of range";
1407         }
1408
1409         in mod rangeinclusive_len {
1410             data: [0, 1, 2, 3, 4, 5];
1411
1412             good: data[0..=5] == [0, 1, 2, 3, 4, 5];
1413             bad: data[0..=6];
1414             message: "out of range";
1415         }
1416
1417         in mod range_len_len {
1418             data: [0, 1, 2, 3, 4, 5];
1419
1420             good: data[6..6] == [];
1421             bad: data[7..7];
1422             message: "out of range";
1423         }
1424
1425         in mod rangeinclusive_len_len {
1426             data: [0, 1, 2, 3, 4, 5];
1427
1428             good: data[6..=5] == [];
1429             bad: data[7..=6];
1430             message: "out of range";
1431         }
1432
1433         in mod boundpair_len {
1434             data: [0, 1, 2, 3, 4, 5];
1435
1436             good: data[(Bound::Included(6), Bound::Unbounded)] == [];
1437             good: data[(Bound::Unbounded, Bound::Included(5))] == [0, 1, 2, 3, 4, 5];
1438             good: data[(Bound::Unbounded, Bound::Excluded(6))] == [0, 1, 2, 3, 4, 5];
1439             good: data[(Bound::Included(0), Bound::Included(5))] == [0, 1, 2, 3, 4, 5];
1440             good: data[(Bound::Included(0), Bound::Excluded(6))] == [0, 1, 2, 3, 4, 5];
1441             good: data[(Bound::Included(2), Bound::Excluded(4))] == [2, 3];
1442             good: data[(Bound::Excluded(1), Bound::Included(4))] == [2, 3, 4];
1443             good: data[(Bound::Excluded(5), Bound::Excluded(6))] == [];
1444             good: data[(Bound::Included(6), Bound::Excluded(6))] == [];
1445             good: data[(Bound::Excluded(5), Bound::Included(5))] == [];
1446             good: data[(Bound::Included(6), Bound::Included(5))] == [];
1447             bad: data[(Bound::Unbounded, Bound::Included(6))];
1448             message: "out of range";
1449         }
1450     }
1451
1452     panic_cases! {
1453         in mod rangeinclusive_exhausted {
1454             data: [0, 1, 2, 3, 4, 5];
1455
1456             good: data[0..=5] == [0, 1, 2, 3, 4, 5];
1457             good: data[{
1458                 let mut iter = 0..=5;
1459                 iter.by_ref().count(); // exhaust it
1460                 iter
1461             }] == [];
1462
1463             // 0..=6 is out of range before exhaustion, so it
1464             // stands to reason that it still would be after.
1465             bad: data[{
1466                 let mut iter = 0..=6;
1467                 iter.by_ref().count(); // exhaust it
1468                 iter
1469             }];
1470             message: "out of range";
1471         }
1472     }
1473
1474     panic_cases! {
1475         in mod range_neg_width {
1476             data: [0, 1, 2, 3, 4, 5];
1477
1478             good: data[4..4] == [];
1479             bad: data[4..3];
1480             message: "but ends at";
1481         }
1482
1483         in mod rangeinclusive_neg_width {
1484             data: [0, 1, 2, 3, 4, 5];
1485
1486             good: data[4..=3] == [];
1487             bad: data[4..=2];
1488             message: "but ends at";
1489         }
1490
1491         in mod boundpair_neg_width {
1492             data: [0, 1, 2, 3, 4, 5];
1493
1494             good: data[(Bound::Included(4), Bound::Excluded(4))] == [];
1495             bad: data[(Bound::Included(4), Bound::Excluded(3))];
1496             message: "but ends at";
1497         }
1498     }
1499
1500     panic_cases! {
1501         in mod rangeinclusive_overflow {
1502             data: [0, 1];
1503
1504             // note: using 0 specifically ensures that the result of overflowing is 0..0,
1505             //       so that `get` doesn't simply return None for the wrong reason.
1506             bad: data[0 ..= usize::MAX];
1507             message: "maximum usize";
1508         }
1509
1510         in mod rangetoinclusive_overflow {
1511             data: [0, 1];
1512
1513             bad: data[..= usize::MAX];
1514             message: "maximum usize";
1515         }
1516
1517         in mod boundpair_overflow_end {
1518             data: [0; 1];
1519
1520             bad: data[(Bound::Unbounded, Bound::Included(usize::MAX))];
1521             message: "maximum usize";
1522         }
1523
1524         in mod boundpair_overflow_start {
1525             data: [0; 1];
1526
1527             bad: data[(Bound::Excluded(usize::MAX), Bound::Unbounded)];
1528             message: "maximum usize";
1529         }
1530     } // panic_cases!
1531 }
1532
1533 #[test]
1534 fn test_find_rfind() {
1535     let v = [0, 1, 2, 3, 4, 5];
1536     let mut iter = v.iter();
1537     let mut i = v.len();
1538     while let Some(&elt) = iter.rfind(|_| true) {
1539         i -= 1;
1540         assert_eq!(elt, v[i]);
1541     }
1542     assert_eq!(i, 0);
1543     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
1544 }
1545
1546 #[test]
1547 fn test_iter_folds() {
1548     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
1549     assert_eq!(a.iter().fold(0, |acc, &x| 2 * acc + x), 57);
1550     assert_eq!(a.iter().rfold(0, |acc, &x| 2 * acc + x), 129);
1551     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
1552     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
1553     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
1554
1555     // short-circuiting try_fold, through other methods
1556     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
1557     let mut iter = a.iter();
1558     assert_eq!(iter.position(|&x| x == 3), Some(3));
1559     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
1560     assert_eq!(iter.len(), 2);
1561 }
1562
1563 #[test]
1564 fn test_rotate_left() {
1565     const N: usize = 600;
1566     let a: &mut [_] = &mut [0; N];
1567     for i in 0..N {
1568         a[i] = i;
1569     }
1570
1571     a.rotate_left(42);
1572     let k = N - 42;
1573
1574     for i in 0..N {
1575         assert_eq!(a[(i + k) % N], i);
1576     }
1577 }
1578
1579 #[test]
1580 fn test_rotate_right() {
1581     const N: usize = 600;
1582     let a: &mut [_] = &mut [0; N];
1583     for i in 0..N {
1584         a[i] = i;
1585     }
1586
1587     a.rotate_right(42);
1588
1589     for i in 0..N {
1590         assert_eq!(a[(i + 42) % N], i);
1591     }
1592 }
1593
1594 #[test]
1595 #[cfg_attr(miri, ignore)] // Miri is too slow
1596 fn brute_force_rotate_test_0() {
1597     // In case of edge cases involving multiple algorithms
1598     let n = 300;
1599     for len in 0..n {
1600         for s in 0..len {
1601             let mut v = Vec::with_capacity(len);
1602             for i in 0..len {
1603                 v.push(i);
1604             }
1605             v[..].rotate_right(s);
1606             for i in 0..v.len() {
1607                 assert_eq!(v[i], v.len().wrapping_add(i.wrapping_sub(s)) % v.len());
1608             }
1609         }
1610     }
1611 }
1612
1613 #[test]
1614 fn brute_force_rotate_test_1() {
1615     // `ptr_rotate` covers so many kinds of pointer usage, that this is just a good test for
1616     // pointers in general. This uses a `[usize; 4]` to hit all algorithms without overwhelming miri
1617     let n = 30;
1618     for len in 0..n {
1619         for s in 0..len {
1620             let mut v: Vec<[usize; 4]> = Vec::with_capacity(len);
1621             for i in 0..len {
1622                 v.push([i, 0, 0, 0]);
1623             }
1624             v[..].rotate_right(s);
1625             for i in 0..v.len() {
1626                 assert_eq!(v[i][0], v.len().wrapping_add(i.wrapping_sub(s)) % v.len());
1627             }
1628         }
1629     }
1630 }
1631
1632 #[test]
1633 #[cfg(not(target_arch = "wasm32"))]
1634 fn sort_unstable() {
1635     use core::cmp::Ordering::{Equal, Greater, Less};
1636     use core::slice::heapsort;
1637     use rand::{rngs::StdRng, seq::SliceRandom, Rng, SeedableRng};
1638
1639     // Miri is too slow (but still need to `chain` to make the types match)
1640     let lens = if cfg!(miri) { (2..20).chain(0..0) } else { (2..25).chain(500..510) };
1641     let rounds = if cfg!(miri) { 1 } else { 100 };
1642
1643     let mut v = [0; 600];
1644     let mut tmp = [0; 600];
1645     let mut rng = StdRng::from_entropy();
1646
1647     for len in lens {
1648         let v = &mut v[0..len];
1649         let tmp = &mut tmp[0..len];
1650
1651         for &modulus in &[5, 10, 100, 1000] {
1652             for _ in 0..rounds {
1653                 for i in 0..len {
1654                     v[i] = rng.gen::<i32>() % modulus;
1655                 }
1656
1657                 // Sort in default order.
1658                 tmp.copy_from_slice(v);
1659                 tmp.sort_unstable();
1660                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1661
1662                 // Sort in ascending order.
1663                 tmp.copy_from_slice(v);
1664                 tmp.sort_unstable_by(|a, b| a.cmp(b));
1665                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1666
1667                 // Sort in descending order.
1668                 tmp.copy_from_slice(v);
1669                 tmp.sort_unstable_by(|a, b| b.cmp(a));
1670                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1671
1672                 // Test heapsort using `<` operator.
1673                 tmp.copy_from_slice(v);
1674                 heapsort(tmp, |a, b| a < b);
1675                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1676
1677                 // Test heapsort using `>` operator.
1678                 tmp.copy_from_slice(v);
1679                 heapsort(tmp, |a, b| a > b);
1680                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1681             }
1682         }
1683     }
1684
1685     // Sort using a completely random comparison function.
1686     // This will reorder the elements *somehow*, but won't panic.
1687     for i in 0..v.len() {
1688         v[i] = i as i32;
1689     }
1690     v.sort_unstable_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1691     v.sort_unstable();
1692     for i in 0..v.len() {
1693         assert_eq!(v[i], i as i32);
1694     }
1695
1696     // Should not panic.
1697     [0i32; 0].sort_unstable();
1698     [(); 10].sort_unstable();
1699     [(); 100].sort_unstable();
1700
1701     let mut v = [0xDEADBEEFu64];
1702     v.sort_unstable();
1703     assert!(v == [0xDEADBEEF]);
1704 }
1705
1706 #[test]
1707 #[cfg(not(target_arch = "wasm32"))]
1708 #[cfg_attr(miri, ignore)] // Miri is too slow
1709 fn select_nth_unstable() {
1710     use core::cmp::Ordering::{Equal, Greater, Less};
1711     use rand::rngs::StdRng;
1712     use rand::seq::SliceRandom;
1713     use rand::{Rng, SeedableRng};
1714
1715     let mut rng = StdRng::from_entropy();
1716
1717     for len in (2..21).chain(500..501) {
1718         let mut orig = vec![0; len];
1719
1720         for &modulus in &[5, 10, 1000] {
1721             for _ in 0..10 {
1722                 for i in 0..len {
1723                     orig[i] = rng.gen::<i32>() % modulus;
1724                 }
1725
1726                 let v_sorted = {
1727                     let mut v = orig.clone();
1728                     v.sort();
1729                     v
1730                 };
1731
1732                 // Sort in default order.
1733                 for pivot in 0..len {
1734                     let mut v = orig.clone();
1735                     v.select_nth_unstable(pivot);
1736
1737                     assert_eq!(v_sorted[pivot], v[pivot]);
1738                     for i in 0..pivot {
1739                         for j in pivot..len {
1740                             assert!(v[i] <= v[j]);
1741                         }
1742                     }
1743                 }
1744
1745                 // Sort in ascending order.
1746                 for pivot in 0..len {
1747                     let mut v = orig.clone();
1748                     let (left, pivot, right) = v.select_nth_unstable_by(pivot, |a, b| a.cmp(b));
1749
1750                     assert_eq!(left.len() + right.len(), len - 1);
1751
1752                     for l in left {
1753                         assert!(l <= pivot);
1754                         for r in right.iter_mut() {
1755                             assert!(l <= r);
1756                             assert!(pivot <= r);
1757                         }
1758                     }
1759                 }
1760
1761                 // Sort in descending order.
1762                 let sort_descending_comparator = |a: &i32, b: &i32| b.cmp(a);
1763                 let v_sorted_descending = {
1764                     let mut v = orig.clone();
1765                     v.sort_by(sort_descending_comparator);
1766                     v
1767                 };
1768
1769                 for pivot in 0..len {
1770                     let mut v = orig.clone();
1771                     v.select_nth_unstable_by(pivot, sort_descending_comparator);
1772
1773                     assert_eq!(v_sorted_descending[pivot], v[pivot]);
1774                     for i in 0..pivot {
1775                         for j in pivot..len {
1776                             assert!(v[j] <= v[i]);
1777                         }
1778                     }
1779                 }
1780             }
1781         }
1782     }
1783
1784     // Sort at index using a completely random comparison function.
1785     // This will reorder the elements *somehow*, but won't panic.
1786     let mut v = [0; 500];
1787     for i in 0..v.len() {
1788         v[i] = i as i32;
1789     }
1790
1791     for pivot in 0..v.len() {
1792         v.select_nth_unstable_by(pivot, |_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1793         v.sort();
1794         for i in 0..v.len() {
1795             assert_eq!(v[i], i as i32);
1796         }
1797     }
1798
1799     // Should not panic.
1800     [(); 10].select_nth_unstable(0);
1801     [(); 10].select_nth_unstable(5);
1802     [(); 10].select_nth_unstable(9);
1803     [(); 100].select_nth_unstable(0);
1804     [(); 100].select_nth_unstable(50);
1805     [(); 100].select_nth_unstable(99);
1806
1807     let mut v = [0xDEADBEEFu64];
1808     v.select_nth_unstable(0);
1809     assert!(v == [0xDEADBEEF]);
1810 }
1811
1812 #[test]
1813 #[should_panic(expected = "index 0 greater than length of slice")]
1814 fn select_nth_unstable_zero_length() {
1815     [0i32; 0].select_nth_unstable(0);
1816 }
1817
1818 #[test]
1819 #[should_panic(expected = "index 20 greater than length of slice")]
1820 fn select_nth_unstable_past_length() {
1821     [0i32; 10].select_nth_unstable(20);
1822 }
1823
1824 pub mod memchr {
1825     use core::slice::memchr::{memchr, memrchr};
1826
1827     // test fallback implementations on all platforms
1828     #[test]
1829     fn matches_one() {
1830         assert_eq!(Some(0), memchr(b'a', b"a"));
1831     }
1832
1833     #[test]
1834     fn matches_begin() {
1835         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
1836     }
1837
1838     #[test]
1839     fn matches_end() {
1840         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
1841     }
1842
1843     #[test]
1844     fn matches_nul() {
1845         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
1846     }
1847
1848     #[test]
1849     fn matches_past_nul() {
1850         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
1851     }
1852
1853     #[test]
1854     fn no_match_empty() {
1855         assert_eq!(None, memchr(b'a', b""));
1856     }
1857
1858     #[test]
1859     fn no_match() {
1860         assert_eq!(None, memchr(b'a', b"xyz"));
1861     }
1862
1863     #[test]
1864     fn matches_one_reversed() {
1865         assert_eq!(Some(0), memrchr(b'a', b"a"));
1866     }
1867
1868     #[test]
1869     fn matches_begin_reversed() {
1870         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
1871     }
1872
1873     #[test]
1874     fn matches_end_reversed() {
1875         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
1876     }
1877
1878     #[test]
1879     fn matches_nul_reversed() {
1880         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
1881     }
1882
1883     #[test]
1884     fn matches_past_nul_reversed() {
1885         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
1886     }
1887
1888     #[test]
1889     fn no_match_empty_reversed() {
1890         assert_eq!(None, memrchr(b'a', b""));
1891     }
1892
1893     #[test]
1894     fn no_match_reversed() {
1895         assert_eq!(None, memrchr(b'a', b"xyz"));
1896     }
1897
1898     #[test]
1899     fn each_alignment_reversed() {
1900         let mut data = [1u8; 64];
1901         let needle = 2;
1902         let pos = 40;
1903         data[pos] = needle;
1904         for start in 0..16 {
1905             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
1906         }
1907     }
1908 }
1909
1910 #[test]
1911 fn test_align_to_simple() {
1912     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
1913     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
1914     assert_eq!(aligned.len(), 3);
1915     assert!(prefix == [1] || suffix == [7]);
1916     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
1917     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
1918     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
1919     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
1920     assert!(
1921         aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
1922         "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
1923         aligned,
1924         expect1,
1925         expect2,
1926         expect3,
1927         expect4
1928     );
1929 }
1930
1931 #[test]
1932 fn test_align_to_zst() {
1933     let bytes = [1, 2, 3, 4, 5, 6, 7];
1934     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
1935     assert_eq!(aligned.len(), 0);
1936     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
1937 }
1938
1939 #[test]
1940 fn test_align_to_non_trivial() {
1941     #[repr(align(8))]
1942     struct U64(u64, u64);
1943     #[repr(align(8))]
1944     struct U64U64U32(u64, u64, u32);
1945     let data = [
1946         U64(1, 2),
1947         U64(3, 4),
1948         U64(5, 6),
1949         U64(7, 8),
1950         U64(9, 10),
1951         U64(11, 12),
1952         U64(13, 14),
1953         U64(15, 16),
1954     ];
1955     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
1956     assert_eq!(aligned.len(), 4);
1957     assert_eq!(prefix.len() + suffix.len(), 2);
1958 }
1959
1960 #[test]
1961 fn test_align_to_empty_mid() {
1962     use core::mem;
1963
1964     // Make sure that we do not create empty unaligned slices for the mid part, even when the
1965     // overall slice is too short to contain an aligned address.
1966     let bytes = [1, 2, 3, 4, 5, 6, 7];
1967     type Chunk = u32;
1968     for offset in 0..4 {
1969         let (_, mid, _) = unsafe { bytes[offset..offset + 1].align_to::<Chunk>() };
1970         assert_eq!(mid.as_ptr() as usize % mem::align_of::<Chunk>(), 0);
1971     }
1972 }
1973
1974 #[test]
1975 fn test_align_to_mut_aliasing() {
1976     let mut val = [1u8, 2, 3, 4, 5];
1977     // `align_to_mut` used to create `mid` in a way that there was some intermediate
1978     // incorrect aliasing, invalidating the resulting `mid` slice.
1979     let (begin, mid, end) = unsafe { val.align_to_mut::<[u8; 2]>() };
1980     assert!(begin.len() == 0);
1981     assert!(end.len() == 1);
1982     mid[0] = mid[1];
1983     assert_eq!(val, [3, 4, 3, 4, 5])
1984 }
1985
1986 #[test]
1987 fn test_slice_partition_dedup_by() {
1988     let mut slice: [i32; 9] = [1, -1, 2, 3, 1, -5, 5, -2, 2];
1989
1990     let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.abs() == b.abs());
1991
1992     assert_eq!(dedup, [1, 2, 3, 1, -5, -2]);
1993     assert_eq!(duplicates, [5, -1, 2]);
1994 }
1995
1996 #[test]
1997 fn test_slice_partition_dedup_empty() {
1998     let mut slice: [i32; 0] = [];
1999
2000     let (dedup, duplicates) = slice.partition_dedup();
2001
2002     assert_eq!(dedup, []);
2003     assert_eq!(duplicates, []);
2004 }
2005
2006 #[test]
2007 fn test_slice_partition_dedup_one() {
2008     let mut slice = [12];
2009
2010     let (dedup, duplicates) = slice.partition_dedup();
2011
2012     assert_eq!(dedup, [12]);
2013     assert_eq!(duplicates, []);
2014 }
2015
2016 #[test]
2017 fn test_slice_partition_dedup_multiple_ident() {
2018     let mut slice = [12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
2019
2020     let (dedup, duplicates) = slice.partition_dedup();
2021
2022     assert_eq!(dedup, [12, 11]);
2023     assert_eq!(duplicates, [12, 12, 12, 12, 11, 11, 11, 11, 11]);
2024 }
2025
2026 #[test]
2027 fn test_slice_partition_dedup_partialeq() {
2028     #[derive(Debug)]
2029     struct Foo(i32, i32);
2030
2031     impl PartialEq for Foo {
2032         fn eq(&self, other: &Foo) -> bool {
2033             self.0 == other.0
2034         }
2035     }
2036
2037     let mut slice = [Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
2038
2039     let (dedup, duplicates) = slice.partition_dedup();
2040
2041     assert_eq!(dedup, [Foo(0, 1), Foo(1, 7)]);
2042     assert_eq!(duplicates, [Foo(0, 5), Foo(1, 9)]);
2043 }
2044
2045 #[test]
2046 fn test_copy_within() {
2047     // Start to end, with a RangeTo.
2048     let mut bytes = *b"Hello, World!";
2049     bytes.copy_within(..3, 10);
2050     assert_eq!(&bytes, b"Hello, WorHel");
2051
2052     // End to start, with a RangeFrom.
2053     let mut bytes = *b"Hello, World!";
2054     bytes.copy_within(10.., 0);
2055     assert_eq!(&bytes, b"ld!lo, World!");
2056
2057     // Overlapping, with a RangeInclusive.
2058     let mut bytes = *b"Hello, World!";
2059     bytes.copy_within(0..=11, 1);
2060     assert_eq!(&bytes, b"HHello, World");
2061
2062     // Whole slice, with a RangeFull.
2063     let mut bytes = *b"Hello, World!";
2064     bytes.copy_within(.., 0);
2065     assert_eq!(&bytes, b"Hello, World!");
2066
2067     // Ensure that copying at the end of slice won't cause UB.
2068     let mut bytes = *b"Hello, World!";
2069     bytes.copy_within(13..13, 5);
2070     assert_eq!(&bytes, b"Hello, World!");
2071     bytes.copy_within(5..5, 13);
2072     assert_eq!(&bytes, b"Hello, World!");
2073 }
2074
2075 #[test]
2076 #[should_panic(expected = "range end index 14 out of range for slice of length 13")]
2077 fn test_copy_within_panics_src_too_long() {
2078     let mut bytes = *b"Hello, World!";
2079     // The length is only 13, so 14 is out of bounds.
2080     bytes.copy_within(10..14, 0);
2081 }
2082
2083 #[test]
2084 #[should_panic(expected = "dest is out of bounds")]
2085 fn test_copy_within_panics_dest_too_long() {
2086     let mut bytes = *b"Hello, World!";
2087     // The length is only 13, so a slice of length 4 starting at index 10 is out of bounds.
2088     bytes.copy_within(0..4, 10);
2089 }
2090
2091 #[test]
2092 #[should_panic(expected = "slice index starts at 2 but ends at 1")]
2093 fn test_copy_within_panics_src_inverted() {
2094     let mut bytes = *b"Hello, World!";
2095     // 2 is greater than 1, so this range is invalid.
2096     bytes.copy_within(2..1, 0);
2097 }
2098 #[test]
2099 #[should_panic(expected = "attempted to index slice up to maximum usize")]
2100 fn test_copy_within_panics_src_out_of_bounds() {
2101     let mut bytes = *b"Hello, World!";
2102     // an inclusive range ending at usize::MAX would make src_end overflow
2103     bytes.copy_within(usize::MAX..=usize::MAX, 0);
2104 }
2105
2106 #[test]
2107 fn test_is_sorted() {
2108     let empty: [i32; 0] = [];
2109
2110     assert!([1, 2, 2, 9].is_sorted());
2111     assert!(![1, 3, 2].is_sorted());
2112     assert!([0].is_sorted());
2113     assert!(empty.is_sorted());
2114     assert!(![0.0, 1.0, f32::NAN].is_sorted());
2115     assert!([-2, -1, 0, 3].is_sorted());
2116     assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
2117     assert!(!["c", "bb", "aaa"].is_sorted());
2118     assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
2119 }
2120
2121 #[test]
2122 fn test_slice_run_destructors() {
2123     // Make sure that destructors get run on slice literals
2124     struct Foo<'a> {
2125         x: &'a Cell<isize>,
2126     }
2127
2128     impl<'a> Drop for Foo<'a> {
2129         fn drop(&mut self) {
2130             self.x.set(self.x.get() + 1);
2131         }
2132     }
2133
2134     fn foo(x: &Cell<isize>) -> Foo<'_> {
2135         Foo { x }
2136     }
2137
2138     let x = &Cell::new(0);
2139
2140     {
2141         let l = &[foo(x)];
2142         assert_eq!(l[0].x.get(), 0);
2143     }
2144
2145     assert_eq!(x.get(), 1);
2146 }