src/libcore/tests/slice.rs

   1 use core::result::Result::{Ok, Err};
   2
   3 #[test]
   4 fn test_position() {
   5     let b = [1, 2, 3, 5, 5];
   6     assert!(b.iter().position(|&v| v == 9) == None);
   7     assert!(b.iter().position(|&v| v == 5) == Some(3));
   8     assert!(b.iter().position(|&v| v == 3) == Some(2));
   9     assert!(b.iter().position(|&v| v == 0) == None);
  10 }
  11
  12 #[test]
  13 fn test_rposition() {
  14     let b = [1, 2, 3, 5, 5];
  15     assert!(b.iter().rposition(|&v| v == 9) == None);
  16     assert!(b.iter().rposition(|&v| v == 5) == Some(4));
  17     assert!(b.iter().rposition(|&v| v == 3) == Some(2));
  18     assert!(b.iter().rposition(|&v| v == 0) == None);
  19 }
  20
  21 #[test]
  22 fn test_binary_search() {
  23     let b: [i32; 0] = [];
  24     assert_eq!(b.binary_search(&5), Err(0));
  25
  26     let b = [4];
  27     assert_eq!(b.binary_search(&3), Err(0));
  28     assert_eq!(b.binary_search(&4), Ok(0));
  29     assert_eq!(b.binary_search(&5), Err(1));
  30
  31     let b = [1, 2, 4, 6, 8, 9];
  32     assert_eq!(b.binary_search(&5), Err(3));
  33     assert_eq!(b.binary_search(&6), Ok(3));
  34     assert_eq!(b.binary_search(&7), Err(4));
  35     assert_eq!(b.binary_search(&8), Ok(4));
  36
  37     let b = [1, 2, 4, 5, 6, 8];
  38     assert_eq!(b.binary_search(&9), Err(6));
  39
  40     let b = [1, 2, 4, 6, 7, 8, 9];
  41     assert_eq!(b.binary_search(&6), Ok(3));
  42     assert_eq!(b.binary_search(&5), Err(3));
  43     assert_eq!(b.binary_search(&8), Ok(5));
  44
  45     let b = [1, 2, 4, 5, 6, 8, 9];
  46     assert_eq!(b.binary_search(&7), Err(5));
  47     assert_eq!(b.binary_search(&0), Err(0));
  48
  49     let b = [1, 3, 3, 3, 7];
  50     assert_eq!(b.binary_search(&0), Err(0));
  51     assert_eq!(b.binary_search(&1), Ok(0));
  52     assert_eq!(b.binary_search(&2), Err(1));
  53     assert!(match b.binary_search(&3) { Ok(1..=3) => true, _ => false });
  54     assert!(match b.binary_search(&3) { Ok(1..=3) => true, _ => false });
  55     assert_eq!(b.binary_search(&4), Err(4));
  56     assert_eq!(b.binary_search(&5), Err(4));
  57     assert_eq!(b.binary_search(&6), Err(4));
  58     assert_eq!(b.binary_search(&7), Ok(4));
  59     assert_eq!(b.binary_search(&8), Err(5));
  60 }
  61
  62 #[test]
  63 // Test implementation specific behavior when finding equivalent elements.
  64 // It is ok to break this test but when you do a crater run is highly advisable.
  65 fn test_binary_search_implementation_details() {
  66     let b = [1, 1, 2, 2, 3, 3, 3];
  67     assert_eq!(b.binary_search(&1), Ok(1));
  68     assert_eq!(b.binary_search(&2), Ok(3));
  69     assert_eq!(b.binary_search(&3), Ok(6));
  70     let b = [1, 1, 1, 1, 1, 3, 3, 3, 3];
  71     assert_eq!(b.binary_search(&1), Ok(4));
  72     assert_eq!(b.binary_search(&3), Ok(8));
  73     let b = [1, 1, 1, 1, 3, 3, 3, 3, 3];
  74     assert_eq!(b.binary_search(&1), Ok(3));
  75     assert_eq!(b.binary_search(&3), Ok(8));
  76 }
  77
  78 #[test]
  79 fn test_iterator_nth() {
  80     let v: &[_] = &[0, 1, 2, 3, 4];
  81     for i in 0..v.len() {
  82         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
  83     }
  84     assert_eq!(v.iter().nth(v.len()), None);
  85
  86     let mut iter = v.iter();
  87     assert_eq!(iter.nth(2).unwrap(), &v[2]);
  88     assert_eq!(iter.nth(1).unwrap(), &v[4]);
  89 }
  90
  91 #[test]
  92 fn test_iterator_nth_back() {
  93     let v: &[_] = &[0, 1, 2, 3, 4];
  94     for i in 0..v.len() {
  95         assert_eq!(v.iter().nth_back(i).unwrap(), &v[v.len() - i - 1]);
  96     }
  97     assert_eq!(v.iter().nth_back(v.len()), None);
  98
  99     let mut iter = v.iter();
 100     assert_eq!(iter.nth_back(2).unwrap(), &v[2]);
 101     assert_eq!(iter.nth_back(1).unwrap(), &v[0]);
 102 }
 103
 104 #[test]
 105 fn test_iterator_last() {
 106     let v: &[_] = &[0, 1, 2, 3, 4];
 107     assert_eq!(v.iter().last().unwrap(), &4);
 108     assert_eq!(v[..1].iter().last().unwrap(), &0);
 109 }
 110
 111 #[test]
 112 fn test_iterator_count() {
 113     let v: &[_] = &[0, 1, 2, 3, 4];
 114     assert_eq!(v.iter().count(), 5);
 115
 116     let mut iter2 = v.iter();
 117     iter2.next();
 118     iter2.next();
 119     assert_eq!(iter2.count(), 3);
 120 }
 121
 122 #[test]
 123 fn test_chunks_count() {
 124     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 125     let c = v.chunks(3);
 126     assert_eq!(c.count(), 2);
 127
 128     let v2: &[i32] = &[0, 1, 2, 3, 4];
 129     let c2 = v2.chunks(2);
 130     assert_eq!(c2.count(), 3);
 131
 132     let v3: &[i32] = &[];
 133     let c3 = v3.chunks(2);
 134     assert_eq!(c3.count(), 0);
 135 }
 136
 137 #[test]
 138 fn test_chunks_nth() {
 139     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 140     let mut c = v.chunks(2);
 141     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 142     assert_eq!(c.next().unwrap(), &[4, 5]);
 143
 144     let v2: &[i32] = &[0, 1, 2, 3, 4];
 145     let mut c2 = v2.chunks(3);
 146     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 147     assert_eq!(c2.next(), None);
 148 }
 149
 150 #[test]
 151 fn test_chunks_nth_back() {
 152     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 153     let mut c = v.chunks(2);
 154     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 155     assert_eq!(c.next().unwrap(), &[0, 1]);
 156     assert_eq!(c.next(), None);
 157
 158     let v2: &[i32] = &[0, 1, 2, 3, 4];
 159     let mut c2 = v2.chunks(3);
 160     assert_eq!(c2.nth_back(1).unwrap(), &[0, 1, 2]);
 161     assert_eq!(c2.next(), None);
 162     assert_eq!(c2.next_back(), None);
 163
 164     let v3: &[i32] = &[0, 1, 2, 3, 4];
 165     let mut c3 = v3.chunks(10);
 166     assert_eq!(c3.nth_back(0).unwrap(), &[0, 1, 2, 3, 4]);
 167     assert_eq!(c3.next(), None);
 168
 169     let v4: &[i32] = &[0, 1, 2];
 170     let mut c4 = v4.chunks(10);
 171     assert_eq!(c4.nth_back(1_000_000_000usize), None);
 172 }
 173
 174 #[test]
 175 fn test_chunks_last() {
 176     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 177     let c = v.chunks(2);
 178     assert_eq!(c.last().unwrap()[1], 5);
 179
 180     let v2: &[i32] = &[0, 1, 2, 3, 4];
 181     let c2 = v2.chunks(2);
 182     assert_eq!(c2.last().unwrap()[0], 4);
 183 }
 184
 185 #[test]
 186 fn test_chunks_zip() {
 187     let v1: &[i32] = &[0, 1, 2, 3, 4];
 188     let v2: &[i32] = &[6, 7, 8, 9, 10];
 189
 190     let res = v1.chunks(2)
 191         .zip(v2.chunks(2))
 192         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 193         .collect::<Vec<_>>();
 194     assert_eq!(res, vec![14, 22, 14]);
 195 }
 196
 197 #[test]
 198 fn test_chunks_mut_count() {
 199     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 200     let c = v.chunks_mut(3);
 201     assert_eq!(c.count(), 2);
 202
 203     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 204     let c2 = v2.chunks_mut(2);
 205     assert_eq!(c2.count(), 3);
 206
 207     let v3: &mut [i32] = &mut [];
 208     let c3 = v3.chunks_mut(2);
 209     assert_eq!(c3.count(), 0);
 210 }
 211
 212 #[test]
 213 fn test_chunks_mut_nth() {
 214     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 215     let mut c = v.chunks_mut(2);
 216     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 217     assert_eq!(c.next().unwrap(), &[4, 5]);
 218
 219     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 220     let mut c2 = v2.chunks_mut(3);
 221     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 222     assert_eq!(c2.next(), None);
 223 }
 224
 225 #[test]
 226 fn test_chunks_mut_nth_back() {
 227     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 228     let mut c = v.chunks_mut(2);
 229     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 230     assert_eq!(c.next().unwrap(), &[0, 1]);
 231
 232     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 233     let mut c1 = v1.chunks_mut(3);
 234     assert_eq!(c1.nth_back(1).unwrap(), &[0, 1, 2]);
 235     assert_eq!(c1.next(), None);
 236
 237     let v3: &mut [i32] = &mut [0, 1, 2, 3, 4];
 238     let mut c3 = v3.chunks_mut(10);
 239     assert_eq!(c3.nth_back(0).unwrap(), &[0, 1, 2, 3, 4]);
 240     assert_eq!(c3.next(), None);
 241
 242     let v4: &mut [i32] = &mut [0, 1, 2];
 243     let mut c4 = v4.chunks_mut(10);
 244     assert_eq!(c4.nth_back(1_000_000_000usize), None);
 245 }
 246
 247 #[test]
 248 fn test_chunks_mut_last() {
 249     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 250     let c = v.chunks_mut(2);
 251     assert_eq!(c.last().unwrap(), &[4, 5]);
 252
 253     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 254     let c2 = v2.chunks_mut(2);
 255     assert_eq!(c2.last().unwrap(), &[4]);
 256 }
 257
 258 #[test]
 259 fn test_chunks_mut_zip() {
 260     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 261     let v2: &[i32] = &[6, 7, 8, 9, 10];
 262
 263     for (a, b) in v1.chunks_mut(2).zip(v2.chunks(2)) {
 264         let sum = b.iter().sum::<i32>();
 265         for v in a {
 266             *v += sum;
 267         }
 268     }
 269     assert_eq!(v1, [13, 14, 19, 20, 14]);
 270 }
 271
 272 #[test]
 273 fn test_chunks_exact_count() {
 274     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 275     let c = v.chunks_exact(3);
 276     assert_eq!(c.count(), 2);
 277
 278     let v2: &[i32] = &[0, 1, 2, 3, 4];
 279     let c2 = v2.chunks_exact(2);
 280     assert_eq!(c2.count(), 2);
 281
 282     let v3: &[i32] = &[];
 283     let c3 = v3.chunks_exact(2);
 284     assert_eq!(c3.count(), 0);
 285 }
 286
 287 #[test]
 288 fn test_chunks_exact_nth() {
 289     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 290     let mut c = v.chunks_exact(2);
 291     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 292     assert_eq!(c.next().unwrap(), &[4, 5]);
 293
 294     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 295     let mut c2 = v2.chunks_exact(3);
 296     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 297     assert_eq!(c2.next(), None);
 298 }
 299
 300 #[test]
 301 fn test_chunks_exact_nth_back() {
 302     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 303     let mut c = v.chunks_exact(2);
 304     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 305     assert_eq!(c.next().unwrap(), &[0, 1]);
 306     assert_eq!(c.next(), None);
 307
 308     let v2: &[i32] = &[0, 1, 2, 3, 4];
 309     let mut c2 = v2.chunks_exact(3);
 310     assert_eq!(c2.nth_back(0).unwrap(), &[0, 1, 2]);
 311     assert_eq!(c2.next(), None);
 312     assert_eq!(c2.next_back(), None);
 313
 314     let v3: &[i32] = &[0, 1, 2, 3, 4];
 315     let mut c3 = v3.chunks_exact(10);
 316     assert_eq!(c3.nth_back(0), None);
 317 }
 318
 319 #[test]
 320 fn test_chunks_exact_last() {
 321     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 322     let c = v.chunks_exact(2);
 323     assert_eq!(c.last().unwrap(), &[4, 5]);
 324
 325     let v2: &[i32] = &[0, 1, 2, 3, 4];
 326     let c2 = v2.chunks_exact(2);
 327     assert_eq!(c2.last().unwrap(), &[2, 3]);
 328 }
 329
 330 #[test]
 331 fn test_chunks_exact_remainder() {
 332     let v: &[i32] = &[0, 1, 2, 3, 4];
 333     let c = v.chunks_exact(2);
 334     assert_eq!(c.remainder(), &[4]);
 335 }
 336
 337 #[test]
 338 fn test_chunks_exact_zip() {
 339     let v1: &[i32] = &[0, 1, 2, 3, 4];
 340     let v2: &[i32] = &[6, 7, 8, 9, 10];
 341
 342     let res = v1.chunks_exact(2)
 343         .zip(v2.chunks_exact(2))
 344         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 345         .collect::<Vec<_>>();
 346     assert_eq!(res, vec![14, 22]);
 347 }
 348
 349 #[test]
 350 fn test_chunks_exact_mut_count() {
 351     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 352     let c = v.chunks_exact_mut(3);
 353     assert_eq!(c.count(), 2);
 354
 355     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 356     let c2 = v2.chunks_exact_mut(2);
 357     assert_eq!(c2.count(), 2);
 358
 359     let v3: &mut [i32] = &mut [];
 360     let c3 = v3.chunks_exact_mut(2);
 361     assert_eq!(c3.count(), 0);
 362 }
 363
 364 #[test]
 365 fn test_chunks_exact_mut_nth() {
 366     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 367     let mut c = v.chunks_exact_mut(2);
 368     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 369     assert_eq!(c.next().unwrap(), &[4, 5]);
 370
 371     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 372     let mut c2 = v2.chunks_exact_mut(3);
 373     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 374     assert_eq!(c2.next(), None);
 375 }
 376
 377 #[test]
 378 fn test_chunks_exact_mut_last() {
 379     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 380     let c = v.chunks_exact_mut(2);
 381     assert_eq!(c.last().unwrap(), &[4, 5]);
 382
 383     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 384     let c2 = v2.chunks_exact_mut(2);
 385     assert_eq!(c2.last().unwrap(), &[2, 3]);
 386 }
 387
 388 #[test]
 389 fn test_chunks_exact_mut_remainder() {
 390     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 391     let c = v.chunks_exact_mut(2);
 392     assert_eq!(c.into_remainder(), &[4]);
 393 }
 394
 395 #[test]
 396 fn test_chunks_exact_mut_zip() {
 397     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 398     let v2: &[i32] = &[6, 7, 8, 9, 10];
 399
 400     for (a, b) in v1.chunks_exact_mut(2).zip(v2.chunks_exact(2)) {
 401         let sum = b.iter().sum::<i32>();
 402         for v in a {
 403             *v += sum;
 404         }
 405     }
 406     assert_eq!(v1, [13, 14, 19, 20, 4]);
 407 }
 408
 409 #[test]
 410 fn test_rchunks_count() {
 411     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 412     let c = v.rchunks(3);
 413     assert_eq!(c.count(), 2);
 414
 415     let v2: &[i32] = &[0, 1, 2, 3, 4];
 416     let c2 = v2.rchunks(2);
 417     assert_eq!(c2.count(), 3);
 418
 419     let v3: &[i32] = &[];
 420     let c3 = v3.rchunks(2);
 421     assert_eq!(c3.count(), 0);
 422 }
 423
 424 #[test]
 425 fn test_rchunks_nth() {
 426     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 427     let mut c = v.rchunks(2);
 428     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 429     assert_eq!(c.next().unwrap(), &[0, 1]);
 430
 431     let v2: &[i32] = &[0, 1, 2, 3, 4];
 432     let mut c2 = v2.rchunks(3);
 433     assert_eq!(c2.nth(1).unwrap(), &[0, 1]);
 434     assert_eq!(c2.next(), None);
 435 }
 436
 437 #[test]
 438 fn test_rchunks_nth_back() {
 439     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 440     let mut c = v.rchunks(2);
 441     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 442     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 443
 444     let v2: &[i32] = &[0, 1, 2, 3, 4];
 445     let mut c2 = v2.rchunks(3);
 446     assert_eq!(c2.nth_back(1).unwrap(), &[2, 3, 4]);
 447     assert_eq!(c2.next_back(), None);
 448 }
 449
 450 #[test]
 451 fn test_rchunks_last() {
 452     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 453     let c = v.rchunks(2);
 454     assert_eq!(c.last().unwrap()[1], 1);
 455
 456     let v2: &[i32] = &[0, 1, 2, 3, 4];
 457     let c2 = v2.rchunks(2);
 458     assert_eq!(c2.last().unwrap()[0], 0);
 459 }
 460
 461 #[test]
 462 fn test_rchunks_zip() {
 463     let v1: &[i32] = &[0, 1, 2, 3, 4];
 464     let v2: &[i32] = &[6, 7, 8, 9, 10];
 465
 466     let res = v1.rchunks(2)
 467         .zip(v2.rchunks(2))
 468         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 469         .collect::<Vec<_>>();
 470     assert_eq!(res, vec![26, 18, 6]);
 471 }
 472
 473 #[test]
 474 fn test_rchunks_mut_count() {
 475     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 476     let c = v.rchunks_mut(3);
 477     assert_eq!(c.count(), 2);
 478
 479     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 480     let c2 = v2.rchunks_mut(2);
 481     assert_eq!(c2.count(), 3);
 482
 483     let v3: &mut [i32] = &mut [];
 484     let c3 = v3.rchunks_mut(2);
 485     assert_eq!(c3.count(), 0);
 486 }
 487
 488 #[test]
 489 fn test_rchunks_mut_nth() {
 490     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 491     let mut c = v.rchunks_mut(2);
 492     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 493     assert_eq!(c.next().unwrap(), &[0, 1]);
 494
 495     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 496     let mut c2 = v2.rchunks_mut(3);
 497     assert_eq!(c2.nth(1).unwrap(), &[0, 1]);
 498     assert_eq!(c2.next(), None);
 499 }
 500
 501 #[test]
 502 fn test_rchunks_mut_nth_back() {
 503     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 504     let mut c = v.rchunks_mut(2);
 505     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 506     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 507
 508     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 509     let mut c2 = v2.rchunks_mut(3);
 510     assert_eq!(c2.nth_back(1).unwrap(), &[2, 3, 4]);
 511     assert_eq!(c2.next_back(), None);
 512 }
 513
 514 #[test]
 515 fn test_rchunks_mut_last() {
 516     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 517     let c = v.rchunks_mut(2);
 518     assert_eq!(c.last().unwrap(), &[0, 1]);
 519
 520     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 521     let c2 = v2.rchunks_mut(2);
 522     assert_eq!(c2.last().unwrap(), &[0]);
 523 }
 524
 525 #[test]
 526 fn test_rchunks_mut_zip() {
 527     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 528     let v2: &[i32] = &[6, 7, 8, 9, 10];
 529
 530     for (a, b) in v1.rchunks_mut(2).zip(v2.rchunks(2)) {
 531         let sum = b.iter().sum::<i32>();
 532         for v in a {
 533             *v += sum;
 534         }
 535     }
 536     assert_eq!(v1, [6, 16, 17, 22, 23]);
 537 }
 538
 539 #[test]
 540 fn test_rchunks_exact_count() {
 541     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 542     let c = v.rchunks_exact(3);
 543     assert_eq!(c.count(), 2);
 544
 545     let v2: &[i32] = &[0, 1, 2, 3, 4];
 546     let c2 = v2.rchunks_exact(2);
 547     assert_eq!(c2.count(), 2);
 548
 549     let v3: &[i32] = &[];
 550     let c3 = v3.rchunks_exact(2);
 551     assert_eq!(c3.count(), 0);
 552 }
 553
 554 #[test]
 555 fn test_rchunks_exact_nth() {
 556     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 557     let mut c = v.rchunks_exact(2);
 558     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 559     assert_eq!(c.next().unwrap(), &[0, 1]);
 560
 561     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 562     let mut c2 = v2.rchunks_exact(3);
 563     assert_eq!(c2.nth(1).unwrap(), &[1, 2, 3]);
 564     assert_eq!(c2.next(), None);
 565 }
 566
 567 #[test]
 568 fn test_rchunks_exact_nth_back() {
 569     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 570     let mut c = v.rchunks_exact(2);
 571     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 572     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 573
 574     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 575     let mut c2 = v2.rchunks_exact(3);
 576     assert_eq!(c2.nth_back(1).unwrap(), &[4, 5, 6]);
 577     assert_eq!(c2.next(), None);
 578 }
 579
 580 #[test]
 581 fn test_rchunks_exact_last() {
 582     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 583     let c = v.rchunks_exact(2);
 584     assert_eq!(c.last().unwrap(), &[0, 1]);
 585
 586     let v2: &[i32] = &[0, 1, 2, 3, 4];
 587     let c2 = v2.rchunks_exact(2);
 588     assert_eq!(c2.last().unwrap(), &[1, 2]);
 589 }
 590
 591 #[test]
 592 fn test_rchunks_exact_remainder() {
 593     let v: &[i32] = &[0, 1, 2, 3, 4];
 594     let c = v.rchunks_exact(2);
 595     assert_eq!(c.remainder(), &[0]);
 596 }
 597
 598 #[test]
 599 fn test_rchunks_exact_zip() {
 600     let v1: &[i32] = &[0, 1, 2, 3, 4];
 601     let v2: &[i32] = &[6, 7, 8, 9, 10];
 602
 603     let res = v1.rchunks_exact(2)
 604         .zip(v2.rchunks_exact(2))
 605         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 606         .collect::<Vec<_>>();
 607     assert_eq!(res, vec![26, 18]);
 608 }
 609
 610 #[test]
 611 fn test_rchunks_exact_mut_count() {
 612     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 613     let c = v.rchunks_exact_mut(3);
 614     assert_eq!(c.count(), 2);
 615
 616     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 617     let c2 = v2.rchunks_exact_mut(2);
 618     assert_eq!(c2.count(), 2);
 619
 620     let v3: &mut [i32] = &mut [];
 621     let c3 = v3.rchunks_exact_mut(2);
 622     assert_eq!(c3.count(), 0);
 623 }
 624
 625 #[test]
 626 fn test_rchunks_exact_mut_nth() {
 627     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 628     let mut c = v.rchunks_exact_mut(2);
 629     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 630     assert_eq!(c.next().unwrap(), &[0, 1]);
 631
 632     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 633     let mut c2 = v2.rchunks_exact_mut(3);
 634     assert_eq!(c2.nth(1).unwrap(), &[1, 2, 3]);
 635     assert_eq!(c2.next(), None);
 636 }
 637
 638 #[test]
 639 fn test_rchunks_exact_mut_nth_back() {
 640     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 641     let mut c = v.rchunks_exact_mut(2);
 642     assert_eq!(c.nth_back(1).unwrap(), &[2, 3]);
 643     assert_eq!(c.next_back().unwrap(), &[4, 5]);
 644
 645     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 646     let mut c2 = v2.rchunks_exact_mut(3);
 647     assert_eq!(c2.nth_back(1).unwrap(), &[4, 5, 6]);
 648     assert_eq!(c2.next(), None);
 649 }
 650
 651 #[test]
 652 fn test_rchunks_exact_mut_last() {
 653     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 654     let c = v.rchunks_exact_mut(2);
 655     assert_eq!(c.last().unwrap(), &[0, 1]);
 656
 657     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 658     let c2 = v2.rchunks_exact_mut(2);
 659     assert_eq!(c2.last().unwrap(), &[1, 2]);
 660 }
 661
 662 #[test]
 663 fn test_rchunks_exact_mut_remainder() {
 664     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 665     let c = v.rchunks_exact_mut(2);
 666     assert_eq!(c.into_remainder(), &[0]);
 667 }
 668
 669 #[test]
 670 fn test_rchunks_exact_mut_zip() {
 671     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 672     let v2: &[i32] = &[6, 7, 8, 9, 10];
 673
 674     for (a, b) in v1.rchunks_exact_mut(2).zip(v2.rchunks_exact(2)) {
 675         let sum = b.iter().sum::<i32>();
 676         for v in a {
 677             *v += sum;
 678         }
 679     }
 680     assert_eq!(v1, [0, 16, 17, 22, 23]);
 681 }
 682
 683 #[test]
 684 fn test_windows_count() {
 685     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 686     let c = v.windows(3);
 687     assert_eq!(c.count(), 4);
 688
 689     let v2: &[i32] = &[0, 1, 2, 3, 4];
 690     let c2 = v2.windows(6);
 691     assert_eq!(c2.count(), 0);
 692
 693     let v3: &[i32] = &[];
 694     let c3 = v3.windows(2);
 695     assert_eq!(c3.count(), 0);
 696 }
 697
 698 #[test]
 699 fn test_windows_nth() {
 700     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 701     let mut c = v.windows(2);
 702     assert_eq!(c.nth(2).unwrap()[1], 3);
 703     assert_eq!(c.next().unwrap()[0], 3);
 704
 705     let v2: &[i32] = &[0, 1, 2, 3, 4];
 706     let mut c2 = v2.windows(4);
 707     assert_eq!(c2.nth(1).unwrap()[1], 2);
 708     assert_eq!(c2.next(), None);
 709 }
 710
 711 #[test]
 712 fn test_windows_nth_back() {
 713     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 714     let mut c = v.windows(2);
 715     assert_eq!(c.nth_back(2).unwrap()[0], 2);
 716     assert_eq!(c.next_back().unwrap()[1], 2);
 717
 718     let v2: &[i32] = &[0, 1, 2, 3, 4];
 719     let mut c2 = v2.windows(4);
 720     assert_eq!(c2.nth_back(1).unwrap()[1], 1);
 721     assert_eq!(c2.next_back(), None);
 722 }
 723
 724 #[test]
 725 fn test_windows_last() {
 726     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 727     let c = v.windows(2);
 728     assert_eq!(c.last().unwrap()[1], 5);
 729
 730     let v2: &[i32] = &[0, 1, 2, 3, 4];
 731     let c2 = v2.windows(2);
 732     assert_eq!(c2.last().unwrap()[0], 3);
 733 }
 734
 735 #[test]
 736 fn test_windows_zip() {
 737     let v1: &[i32] = &[0, 1, 2, 3, 4];
 738     let v2: &[i32] = &[6, 7, 8, 9, 10];
 739
 740     let res = v1.windows(2)
 741         .zip(v2.windows(2))
 742         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 743         .collect::<Vec<_>>();
 744
 745     assert_eq!(res, [14, 18, 22, 26]);
 746 }
 747
 748 #[test]
 749 #[allow(const_err)]
 750 fn test_iter_ref_consistency() {
 751     use std::fmt::Debug;
 752
 753     fn test<T : Copy + Debug + PartialEq>(x : T) {
 754         let v : &[T] = &[x, x, x];
 755         let v_ptrs : [*const T; 3] = match v {
 756             [ref v1, ref v2, ref v3] => [v1 as *const _, v2 as *const _, v3 as *const _],
 757             _ => unreachable!()
 758         };
 759         let len = v.len();
 760
 761         // nth(i)
 762         for i in 0..len {
 763             assert_eq!(&v[i] as *const _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 764             let nth = v.iter().nth(i).unwrap();
 765             assert_eq!(nth as *const _, v_ptrs[i]);
 766         }
 767         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 768
 769         // stepping through with nth(0)
 770         {
 771             let mut it = v.iter();
 772             for i in 0..len {
 773                 let next = it.nth(0).unwrap();
 774                 assert_eq!(next as *const _, v_ptrs[i]);
 775             }
 776             assert_eq!(it.nth(0), None);
 777         }
 778
 779         // next()
 780         {
 781             let mut it = v.iter();
 782             for i in 0..len {
 783                 let remaining = len - i;
 784                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 785
 786                 let next = it.next().unwrap();
 787                 assert_eq!(next as *const _, v_ptrs[i]);
 788             }
 789             assert_eq!(it.size_hint(), (0, Some(0)));
 790             assert_eq!(it.next(), None, "The final call to next() should return None");
 791         }
 792
 793         // next_back()
 794         {
 795             let mut it = v.iter();
 796             for i in 0..len {
 797                 let remaining = len - i;
 798                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 799
 800                 let prev = it.next_back().unwrap();
 801                 assert_eq!(prev as *const _, v_ptrs[remaining-1]);
 802             }
 803             assert_eq!(it.size_hint(), (0, Some(0)));
 804             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 805         }
 806     }
 807
 808     fn test_mut<T : Copy + Debug + PartialEq>(x : T) {
 809         let v : &mut [T] = &mut [x, x, x];
 810         let v_ptrs : [*mut T; 3] = match v {
 811             [ref v1, ref v2, ref v3] =>
 812               [v1 as *const _ as *mut _, v2 as *const _ as *mut _, v3 as *const _ as *mut _],
 813             _ => unreachable!()
 814         };
 815         let len = v.len();
 816
 817         // nth(i)
 818         for i in 0..len {
 819             assert_eq!(&mut v[i] as *mut _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 820             let nth = v.iter_mut().nth(i).unwrap();
 821             assert_eq!(nth as *mut _, v_ptrs[i]);
 822         }
 823         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 824
 825         // stepping through with nth(0)
 826         {
 827             let mut it = v.iter();
 828             for i in 0..len {
 829                 let next = it.nth(0).unwrap();
 830                 assert_eq!(next as *const _, v_ptrs[i]);
 831             }
 832             assert_eq!(it.nth(0), None);
 833         }
 834
 835         // next()
 836         {
 837             let mut it = v.iter_mut();
 838             for i in 0..len {
 839                 let remaining = len - i;
 840                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 841
 842                 let next = it.next().unwrap();
 843                 assert_eq!(next as *mut _, v_ptrs[i]);
 844             }
 845             assert_eq!(it.size_hint(), (0, Some(0)));
 846             assert_eq!(it.next(), None, "The final call to next() should return None");
 847         }
 848
 849         // next_back()
 850         {
 851             let mut it = v.iter_mut();
 852             for i in 0..len {
 853                 let remaining = len - i;
 854                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 855
 856                 let prev = it.next_back().unwrap();
 857                 assert_eq!(prev as *mut _, v_ptrs[remaining-1]);
 858             }
 859             assert_eq!(it.size_hint(), (0, Some(0)));
 860             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 861         }
 862     }
 863
 864     // Make sure iterators and slice patterns yield consistent addresses for various types,
 865     // including ZSTs.
 866     test(0u32);
 867     test(());
 868     test([0u32; 0]); // ZST with alignment > 0
 869     test_mut(0u32);
 870     test_mut(());
 871     test_mut([0u32; 0]); // ZST with alignment > 0
 872 }
 873
 874 // The current implementation of SliceIndex fails to handle methods
 875 // orthogonally from range types; therefore, it is worth testing
 876 // all of the indexing operations on each input.
 877 mod slice_index {
 878     // This checks all six indexing methods, given an input range that
 879     // should succeed. (it is NOT suitable for testing invalid inputs)
 880     macro_rules! assert_range_eq {
 881         ($arr:expr, $range:expr, $expected:expr)
 882         => {
 883             let mut arr = $arr;
 884             let mut expected = $expected;
 885             {
 886                 let s: &[_] = &arr;
 887                 let expected: &[_] = &expected;
 888
 889                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
 890                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
 891                 unsafe {
 892                     assert_eq!(
 893                         s.get_unchecked($range), expected,
 894                         "(in assertion for: get_unchecked)",
 895                     );
 896                 }
 897             }
 898             {
 899                 let s: &mut [_] = &mut arr;
 900                 let expected: &mut [_] = &mut expected;
 901
 902                 assert_eq!(
 903                     &mut s[$range], expected,
 904                     "(in assertion for: index_mut)",
 905                 );
 906                 assert_eq!(
 907                     s.get_mut($range), Some(&mut expected[..]),
 908                     "(in assertion for: get_mut)",
 909                 );
 910                 unsafe {
 911                     assert_eq!(
 912                         s.get_unchecked_mut($range), expected,
 913                         "(in assertion for: get_unchecked_mut)",
 914                     );
 915                 }
 916             }
 917         }
 918     }
 919
 920     // Make sure the macro can actually detect bugs,
 921     // because if it can't, then what are we even doing here?
 922     //
 923     // (Be aware this only demonstrates the ability to detect bugs
 924     //  in the FIRST method that panics, as the macro is not designed
 925     //  to be used in `should_panic`)
 926     #[test]
 927     #[should_panic(expected = "out of range")]
 928     fn assert_range_eq_can_fail_by_panic() {
 929         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
 930     }
 931
 932     // (Be aware this only demonstrates the ability to detect bugs
 933     //  in the FIRST method it calls, as the macro is not designed
 934     //  to be used in `should_panic`)
 935     #[test]
 936     #[should_panic(expected = "==")]
 937     fn assert_range_eq_can_fail_by_inequality() {
 938         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
 939     }
 940
 941     // Test cases for bad index operations.
 942     //
 943     // This generates `should_panic` test cases for Index/IndexMut
 944     // and `None` test cases for get/get_mut.
 945     macro_rules! panic_cases {
 946         ($(
 947             // each test case needs a unique name to namespace the tests
 948             in mod $case_name:ident {
 949                 data: $data:expr;
 950
 951                 // optional:
 952                 //
 953                 // one or more similar inputs for which data[input] succeeds,
 954                 // and the corresponding output as an array.  This helps validate
 955                 // "critical points" where an input range straddles the boundary
 956                 // between valid and invalid.
 957                 // (such as the input `len..len`, which is just barely valid)
 958                 $(
 959                     good: data[$good:expr] == $output:expr;
 960                 )*
 961
 962                 bad: data[$bad:expr];
 963                 message: $expect_msg:expr;
 964             }
 965         )*) => {$(
 966             mod $case_name {
 967                 #[test]
 968                 fn pass() {
 969                     let mut v = $data;
 970
 971                     $( assert_range_eq!($data, $good, $output); )*
 972
 973                     {
 974                         let v: &[_] = &v;
 975                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
 976                     }
 977
 978                     {
 979                         let v: &mut [_] = &mut v;
 980                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
 981                     }
 982                 }
 983
 984                 #[test]
 985                 #[should_panic(expected = $expect_msg)]
 986                 fn index_fail() {
 987                     let v = $data;
 988                     let v: &[_] = &v;
 989                     let _v = &v[$bad];
 990                 }
 991
 992                 #[test]
 993                 #[should_panic(expected = $expect_msg)]
 994                 fn index_mut_fail() {
 995                     let mut v = $data;
 996                     let v: &mut [_] = &mut v;
 997                     let _v = &mut v[$bad];
 998                 }
 999             }
1000         )*};
1001     }
1002
1003     #[test]
1004     fn simple() {
1005         let v = [0, 1, 2, 3, 4, 5];
1006
1007         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
1008         assert_range_eq!(v, ..2, [0, 1]);
1009         assert_range_eq!(v, ..=1, [0, 1]);
1010         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
1011         assert_range_eq!(v, 1..4, [1, 2, 3]);
1012         assert_range_eq!(v, 1..=3, [1, 2, 3]);
1013     }
1014
1015     panic_cases! {
1016         in mod rangefrom_len {
1017             data: [0, 1, 2, 3, 4, 5];
1018
1019             good: data[6..] == [];
1020             bad: data[7..];
1021             message: "but ends at"; // perhaps not ideal
1022         }
1023
1024         in mod rangeto_len {
1025             data: [0, 1, 2, 3, 4, 5];
1026
1027             good: data[..6] == [0, 1, 2, 3, 4, 5];
1028             bad: data[..7];
1029             message: "out of range";
1030         }
1031
1032         in mod rangetoinclusive_len {
1033             data: [0, 1, 2, 3, 4, 5];
1034
1035             good: data[..=5] == [0, 1, 2, 3, 4, 5];
1036             bad: data[..=6];
1037             message: "out of range";
1038         }
1039
1040         in mod range_len_len {
1041             data: [0, 1, 2, 3, 4, 5];
1042
1043             good: data[6..6] == [];
1044             bad: data[7..7];
1045             message: "out of range";
1046         }
1047
1048         in mod rangeinclusive_len_len {
1049             data: [0, 1, 2, 3, 4, 5];
1050
1051             good: data[6..=5] == [];
1052             bad: data[7..=6];
1053             message: "out of range";
1054         }
1055     }
1056
1057     panic_cases! {
1058         in mod range_neg_width {
1059             data: [0, 1, 2, 3, 4, 5];
1060
1061             good: data[4..4] == [];
1062             bad: data[4..3];
1063             message: "but ends at";
1064         }
1065
1066         in mod rangeinclusive_neg_width {
1067             data: [0, 1, 2, 3, 4, 5];
1068
1069             good: data[4..=3] == [];
1070             bad: data[4..=2];
1071             message: "but ends at";
1072         }
1073     }
1074
1075     panic_cases! {
1076         in mod rangeinclusive_overflow {
1077             data: [0, 1];
1078
1079             // note: using 0 specifically ensures that the result of overflowing is 0..0,
1080             //       so that `get` doesn't simply return None for the wrong reason.
1081             bad: data[0 ..= ::std::usize::MAX];
1082             message: "maximum usize";
1083         }
1084
1085         in mod rangetoinclusive_overflow {
1086             data: [0, 1];
1087
1088             bad: data[..= ::std::usize::MAX];
1089             message: "maximum usize";
1090         }
1091     } // panic_cases!
1092 }
1093
1094 #[test]
1095 fn test_find_rfind() {
1096     let v = [0, 1, 2, 3, 4, 5];
1097     let mut iter = v.iter();
1098     let mut i = v.len();
1099     while let Some(&elt) = iter.rfind(|_| true) {
1100         i -= 1;
1101         assert_eq!(elt, v[i]);
1102     }
1103     assert_eq!(i, 0);
1104     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
1105 }
1106
1107 #[test]
1108 fn test_iter_folds() {
1109     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
1110     assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
1111     assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
1112     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
1113     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
1114     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
1115
1116     // short-circuiting try_fold, through other methods
1117     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
1118     let mut iter = a.iter();
1119     assert_eq!(iter.position(|&x| x == 3), Some(3));
1120     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
1121     assert_eq!(iter.len(), 2);
1122 }
1123
1124 #[test]
1125 fn test_rotate_left() {
1126     const N: usize = 600;
1127     let a: &mut [_] = &mut [0; N];
1128     for i in 0..N {
1129         a[i] = i;
1130     }
1131
1132     a.rotate_left(42);
1133     let k = N - 42;
1134
1135     for i in 0..N {
1136         assert_eq!(a[(i + k) % N], i);
1137     }
1138 }
1139
1140 #[test]
1141 fn test_rotate_right() {
1142     const N: usize = 600;
1143     let a: &mut [_] = &mut [0; N];
1144     for i in 0..N {
1145         a[i] = i;
1146     }
1147
1148     a.rotate_right(42);
1149
1150     for i in 0..N {
1151         assert_eq!(a[(i + 42) % N], i);
1152     }
1153 }
1154
1155 #[test]
1156 #[cfg(not(target_arch = "wasm32"))]
1157 fn sort_unstable() {
1158     use core::cmp::Ordering::{Equal, Greater, Less};
1159     use core::slice::heapsort;
1160     use rand::{FromEntropy, Rng, rngs::SmallRng, seq::SliceRandom};
1161
1162     #[cfg(not(miri))] // Miri is too slow
1163     let large_range = 500..510;
1164     #[cfg(not(miri))] // Miri is too slow
1165     let rounds = 100;
1166
1167     #[cfg(miri)]
1168     let large_range = 0..0; // empty range
1169     #[cfg(miri)]
1170     let rounds = 1;
1171
1172     let mut v = [0; 600];
1173     let mut tmp = [0; 600];
1174     let mut rng = SmallRng::from_entropy();
1175
1176     for len in (2..25).chain(large_range) {
1177         let v = &mut v[0..len];
1178         let tmp = &mut tmp[0..len];
1179
1180         for &modulus in &[5, 10, 100, 1000] {
1181             for _ in 0..rounds {
1182                 for i in 0..len {
1183                     v[i] = rng.gen::<i32>() % modulus;
1184                 }
1185
1186                 // Sort in default order.
1187                 tmp.copy_from_slice(v);
1188                 tmp.sort_unstable();
1189                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1190
1191                 // Sort in ascending order.
1192                 tmp.copy_from_slice(v);
1193                 tmp.sort_unstable_by(|a, b| a.cmp(b));
1194                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1195
1196                 // Sort in descending order.
1197                 tmp.copy_from_slice(v);
1198                 tmp.sort_unstable_by(|a, b| b.cmp(a));
1199                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1200
1201                 // Test heapsort using `<` operator.
1202                 tmp.copy_from_slice(v);
1203                 heapsort(tmp, |a, b| a < b);
1204                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
1205
1206                 // Test heapsort using `>` operator.
1207                 tmp.copy_from_slice(v);
1208                 heapsort(tmp, |a, b| a > b);
1209                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
1210             }
1211         }
1212     }
1213
1214     // Sort using a completely random comparison function.
1215     // This will reorder the elements *somehow*, but won't panic.
1216     for i in 0..v.len() {
1217         v[i] = i as i32;
1218     }
1219     v.sort_unstable_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1220     v.sort_unstable();
1221     for i in 0..v.len() {
1222         assert_eq!(v[i], i as i32);
1223     }
1224
1225     // Should not panic.
1226     [0i32; 0].sort_unstable();
1227     [(); 10].sort_unstable();
1228     [(); 100].sort_unstable();
1229
1230     let mut v = [0xDEADBEEFu64];
1231     v.sort_unstable();
1232     assert!(v == [0xDEADBEEF]);
1233 }
1234
1235 #[test]
1236 #[cfg(not(target_arch = "wasm32"))]
1237 #[cfg(not(miri))] // Miri is too slow
1238 fn partition_at_index() {
1239     use core::cmp::Ordering::{Equal, Greater, Less};
1240     use rand::rngs::SmallRng;
1241     use rand::seq::SliceRandom;
1242     use rand::{FromEntropy, Rng};
1243
1244     let mut rng = SmallRng::from_entropy();
1245
1246     for len in (2..21).chain(500..501) {
1247         let mut orig = vec![0; len];
1248
1249         for &modulus in &[5, 10, 1000] {
1250             for _ in 0..10 {
1251                 for i in 0..len {
1252                     orig[i] = rng.gen::<i32>() % modulus;
1253                 }
1254
1255                 let v_sorted = {
1256                     let mut v = orig.clone();
1257                     v.sort();
1258                     v
1259                 };
1260
1261                 // Sort in default order.
1262                 for pivot in 0..len {
1263                     let mut v = orig.clone();
1264                     v.partition_at_index(pivot);
1265
1266                     assert_eq!(v_sorted[pivot], v[pivot]);
1267                     for i in 0..pivot {
1268                         for j in pivot..len {
1269                             assert!(v[i] <= v[j]);
1270                         }
1271                     }
1272                 }
1273
1274                 // Sort in ascending order.
1275                 for pivot in 0..len {
1276                     let mut v = orig.clone();
1277                     let (left, pivot, right) = v.partition_at_index_by(pivot, |a, b| a.cmp(b));
1278
1279                     assert_eq!(left.len() + right.len(), len - 1);
1280
1281                     for l in left {
1282                         assert!(l <= pivot);
1283                         for r in right.iter_mut() {
1284                             assert!(l <= r);
1285                             assert!(pivot <= r);
1286                         }
1287                     }
1288                 }
1289
1290                 // Sort in descending order.
1291                 let sort_descending_comparator = |a: &i32, b: &i32| b.cmp(a);
1292                 let v_sorted_descending = {
1293                     let mut v = orig.clone();
1294                     v.sort_by(sort_descending_comparator);
1295                     v
1296                 };
1297
1298                 for pivot in 0..len {
1299                     let mut v = orig.clone();
1300                     v.partition_at_index_by(pivot, sort_descending_comparator);
1301
1302                     assert_eq!(v_sorted_descending[pivot], v[pivot]);
1303                     for i in 0..pivot {
1304                         for j in pivot..len {
1305                             assert!(v[j] <= v[i]);
1306                         }
1307                     }
1308                 }
1309             }
1310         }
1311     }
1312
1313     // Sort at index using a completely random comparison function.
1314     // This will reorder the elements *somehow*, but won't panic.
1315     let mut v = [0; 500];
1316     for i in 0..v.len() {
1317         v[i] = i as i32;
1318     }
1319
1320     for pivot in 0..v.len() {
1321         v.partition_at_index_by(pivot, |_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
1322         v.sort();
1323         for i in 0..v.len() {
1324             assert_eq!(v[i], i as i32);
1325         }
1326     }
1327
1328     // Should not panic.
1329     [(); 10].partition_at_index(0);
1330     [(); 10].partition_at_index(5);
1331     [(); 10].partition_at_index(9);
1332     [(); 100].partition_at_index(0);
1333     [(); 100].partition_at_index(50);
1334     [(); 100].partition_at_index(99);
1335
1336     let mut v = [0xDEADBEEFu64];
1337     v.partition_at_index(0);
1338     assert!(v == [0xDEADBEEF]);
1339 }
1340
1341 #[test]
1342 #[should_panic(expected = "index 0 greater than length of slice")]
1343 fn partition_at_index_zero_length() {
1344     [0i32; 0].partition_at_index(0);
1345 }
1346
1347 #[test]
1348 #[should_panic(expected = "index 20 greater than length of slice")]
1349 fn partition_at_index_past_length() {
1350     [0i32; 10].partition_at_index(20);
1351 }
1352
1353 pub mod memchr {
1354     use core::slice::memchr::{memchr, memrchr};
1355
1356     // test fallback implementations on all platforms
1357     #[test]
1358     fn matches_one() {
1359         assert_eq!(Some(0), memchr(b'a', b"a"));
1360     }
1361
1362     #[test]
1363     fn matches_begin() {
1364         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
1365     }
1366
1367     #[test]
1368     fn matches_end() {
1369         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
1370     }
1371
1372     #[test]
1373     fn matches_nul() {
1374         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
1375     }
1376
1377     #[test]
1378     fn matches_past_nul() {
1379         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
1380     }
1381
1382     #[test]
1383     fn no_match_empty() {
1384         assert_eq!(None, memchr(b'a', b""));
1385     }
1386
1387     #[test]
1388     fn no_match() {
1389         assert_eq!(None, memchr(b'a', b"xyz"));
1390     }
1391
1392     #[test]
1393     fn matches_one_reversed() {
1394         assert_eq!(Some(0), memrchr(b'a', b"a"));
1395     }
1396
1397     #[test]
1398     fn matches_begin_reversed() {
1399         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
1400     }
1401
1402     #[test]
1403     fn matches_end_reversed() {
1404         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
1405     }
1406
1407     #[test]
1408     fn matches_nul_reversed() {
1409         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
1410     }
1411
1412     #[test]
1413     fn matches_past_nul_reversed() {
1414         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
1415     }
1416
1417     #[test]
1418     fn no_match_empty_reversed() {
1419         assert_eq!(None, memrchr(b'a', b""));
1420     }
1421
1422     #[test]
1423     fn no_match_reversed() {
1424         assert_eq!(None, memrchr(b'a', b"xyz"));
1425     }
1426
1427     #[test]
1428     fn each_alignment_reversed() {
1429         let mut data = [1u8; 64];
1430         let needle = 2;
1431         let pos = 40;
1432         data[pos] = needle;
1433         for start in 0..16 {
1434             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
1435         }
1436     }
1437 }
1438
1439 #[test]
1440 #[cfg(not(miri))] // Miri does not compute a maximal `mid` for `align_offset`
1441 fn test_align_to_simple() {
1442     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
1443     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
1444     assert_eq!(aligned.len(), 3);
1445     assert!(prefix == [1] || suffix == [7]);
1446     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
1447     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
1448     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
1449     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
1450     assert!(aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
1451             "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
1452             aligned, expect1, expect2, expect3, expect4);
1453 }
1454
1455 #[test]
1456 fn test_align_to_zst() {
1457     let bytes = [1, 2, 3, 4, 5, 6, 7];
1458     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
1459     assert_eq!(aligned.len(), 0);
1460     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
1461 }
1462
1463 #[test]
1464 #[cfg(not(miri))] // Miri does not compute a maximal `mid` for `align_offset`
1465 fn test_align_to_non_trivial() {
1466     #[repr(align(8))] struct U64(u64, u64);
1467     #[repr(align(8))] struct U64U64U32(u64, u64, u32);
1468     let data = [U64(1, 2), U64(3, 4), U64(5, 6), U64(7, 8), U64(9, 10), U64(11, 12), U64(13, 14),
1469                 U64(15, 16)];
1470     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
1471     assert_eq!(aligned.len(), 4);
1472     assert_eq!(prefix.len() + suffix.len(), 2);
1473 }
1474
1475 #[test]
1476 fn test_align_to_empty_mid() {
1477     use core::mem;
1478
1479     // Make sure that we do not create empty unaligned slices for the mid part, even when the
1480     // overall slice is too short to contain an aligned address.
1481     let bytes = [1, 2, 3, 4, 5, 6, 7];
1482     type Chunk = u32;
1483     for offset in 0..4 {
1484         let (_, mid, _) = unsafe { bytes[offset..offset+1].align_to::<Chunk>() };
1485         assert_eq!(mid.as_ptr() as usize % mem::align_of::<Chunk>(), 0);
1486     }
1487 }
1488
1489 #[test]
1490 fn test_slice_partition_dedup_by() {
1491     let mut slice: [i32; 9] = [1, -1, 2, 3, 1, -5, 5, -2, 2];
1492
1493     let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.abs() == b.abs());
1494
1495     assert_eq!(dedup, [1, 2, 3, 1, -5, -2]);
1496     assert_eq!(duplicates, [5, -1, 2]);
1497 }
1498
1499 #[test]
1500 fn test_slice_partition_dedup_empty() {
1501     let mut slice: [i32; 0] = [];
1502
1503     let (dedup, duplicates) = slice.partition_dedup();
1504
1505     assert_eq!(dedup, []);
1506     assert_eq!(duplicates, []);
1507 }
1508
1509 #[test]
1510 fn test_slice_partition_dedup_one() {
1511     let mut slice = [12];
1512
1513     let (dedup, duplicates) = slice.partition_dedup();
1514
1515     assert_eq!(dedup, [12]);
1516     assert_eq!(duplicates, []);
1517 }
1518
1519 #[test]
1520 fn test_slice_partition_dedup_multiple_ident() {
1521     let mut slice = [12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
1522
1523     let (dedup, duplicates) = slice.partition_dedup();
1524
1525     assert_eq!(dedup, [12, 11]);
1526     assert_eq!(duplicates, [12, 12, 12, 12, 11, 11, 11, 11, 11]);
1527 }
1528
1529 #[test]
1530 fn test_slice_partition_dedup_partialeq() {
1531     #[derive(Debug)]
1532     struct Foo(i32, i32);
1533
1534     impl PartialEq for Foo {
1535         fn eq(&self, other: &Foo) -> bool {
1536             self.0 == other.0
1537         }
1538     }
1539
1540     let mut slice = [Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
1541
1542     let (dedup, duplicates) = slice.partition_dedup();
1543
1544     assert_eq!(dedup, [Foo(0, 1), Foo(1, 7)]);
1545     assert_eq!(duplicates, [Foo(0, 5), Foo(1, 9)]);
1546 }
1547
1548 #[test]
1549 fn test_copy_within() {
1550     // Start to end, with a RangeTo.
1551     let mut bytes = *b"Hello, World!";
1552     bytes.copy_within(..3, 10);
1553     assert_eq!(&bytes, b"Hello, WorHel");
1554
1555     // End to start, with a RangeFrom.
1556     let mut bytes = *b"Hello, World!";
1557     bytes.copy_within(10.., 0);
1558     assert_eq!(&bytes, b"ld!lo, World!");
1559
1560     // Overlapping, with a RangeInclusive.
1561     let mut bytes = *b"Hello, World!";
1562     bytes.copy_within(0..=11, 1);
1563     assert_eq!(&bytes, b"HHello, World");
1564
1565     // Whole slice, with a RangeFull.
1566     let mut bytes = *b"Hello, World!";
1567     bytes.copy_within(.., 0);
1568     assert_eq!(&bytes, b"Hello, World!");
1569
1570     // Ensure that copying at the end of slice won't cause UB.
1571     let mut bytes = *b"Hello, World!";
1572     bytes.copy_within(13..13, 5);
1573     assert_eq!(&bytes, b"Hello, World!");
1574     bytes.copy_within(5..5, 13);
1575     assert_eq!(&bytes, b"Hello, World!");
1576 }
1577
1578 #[test]
1579 #[should_panic(expected = "src is out of bounds")]
1580 fn test_copy_within_panics_src_too_long() {
1581     let mut bytes = *b"Hello, World!";
1582     // The length is only 13, so 14 is out of bounds.
1583     bytes.copy_within(10..14, 0);
1584 }
1585
1586 #[test]
1587 #[should_panic(expected = "dest is out of bounds")]
1588 fn test_copy_within_panics_dest_too_long() {
1589     let mut bytes = *b"Hello, World!";
1590     // The length is only 13, so a slice of length 4 starting at index 10 is out of bounds.
1591     bytes.copy_within(0..4, 10);
1592 }
1593 #[test]
1594 #[should_panic(expected = "src end is before src start")]
1595 fn test_copy_within_panics_src_inverted() {
1596     let mut bytes = *b"Hello, World!";
1597     // 2 is greater than 1, so this range is invalid.
1598     bytes.copy_within(2..1, 0);
1599 }
1600 #[test]
1601 #[should_panic(expected = "attempted to index slice up to maximum usize")]
1602 fn test_copy_within_panics_src_out_of_bounds() {
1603     let mut bytes = *b"Hello, World!";
1604     // an inclusive range ending at usize::max_value() would make src_end overflow
1605     bytes.copy_within(usize::max_value()..=usize::max_value(), 0);
1606 }
1607
1608 #[test]
1609 fn test_is_sorted() {
1610     let empty: [i32; 0] = [];
1611
1612     assert!([1, 2, 2, 9].is_sorted());
1613     assert!(![1, 3, 2].is_sorted());
1614     assert!([0].is_sorted());
1615     assert!(empty.is_sorted());
1616     assert!(![0.0, 1.0, std::f32::NAN].is_sorted());
1617     assert!([-2, -1, 0, 3].is_sorted());
1618     assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
1619     assert!(!["c", "bb", "aaa"].is_sorted());
1620     assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
1621 }