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_remainder() {
 264     let v: &[i32] = &[0, 1, 2, 3, 4];
 265     let c = v.exact_chunks(2);
 266     assert_eq!(c.remainder(), &[4]);
 267 }
 268
 269 #[test]
 270 fn test_exact_chunks_zip() {
 271     let v1: &[i32] = &[0, 1, 2, 3, 4];
 272     let v2: &[i32] = &[6, 7, 8, 9, 10];
 273
 274     let res = v1.exact_chunks(2)
 275         .zip(v2.exact_chunks(2))
 276         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 277         .collect::<Vec<_>>();
 278     assert_eq!(res, vec![14, 22]);
 279 }
 280
 281 #[test]
 282 fn test_exact_chunks_mut_count() {
 283     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 284     let c = v.exact_chunks_mut(3);
 285     assert_eq!(c.count(), 2);
 286
 287     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 288     let c2 = v2.exact_chunks_mut(2);
 289     assert_eq!(c2.count(), 2);
 290
 291     let v3: &mut [i32] = &mut [];
 292     let c3 = v3.exact_chunks_mut(2);
 293     assert_eq!(c3.count(), 0);
 294 }
 295
 296 #[test]
 297 fn test_exact_chunks_mut_nth() {
 298     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 299     let mut c = v.exact_chunks_mut(2);
 300     assert_eq!(c.nth(1).unwrap(), &[2, 3]);
 301     assert_eq!(c.next().unwrap(), &[4, 5]);
 302
 303     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4, 5, 6];
 304     let mut c2 = v2.exact_chunks_mut(3);
 305     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 306     assert_eq!(c2.next(), None);
 307 }
 308
 309 #[test]
 310 fn test_exact_chunks_mut_last() {
 311     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 312     let c = v.exact_chunks_mut(2);
 313     assert_eq!(c.last().unwrap(), &[4, 5]);
 314
 315     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 316     let c2 = v2.exact_chunks_mut(2);
 317     assert_eq!(c2.last().unwrap(), &[2, 3]);
 318 }
 319
 320 #[test]
 321 fn test_exact_chunks_mut_remainder() {
 322     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 323     let c = v.exact_chunks_mut(2);
 324     assert_eq!(c.into_remainder(), &[4]);
 325 }
 326
 327 #[test]
 328 fn test_exact_chunks_mut_zip() {
 329     let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
 330     let v2: &[i32] = &[6, 7, 8, 9, 10];
 331
 332     for (a, b) in v1.exact_chunks_mut(2).zip(v2.exact_chunks(2)) {
 333         let sum = b.iter().sum::<i32>();
 334         for v in a {
 335             *v += sum;
 336         }
 337     }
 338     assert_eq!(v1, [13, 14, 19, 20, 4]);
 339 }
 340
 341 #[test]
 342 fn test_windows_count() {
 343     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 344     let c = v.windows(3);
 345     assert_eq!(c.count(), 4);
 346
 347     let v2: &[i32] = &[0, 1, 2, 3, 4];
 348     let c2 = v2.windows(6);
 349     assert_eq!(c2.count(), 0);
 350
 351     let v3: &[i32] = &[];
 352     let c3 = v3.windows(2);
 353     assert_eq!(c3.count(), 0);
 354 }
 355
 356 #[test]
 357 fn test_windows_nth() {
 358     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 359     let mut c = v.windows(2);
 360     assert_eq!(c.nth(2).unwrap()[1], 3);
 361     assert_eq!(c.next().unwrap()[0], 3);
 362
 363     let v2: &[i32] = &[0, 1, 2, 3, 4];
 364     let mut c2 = v2.windows(4);
 365     assert_eq!(c2.nth(1).unwrap()[1], 2);
 366     assert_eq!(c2.next(), None);
 367 }
 368
 369 #[test]
 370 fn test_windows_last() {
 371     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 372     let c = v.windows(2);
 373     assert_eq!(c.last().unwrap()[1], 5);
 374
 375     let v2: &[i32] = &[0, 1, 2, 3, 4];
 376     let c2 = v2.windows(2);
 377     assert_eq!(c2.last().unwrap()[0], 3);
 378 }
 379
 380 #[test]
 381 fn test_windows_zip() {
 382     let v1: &[i32] = &[0, 1, 2, 3, 4];
 383     let v2: &[i32] = &[6, 7, 8, 9, 10];
 384
 385     let res = v1.windows(2)
 386         .zip(v2.windows(2))
 387         .map(|(a, b)| a.iter().sum::<i32>() + b.iter().sum::<i32>())
 388         .collect::<Vec<_>>();
 389
 390     assert_eq!(res, [14, 18, 22, 26]);
 391 }
 392
 393 // The current implementation of SliceIndex fails to handle methods
 394 // orthogonally from range types; therefore, it is worth testing
 395 // all of the indexing operations on each input.
 396 mod slice_index {
 397     // This checks all six indexing methods, given an input range that
 398     // should succeed. (it is NOT suitable for testing invalid inputs)
 399     macro_rules! assert_range_eq {
 400         ($arr:expr, $range:expr, $expected:expr)
 401         => {
 402             let mut arr = $arr;
 403             let mut expected = $expected;
 404             {
 405                 let s: &[_] = &arr;
 406                 let expected: &[_] = &expected;
 407
 408                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
 409                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
 410                 unsafe {
 411                     assert_eq!(
 412                         s.get_unchecked($range), expected,
 413                         "(in assertion for: get_unchecked)",
 414                     );
 415                 }
 416             }
 417             {
 418                 let s: &mut [_] = &mut arr;
 419                 let expected: &mut [_] = &mut expected;
 420
 421                 assert_eq!(
 422                     &mut s[$range], expected,
 423                     "(in assertion for: index_mut)",
 424                 );
 425                 assert_eq!(
 426                     s.get_mut($range), Some(&mut expected[..]),
 427                     "(in assertion for: get_mut)",
 428                 );
 429                 unsafe {
 430                     assert_eq!(
 431                         s.get_unchecked_mut($range), expected,
 432                         "(in assertion for: get_unchecked_mut)",
 433                     );
 434                 }
 435             }
 436         }
 437     }
 438
 439     // Make sure the macro can actually detect bugs,
 440     // because if it can't, then what are we even doing here?
 441     //
 442     // (Be aware this only demonstrates the ability to detect bugs
 443     //  in the FIRST method that panics, as the macro is not designed
 444     //  to be used in `should_panic`)
 445     #[test]
 446     #[should_panic(expected = "out of range")]
 447     fn assert_range_eq_can_fail_by_panic() {
 448         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
 449     }
 450
 451     // (Be aware this only demonstrates the ability to detect bugs
 452     //  in the FIRST method it calls, as the macro is not designed
 453     //  to be used in `should_panic`)
 454     #[test]
 455     #[should_panic(expected = "==")]
 456     fn assert_range_eq_can_fail_by_inequality() {
 457         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
 458     }
 459
 460     // Test cases for bad index operations.
 461     //
 462     // This generates `should_panic` test cases for Index/IndexMut
 463     // and `None` test cases for get/get_mut.
 464     macro_rules! panic_cases {
 465         ($(
 466             // each test case needs a unique name to namespace the tests
 467             in mod $case_name:ident {
 468                 data: $data:expr;
 469
 470                 // optional:
 471                 //
 472                 // one or more similar inputs for which data[input] succeeds,
 473                 // and the corresponding output as an array.  This helps validate
 474                 // "critical points" where an input range straddles the boundary
 475                 // between valid and invalid.
 476                 // (such as the input `len..len`, which is just barely valid)
 477                 $(
 478                     good: data[$good:expr] == $output:expr;
 479                 )*
 480
 481                 bad: data[$bad:expr];
 482                 message: $expect_msg:expr;
 483             }
 484         )*) => {$(
 485             mod $case_name {
 486                 #[test]
 487                 fn pass() {
 488                     let mut v = $data;
 489
 490                     $( assert_range_eq!($data, $good, $output); )*
 491
 492                     {
 493                         let v: &[_] = &v;
 494                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
 495                     }
 496
 497                     {
 498                         let v: &mut [_] = &mut v;
 499                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
 500                     }
 501                 }
 502
 503                 #[test]
 504                 #[should_panic(expected = $expect_msg)]
 505                 fn index_fail() {
 506                     let v = $data;
 507                     let v: &[_] = &v;
 508                     let _v = &v[$bad];
 509                 }
 510
 511                 #[test]
 512                 #[should_panic(expected = $expect_msg)]
 513                 fn index_mut_fail() {
 514                     let mut v = $data;
 515                     let v: &mut [_] = &mut v;
 516                     let _v = &mut v[$bad];
 517                 }
 518             }
 519         )*};
 520     }
 521
 522     #[test]
 523     fn simple() {
 524         let v = [0, 1, 2, 3, 4, 5];
 525
 526         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
 527         assert_range_eq!(v, ..2, [0, 1]);
 528         assert_range_eq!(v, ..=1, [0, 1]);
 529         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
 530         assert_range_eq!(v, 1..4, [1, 2, 3]);
 531         assert_range_eq!(v, 1..=3, [1, 2, 3]);
 532     }
 533
 534     panic_cases! {
 535         in mod rangefrom_len {
 536             data: [0, 1, 2, 3, 4, 5];
 537
 538             good: data[6..] == [];
 539             bad: data[7..];
 540             message: "but ends at"; // perhaps not ideal
 541         }
 542
 543         in mod rangeto_len {
 544             data: [0, 1, 2, 3, 4, 5];
 545
 546             good: data[..6] == [0, 1, 2, 3, 4, 5];
 547             bad: data[..7];
 548             message: "out of range";
 549         }
 550
 551         in mod rangetoinclusive_len {
 552             data: [0, 1, 2, 3, 4, 5];
 553
 554             good: data[..=5] == [0, 1, 2, 3, 4, 5];
 555             bad: data[..=6];
 556             message: "out of range";
 557         }
 558
 559         in mod range_len_len {
 560             data: [0, 1, 2, 3, 4, 5];
 561
 562             good: data[6..6] == [];
 563             bad: data[7..7];
 564             message: "out of range";
 565         }
 566
 567         in mod rangeinclusive_len_len {
 568             data: [0, 1, 2, 3, 4, 5];
 569
 570             good: data[6..=5] == [];
 571             bad: data[7..=6];
 572             message: "out of range";
 573         }
 574     }
 575
 576     panic_cases! {
 577         in mod range_neg_width {
 578             data: [0, 1, 2, 3, 4, 5];
 579
 580             good: data[4..4] == [];
 581             bad: data[4..3];
 582             message: "but ends at";
 583         }
 584
 585         in mod rangeinclusive_neg_width {
 586             data: [0, 1, 2, 3, 4, 5];
 587
 588             good: data[4..=3] == [];
 589             bad: data[4..=2];
 590             message: "but ends at";
 591         }
 592     }
 593
 594     panic_cases! {
 595         in mod rangeinclusive_overflow {
 596             data: [0, 1];
 597
 598             // note: using 0 specifically ensures that the result of overflowing is 0..0,
 599             //       so that `get` doesn't simply return None for the wrong reason.
 600             bad: data[0 ..= ::std::usize::MAX];
 601             message: "maximum usize";
 602         }
 603
 604         in mod rangetoinclusive_overflow {
 605             data: [0, 1];
 606
 607             bad: data[..= ::std::usize::MAX];
 608             message: "maximum usize";
 609         }
 610     } // panic_cases!
 611 }
 612
 613 #[test]
 614 fn test_find_rfind() {
 615     let v = [0, 1, 2, 3, 4, 5];
 616     let mut iter = v.iter();
 617     let mut i = v.len();
 618     while let Some(&elt) = iter.rfind(|_| true) {
 619         i -= 1;
 620         assert_eq!(elt, v[i]);
 621     }
 622     assert_eq!(i, 0);
 623     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
 624 }
 625
 626 #[test]
 627 fn test_iter_folds() {
 628     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
 629     assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
 630     assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
 631     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
 632     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
 633     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
 634
 635     // short-circuiting try_fold, through other methods
 636     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
 637     let mut iter = a.iter();
 638     assert_eq!(iter.position(|&x| x == 3), Some(3));
 639     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
 640     assert_eq!(iter.len(), 2);
 641 }
 642
 643 #[test]
 644 fn test_rotate_left() {
 645     const N: usize = 600;
 646     let a: &mut [_] = &mut [0; N];
 647     for i in 0..N {
 648         a[i] = i;
 649     }
 650
 651     a.rotate_left(42);
 652     let k = N - 42;
 653
 654     for i in 0..N {
 655         assert_eq!(a[(i + k) % N], i);
 656     }
 657 }
 658
 659 #[test]
 660 fn test_rotate_right() {
 661     const N: usize = 600;
 662     let a: &mut [_] = &mut [0; N];
 663     for i in 0..N {
 664         a[i] = i;
 665     }
 666
 667     a.rotate_right(42);
 668
 669     for i in 0..N {
 670         assert_eq!(a[(i + 42) % N], i);
 671     }
 672 }
 673
 674 #[test]
 675 #[cfg(not(target_arch = "wasm32"))]
 676 fn sort_unstable() {
 677     use core::cmp::Ordering::{Equal, Greater, Less};
 678     use core::slice::heapsort;
 679     use rand::{Rng, XorShiftRng};
 680
 681     let mut v = [0; 600];
 682     let mut tmp = [0; 600];
 683     let mut rng = XorShiftRng::new_unseeded();
 684
 685     for len in (2..25).chain(500..510) {
 686         let v = &mut v[0..len];
 687         let tmp = &mut tmp[0..len];
 688
 689         for &modulus in &[5, 10, 100, 1000] {
 690             for _ in 0..100 {
 691                 for i in 0..len {
 692                     v[i] = rng.gen::<i32>() % modulus;
 693                 }
 694
 695                 // Sort in default order.
 696                 tmp.copy_from_slice(v);
 697                 tmp.sort_unstable();
 698                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 699
 700                 // Sort in ascending order.
 701                 tmp.copy_from_slice(v);
 702                 tmp.sort_unstable_by(|a, b| a.cmp(b));
 703                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 704
 705                 // Sort in descending order.
 706                 tmp.copy_from_slice(v);
 707                 tmp.sort_unstable_by(|a, b| b.cmp(a));
 708                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 709
 710                 // Test heapsort using `<` operator.
 711                 tmp.copy_from_slice(v);
 712                 heapsort(tmp, |a, b| a < b);
 713                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 714
 715                 // Test heapsort using `>` operator.
 716                 tmp.copy_from_slice(v);
 717                 heapsort(tmp, |a, b| a > b);
 718                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 719             }
 720         }
 721     }
 722
 723     // Sort using a completely random comparison function.
 724     // This will reorder the elements *somehow*, but won't panic.
 725     for i in 0..v.len() {
 726         v[i] = i as i32;
 727     }
 728     v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
 729     v.sort_unstable();
 730     for i in 0..v.len() {
 731         assert_eq!(v[i], i as i32);
 732     }
 733
 734     // Should not panic.
 735     [0i32; 0].sort_unstable();
 736     [(); 10].sort_unstable();
 737     [(); 100].sort_unstable();
 738
 739     let mut v = [0xDEADBEEFu64];
 740     v.sort_unstable();
 741     assert!(v == [0xDEADBEEF]);
 742 }
 743
 744 pub mod memchr {
 745     use core::slice::memchr::{memchr, memrchr};
 746
 747     // test fallback implementations on all platforms
 748     #[test]
 749     fn matches_one() {
 750         assert_eq!(Some(0), memchr(b'a', b"a"));
 751     }
 752
 753     #[test]
 754     fn matches_begin() {
 755         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
 756     }
 757
 758     #[test]
 759     fn matches_end() {
 760         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
 761     }
 762
 763     #[test]
 764     fn matches_nul() {
 765         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
 766     }
 767
 768     #[test]
 769     fn matches_past_nul() {
 770         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
 771     }
 772
 773     #[test]
 774     fn no_match_empty() {
 775         assert_eq!(None, memchr(b'a', b""));
 776     }
 777
 778     #[test]
 779     fn no_match() {
 780         assert_eq!(None, memchr(b'a', b"xyz"));
 781     }
 782
 783     #[test]
 784     fn matches_one_reversed() {
 785         assert_eq!(Some(0), memrchr(b'a', b"a"));
 786     }
 787
 788     #[test]
 789     fn matches_begin_reversed() {
 790         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
 791     }
 792
 793     #[test]
 794     fn matches_end_reversed() {
 795         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
 796     }
 797
 798     #[test]
 799     fn matches_nul_reversed() {
 800         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
 801     }
 802
 803     #[test]
 804     fn matches_past_nul_reversed() {
 805         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
 806     }
 807
 808     #[test]
 809     fn no_match_empty_reversed() {
 810         assert_eq!(None, memrchr(b'a', b""));
 811     }
 812
 813     #[test]
 814     fn no_match_reversed() {
 815         assert_eq!(None, memrchr(b'a', b"xyz"));
 816     }
 817
 818     #[test]
 819     fn each_alignment_reversed() {
 820         let mut data = [1u8; 64];
 821         let needle = 2;
 822         let pos = 40;
 823         data[pos] = needle;
 824         for start in 0..16 {
 825             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
 826         }
 827     }
 828 }
 829
 830 #[test]
 831 fn test_align_to_simple() {
 832     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
 833     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
 834     assert_eq!(aligned.len(), 3);
 835     assert!(prefix == [1] || suffix == [7]);
 836     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
 837     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
 838     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
 839     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
 840     assert!(aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
 841             "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
 842             aligned, expect1, expect2, expect3, expect4);
 843 }
 844
 845 #[test]
 846 fn test_align_to_zst() {
 847     let bytes = [1, 2, 3, 4, 5, 6, 7];
 848     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
 849     assert_eq!(aligned.len(), 0);
 850     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
 851 }
 852
 853 #[test]
 854 fn test_align_to_non_trivial() {
 855     #[repr(align(8))] struct U64(u64, u64);
 856     #[repr(align(8))] struct U64U64U32(u64, u64, u32);
 857     let data = [U64(1, 2), U64(3, 4), U64(5, 6), U64(7, 8), U64(9, 10), U64(11, 12), U64(13, 14),
 858                 U64(15, 16)];
 859     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
 860     assert_eq!(aligned.len(), 4);
 861     assert_eq!(prefix.len() + suffix.len(), 2);
 862 }