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 #[test]
 394 #[allow(const_err)]
 395 fn test_iter_ref_consistency() {
 396     use std::fmt::Debug;
 397
 398     fn helper<T : Copy + Debug + PartialEq>(x : T) {
 399         let v : &[T] = &[x, x, x];
 400         let v_ptrs : [*const T; 3] = match v {
 401             [ref v1, ref v2, ref v3] => [v1 as *const _, v2 as *const _, v3 as *const _],
 402             _ => unreachable!()
 403         };
 404         let len = v.len();
 405
 406         for i in 0..len {
 407             assert_eq!(&v[i] as *const _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 408             let nth = v.iter().nth(i).unwrap();
 409             assert_eq!(nth as *const _, v_ptrs[i]);
 410         }
 411         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 412
 413         {
 414             let mut it = v.iter();
 415             for i in 0..len{
 416                 let remaining = len - i;
 417                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 418
 419                 let next = it.next().unwrap();
 420                 assert_eq!(next as *const _, v_ptrs[i]);
 421             }
 422             assert_eq!(it.size_hint(), (0, Some(0)));
 423             assert_eq!(it.next(), None, "The final call to next() should return None");
 424         }
 425
 426         {
 427             let mut it = v.iter();
 428             for i in 0..len{
 429                 let remaining = len - i;
 430                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 431
 432                 let prev = it.next_back().unwrap();
 433                 assert_eq!(prev as *const _, v_ptrs[remaining-1]);
 434             }
 435             assert_eq!(it.size_hint(), (0, Some(0)));
 436             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 437         }
 438     }
 439
 440     fn helper_mut<T : Copy + Debug + PartialEq>(x : T) {
 441         let v : &mut [T] = &mut [x, x, x];
 442         let v_ptrs : [*mut T; 3] = match v {
 443             [ref v1, ref v2, ref v3] =>
 444               [v1 as *const _ as *mut _, v2 as *const _ as *mut _, v3 as *const _ as *mut _],
 445             _ => unreachable!()
 446         };
 447         let len = v.len();
 448
 449         for i in 0..len {
 450             assert_eq!(&mut v[i] as *mut _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 451             let nth = v.iter_mut().nth(i).unwrap();
 452             assert_eq!(nth as *mut _, v_ptrs[i]);
 453         }
 454         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 455
 456         {
 457             let mut it = v.iter_mut();
 458             for i in 0..len {
 459                 let remaining = len - i;
 460                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 461
 462                 let next = it.next().unwrap();
 463                 assert_eq!(next as *mut _, v_ptrs[i]);
 464             }
 465             assert_eq!(it.size_hint(), (0, Some(0)));
 466             assert_eq!(it.next(), None, "The final call to next() should return None");
 467         }
 468
 469         {
 470             let mut it = v.iter_mut();
 471             for i in 0..len{
 472                 let remaining = len - i;
 473                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 474
 475                 let prev = it.next_back().unwrap();
 476                 assert_eq!(prev as *mut _, v_ptrs[remaining-1]);
 477             }
 478             assert_eq!(it.size_hint(), (0, Some(0)));
 479             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 480         }
 481     }
 482
 483     // Make sure iterators and slice patterns yield consistent addresses for various types,
 484     // including ZSTs.
 485     helper(0u32);
 486     helper(());
 487     helper([0u32; 0]); // ZST with alignment > 0
 488     helper_mut(0u32);
 489     helper_mut(());
 490     helper_mut([0u32; 0]); // ZST with alignment > 0
 491 }
 492
 493 // The current implementation of SliceIndex fails to handle methods
 494 // orthogonally from range types; therefore, it is worth testing
 495 // all of the indexing operations on each input.
 496 mod slice_index {
 497     // This checks all six indexing methods, given an input range that
 498     // should succeed. (it is NOT suitable for testing invalid inputs)
 499     macro_rules! assert_range_eq {
 500         ($arr:expr, $range:expr, $expected:expr)
 501         => {
 502             let mut arr = $arr;
 503             let mut expected = $expected;
 504             {
 505                 let s: &[_] = &arr;
 506                 let expected: &[_] = &expected;
 507
 508                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
 509                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
 510                 unsafe {
 511                     assert_eq!(
 512                         s.get_unchecked($range), expected,
 513                         "(in assertion for: get_unchecked)",
 514                     );
 515                 }
 516             }
 517             {
 518                 let s: &mut [_] = &mut arr;
 519                 let expected: &mut [_] = &mut expected;
 520
 521                 assert_eq!(
 522                     &mut s[$range], expected,
 523                     "(in assertion for: index_mut)",
 524                 );
 525                 assert_eq!(
 526                     s.get_mut($range), Some(&mut expected[..]),
 527                     "(in assertion for: get_mut)",
 528                 );
 529                 unsafe {
 530                     assert_eq!(
 531                         s.get_unchecked_mut($range), expected,
 532                         "(in assertion for: get_unchecked_mut)",
 533                     );
 534                 }
 535             }
 536         }
 537     }
 538
 539     // Make sure the macro can actually detect bugs,
 540     // because if it can't, then what are we even doing here?
 541     //
 542     // (Be aware this only demonstrates the ability to detect bugs
 543     //  in the FIRST method that panics, as the macro is not designed
 544     //  to be used in `should_panic`)
 545     #[test]
 546     #[should_panic(expected = "out of range")]
 547     fn assert_range_eq_can_fail_by_panic() {
 548         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
 549     }
 550
 551     // (Be aware this only demonstrates the ability to detect bugs
 552     //  in the FIRST method it calls, as the macro is not designed
 553     //  to be used in `should_panic`)
 554     #[test]
 555     #[should_panic(expected = "==")]
 556     fn assert_range_eq_can_fail_by_inequality() {
 557         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
 558     }
 559
 560     // Test cases for bad index operations.
 561     //
 562     // This generates `should_panic` test cases for Index/IndexMut
 563     // and `None` test cases for get/get_mut.
 564     macro_rules! panic_cases {
 565         ($(
 566             // each test case needs a unique name to namespace the tests
 567             in mod $case_name:ident {
 568                 data: $data:expr;
 569
 570                 // optional:
 571                 //
 572                 // one or more similar inputs for which data[input] succeeds,
 573                 // and the corresponding output as an array.  This helps validate
 574                 // "critical points" where an input range straddles the boundary
 575                 // between valid and invalid.
 576                 // (such as the input `len..len`, which is just barely valid)
 577                 $(
 578                     good: data[$good:expr] == $output:expr;
 579                 )*
 580
 581                 bad: data[$bad:expr];
 582                 message: $expect_msg:expr;
 583             }
 584         )*) => {$(
 585             mod $case_name {
 586                 #[test]
 587                 fn pass() {
 588                     let mut v = $data;
 589
 590                     $( assert_range_eq!($data, $good, $output); )*
 591
 592                     {
 593                         let v: &[_] = &v;
 594                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
 595                     }
 596
 597                     {
 598                         let v: &mut [_] = &mut v;
 599                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
 600                     }
 601                 }
 602
 603                 #[test]
 604                 #[should_panic(expected = $expect_msg)]
 605                 fn index_fail() {
 606                     let v = $data;
 607                     let v: &[_] = &v;
 608                     let _v = &v[$bad];
 609                 }
 610
 611                 #[test]
 612                 #[should_panic(expected = $expect_msg)]
 613                 fn index_mut_fail() {
 614                     let mut v = $data;
 615                     let v: &mut [_] = &mut v;
 616                     let _v = &mut v[$bad];
 617                 }
 618             }
 619         )*};
 620     }
 621
 622     #[test]
 623     fn simple() {
 624         let v = [0, 1, 2, 3, 4, 5];
 625
 626         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
 627         assert_range_eq!(v, ..2, [0, 1]);
 628         assert_range_eq!(v, ..=1, [0, 1]);
 629         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
 630         assert_range_eq!(v, 1..4, [1, 2, 3]);
 631         assert_range_eq!(v, 1..=3, [1, 2, 3]);
 632     }
 633
 634     panic_cases! {
 635         in mod rangefrom_len {
 636             data: [0, 1, 2, 3, 4, 5];
 637
 638             good: data[6..] == [];
 639             bad: data[7..];
 640             message: "but ends at"; // perhaps not ideal
 641         }
 642
 643         in mod rangeto_len {
 644             data: [0, 1, 2, 3, 4, 5];
 645
 646             good: data[..6] == [0, 1, 2, 3, 4, 5];
 647             bad: data[..7];
 648             message: "out of range";
 649         }
 650
 651         in mod rangetoinclusive_len {
 652             data: [0, 1, 2, 3, 4, 5];
 653
 654             good: data[..=5] == [0, 1, 2, 3, 4, 5];
 655             bad: data[..=6];
 656             message: "out of range";
 657         }
 658
 659         in mod range_len_len {
 660             data: [0, 1, 2, 3, 4, 5];
 661
 662             good: data[6..6] == [];
 663             bad: data[7..7];
 664             message: "out of range";
 665         }
 666
 667         in mod rangeinclusive_len_len {
 668             data: [0, 1, 2, 3, 4, 5];
 669
 670             good: data[6..=5] == [];
 671             bad: data[7..=6];
 672             message: "out of range";
 673         }
 674     }
 675
 676     panic_cases! {
 677         in mod range_neg_width {
 678             data: [0, 1, 2, 3, 4, 5];
 679
 680             good: data[4..4] == [];
 681             bad: data[4..3];
 682             message: "but ends at";
 683         }
 684
 685         in mod rangeinclusive_neg_width {
 686             data: [0, 1, 2, 3, 4, 5];
 687
 688             good: data[4..=3] == [];
 689             bad: data[4..=2];
 690             message: "but ends at";
 691         }
 692     }
 693
 694     panic_cases! {
 695         in mod rangeinclusive_overflow {
 696             data: [0, 1];
 697
 698             // note: using 0 specifically ensures that the result of overflowing is 0..0,
 699             //       so that `get` doesn't simply return None for the wrong reason.
 700             bad: data[0 ..= ::std::usize::MAX];
 701             message: "maximum usize";
 702         }
 703
 704         in mod rangetoinclusive_overflow {
 705             data: [0, 1];
 706
 707             bad: data[..= ::std::usize::MAX];
 708             message: "maximum usize";
 709         }
 710     } // panic_cases!
 711 }
 712
 713 #[test]
 714 fn test_find_rfind() {
 715     let v = [0, 1, 2, 3, 4, 5];
 716     let mut iter = v.iter();
 717     let mut i = v.len();
 718     while let Some(&elt) = iter.rfind(|_| true) {
 719         i -= 1;
 720         assert_eq!(elt, v[i]);
 721     }
 722     assert_eq!(i, 0);
 723     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
 724 }
 725
 726 #[test]
 727 fn test_iter_folds() {
 728     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
 729     assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
 730     assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
 731     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
 732     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
 733     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
 734
 735     // short-circuiting try_fold, through other methods
 736     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
 737     let mut iter = a.iter();
 738     assert_eq!(iter.position(|&x| x == 3), Some(3));
 739     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
 740     assert_eq!(iter.len(), 2);
 741 }
 742
 743 #[test]
 744 fn test_rotate_left() {
 745     const N: usize = 600;
 746     let a: &mut [_] = &mut [0; N];
 747     for i in 0..N {
 748         a[i] = i;
 749     }
 750
 751     a.rotate_left(42);
 752     let k = N - 42;
 753
 754     for i in 0..N {
 755         assert_eq!(a[(i + k) % N], i);
 756     }
 757 }
 758
 759 #[test]
 760 fn test_rotate_right() {
 761     const N: usize = 600;
 762     let a: &mut [_] = &mut [0; N];
 763     for i in 0..N {
 764         a[i] = i;
 765     }
 766
 767     a.rotate_right(42);
 768
 769     for i in 0..N {
 770         assert_eq!(a[(i + 42) % N], i);
 771     }
 772 }
 773
 774 #[test]
 775 #[cfg(not(target_arch = "wasm32"))]
 776 fn sort_unstable() {
 777     use core::cmp::Ordering::{Equal, Greater, Less};
 778     use core::slice::heapsort;
 779     use rand::{Rng, XorShiftRng};
 780
 781     let mut v = [0; 600];
 782     let mut tmp = [0; 600];
 783     let mut rng = XorShiftRng::new_unseeded();
 784
 785     for len in (2..25).chain(500..510) {
 786         let v = &mut v[0..len];
 787         let tmp = &mut tmp[0..len];
 788
 789         for &modulus in &[5, 10, 100, 1000] {
 790             for _ in 0..100 {
 791                 for i in 0..len {
 792                     v[i] = rng.gen::<i32>() % modulus;
 793                 }
 794
 795                 // Sort in default order.
 796                 tmp.copy_from_slice(v);
 797                 tmp.sort_unstable();
 798                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 799
 800                 // Sort in ascending order.
 801                 tmp.copy_from_slice(v);
 802                 tmp.sort_unstable_by(|a, b| a.cmp(b));
 803                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 804
 805                 // Sort in descending order.
 806                 tmp.copy_from_slice(v);
 807                 tmp.sort_unstable_by(|a, b| b.cmp(a));
 808                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 809
 810                 // Test heapsort using `<` operator.
 811                 tmp.copy_from_slice(v);
 812                 heapsort(tmp, |a, b| a < b);
 813                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 814
 815                 // Test heapsort using `>` operator.
 816                 tmp.copy_from_slice(v);
 817                 heapsort(tmp, |a, b| a > b);
 818                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 819             }
 820         }
 821     }
 822
 823     // Sort using a completely random comparison function.
 824     // This will reorder the elements *somehow*, but won't panic.
 825     for i in 0..v.len() {
 826         v[i] = i as i32;
 827     }
 828     v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
 829     v.sort_unstable();
 830     for i in 0..v.len() {
 831         assert_eq!(v[i], i as i32);
 832     }
 833
 834     // Should not panic.
 835     [0i32; 0].sort_unstable();
 836     [(); 10].sort_unstable();
 837     [(); 100].sort_unstable();
 838
 839     let mut v = [0xDEADBEEFu64];
 840     v.sort_unstable();
 841     assert!(v == [0xDEADBEEF]);
 842 }
 843
 844 pub mod memchr {
 845     use core::slice::memchr::{memchr, memrchr};
 846
 847     // test fallback implementations on all platforms
 848     #[test]
 849     fn matches_one() {
 850         assert_eq!(Some(0), memchr(b'a', b"a"));
 851     }
 852
 853     #[test]
 854     fn matches_begin() {
 855         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
 856     }
 857
 858     #[test]
 859     fn matches_end() {
 860         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
 861     }
 862
 863     #[test]
 864     fn matches_nul() {
 865         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
 866     }
 867
 868     #[test]
 869     fn matches_past_nul() {
 870         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
 871     }
 872
 873     #[test]
 874     fn no_match_empty() {
 875         assert_eq!(None, memchr(b'a', b""));
 876     }
 877
 878     #[test]
 879     fn no_match() {
 880         assert_eq!(None, memchr(b'a', b"xyz"));
 881     }
 882
 883     #[test]
 884     fn matches_one_reversed() {
 885         assert_eq!(Some(0), memrchr(b'a', b"a"));
 886     }
 887
 888     #[test]
 889     fn matches_begin_reversed() {
 890         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
 891     }
 892
 893     #[test]
 894     fn matches_end_reversed() {
 895         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
 896     }
 897
 898     #[test]
 899     fn matches_nul_reversed() {
 900         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
 901     }
 902
 903     #[test]
 904     fn matches_past_nul_reversed() {
 905         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
 906     }
 907
 908     #[test]
 909     fn no_match_empty_reversed() {
 910         assert_eq!(None, memrchr(b'a', b""));
 911     }
 912
 913     #[test]
 914     fn no_match_reversed() {
 915         assert_eq!(None, memrchr(b'a', b"xyz"));
 916     }
 917
 918     #[test]
 919     fn each_alignment_reversed() {
 920         let mut data = [1u8; 64];
 921         let needle = 2;
 922         let pos = 40;
 923         data[pos] = needle;
 924         for start in 0..16 {
 925             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
 926         }
 927     }
 928 }
 929
 930 #[test]
 931 fn test_align_to_simple() {
 932     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
 933     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
 934     assert_eq!(aligned.len(), 3);
 935     assert!(prefix == [1] || suffix == [7]);
 936     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
 937     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
 938     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
 939     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
 940     assert!(aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
 941             "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
 942             aligned, expect1, expect2, expect3, expect4);
 943 }
 944
 945 #[test]
 946 fn test_align_to_zst() {
 947     let bytes = [1, 2, 3, 4, 5, 6, 7];
 948     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
 949     assert_eq!(aligned.len(), 0);
 950     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
 951 }
 952
 953 #[test]
 954 fn test_align_to_non_trivial() {
 955     #[repr(align(8))] struct U64(u64, u64);
 956     #[repr(align(8))] struct U64U64U32(u64, u64, u32);
 957     let data = [U64(1, 2), U64(3, 4), U64(5, 6), U64(7, 8), U64(9, 10), U64(11, 12), U64(13, 14),
 958                 U64(15, 16)];
 959     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
 960     assert_eq!(aligned.len(), 4);
 961     assert_eq!(prefix.len() + suffix.len(), 2);
 962 }