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_chunks_exact_count() {
 225     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 226     let c = v.chunks_exact(3);
 227     assert_eq!(c.count(), 2);
 228
 229     let v2: &[i32] = &[0, 1, 2, 3, 4];
 230     let c2 = v2.chunks_exact(2);
 231     assert_eq!(c2.count(), 2);
 232
 233     let v3: &[i32] = &[];
 234     let c3 = v3.chunks_exact(2);
 235     assert_eq!(c3.count(), 0);
 236 }
 237
 238 #[test]
 239 fn test_chunks_exact_nth() {
 240     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 241     let mut c = v.chunks_exact(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.chunks_exact(3);
 247     assert_eq!(c2.nth(1).unwrap(), &[3, 4, 5]);
 248     assert_eq!(c2.next(), None);
 249 }
 250
 251 #[test]
 252 fn test_chunks_exact_last() {
 253     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 254     let c = v.chunks_exact(2);
 255     assert_eq!(c.last().unwrap(), &[4, 5]);
 256
 257     let v2: &[i32] = &[0, 1, 2, 3, 4];
 258     let c2 = v2.chunks_exact(2);
 259     assert_eq!(c2.last().unwrap(), &[2, 3]);
 260 }
 261
 262 #[test]
 263 fn test_chunks_exact_remainder() {
 264     let v: &[i32] = &[0, 1, 2, 3, 4];
 265     let c = v.chunks_exact(2);
 266     assert_eq!(c.remainder(), &[4]);
 267 }
 268
 269 #[test]
 270 fn test_chunks_exact_zip() {
 271     let v1: &[i32] = &[0, 1, 2, 3, 4];
 272     let v2: &[i32] = &[6, 7, 8, 9, 10];
 273
 274     let res = v1.chunks_exact(2)
 275         .zip(v2.chunks_exact(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_chunks_exact_mut_count() {
 283     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 284     let c = v.chunks_exact_mut(3);
 285     assert_eq!(c.count(), 2);
 286
 287     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 288     let c2 = v2.chunks_exact_mut(2);
 289     assert_eq!(c2.count(), 2);
 290
 291     let v3: &mut [i32] = &mut [];
 292     let c3 = v3.chunks_exact_mut(2);
 293     assert_eq!(c3.count(), 0);
 294 }
 295
 296 #[test]
 297 fn test_chunks_exact_mut_nth() {
 298     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 299     let mut c = v.chunks_exact_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.chunks_exact_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_chunks_exact_mut_last() {
 311     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 312     let c = v.chunks_exact_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.chunks_exact_mut(2);
 317     assert_eq!(c2.last().unwrap(), &[2, 3]);
 318 }
 319
 320 #[test]
 321 fn test_chunks_exact_mut_remainder() {
 322     let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
 323     let c = v.chunks_exact_mut(2);
 324     assert_eq!(c.into_remainder(), &[4]);
 325 }
 326
 327 #[test]
 328 fn test_chunks_exact_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.chunks_exact_mut(2).zip(v2.chunks_exact(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 test<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         // nth(i)
 407         for i in 0..len {
 408             assert_eq!(&v[i] as *const _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 409             let nth = v.iter().nth(i).unwrap();
 410             assert_eq!(nth as *const _, v_ptrs[i]);
 411         }
 412         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 413
 414         // stepping through with nth(0)
 415         {
 416             let mut it = v.iter();
 417             for i in 0..len {
 418                 let next = it.nth(0).unwrap();
 419                 assert_eq!(next as *const _, v_ptrs[i]);
 420             }
 421             assert_eq!(it.nth(0), None);
 422         }
 423
 424         // next()
 425         {
 426             let mut it = v.iter();
 427             for i in 0..len {
 428                 let remaining = len - i;
 429                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 430
 431                 let next = it.next().unwrap();
 432                 assert_eq!(next as *const _, v_ptrs[i]);
 433             }
 434             assert_eq!(it.size_hint(), (0, Some(0)));
 435             assert_eq!(it.next(), None, "The final call to next() should return None");
 436         }
 437
 438         // next_back()
 439         {
 440             let mut it = v.iter();
 441             for i in 0..len {
 442                 let remaining = len - i;
 443                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 444
 445                 let prev = it.next_back().unwrap();
 446                 assert_eq!(prev as *const _, v_ptrs[remaining-1]);
 447             }
 448             assert_eq!(it.size_hint(), (0, Some(0)));
 449             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 450         }
 451     }
 452
 453     fn test_mut<T : Copy + Debug + PartialEq>(x : T) {
 454         let v : &mut [T] = &mut [x, x, x];
 455         let v_ptrs : [*mut T; 3] = match v {
 456             [ref v1, ref v2, ref v3] =>
 457               [v1 as *const _ as *mut _, v2 as *const _ as *mut _, v3 as *const _ as *mut _],
 458             _ => unreachable!()
 459         };
 460         let len = v.len();
 461
 462         // nth(i)
 463         for i in 0..len {
 464             assert_eq!(&mut v[i] as *mut _, v_ptrs[i]); // check the v_ptrs array, just to be sure
 465             let nth = v.iter_mut().nth(i).unwrap();
 466             assert_eq!(nth as *mut _, v_ptrs[i]);
 467         }
 468         assert_eq!(v.iter().nth(len), None, "nth(len) should return None");
 469
 470         // stepping through with nth(0)
 471         {
 472             let mut it = v.iter();
 473             for i in 0..len {
 474                 let next = it.nth(0).unwrap();
 475                 assert_eq!(next as *const _, v_ptrs[i]);
 476             }
 477             assert_eq!(it.nth(0), None);
 478         }
 479
 480         // next()
 481         {
 482             let mut it = v.iter_mut();
 483             for i in 0..len {
 484                 let remaining = len - i;
 485                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 486
 487                 let next = it.next().unwrap();
 488                 assert_eq!(next as *mut _, v_ptrs[i]);
 489             }
 490             assert_eq!(it.size_hint(), (0, Some(0)));
 491             assert_eq!(it.next(), None, "The final call to next() should return None");
 492         }
 493
 494         // next_back()
 495         {
 496             let mut it = v.iter_mut();
 497             for i in 0..len {
 498                 let remaining = len - i;
 499                 assert_eq!(it.size_hint(), (remaining, Some(remaining)));
 500
 501                 let prev = it.next_back().unwrap();
 502                 assert_eq!(prev as *mut _, v_ptrs[remaining-1]);
 503             }
 504             assert_eq!(it.size_hint(), (0, Some(0)));
 505             assert_eq!(it.next_back(), None, "The final call to next_back() should return None");
 506         }
 507     }
 508
 509     // Make sure iterators and slice patterns yield consistent addresses for various types,
 510     // including ZSTs.
 511     test(0u32);
 512     test(());
 513     test([0u32; 0]); // ZST with alignment > 0
 514     test_mut(0u32);
 515     test_mut(());
 516     test_mut([0u32; 0]); // ZST with alignment > 0
 517 }
 518
 519 // The current implementation of SliceIndex fails to handle methods
 520 // orthogonally from range types; therefore, it is worth testing
 521 // all of the indexing operations on each input.
 522 mod slice_index {
 523     // This checks all six indexing methods, given an input range that
 524     // should succeed. (it is NOT suitable for testing invalid inputs)
 525     macro_rules! assert_range_eq {
 526         ($arr:expr, $range:expr, $expected:expr)
 527         => {
 528             let mut arr = $arr;
 529             let mut expected = $expected;
 530             {
 531                 let s: &[_] = &arr;
 532                 let expected: &[_] = &expected;
 533
 534                 assert_eq!(&s[$range], expected, "(in assertion for: index)");
 535                 assert_eq!(s.get($range), Some(expected), "(in assertion for: get)");
 536                 unsafe {
 537                     assert_eq!(
 538                         s.get_unchecked($range), expected,
 539                         "(in assertion for: get_unchecked)",
 540                     );
 541                 }
 542             }
 543             {
 544                 let s: &mut [_] = &mut arr;
 545                 let expected: &mut [_] = &mut expected;
 546
 547                 assert_eq!(
 548                     &mut s[$range], expected,
 549                     "(in assertion for: index_mut)",
 550                 );
 551                 assert_eq!(
 552                     s.get_mut($range), Some(&mut expected[..]),
 553                     "(in assertion for: get_mut)",
 554                 );
 555                 unsafe {
 556                     assert_eq!(
 557                         s.get_unchecked_mut($range), expected,
 558                         "(in assertion for: get_unchecked_mut)",
 559                     );
 560                 }
 561             }
 562         }
 563     }
 564
 565     // Make sure the macro can actually detect bugs,
 566     // because if it can't, then what are we even doing here?
 567     //
 568     // (Be aware this only demonstrates the ability to detect bugs
 569     //  in the FIRST method that panics, as the macro is not designed
 570     //  to be used in `should_panic`)
 571     #[test]
 572     #[should_panic(expected = "out of range")]
 573     fn assert_range_eq_can_fail_by_panic() {
 574         assert_range_eq!([0, 1, 2], 0..5, [0, 1, 2]);
 575     }
 576
 577     // (Be aware this only demonstrates the ability to detect bugs
 578     //  in the FIRST method it calls, as the macro is not designed
 579     //  to be used in `should_panic`)
 580     #[test]
 581     #[should_panic(expected = "==")]
 582     fn assert_range_eq_can_fail_by_inequality() {
 583         assert_range_eq!([0, 1, 2], 0..2, [0, 1, 2]);
 584     }
 585
 586     // Test cases for bad index operations.
 587     //
 588     // This generates `should_panic` test cases for Index/IndexMut
 589     // and `None` test cases for get/get_mut.
 590     macro_rules! panic_cases {
 591         ($(
 592             // each test case needs a unique name to namespace the tests
 593             in mod $case_name:ident {
 594                 data: $data:expr;
 595
 596                 // optional:
 597                 //
 598                 // one or more similar inputs for which data[input] succeeds,
 599                 // and the corresponding output as an array.  This helps validate
 600                 // "critical points" where an input range straddles the boundary
 601                 // between valid and invalid.
 602                 // (such as the input `len..len`, which is just barely valid)
 603                 $(
 604                     good: data[$good:expr] == $output:expr;
 605                 )*
 606
 607                 bad: data[$bad:expr];
 608                 message: $expect_msg:expr;
 609             }
 610         )*) => {$(
 611             mod $case_name {
 612                 #[test]
 613                 fn pass() {
 614                     let mut v = $data;
 615
 616                     $( assert_range_eq!($data, $good, $output); )*
 617
 618                     {
 619                         let v: &[_] = &v;
 620                         assert_eq!(v.get($bad), None, "(in None assertion for get)");
 621                     }
 622
 623                     {
 624                         let v: &mut [_] = &mut v;
 625                         assert_eq!(v.get_mut($bad), None, "(in None assertion for get_mut)");
 626                     }
 627                 }
 628
 629                 #[test]
 630                 #[should_panic(expected = $expect_msg)]
 631                 fn index_fail() {
 632                     let v = $data;
 633                     let v: &[_] = &v;
 634                     let _v = &v[$bad];
 635                 }
 636
 637                 #[test]
 638                 #[should_panic(expected = $expect_msg)]
 639                 fn index_mut_fail() {
 640                     let mut v = $data;
 641                     let v: &mut [_] = &mut v;
 642                     let _v = &mut v[$bad];
 643                 }
 644             }
 645         )*};
 646     }
 647
 648     #[test]
 649     fn simple() {
 650         let v = [0, 1, 2, 3, 4, 5];
 651
 652         assert_range_eq!(v, .., [0, 1, 2, 3, 4, 5]);
 653         assert_range_eq!(v, ..2, [0, 1]);
 654         assert_range_eq!(v, ..=1, [0, 1]);
 655         assert_range_eq!(v, 2.., [2, 3, 4, 5]);
 656         assert_range_eq!(v, 1..4, [1, 2, 3]);
 657         assert_range_eq!(v, 1..=3, [1, 2, 3]);
 658     }
 659
 660     panic_cases! {
 661         in mod rangefrom_len {
 662             data: [0, 1, 2, 3, 4, 5];
 663
 664             good: data[6..] == [];
 665             bad: data[7..];
 666             message: "but ends at"; // perhaps not ideal
 667         }
 668
 669         in mod rangeto_len {
 670             data: [0, 1, 2, 3, 4, 5];
 671
 672             good: data[..6] == [0, 1, 2, 3, 4, 5];
 673             bad: data[..7];
 674             message: "out of range";
 675         }
 676
 677         in mod rangetoinclusive_len {
 678             data: [0, 1, 2, 3, 4, 5];
 679
 680             good: data[..=5] == [0, 1, 2, 3, 4, 5];
 681             bad: data[..=6];
 682             message: "out of range";
 683         }
 684
 685         in mod range_len_len {
 686             data: [0, 1, 2, 3, 4, 5];
 687
 688             good: data[6..6] == [];
 689             bad: data[7..7];
 690             message: "out of range";
 691         }
 692
 693         in mod rangeinclusive_len_len {
 694             data: [0, 1, 2, 3, 4, 5];
 695
 696             good: data[6..=5] == [];
 697             bad: data[7..=6];
 698             message: "out of range";
 699         }
 700     }
 701
 702     panic_cases! {
 703         in mod range_neg_width {
 704             data: [0, 1, 2, 3, 4, 5];
 705
 706             good: data[4..4] == [];
 707             bad: data[4..3];
 708             message: "but ends at";
 709         }
 710
 711         in mod rangeinclusive_neg_width {
 712             data: [0, 1, 2, 3, 4, 5];
 713
 714             good: data[4..=3] == [];
 715             bad: data[4..=2];
 716             message: "but ends at";
 717         }
 718     }
 719
 720     panic_cases! {
 721         in mod rangeinclusive_overflow {
 722             data: [0, 1];
 723
 724             // note: using 0 specifically ensures that the result of overflowing is 0..0,
 725             //       so that `get` doesn't simply return None for the wrong reason.
 726             bad: data[0 ..= ::std::usize::MAX];
 727             message: "maximum usize";
 728         }
 729
 730         in mod rangetoinclusive_overflow {
 731             data: [0, 1];
 732
 733             bad: data[..= ::std::usize::MAX];
 734             message: "maximum usize";
 735         }
 736     } // panic_cases!
 737 }
 738
 739 #[test]
 740 fn test_find_rfind() {
 741     let v = [0, 1, 2, 3, 4, 5];
 742     let mut iter = v.iter();
 743     let mut i = v.len();
 744     while let Some(&elt) = iter.rfind(|_| true) {
 745         i -= 1;
 746         assert_eq!(elt, v[i]);
 747     }
 748     assert_eq!(i, 0);
 749     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
 750 }
 751
 752 #[test]
 753 fn test_iter_folds() {
 754     let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
 755     assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
 756     assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
 757     let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
 758     assert_eq!(a.iter().try_fold(0, &fold), Some(57));
 759     assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
 760
 761     // short-circuiting try_fold, through other methods
 762     let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
 763     let mut iter = a.iter();
 764     assert_eq!(iter.position(|&x| x == 3), Some(3));
 765     assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
 766     assert_eq!(iter.len(), 2);
 767 }
 768
 769 #[test]
 770 fn test_rotate_left() {
 771     const N: usize = 600;
 772     let a: &mut [_] = &mut [0; N];
 773     for i in 0..N {
 774         a[i] = i;
 775     }
 776
 777     a.rotate_left(42);
 778     let k = N - 42;
 779
 780     for i in 0..N {
 781         assert_eq!(a[(i + k) % N], i);
 782     }
 783 }
 784
 785 #[test]
 786 fn test_rotate_right() {
 787     const N: usize = 600;
 788     let a: &mut [_] = &mut [0; N];
 789     for i in 0..N {
 790         a[i] = i;
 791     }
 792
 793     a.rotate_right(42);
 794
 795     for i in 0..N {
 796         assert_eq!(a[(i + 42) % N], i);
 797     }
 798 }
 799
 800 #[test]
 801 #[cfg(not(target_arch = "wasm32"))]
 802 fn sort_unstable() {
 803     use core::cmp::Ordering::{Equal, Greater, Less};
 804     use core::slice::heapsort;
 805     use rand::{FromEntropy, Rng, XorShiftRng};
 806
 807     let mut v = [0; 600];
 808     let mut tmp = [0; 600];
 809     let mut rng = XorShiftRng::from_entropy();
 810
 811     for len in (2..25).chain(500..510) {
 812         let v = &mut v[0..len];
 813         let tmp = &mut tmp[0..len];
 814
 815         for &modulus in &[5, 10, 100, 1000] {
 816             for _ in 0..100 {
 817                 for i in 0..len {
 818                     v[i] = rng.gen::<i32>() % modulus;
 819                 }
 820
 821                 // Sort in default order.
 822                 tmp.copy_from_slice(v);
 823                 tmp.sort_unstable();
 824                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 825
 826                 // Sort in ascending order.
 827                 tmp.copy_from_slice(v);
 828                 tmp.sort_unstable_by(|a, b| a.cmp(b));
 829                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 830
 831                 // Sort in descending order.
 832                 tmp.copy_from_slice(v);
 833                 tmp.sort_unstable_by(|a, b| b.cmp(a));
 834                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 835
 836                 // Test heapsort using `<` operator.
 837                 tmp.copy_from_slice(v);
 838                 heapsort(tmp, |a, b| a < b);
 839                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 840
 841                 // Test heapsort using `>` operator.
 842                 tmp.copy_from_slice(v);
 843                 heapsort(tmp, |a, b| a > b);
 844                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 845             }
 846         }
 847     }
 848
 849     // Sort using a completely random comparison function.
 850     // This will reorder the elements *somehow*, but won't panic.
 851     for i in 0..v.len() {
 852         v[i] = i as i32;
 853     }
 854     v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
 855     v.sort_unstable();
 856     for i in 0..v.len() {
 857         assert_eq!(v[i], i as i32);
 858     }
 859
 860     // Should not panic.
 861     [0i32; 0].sort_unstable();
 862     [(); 10].sort_unstable();
 863     [(); 100].sort_unstable();
 864
 865     let mut v = [0xDEADBEEFu64];
 866     v.sort_unstable();
 867     assert!(v == [0xDEADBEEF]);
 868 }
 869
 870 pub mod memchr {
 871     use core::slice::memchr::{memchr, memrchr};
 872
 873     // test fallback implementations on all platforms
 874     #[test]
 875     fn matches_one() {
 876         assert_eq!(Some(0), memchr(b'a', b"a"));
 877     }
 878
 879     #[test]
 880     fn matches_begin() {
 881         assert_eq!(Some(0), memchr(b'a', b"aaaa"));
 882     }
 883
 884     #[test]
 885     fn matches_end() {
 886         assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
 887     }
 888
 889     #[test]
 890     fn matches_nul() {
 891         assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
 892     }
 893
 894     #[test]
 895     fn matches_past_nul() {
 896         assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
 897     }
 898
 899     #[test]
 900     fn no_match_empty() {
 901         assert_eq!(None, memchr(b'a', b""));
 902     }
 903
 904     #[test]
 905     fn no_match() {
 906         assert_eq!(None, memchr(b'a', b"xyz"));
 907     }
 908
 909     #[test]
 910     fn matches_one_reversed() {
 911         assert_eq!(Some(0), memrchr(b'a', b"a"));
 912     }
 913
 914     #[test]
 915     fn matches_begin_reversed() {
 916         assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
 917     }
 918
 919     #[test]
 920     fn matches_end_reversed() {
 921         assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
 922     }
 923
 924     #[test]
 925     fn matches_nul_reversed() {
 926         assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
 927     }
 928
 929     #[test]
 930     fn matches_past_nul_reversed() {
 931         assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
 932     }
 933
 934     #[test]
 935     fn no_match_empty_reversed() {
 936         assert_eq!(None, memrchr(b'a', b""));
 937     }
 938
 939     #[test]
 940     fn no_match_reversed() {
 941         assert_eq!(None, memrchr(b'a', b"xyz"));
 942     }
 943
 944     #[test]
 945     fn each_alignment_reversed() {
 946         let mut data = [1u8; 64];
 947         let needle = 2;
 948         let pos = 40;
 949         data[pos] = needle;
 950         for start in 0..16 {
 951             assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
 952         }
 953     }
 954 }
 955
 956 #[test]
 957 fn test_align_to_simple() {
 958     let bytes = [1u8, 2, 3, 4, 5, 6, 7];
 959     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<u16>() };
 960     assert_eq!(aligned.len(), 3);
 961     assert!(prefix == [1] || suffix == [7]);
 962     let expect1 = [1 << 8 | 2, 3 << 8 | 4, 5 << 8 | 6];
 963     let expect2 = [1 | 2 << 8, 3 | 4 << 8, 5 | 6 << 8];
 964     let expect3 = [2 << 8 | 3, 4 << 8 | 5, 6 << 8 | 7];
 965     let expect4 = [2 | 3 << 8, 4 | 5 << 8, 6 | 7 << 8];
 966     assert!(aligned == expect1 || aligned == expect2 || aligned == expect3 || aligned == expect4,
 967             "aligned={:?} expected={:?} || {:?} || {:?} || {:?}",
 968             aligned, expect1, expect2, expect3, expect4);
 969 }
 970
 971 #[test]
 972 fn test_align_to_zst() {
 973     let bytes = [1, 2, 3, 4, 5, 6, 7];
 974     let (prefix, aligned, suffix) = unsafe { bytes.align_to::<()>() };
 975     assert_eq!(aligned.len(), 0);
 976     assert!(prefix == [1, 2, 3, 4, 5, 6, 7] || suffix == [1, 2, 3, 4, 5, 6, 7]);
 977 }
 978
 979 #[test]
 980 fn test_align_to_non_trivial() {
 981     #[repr(align(8))] struct U64(u64, u64);
 982     #[repr(align(8))] struct U64U64U32(u64, u64, u32);
 983     let data = [U64(1, 2), U64(3, 4), U64(5, 6), U64(7, 8), U64(9, 10), U64(11, 12), U64(13, 14),
 984                 U64(15, 16)];
 985     let (prefix, aligned, suffix) = unsafe { data.align_to::<U64U64U32>() };
 986     assert_eq!(aligned.len(), 4);
 987     assert_eq!(prefix.len() + suffix.len(), 2);
 988 }
 989
 990 #[test]
 991 fn test_align_to_empty_mid() {
 992     use core::mem;
 993
 994     // Make sure that we do not create empty unaligned slices for the mid part, even when the
 995     // overall slice is too short to contain an aligned address.
 996     let bytes = [1, 2, 3, 4, 5, 6, 7];
 997     type Chunk = u32;
 998     for offset in 0..4 {
 999         let (_, mid, _) = unsafe { bytes[offset..offset+1].align_to::<Chunk>() };
1000         assert_eq!(mid.as_ptr() as usize % mem::align_of::<Chunk>(), 0);
1001     }
1002 }
1003
1004 #[test]
1005 fn test_copy_within() {
1006     // Start to end, with a RangeTo.
1007     let mut bytes = *b"Hello, World!";
1008     bytes.copy_within(..3, 10);
1009     assert_eq!(&bytes, b"Hello, WorHel");
1010
1011     // End to start, with a RangeFrom.
1012     let mut bytes = *b"Hello, World!";
1013     bytes.copy_within(10.., 0);
1014     assert_eq!(&bytes, b"ld!lo, World!");
1015
1016     // Overlapping, with a RangeInclusive.
1017     let mut bytes = *b"Hello, World!";
1018     bytes.copy_within(0..=11, 1);
1019     assert_eq!(&bytes, b"HHello, World");
1020
1021     // Whole slice, with a RangeFull.
1022     let mut bytes = *b"Hello, World!";
1023     bytes.copy_within(.., 0);
1024     assert_eq!(&bytes, b"Hello, World!");
1025 }
1026
1027 #[test]
1028 #[should_panic(expected = "src is out of bounds")]
1029 fn test_copy_within_panics_src_too_long() {
1030     let mut bytes = *b"Hello, World!";
1031     // The length is only 13, so 14 is out of bounds.
1032     bytes.copy_within(10..14, 0);
1033 }
1034
1035 #[test]
1036 #[should_panic(expected = "dest is out of bounds")]
1037 fn test_copy_within_panics_dest_too_long() {
1038     let mut bytes = *b"Hello, World!";
1039     // The length is only 13, so a slice of length 4 starting at index 10 is out of bounds.
1040     bytes.copy_within(0..4, 10);
1041 }
1042 #[test]
1043 #[should_panic(expected = "src end is before src start")]
1044 fn test_copy_within_panics_src_inverted() {
1045     let mut bytes = *b"Hello, World!";
1046     // 2 is greater than 1, so this range is invalid.
1047     bytes.copy_within(2..1, 0);
1048 }