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                 #[allow(unused_imports)]
1284                 use core::ops::Bound;
1285
1286                 #[test]
1287                 fn pass() {
1288                     let mut v = $data;
1289
1290                     $( assert_range_eq!($data, $good, $output); )*
1291
1292                     {
1293                         let v: &[_] = &v;
1294                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
1295                     }
1296
1297                     {
1298                         let v: &mut [_] = &mut v;
1299                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
1300                     }
1301                 }
1302
1303                 #[test]
1304                 #[should_panic(expected = $expect_msg)]
1305                 fn index_fail() {
1306                     let v = $data;
1307                     let v: &[_] = &v;
1308                     let _v = &v[$bad];
1309                 }
1310
1311                 #[test]
1312                 #[should_panic(expected = $expect_msg)]
1313                 fn index_mut_fail() {
1314                     let mut v = $data;
1315                     let v: &mut [_] = &mut v;
1316                     let _v = &mut v[$bad];
1317                 }
1318             }
1319         )*};
1320     }
1321
1322     #[test]
1323     fn simple() {
1324         let v = [0, 1, 2, 3, 4, 5];
1325
1326         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
1327         assert_range_eq!(v, ..2, [0, 1]);
1328         assert_range_eq!(v, ..=1, [0, 1]);
1329         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
1330         assert_range_eq!(v, 1..4, [1, 2, 3]);
1331         assert_range_eq!(v, 1..=3, [1, 2, 3]);
1332     }
1333
1334     panic_cases! {
1335         in mod rangefrom_len {
1336             data: [0, 1, 2, 3, 4, 5];
1337
1338             good: data[6..] == [];
1339             bad: data[7..];
1340             message: "out of range";
1341         }
1342
1343         in mod rangeto_len {
1344             data: [0, 1, 2, 3, 4, 5];
1345
1346             good: data[..6] == [0, 1, 2, 3, 4, 5];
1347             bad: data[..7];
1348             message: "out of range";
1349         }
1350
1351         in mod rangetoinclusive_len {
1352             data: [0, 1, 2, 3, 4, 5];
1353
1354             good: data[..=5] == [0, 1, 2, 3, 4, 5];
1355             bad: data[..=6];
1356             message: "out of range";
1357         }
1358
1359         in mod rangeinclusive_len {
1360             data: [0, 1, 2, 3, 4, 5];
1361
1362             good: data[0..=5] == [0, 1, 2, 3, 4, 5];
1363             bad: data[0..=6];
1364             message: "out of range";
1365         }
1366
1367         in mod range_len_len {
1368             data: [0, 1, 2, 3, 4, 5];
1369
1370             good: data[6..6] == [];
1371             bad: data[7..7];
1372             message: "out of range";
1373         }
1374
1375         in mod rangeinclusive_len_len {
1376             data: [0, 1, 2, 3, 4, 5];
1377
1378             good: data[6..=5] == [];
1379             bad: data[7..=6];
1380             message: "out of range";
1381         }
1382
1383         in mod boundpair_len {
1384             data: [0, 1, 2, 3, 4, 5];
1385
1386             good: data[(Bound::Included(6), Bound::Unbounded)] == [];
1387             good: data[(Bound::Unbounded, Bound::Included(5))] == [0, 1, 2, 3, 4, 5];
1388             good: data[(Bound::Unbounded, Bound::Excluded(6))] == [0, 1, 2, 3, 4, 5];
1389             good: data[(Bound::Included(0), Bound::Included(5))] == [0, 1, 2, 3, 4, 5];
1390             good: data[(Bound::Included(0), Bound::Excluded(6))] == [0, 1, 2, 3, 4, 5];
1391             good: data[(Bound::Included(2), Bound::Excluded(4))] == [2, 3];
1392             good: data[(Bound::Excluded(1), Bound::Included(4))] == [2, 3, 4];
1393             good: data[(Bound::Excluded(5), Bound::Excluded(6))] == [];
1394             good: data[(Bound::Included(6), Bound::Excluded(6))] == [];
1395             good: data[(Bound::Excluded(5), Bound::Included(5))] == [];
1396             good: data[(Bound::Included(6), Bound::Included(5))] == [];
1397             bad: data[(Bound::Unbounded, Bound::Included(6))];
1398             message: "out of range";
1399         }
1400     }
1401
1402     panic_cases! {
1403         in mod rangeinclusive_exhausted {
1404             data: [0, 1, 2, 3, 4, 5];
1405
1406             good: data[0..=5] == [0, 1, 2, 3, 4, 5];
1407             good: data[{
1408                 let mut iter = 0..=5;
1409                 iter.by_ref().count(); // exhaust it
1410                 iter
1411             }] == [];
1412
1413             // 0..=6 is out of range before exhaustion, so it
1414             // stands to reason that it still would be after.
1415             bad: data[{
1416                 let mut iter = 0..=6;
1417                 iter.by_ref().count(); // exhaust it
1418                 iter
1419             }];
1420             message: "out of range";
1421         }
1422     }
1423
1424     panic_cases! {
1425         in mod range_neg_width {
1426             data: [0, 1, 2, 3, 4, 5];
1427
1428             good: data[4..4] == [];
1429             bad: data[4..3];
1430             message: "but ends at";
1431         }
1432
1433         in mod rangeinclusive_neg_width {
1434             data: [0, 1, 2, 3, 4, 5];
1435
1436             good: data[4..=3] == [];
1437             bad: data[4..=2];
1438             message: "but ends at";
1439         }
1440
1441         in mod boundpair_neg_width {
1442             data: [0, 1, 2, 3, 4, 5];
1443
1444             good: data[(Bound::Included(4), Bound::Excluded(4))] == [];
1445             bad: data[(Bound::Included(4), Bound::Excluded(3))];
1446             message: "but ends at";
1447         }
1448     }
1449
1450     panic_cases! {
1451         in mod rangeinclusive_overflow {
1452             data: [0, 1];
1453
1454             // note: using 0 specifically ensures that the result of overflowing is 0..0,
1455             //       so that `get` doesn't simply return None for the wrong reason.
1456             bad: data[0 ..= usize::MAX];
1457             message: "maximum usize";
1458         }
1459
1460         in mod rangetoinclusive_overflow {
1461             data: [0, 1];
1462
1463             bad: data[..= usize::MAX];
1464             message: "maximum usize";
1465         }
1466
1467         in mod boundpair_overflow_end {
1468             data: [0; 1];
1469
1470             bad: data[(Bound::Unbounded, Bound::Included(usize::MAX))];
1471             message: "maximum usize";
1472         }
1473
1474         in mod boundpair_overflow_start {
1475             data: [0; 1];
1476
1477             bad: data[(Bound::Excluded(usize::MAX), Bound::Unbounded)];
1478             message: "maximum usize";
1479         }
1480     } // panic_cases!
1481 }
1482
1483 #[test]
1484 fn test_find_rfind() {
1485     let v = [0, 1, 2, 3, 4, 5];
1486     let mut iter = v.iter();
1487     let mut i = v.len();
1488     while let Some(&elt) = iter.rfind(|_| true) {
1489         i -= 1;
1490         assert_eq!(elt, v[i]);
1491     }
1492     assert_eq!(i, 0);
1493     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
1494 }
1495
1496 #[test]
1497 fn test_iter_folds() {
1498     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
1499     assert_eq!(a.iter().fold(0, |acc, &x| 2 * acc + x), 57);
1500     assert_eq!(a.iter().rfold(0, |acc, &x| 2 * acc + x), 129);
1501     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
1502     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
1503     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
1504
1505     // short-circuiting try_fold, through other methods
1506     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
1507     let mut iter = a.iter();
1508     assert_eq!(iter.position(|&x| x == 3), Some(3));
1509     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
1510     assert_eq!(iter.len(), 2);
1511 }
1512
1513 #[test]
1514 fn test_rotate_left() {
1515     const N: usize = 600;
1516     let a: &mut [_] = &mut [0; N];
1517     for i in 0..N {
1518         a[i] = i;
1519     }
1520
1521     a.rotate_left(42);
1522     let k = N - 42;
1523
1524     for i in 0..N {
1525         assert_eq!(a[(i + k) % N], i);
1526     }
1527 }
1528
1529 #[test]
1530 fn test_rotate_right() {
1531     const N: usize = 600;
1532     let a: &mut [_] = &mut [0; N];
1533     for i in 0..N {
1534         a[i] = i;
1535     }
1536
1537     a.rotate_right(42);
1538
1539     for i in 0..N {
1540         assert_eq!(a[(i + 42) % N], i);
1541     }
1542 }
1543
1544 #[test]
1545 #[cfg_attr(miri, ignore)] // Miri is too slow
1546 fn brute_force_rotate_test_0() {
1547     // In case of edge cases involving multiple algorithms
1548     let n = 300;
1549     for len in 0..n {
1550         for s in 0..len {
1551             let mut v = Vec::with_capacity(len);
1552             for i in 0..len {
1553                 v.push(i);
1554             }
1555             v[..].rotate_right(s);
1556             for i in 0..v.len() {
1557                 assert_eq!(v[i], v.len().wrapping_add(i.wrapping_sub(s)) % v.len());
1558             }
1559         }
1560     }
1561 }
1562
1563 #[test]
1564 fn brute_force_rotate_test_1() {
1565     // `ptr_rotate` covers so many kinds of pointer usage, that this is just a good test for
1566     // pointers in general. This uses a `[usize; 4]` to hit all algorithms without overwhelming miri
1567     let n = 30;
1568     for len in 0..n {
1569         for s in 0..len {
1570             let mut v: Vec<[usize; 4]> = Vec::with_capacity(len);
1571             for i in 0..len {
1572                 v.push([i, 0, 0, 0]);
1573             }
1574             v[..].rotate_right(s);
1575             for i in 0..v.len() {
1576                 assert_eq!(v[i][0], v.len().wrapping_add(i.wrapping_sub(s)) % v.len());
1577             }
1578         }
1579     }
1580 }
1581
1582 #[test]
1583 #[cfg(not(target_arch = "wasm32"))]
1584 fn sort_unstable() {
1585     use core::cmp::Ordering::{Equal, Greater, Less};
1586     use core::slice::heapsort;
1587     use rand::{rngs::StdRng, seq::SliceRandom, Rng, SeedableRng};
1588
1589     // Miri is too slow (but still need to `chain` to make the types match)
1590     let lens = if cfg!(miri) { (2..20).chain(0..0) } else { (2..25).chain(500..510) };
1591     let rounds = if cfg!(miri) { 1 } else { 100 };
1592
1593     let mut v = [0; 600];
1594     let mut tmp = [0; 600];
1595     let mut rng = StdRng::from_entropy();
1596
1597     for len in lens {
1598         let v = &mut v[0..len];
1599         let tmp = &mut tmp[0..len];
1600
1601         for &modulus in &[5, 10, 100, 1000] {
1602             for _ in 0..rounds {
1603                 for i in 0..len {
1604                     v[i] = rng.gen::<i32>() % modulus;
1605                 }
1606
1607                 // Sort in default order.
1608                 tmp.copy_from_slice(v);
1609                 tmp.sort_unstable();
1610                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1611
1612                 // Sort in ascending order.
1613                 tmp.copy_from_slice(v);
1614                 tmp.sort_unstable_by(|a, b| a.cmp(b));
1615                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1616
1617                 // Sort in descending order.
1618                 tmp.copy_from_slice(v);
1619                 tmp.sort_unstable_by(|a, b| b.cmp(a));
1620                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1621
1622                 // Test heapsort using `<` operator.
1623                 tmp.copy_from_slice(v);
1624                 heapsort(tmp, |a, b| a < b);
1625                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1626
1627                 // Test heapsort using `>` operator.
1628                 tmp.copy_from_slice(v);
1629                 heapsort(tmp, |a, b| a > b);
1630                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1631             }
1632         }
1633     }
1634
1635     // Sort using a completely random comparison function.
1636     // This will reorder the elements *somehow*, but won't panic.
1637     for i in 0..v.len() {
1638         v[i] = i as i32;
1639     }
1640     v.sort_unstable_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1641     v.sort_unstable();
1642     for i in 0..v.len() {
1643         assert_eq!(v[i], i as i32);
1644     }
1645
1646     // Should not panic.
1647     [0i32; 0].sort_unstable();
1648     [(); 10].sort_unstable();
1649     [(); 100].sort_unstable();
1650
1651     let mut v = [0xDEADBEEFu64];
1652     v.sort_unstable();
1653     assert!(v == [0xDEADBEEF]);
1654 }
1655
1656 #[test]
1657 #[cfg(not(target_arch = "wasm32"))]
1658 #[cfg_attr(miri, ignore)] // Miri is too slow
1659 fn select_nth_unstable() {
1660     use core::cmp::Ordering::{Equal, Greater, Less};
1661     use rand::rngs::StdRng;
1662     use rand::seq::SliceRandom;
1663     use rand::{Rng, SeedableRng};
1664
1665     let mut rng = StdRng::from_entropy();
1666
1667     for len in (2..21).chain(500..501) {
1668         let mut orig = vec![0; len];
1669
1670         for &modulus in &[5, 10, 1000] {
1671             for _ in 0..10 {
1672                 for i in 0..len {
1673                     orig[i] = rng.gen::<i32>() % modulus;
1674                 }
1675
1676                 let v_sorted = {
1677                     let mut v = orig.clone();
1678                     v.sort();
1679                     v
1680                 };
1681
1682                 // Sort in default order.
1683                 for pivot in 0..len {
1684                     let mut v = orig.clone();
1685                     v.select_nth_unstable(pivot);
1686
1687                     assert_eq!(v_sorted[pivot], v[pivot]);
1688                     for i in 0..pivot {
1689                         for j in pivot..len {
1690                             assert!(v[i] <= v[j]);
1691                         }
1692                     }
1693                 }
1694
1695                 // Sort in ascending order.
1696                 for pivot in 0..len {
1697                     let mut v = orig.clone();
1698                     let (left, pivot, right) = v.select_nth_unstable_by(pivot, |a, b| a.cmp(b));
1699
1700                     assert_eq!(left.len() + right.len(), len - 1);
1701
1702                     for l in left {
1703                         assert!(l <= pivot);
1704                         for r in right.iter_mut() {
1705                             assert!(l <= r);
1706                             assert!(pivot <= r);
1707                         }
1708                     }
1709                 }
1710
1711                 // Sort in descending order.
1712                 let sort_descending_comparator = |a: &i32, b: &i32| b.cmp(a);
1713                 let v_sorted_descending = {
1714                     let mut v = orig.clone();
1715                     v.sort_by(sort_descending_comparator);
1716                     v
1717                 };
1718
1719                 for pivot in 0..len {
1720                     let mut v = orig.clone();
1721                     v.select_nth_unstable_by(pivot, sort_descending_comparator);
1722
1723                     assert_eq!(v_sorted_descending[pivot], v[pivot]);
1724                     for i in 0..pivot {
1725                         for j in pivot..len {
1726                             assert!(v[j] <= v[i]);
1727                         }
1728                     }
1729                 }
1730             }
1731         }
1732     }
1733
1734     // Sort at index using a completely random comparison function.
1735     // This will reorder the elements *somehow*, but won't panic.
1736     let mut v = [0; 500];
1737     for i in 0..v.len() {
1738         v[i] = i as i32;
1739     }
1740
1741     for pivot in 0..v.len() {
1742         v.select_nth_unstable_by(pivot, |_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1743         v.sort();
1744         for i in 0..v.len() {
1745             assert_eq!(v[i], i as i32);
1746         }
1747     }
1748
1749     // Should not panic.
1750     [(); 10].select_nth_unstable(0);
1751     [(); 10].select_nth_unstable(5);
1752     [(); 10].select_nth_unstable(9);
1753     [(); 100].select_nth_unstable(0);
1754     [(); 100].select_nth_unstable(50);
1755     [(); 100].select_nth_unstable(99);
1756
1757     let mut v = [0xDEADBEEFu64];
1758     v.select_nth_unstable(0);
1759     assert!(v == [0xDEADBEEF]);
1760 }
1761
1762 #[test]
1763 #[should_panic(expected = "index 0 greater than length of slice")]
1764 fn select_nth_unstable_zero_length() {
1765     [0i32; 0].select_nth_unstable(0);
1766 }
1767
1768 #[test]
1769 #[should_panic(expected = "index 20 greater than length of slice")]
1770 fn select_nth_unstable_past_length() {
1771     [0i32; 10].select_nth_unstable(20);
1772 }
1773
1774 pub mod memchr {
1775     use core::slice::memchr::{memchr, memrchr};
1776
1777     // test fallback implementations on all platforms
1778     #[test]
1779     fn matches_one() {
1780         assert_eq!(Some(0), memchr(b'a', b"a"));
1781     }
1782
1783     #[test]
1784     fn matches_begin() {
1785         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
1786     }
1787
1788     #[test]
1789     fn matches_end() {
1790         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
1791     }
1792
1793     #[test]
1794     fn matches_nul() {
1795         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
1796     }
1797
1798     #[test]
1799     fn matches_past_nul() {
1800         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
1801     }
1802
1803     #[test]
1804     fn no_match_empty() {
1805         assert_eq!(None, memchr(b'a', b""));
1806     }
1807
1808     #[test]
1809     fn no_match() {
1810         assert_eq!(None, memchr(b'a', b"xyz"));
1811     }
1812
1813     #[test]
1814     fn matches_one_reversed() {
1815         assert_eq!(Some(0), memrchr(b'a', b"a"));
1816     }
1817
1818     #[test]
1819     fn matches_begin_reversed() {
1820         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
1821     }
1822
1823     #[test]
1824     fn matches_end_reversed() {
1825         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
1826     }
1827
1828     #[test]
1829     fn matches_nul_reversed() {
1830         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
1831     }
1832
1833     #[test]
1834     fn matches_past_nul_reversed() {
1835         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
1836     }
1837
1838     #[test]
1839     fn no_match_empty_reversed() {
1840         assert_eq!(None, memrchr(b'a', b""));
1841     }
1842
1843     #[test]
1844     fn no_match_reversed() {
1845         assert_eq!(None, memrchr(b'a', b"xyz"));
1846     }
1847
1848     #[test]
1849     fn each_alignment_reversed() {
1850         let mut data = [1u8; 64];
1851         let needle = 2;
1852         let pos = 40;
1853         data[pos] = needle;
1854         for start in 0..16 {
1855             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
1856         }
1857     }
1858 }
1859
1860 #[test]
1861 fn test_align_to_simple() {
1862     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
1863     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
1864     assert_eq!(aligned.len(), 3);
1865     assert!(prefix == [1] || suffix == [7]);
1866     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
1867     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
1868     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
1869     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
1870     assert!(
1871         aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
1872         "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
1873         aligned,
1874         expect1,
1875         expect2,
1876         expect3,
1877         expect4
1878     );
1879 }
1880
1881 #[test]
1882 fn test_align_to_zst() {
1883     let bytes = [1, 2, 3, 4, 5, 6, 7];
1884     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
1885     assert_eq!(aligned.len(), 0);
1886     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
1887 }
1888
1889 #[test]
1890 fn test_align_to_non_trivial() {
1891     #[repr(align(8))]
1892     struct U64(u64, u64);
1893     #[repr(align(8))]
1894     struct U64U64U32(u64, u64, u32);
1895     let data = [
1896         U64(1, 2),
1897         U64(3, 4),
1898         U64(5, 6),
1899         U64(7, 8),
1900         U64(9, 10),
1901         U64(11, 12),
1902         U64(13, 14),
1903         U64(15, 16),
1904     ];
1905     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
1906     assert_eq!(aligned.len(), 4);
1907     assert_eq!(prefix.len() + suffix.len(), 2);
1908 }
1909
1910 #[test]
1911 fn test_align_to_empty_mid() {
1912     use core::mem;
1913
1914     // Make sure that we do not create empty unaligned slices for the mid part, even when the
1915     // overall slice is too short to contain an aligned address.
1916     let bytes = [1, 2, 3, 4, 5, 6, 7];
1917     type Chunk = u32;
1918     for offset in 0..4 {
1919         let (_, mid, _) = unsafe { bytes[offset..offset + 1].align_to::<Chunk>() };
1920         assert_eq!(mid.as_ptr() as usize % mem::align_of::<Chunk>(), 0);
1921     }
1922 }
1923
1924 #[test]
1925 fn test_align_to_mut_aliasing() {
1926     let mut val = [1u8, 2, 3, 4, 5];
1927     // `align_to_mut` used to create `mid` in a way that there was some intermediate
1928     // incorrect aliasing, invalidating the resulting `mid` slice.
1929     let (begin, mid, end) = unsafe { val.align_to_mut::<[u8; 2]>() };
1930     assert!(begin.len() == 0);
1931     assert!(end.len() == 1);
1932     mid[0] = mid[1];
1933     assert_eq!(val, [3, 4, 3, 4, 5])
1934 }
1935
1936 #[test]
1937 fn test_slice_partition_dedup_by() {
1938     let mut slice: [i32; 9] = [1, -1, 2, 3, 1, -5, 5, -2, 2];
1939
1940     let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.abs() == b.abs());
1941
1942     assert_eq!(dedup, [1, 2, 3, 1, -5, -2]);
1943     assert_eq!(duplicates, [5, -1, 2]);
1944 }
1945
1946 #[test]
1947 fn test_slice_partition_dedup_empty() {
1948     let mut slice: [i32; 0] = [];
1949
1950     let (dedup, duplicates) = slice.partition_dedup();
1951
1952     assert_eq!(dedup, []);
1953     assert_eq!(duplicates, []);
1954 }
1955
1956 #[test]
1957 fn test_slice_partition_dedup_one() {
1958     let mut slice = [12];
1959
1960     let (dedup, duplicates) = slice.partition_dedup();
1961
1962     assert_eq!(dedup, [12]);
1963     assert_eq!(duplicates, []);
1964 }
1965
1966 #[test]
1967 fn test_slice_partition_dedup_multiple_ident() {
1968     let mut slice = [12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
1969
1970     let (dedup, duplicates) = slice.partition_dedup();
1971
1972     assert_eq!(dedup, [12, 11]);
1973     assert_eq!(duplicates, [12, 12, 12, 12, 11, 11, 11, 11, 11]);
1974 }
1975
1976 #[test]
1977 fn test_slice_partition_dedup_partialeq() {
1978     #[derive(Debug)]
1979     struct Foo(i32, i32);
1980
1981     impl PartialEq for Foo {
1982         fn eq(&self, other: &Foo) -> bool {
1983             self.0 == other.0
1984         }
1985     }
1986
1987     let mut slice = [Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
1988
1989     let (dedup, duplicates) = slice.partition_dedup();
1990
1991     assert_eq!(dedup, [Foo(0, 1), Foo(1, 7)]);
1992     assert_eq!(duplicates, [Foo(0, 5), Foo(1, 9)]);
1993 }
1994
1995 #[test]
1996 fn test_copy_within() {
1997     // Start to end, with a RangeTo.
1998     let mut bytes = *b"Hello, World!";
1999     bytes.copy_within(..3, 10);
2000     assert_eq!(&bytes, b"Hello, WorHel");
2001
2002     // End to start, with a RangeFrom.
2003     let mut bytes = *b"Hello, World!";
2004     bytes.copy_within(10.., 0);
2005     assert_eq!(&bytes, b"ld!lo, World!");
2006
2007     // Overlapping, with a RangeInclusive.
2008     let mut bytes = *b"Hello, World!";
2009     bytes.copy_within(0..=11, 1);
2010     assert_eq!(&bytes, b"HHello, World");
2011
2012     // Whole slice, with a RangeFull.
2013     let mut bytes = *b"Hello, World!";
2014     bytes.copy_within(.., 0);
2015     assert_eq!(&bytes, b"Hello, World!");
2016
2017     // Ensure that copying at the end of slice won't cause UB.
2018     let mut bytes = *b"Hello, World!";
2019     bytes.copy_within(13..13, 5);
2020     assert_eq!(&bytes, b"Hello, World!");
2021     bytes.copy_within(5..5, 13);
2022     assert_eq!(&bytes, b"Hello, World!");
2023 }
2024
2025 #[test]
2026 #[should_panic(expected = "range end index 14 out of range for slice of length 13")]
2027 fn test_copy_within_panics_src_too_long() {
2028     let mut bytes = *b"Hello, World!";
2029     // The length is only 13, so 14 is out of bounds.
2030     bytes.copy_within(10..14, 0);
2031 }
2032
2033 #[test]
2034 #[should_panic(expected = "dest is out of bounds")]
2035 fn test_copy_within_panics_dest_too_long() {
2036     let mut bytes = *b"Hello, World!";
2037     // The length is only 13, so a slice of length 4 starting at index 10 is out of bounds.
2038     bytes.copy_within(0..4, 10);
2039 }
2040
2041 #[test]
2042 #[should_panic(expected = "slice index starts at 2 but ends at 1")]
2043 fn test_copy_within_panics_src_inverted() {
2044     let mut bytes = *b"Hello, World!";
2045     // 2 is greater than 1, so this range is invalid.
2046     bytes.copy_within(2..1, 0);
2047 }
2048 #[test]
2049 #[should_panic(expected = "attempted to index slice up to maximum usize")]
2050 fn test_copy_within_panics_src_out_of_bounds() {
2051     let mut bytes = *b"Hello, World!";
2052     // an inclusive range ending at usize::MAX would make src_end overflow
2053     bytes.copy_within(usize::MAX..=usize::MAX, 0);
2054 }
2055
2056 #[test]
2057 fn test_is_sorted() {
2058     let empty: [i32; 0] = [];
2059
2060     assert!([1, 2, 2, 9].is_sorted());
2061     assert!(![1, 3, 2].is_sorted());
2062     assert!([0].is_sorted());
2063     assert!(empty.is_sorted());
2064     assert!(![0.0, 1.0, f32::NAN].is_sorted());
2065     assert!([-2, -1, 0, 3].is_sorted());
2066     assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
2067     assert!(!["c", "bb", "aaa"].is_sorted());
2068     assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
2069 }
2070
2071 #[test]
2072 fn test_slice_run_destructors() {
2073     // Make sure that destructors get run on slice literals
2074     struct Foo<'a> {
2075         x: &'a Cell<isize>,
2076     }
2077
2078     impl<'a> Drop for Foo<'a> {
2079         fn drop(&mut self) {
2080             self.x.set(self.x.get() + 1);
2081         }
2082     }
2083
2084     fn foo(x: &Cell<isize>) -> Foo<'_> {
2085         Foo { x }
2086     }
2087
2088     let x = &Cell::new(0);
2089
2090     {
2091         let l = &[foo(x)];
2092         assert_eq!(l[0].x.get(), 0);
2093     }
2094
2095     assert_eq!(x.get(), 1);
2096 }