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