src/libcore/tests/slice.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use core::result::Result::{Ok, Err};
  12
  13 #[test]
  14 fn test_position() {
  15     let b = [1, 2, 3, 5, 5];
  16     assert!(b.iter().position(|&v| v == 9) == None);
  17     assert!(b.iter().position(|&v| v == 5) == Some(3));
  18     assert!(b.iter().position(|&v| v == 3) == Some(2));
  19     assert!(b.iter().position(|&v| v == 0) == None);
  20 }
  21
  22 #[test]
  23 fn test_rposition() {
  24     let b = [1, 2, 3, 5, 5];
  25     assert!(b.iter().rposition(|&v| v == 9) == None);
  26     assert!(b.iter().rposition(|&v| v == 5) == Some(4));
  27     assert!(b.iter().rposition(|&v| v == 3) == Some(2));
  28     assert!(b.iter().rposition(|&v| v == 0) == None);
  29 }
  30
  31 #[test]
  32 fn test_binary_search() {
  33     let b: [i32; 0] = [];
  34     assert_eq!(b.binary_search(&5), Err(0));
  35
  36     let b = [4];
  37     assert_eq!(b.binary_search(&3), Err(0));
  38     assert_eq!(b.binary_search(&4), Ok(0));
  39     assert_eq!(b.binary_search(&5), Err(1));
  40
  41     let b = [1, 2, 4, 6, 8, 9];
  42     assert_eq!(b.binary_search(&5), Err(3));
  43     assert_eq!(b.binary_search(&6), Ok(3));
  44     assert_eq!(b.binary_search(&7), Err(4));
  45     assert_eq!(b.binary_search(&8), Ok(4));
  46
  47     let b = [1, 2, 4, 5, 6, 8];
  48     assert_eq!(b.binary_search(&9), Err(6));
  49
  50     let b = [1, 2, 4, 6, 7, 8, 9];
  51     assert_eq!(b.binary_search(&6), Ok(3));
  52     assert_eq!(b.binary_search(&5), Err(3));
  53     assert_eq!(b.binary_search(&8), Ok(5));
  54
  55     let b = [1, 2, 4, 5, 6, 8, 9];
  56     assert_eq!(b.binary_search(&7), Err(5));
  57     assert_eq!(b.binary_search(&0), Err(0));
  58
  59     let b = [1, 3, 3, 3, 7];
  60     assert_eq!(b.binary_search(&0), Err(0));
  61     assert_eq!(b.binary_search(&1), Ok(0));
  62     assert_eq!(b.binary_search(&2), Err(1));
  63     assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false });
  64     assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false });
  65     assert_eq!(b.binary_search(&4), Err(4));
  66     assert_eq!(b.binary_search(&5), Err(4));
  67     assert_eq!(b.binary_search(&6), Err(4));
  68     assert_eq!(b.binary_search(&7), Ok(4));
  69     assert_eq!(b.binary_search(&8), Err(5));
  70 }
  71
  72 #[test]
  73 // Test implementation specific behavior when finding equivalent elements.
  74 // It is ok to break this test but when you do a crater run is highly advisable.
  75 fn test_binary_search_implementation_details() {
  76     let b = [1, 1, 2, 2, 3, 3, 3];
  77     assert_eq!(b.binary_search(&1), Ok(1));
  78     assert_eq!(b.binary_search(&2), Ok(3));
  79     assert_eq!(b.binary_search(&3), Ok(6));
  80     let b = [1, 1, 1, 1, 1, 3, 3, 3, 3];
  81     assert_eq!(b.binary_search(&1), Ok(4));
  82     assert_eq!(b.binary_search(&3), Ok(8));
  83     let b = [1, 1, 1, 1, 3, 3, 3, 3, 3];
  84     assert_eq!(b.binary_search(&1), Ok(3));
  85     assert_eq!(b.binary_search(&3), Ok(8));
  86 }
  87
  88 #[test]
  89 fn test_iterator_nth() {
  90     let v: &[_] = &[0, 1, 2, 3, 4];
  91     for i in 0..v.len() {
  92         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
  93     }
  94     assert_eq!(v.iter().nth(v.len()), None);
  95
  96     let mut iter = v.iter();
  97     assert_eq!(iter.nth(2).unwrap(), &v[2]);
  98     assert_eq!(iter.nth(1).unwrap(), &v[4]);
  99 }
 100
 101 #[test]
 102 fn test_iterator_last() {
 103     let v: &[_] = &[0, 1, 2, 3, 4];
 104     assert_eq!(v.iter().last().unwrap(), &4);
 105     assert_eq!(v[..1].iter().last().unwrap(), &0);
 106 }
 107
 108 #[test]
 109 fn test_iterator_count() {
 110     let v: &[_] = &[0, 1, 2, 3, 4];
 111     assert_eq!(v.iter().count(), 5);
 112
 113     let mut iter2 = v.iter();
 114     iter2.next();
 115     iter2.next();
 116     assert_eq!(iter2.count(), 3);
 117 }
 118
 119 #[test]
 120 fn test_chunks_count() {
 121     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 122     let c = v.chunks(3);
 123     assert_eq!(c.count(), 2);
 124
 125     let v2: &[i32] = &[0, 1, 2, 3, 4];
 126     let c2 = v2.chunks(2);
 127     assert_eq!(c2.count(), 3);
 128
 129     let v3: &[i32] = &[];
 130     let c3 = v3.chunks(2);
 131     assert_eq!(c3.count(), 0);
 132 }
 133
 134 #[test]
 135 fn test_chunks_nth() {
 136     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 137     let mut c = v.chunks(2);
 138     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 139     assert_eq!(c.next().unwrap(), &[4, 5]);
 140
 141     let v2: &[i32] = &[0, 1, 2, 3, 4];
 142     let mut c2 = v2.chunks(3);
 143     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 144     assert_eq!(c2.next(), None);
 145 }
 146
 147 #[test]
 148 fn test_chunks_last() {
 149     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 150     let c = v.chunks(2);
 151     assert_eq!(c.last().unwrap()[1], 5);
 152
 153     let v2: &[i32] = &[0, 1, 2, 3, 4];
 154     let c2 = v2.chunks(2);
 155     assert_eq!(c2.last().unwrap()[0], 4);
 156 }
 157
 158 #[test]
 159 fn test_chunks_zip() {
 160     let v1: &[i32] = &[0, 1, 2, 3, 4];
 161     let v2: &[i32] = &[6, 7, 8, 9, 10];
 162
 163     let res = v1.chunks(2)
 164         .zip(v2.chunks(2))
 165         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 166         .collect::<Vec<_>>();
 167     assert_eq!(res, vec![14, 22, 14]);
 168 }
 169
 170 #[test]
 171 fn test_chunks_mut_count() {
 172     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 173     let c = v.chunks_mut(3);
 174     assert_eq!(c.count(), 2);
 175
 176     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 177     let c2 = v2.chunks_mut(2);
 178     assert_eq!(c2.count(), 3);
 179
 180     let v3: &mut [i32] = &mut [];
 181     let c3 = v3.chunks_mut(2);
 182     assert_eq!(c3.count(), 0);
 183 }
 184
 185 #[test]
 186 fn test_chunks_mut_nth() {
 187     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 188     let mut c = v.chunks_mut(2);
 189     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 190     assert_eq!(c.next().unwrap(), &[4, 5]);
 191
 192     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 193     let mut c2 = v2.chunks_mut(3);
 194     assert_eq!(c2.nth(1).unwrap(), &[3, 4]);
 195     assert_eq!(c2.next(), None);
 196 }
 197
 198 #[test]
 199 fn test_chunks_mut_last() {
 200     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 201     let c = v.chunks_mut(2);
 202     assert_eq!(c.last().unwrap(), &[4, 5]);
 203
 204     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 205     let c2 = v2.chunks_mut(2);
 206     assert_eq!(c2.last().unwrap(), &[4]);
 207 }
 208
 209 #[test]
 210 fn test_chunks_mut_zip() {
 211     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 212     let v2: &[i32] = &[6, 7, 8, 9, 10];
 213
 214     for (a, b) in v1.chunks_mut(2).zip(v2.chunks(2)) {
 215         let sum = b.iter().sum::<i32>();
 216         for v in a {
 217             *v += sum;
 218         }
 219     }
 220     assert_eq!(v1, [13, 14, 19, 20, 14]);
 221 }
 222
 223 #[test]
 224 fn test_exact_chunks_count() {
 225     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 226     let c = v.exact_chunks(3);
 227     assert_eq!(c.count(), 2);
 228
 229     let v2: &[i32] = &[0, 1, 2, 3, 4];
 230     let c2 = v2.exact_chunks(2);
 231     assert_eq!(c2.count(), 2);
 232
 233     let v3: &[i32] = &[];
 234     let c3 = v3.exact_chunks(2);
 235     assert_eq!(c3.count(), 0);
 236 }
 237
 238 #[test]
 239 fn test_exact_chunks_nth() {
 240     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 241     let mut c = v.exact_chunks(2);
 242     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 243     assert_eq!(c.next().unwrap(), &[4, 5]);
 244
 245     let v2: &[i32] = &[0, 1, 2, 3, 4, 5, 6];
 246     let mut c2 = v2.exact_chunks(3);
 247     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 248     assert_eq!(c2.next(), None);
 249 }
 250
 251 #[test]
 252 fn test_exact_chunks_last() {
 253     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 254     let c = v.exact_chunks(2);
 255     assert_eq!(c.last().unwrap(), &[4, 5]);
 256
 257     let v2: &[i32] = &[0, 1, 2, 3, 4];
 258     let c2 = v2.exact_chunks(2);
 259     assert_eq!(c2.last().unwrap(), &[2, 3]);
 260 }
 261
 262 #[test]
 263 fn test_exact_chunks_zip() {
 264     let v1: &[i32] = &[0, 1, 2, 3, 4];
 265     let v2: &[i32] = &[6, 7, 8, 9, 10];
 266
 267     let res = v1.exact_chunks(2)
 268         .zip(v2.exact_chunks(2))
 269         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 270         .collect::<Vec<_>>();
 271     assert_eq!(res, vec![14, 22]);
 272 }
 273
 274 #[test]
 275 fn test_exact_chunks_mut_count() {
 276     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 277     let c = v.exact_chunks_mut(3);
 278     assert_eq!(c.count(), 2);
 279
 280     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 281     let c2 = v2.exact_chunks_mut(2);
 282     assert_eq!(c2.count(), 2);
 283
 284     let v3: &mut [i32] = &mut [];
 285     let c3 = v3.exact_chunks_mut(2);
 286     assert_eq!(c3.count(), 0);
 287 }
 288
 289 #[test]
 290 fn test_exact_chunks_mut_nth() {
 291     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 292     let mut c = v.exact_chunks_mut(2);
 293     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 294     assert_eq!(c.next().unwrap(), &[4, 5]);
 295
 296     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 297     let mut c2 = v2.exact_chunks_mut(3);
 298     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 299     assert_eq!(c2.next(), None);
 300 }
 301
 302 #[test]
 303 fn test_exact_chunks_mut_last() {
 304     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 305     let c = v.exact_chunks_mut(2);
 306     assert_eq!(c.last().unwrap(), &[4, 5]);
 307
 308     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 309     let c2 = v2.exact_chunks_mut(2);
 310     assert_eq!(c2.last().unwrap(), &[2, 3]);
 311 }
 312
 313 #[test]
 314 fn test_exact_chunks_mut_zip() {
 315     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 316     let v2: &[i32] = &[6, 7, 8, 9, 10];
 317
 318     for (a, b) in v1.exact_chunks_mut(2).zip(v2.exact_chunks(2)) {
 319         let sum = b.iter().sum::<i32>();
 320         for v in a {
 321             *v += sum;
 322         }
 323     }
 324     assert_eq!(v1, [13, 14, 19, 20, 4]);
 325 }
 326
 327 #[test]
 328 fn test_windows_count() {
 329     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 330     let c = v.windows(3);
 331     assert_eq!(c.count(), 4);
 332
 333     let v2: &[i32] = &[0, 1, 2, 3, 4];
 334     let c2 = v2.windows(6);
 335     assert_eq!(c2.count(), 0);
 336
 337     let v3: &[i32] = &[];
 338     let c3 = v3.windows(2);
 339     assert_eq!(c3.count(), 0);
 340 }
 341
 342 #[test]
 343 fn test_windows_nth() {
 344     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 345     let mut c = v.windows(2);
 346     assert_eq!(c.nth(2).unwrap()[1], 3);
 347     assert_eq!(c.next().unwrap()[0], 3);
 348
 349     let v2: &[i32] = &[0, 1, 2, 3, 4];
 350     let mut c2 = v2.windows(4);
 351     assert_eq!(c2.nth(1).unwrap()[1], 2);
 352     assert_eq!(c2.next(), None);
 353 }
 354
 355 #[test]
 356 fn test_windows_last() {
 357     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 358     let c = v.windows(2);
 359     assert_eq!(c.last().unwrap()[1], 5);
 360
 361     let v2: &[i32] = &[0, 1, 2, 3, 4];
 362     let c2 = v2.windows(2);
 363     assert_eq!(c2.last().unwrap()[0], 3);
 364 }
 365
 366 #[test]
 367 fn test_windows_zip() {
 368     let v1: &[i32] = &[0, 1, 2, 3, 4];
 369     let v2: &[i32] = &[6, 7, 8, 9, 10];
 370
 371     let res = v1.windows(2)
 372         .zip(v2.windows(2))
 373         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 374         .collect::<Vec<_>>();
 375
 376     assert_eq!(res, [14, 18, 22, 26]);
 377 }
 378
 379 // The current implementation of SliceIndex fails to handle methods
 380 // orthogonally from range types; therefore, it is worth testing
 381 // all of the indexing operations on each input.
 382 mod slice_index {
 383     // This checks all six indexing methods, given an input range that
 384     // should succeed. (it is NOT suitable for testing invalid inputs)
 385     macro_rules! assert_range_eq {
 386         ($arr:expr, $range:expr, $expected:expr)
 387         => {
 388             let mut arr = $arr;
 389             let mut expected = $expected;
 390             {
 391                 let s: &[_] = &arr;
 392                 let expected: &[_] = &expected;
 393
 394                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
 395                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
 396                 unsafe {
 397                     assert_eq!(
 398                         s.get_unchecked($range), expected,
 399                         "(in assertion for: get_unchecked)",
 400                     );
 401                 }
 402             }
 403             {
 404                 let s: &mut [_] = &mut arr;
 405                 let expected: &mut [_] = &mut expected;
 406
 407                 assert_eq!(
 408                     &mut s[$range], expected,
 409                     "(in assertion for: index_mut)",
 410                 );
 411                 assert_eq!(
 412                     s.get_mut($range), Some(&mut expected[..]),
 413                     "(in assertion for: get_mut)",
 414                 );
 415                 unsafe {
 416                     assert_eq!(
 417                         s.get_unchecked_mut($range), expected,
 418                         "(in assertion for: get_unchecked_mut)",
 419                     );
 420                 }
 421             }
 422         }
 423     }
 424
 425     // Make sure the macro can actually detect bugs,
 426     // because if it can't, then what are we even doing here?
 427     //
 428     // (Be aware this only demonstrates the ability to detect bugs
 429     //  in the FIRST method that panics, as the macro is not designed
 430     //  to be used in `should_panic`)
 431     #[test]
 432     #[should_panic(expected = "out of range")]
 433     fn assert_range_eq_can_fail_by_panic() {
 434         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
 435     }
 436
 437     // (Be aware this only demonstrates the ability to detect bugs
 438     //  in the FIRST method it calls, as the macro is not designed
 439     //  to be used in `should_panic`)
 440     #[test]
 441     #[should_panic(expected = "==")]
 442     fn assert_range_eq_can_fail_by_inequality() {
 443         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
 444     }
 445
 446     // Test cases for bad index operations.
 447     //
 448     // This generates `should_panic` test cases for Index/IndexMut
 449     // and `None` test cases for get/get_mut.
 450     macro_rules! panic_cases {
 451         ($(
 452             // each test case needs a unique name to namespace the tests
 453             in mod $case_name:ident {
 454                 data: $data:expr;
 455
 456                 // optional:
 457                 //
 458                 // one or more similar inputs for which data[input] succeeds,
 459                 // and the corresponding output as an array.  This helps validate
 460                 // "critical points" where an input range straddles the boundary
 461                 // between valid and invalid.
 462                 // (such as the input `len..len`, which is just barely valid)
 463                 $(
 464                     good: data[$good:expr] == $output:expr;
 465                 )*
 466
 467                 bad: data[$bad:expr];
 468                 message: $expect_msg:expr;
 469             }
 470         )*) => {$(
 471             mod $case_name {
 472                 #[test]
 473                 fn pass() {
 474                     let mut v = $data;
 475
 476                     $( assert_range_eq!($data, $good, $output); )*
 477
 478                     {
 479                         let v: &[_] = &v;
 480                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
 481                     }
 482
 483                     {
 484                         let v: &mut [_] = &mut v;
 485                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
 486                     }
 487                 }
 488
 489                 #[test]
 490                 #[should_panic(expected = $expect_msg)]
 491                 fn index_fail() {
 492                     let v = $data;
 493                     let v: &[_] = &v;
 494                     let _v = &v[$bad];
 495                 }
 496
 497                 #[test]
 498                 #[should_panic(expected = $expect_msg)]
 499                 fn index_mut_fail() {
 500                     let mut v = $data;
 501                     let v: &mut [_] = &mut v;
 502                     let _v = &mut v[$bad];
 503                 }
 504             }
 505         )*};
 506     }
 507
 508     #[test]
 509     fn simple() {
 510         let v = [0, 1, 2, 3, 4, 5];
 511
 512         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
 513         assert_range_eq!(v, ..2, [0, 1]);
 514         assert_range_eq!(v, ..=1, [0, 1]);
 515         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
 516         assert_range_eq!(v, 1..4, [1, 2, 3]);
 517         assert_range_eq!(v, 1..=3, [1, 2, 3]);
 518     }
 519
 520     panic_cases! {
 521         in mod rangefrom_len {
 522             data: [0, 1, 2, 3, 4, 5];
 523
 524             good: data[6..] == [];
 525             bad: data[7..];
 526             message: "but ends at"; // perhaps not ideal
 527         }
 528
 529         in mod rangeto_len {
 530             data: [0, 1, 2, 3, 4, 5];
 531
 532             good: data[..6] == [0, 1, 2, 3, 4, 5];
 533             bad: data[..7];
 534             message: "out of range";
 535         }
 536
 537         in mod rangetoinclusive_len {
 538             data: [0, 1, 2, 3, 4, 5];
 539
 540             good: data[..=5] == [0, 1, 2, 3, 4, 5];
 541             bad: data[..=6];
 542             message: "out of range";
 543         }
 544
 545         in mod range_len_len {
 546             data: [0, 1, 2, 3, 4, 5];
 547
 548             good: data[6..6] == [];
 549             bad: data[7..7];
 550             message: "out of range";
 551         }
 552
 553         in mod rangeinclusive_len_len {
 554             data: [0, 1, 2, 3, 4, 5];
 555
 556             good: data[6..=5] == [];
 557             bad: data[7..=6];
 558             message: "out of range";
 559         }
 560     }
 561
 562     panic_cases! {
 563         in mod range_neg_width {
 564             data: [0, 1, 2, 3, 4, 5];
 565
 566             good: data[4..4] == [];
 567             bad: data[4..3];
 568             message: "but ends at";
 569         }
 570
 571         in mod rangeinclusive_neg_width {
 572             data: [0, 1, 2, 3, 4, 5];
 573
 574             good: data[4..=3] == [];
 575             bad: data[4..=2];
 576             message: "but ends at";
 577         }
 578     }
 579
 580     panic_cases! {
 581         in mod rangeinclusive_overflow {
 582             data: [0, 1];
 583
 584             // note: using 0 specifically ensures that the result of overflowing is 0..0,
 585             //       so that `get` doesn't simply return None for the wrong reason.
 586             bad: data[0 ..= ::std::usize::MAX];
 587             message: "maximum usize";
 588         }
 589
 590         in mod rangetoinclusive_overflow {
 591             data: [0, 1];
 592
 593             bad: data[..= ::std::usize::MAX];
 594             message: "maximum usize";
 595         }
 596     } // panic_cases!
 597 }
 598
 599 #[test]
 600 fn test_find_rfind() {
 601     let v = [0, 1, 2, 3, 4, 5];
 602     let mut iter = v.iter();
 603     let mut i = v.len();
 604     while let Some(&elt) = iter.rfind(|_| true) {
 605         i -= 1;
 606         assert_eq!(elt, v[i]);
 607     }
 608     assert_eq!(i, 0);
 609     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
 610 }
 611
 612 #[test]
 613 fn test_iter_folds() {
 614     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
 615     assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
 616     assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
 617     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
 618     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
 619     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
 620
 621     // short-circuiting try_fold, through other methods
 622     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
 623     let mut iter = a.iter();
 624     assert_eq!(iter.position(|&x| x == 3), Some(3));
 625     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
 626     assert_eq!(iter.len(), 2);
 627 }
 628
 629 #[test]
 630 fn test_rotate_left() {
 631     const N: usize = 600;
 632     let a: &mut [_] = &mut [0; N];
 633     for i in 0..N {
 634         a[i] = i;
 635     }
 636
 637     a.rotate_left(42);
 638     let k = N - 42;
 639
 640     for i in 0..N {
 641         assert_eq!(a[(i + k) % N], i);
 642     }
 643 }
 644
 645 #[test]
 646 fn test_rotate_right() {
 647     const N: usize = 600;
 648     let a: &mut [_] = &mut [0; N];
 649     for i in 0..N {
 650         a[i] = i;
 651     }
 652
 653     a.rotate_right(42);
 654
 655     for i in 0..N {
 656         assert_eq!(a[(i + 42) % N], i);
 657     }
 658 }
 659
 660 #[test]
 661 #[cfg(not(target_arch = "wasm32"))]
 662 fn sort_unstable() {
 663     use core::cmp::Ordering::{Equal, Greater, Less};
 664     use core::slice::heapsort;
 665     use rand::{Rng, XorShiftRng};
 666
 667     let mut v = [0; 600];
 668     let mut tmp = [0; 600];
 669     let mut rng = XorShiftRng::new_unseeded();
 670
 671     for len in (2..25).chain(500..510) {
 672         let v = &mut v[0..len];
 673         let tmp = &mut tmp[0..len];
 674
 675         for &modulus in &[5, 10, 100, 1000] {
 676             for _ in 0..100 {
 677                 for i in 0..len {
 678                     v[i] = rng.gen::<i32>() % modulus;
 679                 }
 680
 681                 // Sort in default order.
 682                 tmp.copy_from_slice(v);
 683                 tmp.sort_unstable();
 684                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 685
 686                 // Sort in ascending order.
 687                 tmp.copy_from_slice(v);
 688                 tmp.sort_unstable_by(|a, b| a.cmp(b));
 689                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 690
 691                 // Sort in descending order.
 692                 tmp.copy_from_slice(v);
 693                 tmp.sort_unstable_by(|a, b| b.cmp(a));
 694                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 695
 696                 // Test heapsort using `<` operator.
 697                 tmp.copy_from_slice(v);
 698                 heapsort(tmp, |a, b| a < b);
 699                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 700
 701                 // Test heapsort using `>` operator.
 702                 tmp.copy_from_slice(v);
 703                 heapsort(tmp, |a, b| a > b);
 704                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 705             }
 706         }
 707     }
 708
 709     // Sort using a completely random comparison function.
 710     // This will reorder the elements *somehow*, but won't panic.
 711     for i in 0..v.len() {
 712         v[i] = i as i32;
 713     }
 714     v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
 715     v.sort_unstable();
 716     for i in 0..v.len() {
 717         assert_eq!(v[i], i as i32);
 718     }
 719
 720     // Should not panic.
 721     [0i32; 0].sort_unstable();
 722     [(); 10].sort_unstable();
 723     [(); 100].sort_unstable();
 724
 725     let mut v = [0xDEADBEEFu64];
 726     v.sort_unstable();
 727     assert!(v == [0xDEADBEEF]);
 728 }
 729
 730 pub mod memchr {
 731     use core::slice::memchr::{memchr, memrchr};
 732
 733     // test fallback implementations on all platforms
 734     #[test]
 735     fn matches_one() {
 736         assert_eq!(Some(0), memchr(b'a', b"a"));
 737     }
 738
 739     #[test]
 740     fn matches_begin() {
 741         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
 742     }
 743
 744     #[test]
 745     fn matches_end() {
 746         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
 747     }
 748
 749     #[test]
 750     fn matches_nul() {
 751         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
 752     }
 753
 754     #[test]
 755     fn matches_past_nul() {
 756         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
 757     }
 758
 759     #[test]
 760     fn no_match_empty() {
 761         assert_eq!(None, memchr(b'a', b""));
 762     }
 763
 764     #[test]
 765     fn no_match() {
 766         assert_eq!(None, memchr(b'a', b"xyz"));
 767     }
 768
 769     #[test]
 770     fn matches_one_reversed() {
 771         assert_eq!(Some(0), memrchr(b'a', b"a"));
 772     }
 773
 774     #[test]
 775     fn matches_begin_reversed() {
 776         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
 777     }
 778
 779     #[test]
 780     fn matches_end_reversed() {
 781         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
 782     }
 783
 784     #[test]
 785     fn matches_nul_reversed() {
 786         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
 787     }
 788
 789     #[test]
 790     fn matches_past_nul_reversed() {
 791         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
 792     }
 793
 794     #[test]
 795     fn no_match_empty_reversed() {
 796         assert_eq!(None, memrchr(b'a', b""));
 797     }
 798
 799     #[test]
 800     fn no_match_reversed() {
 801         assert_eq!(None, memrchr(b'a', b"xyz"));
 802     }
 803
 804     #[test]
 805     fn each_alignment_reversed() {
 806         let mut data = [1u8; 64];
 807         let needle = 2;
 808         let pos = 40;
 809         data[pos] = needle;
 810         for start in 0..16 {
 811             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
 812         }
 813     }
 814 }
 815
 816 #[test]
 817 fn test_align_to_simple() {
 818     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
 819     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
 820     assert_eq!(aligned.len(), 3);
 821     assert!(prefix == [1] || suffix == [7]);
 822     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
 823     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
 824     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
 825     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
 826     assert!(aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
 827             "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
 828             aligned, expect1, expect2, expect3, expect4);
 829 }
 830
 831 #[test]
 832 fn test_align_to_zst() {
 833     let bytes = [1, 2, 3, 4, 5, 6, 7];
 834     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
 835     assert_eq!(aligned.len(), 0);
 836     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
 837 }
 838
 839 #[test]
 840 fn test_align_to_non_trivial() {
 841     #[repr(align(8))] struct U64(u64, u64);
 842     #[repr(align(8))] struct U64U64U32(u64, u64, u32);
 843     let data = [U64(1, 2), U64(3, 4), U64(5, 6), U64(7, 8), U64(9, 10), U64(11, 12), U64(13, 14),
 844                 U64(15, 16)];
 845     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
 846     assert_eq!(aligned.len(), 4);
 847     assert_eq!(prefix.len() + suffix.len(), 2);
 848 }