library/core/tests/iter.rs

   1 // ignore-tidy-filelength
   2
   3 use core::cell::Cell;
   4 use core::convert::TryFrom;
   5 use core::iter::TrustedRandomAccess;
   6 use core::iter::*;
   7
   8 /// An iterator wrapper that panics whenever `next` or `next_back` is called
   9 /// after `None` has been returned.
  10 struct Unfuse<I> {
  11     iter: I,
  12     exhausted: bool,
  13 }
  14
  15 fn unfuse<I: IntoIterator>(iter: I) -> Unfuse<I::IntoIter> {
  16     Unfuse { iter: iter.into_iter(), exhausted: false }
  17 }
  18
  19 impl<I> Iterator for Unfuse<I>
  20 where
  21     I: Iterator,
  22 {
  23     type Item = I::Item;
  24
  25     fn next(&mut self) -> Option<Self::Item> {
  26         assert!(!self.exhausted);
  27         let next = self.iter.next();
  28         self.exhausted = next.is_none();
  29         next
  30     }
  31 }
  32
  33 impl<I> DoubleEndedIterator for Unfuse<I>
  34 where
  35     I: DoubleEndedIterator,
  36 {
  37     fn next_back(&mut self) -> Option<Self::Item> {
  38         assert!(!self.exhausted);
  39         let next = self.iter.next_back();
  40         self.exhausted = next.is_none();
  41         next
  42     }
  43 }
  44
  45 #[test]
  46 fn test_lt() {
  47     let empty: [isize; 0] = [];
  48     let xs = [1, 2, 3];
  49     let ys = [1, 2, 0];
  50
  51     assert!(!xs.iter().lt(ys.iter()));
  52     assert!(!xs.iter().le(ys.iter()));
  53     assert!(xs.iter().gt(ys.iter()));
  54     assert!(xs.iter().ge(ys.iter()));
  55
  56     assert!(ys.iter().lt(xs.iter()));
  57     assert!(ys.iter().le(xs.iter()));
  58     assert!(!ys.iter().gt(xs.iter()));
  59     assert!(!ys.iter().ge(xs.iter()));
  60
  61     assert!(empty.iter().lt(xs.iter()));
  62     assert!(empty.iter().le(xs.iter()));
  63     assert!(!empty.iter().gt(xs.iter()));
  64     assert!(!empty.iter().ge(xs.iter()));
  65
  66     // Sequence with NaN
  67     let u = [1.0f64, 2.0];
  68     let v = [0.0f64 / 0.0, 3.0];
  69
  70     assert!(!u.iter().lt(v.iter()));
  71     assert!(!u.iter().le(v.iter()));
  72     assert!(!u.iter().gt(v.iter()));
  73     assert!(!u.iter().ge(v.iter()));
  74
  75     let a = [0.0f64 / 0.0];
  76     let b = [1.0f64];
  77     let c = [2.0f64];
  78
  79     assert!(a.iter().lt(b.iter()) == (a[0] < b[0]));
  80     assert!(a.iter().le(b.iter()) == (a[0] <= b[0]));
  81     assert!(a.iter().gt(b.iter()) == (a[0] > b[0]));
  82     assert!(a.iter().ge(b.iter()) == (a[0] >= b[0]));
  83
  84     assert!(c.iter().lt(b.iter()) == (c[0] < b[0]));
  85     assert!(c.iter().le(b.iter()) == (c[0] <= b[0]));
  86     assert!(c.iter().gt(b.iter()) == (c[0] > b[0]));
  87     assert!(c.iter().ge(b.iter()) == (c[0] >= b[0]));
  88 }
  89
  90 #[test]
  91 fn test_multi_iter() {
  92     let xs = [1, 2, 3, 4];
  93     let ys = [4, 3, 2, 1];
  94     assert!(xs.iter().eq(ys.iter().rev()));
  95     assert!(xs.iter().lt(xs.iter().skip(2)));
  96 }
  97
  98 #[test]
  99 fn test_cmp_by() {
 100     use core::cmp::Ordering;
 101
 102     let f = |x: i32, y: i32| (x * x).cmp(&y);
 103     let xs = || [1, 2, 3, 4].iter().copied();
 104     let ys = || [1, 4, 16].iter().copied();
 105
 106     assert_eq!(xs().cmp_by(ys(), f), Ordering::Less);
 107     assert_eq!(ys().cmp_by(xs(), f), Ordering::Greater);
 108     assert_eq!(xs().cmp_by(xs().map(|x| x * x), f), Ordering::Equal);
 109     assert_eq!(xs().rev().cmp_by(ys().rev(), f), Ordering::Greater);
 110     assert_eq!(xs().cmp_by(ys().rev(), f), Ordering::Less);
 111     assert_eq!(xs().cmp_by(ys().take(2), f), Ordering::Greater);
 112 }
 113
 114 #[test]
 115 fn test_partial_cmp_by() {
 116     use core::cmp::Ordering;
 117
 118     let f = |x: i32, y: i32| (x * x).partial_cmp(&y);
 119     let xs = || [1, 2, 3, 4].iter().copied();
 120     let ys = || [1, 4, 16].iter().copied();
 121
 122     assert_eq!(xs().partial_cmp_by(ys(), f), Some(Ordering::Less));
 123     assert_eq!(ys().partial_cmp_by(xs(), f), Some(Ordering::Greater));
 124     assert_eq!(xs().partial_cmp_by(xs().map(|x| x * x), f), Some(Ordering::Equal));
 125     assert_eq!(xs().rev().partial_cmp_by(ys().rev(), f), Some(Ordering::Greater));
 126     assert_eq!(xs().partial_cmp_by(xs().rev(), f), Some(Ordering::Less));
 127     assert_eq!(xs().partial_cmp_by(ys().take(2), f), Some(Ordering::Greater));
 128
 129     let f = |x: f64, y: f64| (x * x).partial_cmp(&y);
 130     let xs = || [1.0, 2.0, 3.0, 4.0].iter().copied();
 131     let ys = || [1.0, 4.0, f64::NAN, 16.0].iter().copied();
 132
 133     assert_eq!(xs().partial_cmp_by(ys(), f), None);
 134     assert_eq!(ys().partial_cmp_by(xs(), f), Some(Ordering::Greater));
 135 }
 136
 137 #[test]
 138 fn test_eq_by() {
 139     let f = |x: i32, y: i32| x * x == y;
 140     let xs = || [1, 2, 3, 4].iter().copied();
 141     let ys = || [1, 4, 9, 16].iter().copied();
 142
 143     assert!(xs().eq_by(ys(), f));
 144     assert!(!ys().eq_by(xs(), f));
 145     assert!(!xs().eq_by(xs(), f));
 146     assert!(!ys().eq_by(ys(), f));
 147
 148     assert!(!xs().take(3).eq_by(ys(), f));
 149     assert!(!xs().eq_by(ys().take(3), f));
 150     assert!(xs().take(3).eq_by(ys().take(3), f));
 151 }
 152
 153 #[test]
 154 fn test_counter_from_iter() {
 155     let it = (0..).step_by(5).take(10);
 156     let xs: Vec<isize> = FromIterator::from_iter(it);
 157     assert_eq!(xs, [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
 158 }
 159
 160 #[test]
 161 fn test_iterator_chain() {
 162     let xs = [0, 1, 2, 3, 4, 5];
 163     let ys = [30, 40, 50, 60];
 164     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 165     let it = xs.iter().chain(&ys);
 166     let mut i = 0;
 167     for &x in it {
 168         assert_eq!(x, expected[i]);
 169         i += 1;
 170     }
 171     assert_eq!(i, expected.len());
 172
 173     let ys = (30..).step_by(10).take(4);
 174     let it = xs.iter().cloned().chain(ys);
 175     let mut i = 0;
 176     for x in it {
 177         assert_eq!(x, expected[i]);
 178         i += 1;
 179     }
 180     assert_eq!(i, expected.len());
 181 }
 182
 183 #[test]
 184 fn test_iterator_chain_advance_by() {
 185     fn test_chain(xs: &[i32], ys: &[i32]) {
 186         let len = xs.len() + ys.len();
 187
 188         for i in 0..xs.len() {
 189             let mut iter = unfuse(xs).chain(unfuse(ys));
 190             iter.advance_by(i).unwrap();
 191             assert_eq!(iter.next(), Some(&xs[i]));
 192             assert_eq!(iter.advance_by(100), Err(len - i - 1));
 193         }
 194
 195         for i in 0..ys.len() {
 196             let mut iter = unfuse(xs).chain(unfuse(ys));
 197             iter.advance_by(xs.len() + i).unwrap();
 198             assert_eq!(iter.next(), Some(&ys[i]));
 199             assert_eq!(iter.advance_by(100), Err(ys.len() - i - 1));
 200         }
 201
 202         let mut iter = xs.iter().chain(ys);
 203         iter.advance_by(len).unwrap();
 204         assert_eq!(iter.next(), None);
 205
 206         let mut iter = xs.iter().chain(ys);
 207         assert_eq!(iter.advance_by(len + 1), Err(len));
 208     }
 209
 210     test_chain(&[], &[]);
 211     test_chain(&[], &[0, 1, 2, 3, 4, 5]);
 212     test_chain(&[0, 1, 2, 3, 4, 5], &[]);
 213     test_chain(&[0, 1, 2, 3, 4, 5], &[30, 40, 50, 60]);
 214 }
 215
 216 #[test]
 217 fn test_iterator_chain_advance_back_by() {
 218     fn test_chain(xs: &[i32], ys: &[i32]) {
 219         let len = xs.len() + ys.len();
 220
 221         for i in 0..ys.len() {
 222             let mut iter = unfuse(xs).chain(unfuse(ys));
 223             iter.advance_back_by(i).unwrap();
 224             assert_eq!(iter.next_back(), Some(&ys[ys.len() - i - 1]));
 225             assert_eq!(iter.advance_back_by(100), Err(len - i - 1));
 226         }
 227
 228         for i in 0..xs.len() {
 229             let mut iter = unfuse(xs).chain(unfuse(ys));
 230             iter.advance_back_by(ys.len() + i).unwrap();
 231             assert_eq!(iter.next_back(), Some(&xs[xs.len() - i - 1]));
 232             assert_eq!(iter.advance_back_by(100), Err(xs.len() - i - 1));
 233         }
 234
 235         let mut iter = xs.iter().chain(ys);
 236         iter.advance_back_by(len).unwrap();
 237         assert_eq!(iter.next_back(), None);
 238
 239         let mut iter = xs.iter().chain(ys);
 240         assert_eq!(iter.advance_back_by(len + 1), Err(len));
 241     }
 242
 243     test_chain(&[], &[]);
 244     test_chain(&[], &[0, 1, 2, 3, 4, 5]);
 245     test_chain(&[0, 1, 2, 3, 4, 5], &[]);
 246     test_chain(&[0, 1, 2, 3, 4, 5], &[30, 40, 50, 60]);
 247 }
 248
 249 #[test]
 250 fn test_iterator_chain_nth() {
 251     let xs = [0, 1, 2, 3, 4, 5];
 252     let ys = [30, 40, 50, 60];
 253     let zs = [];
 254     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 255     for (i, x) in expected.iter().enumerate() {
 256         assert_eq!(Some(x), xs.iter().chain(&ys).nth(i));
 257     }
 258     assert_eq!(zs.iter().chain(&xs).nth(0), Some(&0));
 259
 260     let mut it = xs.iter().chain(&zs);
 261     assert_eq!(it.nth(5), Some(&5));
 262     assert_eq!(it.next(), None);
 263 }
 264
 265 #[test]
 266 fn test_iterator_chain_nth_back() {
 267     let xs = [0, 1, 2, 3, 4, 5];
 268     let ys = [30, 40, 50, 60];
 269     let zs = [];
 270     let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
 271     for (i, x) in expected.iter().rev().enumerate() {
 272         assert_eq!(Some(x), xs.iter().chain(&ys).nth_back(i));
 273     }
 274     assert_eq!(zs.iter().chain(&xs).nth_back(0), Some(&5));
 275
 276     let mut it = xs.iter().chain(&zs);
 277     assert_eq!(it.nth_back(5), Some(&0));
 278     assert_eq!(it.next(), None);
 279 }
 280
 281 #[test]
 282 fn test_iterator_chain_last() {
 283     let xs = [0, 1, 2, 3, 4, 5];
 284     let ys = [30, 40, 50, 60];
 285     let zs = [];
 286     assert_eq!(xs.iter().chain(&ys).last(), Some(&60));
 287     assert_eq!(zs.iter().chain(&ys).last(), Some(&60));
 288     assert_eq!(ys.iter().chain(&zs).last(), Some(&60));
 289     assert_eq!(zs.iter().chain(&zs).last(), None);
 290 }
 291
 292 #[test]
 293 fn test_iterator_chain_count() {
 294     let xs = [0, 1, 2, 3, 4, 5];
 295     let ys = [30, 40, 50, 60];
 296     let zs = [];
 297     assert_eq!(xs.iter().chain(&ys).count(), 10);
 298     assert_eq!(zs.iter().chain(&ys).count(), 4);
 299 }
 300
 301 #[test]
 302 fn test_iterator_chain_find() {
 303     let xs = [0, 1, 2, 3, 4, 5];
 304     let ys = [30, 40, 50, 60];
 305     let mut iter = xs.iter().chain(&ys);
 306     assert_eq!(iter.find(|&&i| i == 4), Some(&4));
 307     assert_eq!(iter.next(), Some(&5));
 308     assert_eq!(iter.find(|&&i| i == 40), Some(&40));
 309     assert_eq!(iter.next(), Some(&50));
 310     assert_eq!(iter.find(|&&i| i == 100), None);
 311     assert_eq!(iter.next(), None);
 312 }
 313
 314 struct Toggle {
 315     is_empty: bool,
 316 }
 317
 318 impl Iterator for Toggle {
 319     type Item = ();
 320
 321     // alternates between `None` and `Some(())`
 322     fn next(&mut self) -> Option<Self::Item> {
 323         if self.is_empty {
 324             self.is_empty = false;
 325             None
 326         } else {
 327             self.is_empty = true;
 328             Some(())
 329         }
 330     }
 331
 332     fn size_hint(&self) -> (usize, Option<usize>) {
 333         if self.is_empty { (0, Some(0)) } else { (1, Some(1)) }
 334     }
 335 }
 336
 337 impl DoubleEndedIterator for Toggle {
 338     fn next_back(&mut self) -> Option<Self::Item> {
 339         self.next()
 340     }
 341 }
 342
 343 #[test]
 344 fn test_iterator_chain_size_hint() {
 345     // this chains an iterator of length 0 with an iterator of length 1,
 346     // so after calling `.next()` once, the iterator is empty and the
 347     // state is `ChainState::Back`. `.size_hint()` should now disregard
 348     // the size hint of the left iterator
 349     let mut iter = Toggle { is_empty: true }.chain(once(()));
 350     assert_eq!(iter.next(), Some(()));
 351     assert_eq!(iter.size_hint(), (0, Some(0)));
 352
 353     let mut iter = once(()).chain(Toggle { is_empty: true });
 354     assert_eq!(iter.next_back(), Some(()));
 355     assert_eq!(iter.size_hint(), (0, Some(0)));
 356 }
 357
 358 #[test]
 359 fn test_iterator_chain_unfused() {
 360     // Chain shouldn't be fused in its second iterator, depending on direction
 361     let mut iter = NonFused::new(empty()).chain(Toggle { is_empty: true });
 362     iter.next().unwrap_none();
 363     iter.next().unwrap();
 364     iter.next().unwrap_none();
 365
 366     let mut iter = Toggle { is_empty: true }.chain(NonFused::new(empty()));
 367     iter.next_back().unwrap_none();
 368     iter.next_back().unwrap();
 369     iter.next_back().unwrap_none();
 370 }
 371
 372 #[test]
 373 fn test_zip_nth() {
 374     let xs = [0, 1, 2, 4, 5];
 375     let ys = [10, 11, 12];
 376
 377     let mut it = xs.iter().zip(&ys);
 378     assert_eq!(it.nth(0), Some((&0, &10)));
 379     assert_eq!(it.nth(1), Some((&2, &12)));
 380     assert_eq!(it.nth(0), None);
 381
 382     let mut it = xs.iter().zip(&ys);
 383     assert_eq!(it.nth(3), None);
 384
 385     let mut it = ys.iter().zip(&xs);
 386     assert_eq!(it.nth(3), None);
 387 }
 388
 389 #[test]
 390 fn test_zip_nth_side_effects() {
 391     let mut a = Vec::new();
 392     let mut b = Vec::new();
 393     let value = [1, 2, 3, 4, 5, 6]
 394         .iter()
 395         .cloned()
 396         .map(|n| {
 397             a.push(n);
 398             n * 10
 399         })
 400         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 401             b.push(n * 100);
 402             n * 1000
 403         }))
 404         .skip(1)
 405         .nth(3);
 406     assert_eq!(value, Some((50, 6000)));
 407     assert_eq!(a, vec![1, 2, 3, 4, 5]);
 408     assert_eq!(b, vec![200, 300, 400, 500, 600]);
 409 }
 410
 411 #[test]
 412 fn test_zip_next_back_side_effects() {
 413     let mut a = Vec::new();
 414     let mut b = Vec::new();
 415     let mut iter = [1, 2, 3, 4, 5, 6]
 416         .iter()
 417         .cloned()
 418         .map(|n| {
 419             a.push(n);
 420             n * 10
 421         })
 422         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 423             b.push(n * 100);
 424             n * 1000
 425         }));
 426
 427     // The second iterator is one item longer, so `next_back` is called on it
 428     // one more time.
 429     assert_eq!(iter.next_back(), Some((60, 7000)));
 430     assert_eq!(iter.next_back(), Some((50, 6000)));
 431     assert_eq!(iter.next_back(), Some((40, 5000)));
 432     assert_eq!(iter.next_back(), Some((30, 4000)));
 433     assert_eq!(a, vec![6, 5, 4, 3]);
 434     assert_eq!(b, vec![800, 700, 600, 500, 400]);
 435 }
 436
 437 #[test]
 438 fn test_zip_nth_back_side_effects() {
 439     let mut a = Vec::new();
 440     let mut b = Vec::new();
 441     let value = [1, 2, 3, 4, 5, 6]
 442         .iter()
 443         .cloned()
 444         .map(|n| {
 445             a.push(n);
 446             n * 10
 447         })
 448         .zip([2, 3, 4, 5, 6, 7, 8].iter().cloned().map(|n| {
 449             b.push(n * 100);
 450             n * 1000
 451         }))
 452         .nth_back(3);
 453     assert_eq!(value, Some((30, 4000)));
 454     assert_eq!(a, vec![6, 5, 4, 3]);
 455     assert_eq!(b, vec![800, 700, 600, 500, 400]);
 456 }
 457
 458 #[test]
 459 fn test_zip_next_back_side_effects_exhausted() {
 460     let mut a = Vec::new();
 461     let mut b = Vec::new();
 462     let mut iter = [1, 2, 3, 4, 5, 6]
 463         .iter()
 464         .cloned()
 465         .map(|n| {
 466             a.push(n);
 467             n * 10
 468         })
 469         .zip([2, 3, 4].iter().cloned().map(|n| {
 470             b.push(n * 100);
 471             n * 1000
 472         }));
 473
 474     iter.next();
 475     iter.next();
 476     iter.next();
 477     iter.next();
 478     assert_eq!(iter.next_back(), None);
 479     assert_eq!(a, vec![1, 2, 3, 4, 6, 5]);
 480     assert_eq!(b, vec![200, 300, 400]);
 481 }
 482
 483 #[derive(Debug)]
 484 struct CountClone(Cell<i32>);
 485
 486 fn count_clone() -> CountClone {
 487     CountClone(Cell::new(0))
 488 }
 489
 490 impl PartialEq<i32> for CountClone {
 491     fn eq(&self, rhs: &i32) -> bool {
 492         self.0.get() == *rhs
 493     }
 494 }
 495
 496 impl Clone for CountClone {
 497     fn clone(&self) -> Self {
 498         let ret = CountClone(self.0.clone());
 499         let n = self.0.get();
 500         self.0.set(n + 1);
 501         ret
 502     }
 503 }
 504
 505 #[test]
 506 fn test_zip_cloned_sideffectful() {
 507     let xs = [count_clone(), count_clone(), count_clone(), count_clone()];
 508     let ys = [count_clone(), count_clone()];
 509
 510     for _ in xs.iter().cloned().zip(ys.iter().cloned()) {}
 511
 512     assert_eq!(&xs, &[1, 1, 1, 0][..]);
 513     assert_eq!(&ys, &[1, 1][..]);
 514
 515     let xs = [count_clone(), count_clone()];
 516     let ys = [count_clone(), count_clone(), count_clone(), count_clone()];
 517
 518     for _ in xs.iter().cloned().zip(ys.iter().cloned()) {}
 519
 520     assert_eq!(&xs, &[1, 1][..]);
 521     assert_eq!(&ys, &[1, 1, 0, 0][..]);
 522 }
 523
 524 #[test]
 525 fn test_zip_map_sideffectful() {
 526     let mut xs = [0; 6];
 527     let mut ys = [0; 4];
 528
 529     for _ in xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1)) {}
 530
 531     assert_eq!(&xs, &[1, 1, 1, 1, 1, 0]);
 532     assert_eq!(&ys, &[1, 1, 1, 1]);
 533
 534     let mut xs = [0; 4];
 535     let mut ys = [0; 6];
 536
 537     for _ in xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1)) {}
 538
 539     assert_eq!(&xs, &[1, 1, 1, 1]);
 540     assert_eq!(&ys, &[1, 1, 1, 1, 0, 0]);
 541 }
 542
 543 #[test]
 544 fn test_zip_map_rev_sideffectful() {
 545     let mut xs = [0; 6];
 546     let mut ys = [0; 4];
 547
 548     {
 549         let mut it = xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1));
 550         it.next_back();
 551     }
 552     assert_eq!(&xs, &[0, 0, 0, 1, 1, 1]);
 553     assert_eq!(&ys, &[0, 0, 0, 1]);
 554
 555     let mut xs = [0; 6];
 556     let mut ys = [0; 4];
 557
 558     {
 559         let mut it = xs.iter_mut().map(|x| *x += 1).zip(ys.iter_mut().map(|y| *y += 1));
 560         (&mut it).take(5).count();
 561         it.next_back();
 562     }
 563     assert_eq!(&xs, &[1, 1, 1, 1, 1, 1]);
 564     assert_eq!(&ys, &[1, 1, 1, 1]);
 565 }
 566
 567 #[test]
 568 fn test_zip_nested_sideffectful() {
 569     let mut xs = [0; 6];
 570     let ys = [0; 4];
 571
 572     {
 573         // test that it has the side effect nested inside enumerate
 574         let it = xs.iter_mut().map(|x| *x = 1).enumerate().zip(&ys);
 575         it.count();
 576     }
 577     assert_eq!(&xs, &[1, 1, 1, 1, 1, 0]);
 578 }
 579
 580 #[test]
 581 fn test_zip_nth_back_side_effects_exhausted() {
 582     let mut a = Vec::new();
 583     let mut b = Vec::new();
 584     let mut iter = [1, 2, 3, 4, 5, 6]
 585         .iter()
 586         .cloned()
 587         .map(|n| {
 588             a.push(n);
 589             n * 10
 590         })
 591         .zip([2, 3, 4].iter().cloned().map(|n| {
 592             b.push(n * 100);
 593             n * 1000
 594         }));
 595
 596     iter.next();
 597     iter.next();
 598     iter.next();
 599     iter.next();
 600     assert_eq!(iter.nth_back(0), None);
 601     assert_eq!(a, vec![1, 2, 3, 4, 6, 5]);
 602     assert_eq!(b, vec![200, 300, 400]);
 603 }
 604
 605 #[test]
 606 fn test_zip_trusted_random_access_composition() {
 607     let a = [0, 1, 2, 3, 4];
 608     let b = a;
 609     let c = a;
 610
 611     let a = a.iter().copied();
 612     let b = b.iter().copied();
 613     let mut c = c.iter().copied();
 614     c.next();
 615
 616     let mut z1 = a.zip(b);
 617     assert_eq!(z1.next().unwrap(), (0, 0));
 618
 619     let mut z2 = z1.zip(c);
 620     fn assert_trusted_random_access<T: TrustedRandomAccess>(_a: &T) {}
 621     assert_trusted_random_access(&z2);
 622     assert_eq!(z2.next().unwrap(), ((1, 1), 1));
 623 }
 624
 625 #[test]
 626 fn test_iterator_step_by() {
 627     // Identity
 628     let mut it = (0..).step_by(1).take(3);
 629     assert_eq!(it.next(), Some(0));
 630     assert_eq!(it.next(), Some(1));
 631     assert_eq!(it.next(), Some(2));
 632     assert_eq!(it.next(), None);
 633
 634     let mut it = (0..).step_by(3).take(4);
 635     assert_eq!(it.next(), Some(0));
 636     assert_eq!(it.next(), Some(3));
 637     assert_eq!(it.next(), Some(6));
 638     assert_eq!(it.next(), Some(9));
 639     assert_eq!(it.next(), None);
 640
 641     let mut it = (0..3).step_by(1);
 642     assert_eq!(it.next_back(), Some(2));
 643     assert_eq!(it.next_back(), Some(1));
 644     assert_eq!(it.next_back(), Some(0));
 645     assert_eq!(it.next_back(), None);
 646
 647     let mut it = (0..11).step_by(3);
 648     assert_eq!(it.next_back(), Some(9));
 649     assert_eq!(it.next_back(), Some(6));
 650     assert_eq!(it.next_back(), Some(3));
 651     assert_eq!(it.next_back(), Some(0));
 652     assert_eq!(it.next_back(), None);
 653 }
 654
 655 #[test]
 656 fn test_iterator_step_by_nth() {
 657     let mut it = (0..16).step_by(5);
 658     assert_eq!(it.nth(0), Some(0));
 659     assert_eq!(it.nth(0), Some(5));
 660     assert_eq!(it.nth(0), Some(10));
 661     assert_eq!(it.nth(0), Some(15));
 662     assert_eq!(it.nth(0), None);
 663
 664     let it = (0..18).step_by(5);
 665     assert_eq!(it.clone().nth(0), Some(0));
 666     assert_eq!(it.clone().nth(1), Some(5));
 667     assert_eq!(it.clone().nth(2), Some(10));
 668     assert_eq!(it.clone().nth(3), Some(15));
 669     assert_eq!(it.clone().nth(4), None);
 670     assert_eq!(it.clone().nth(42), None);
 671 }
 672
 673 #[test]
 674 fn test_iterator_step_by_nth_overflow() {
 675     #[cfg(target_pointer_width = "8")]
 676     type Bigger = u16;
 677     #[cfg(target_pointer_width = "16")]
 678     type Bigger = u32;
 679     #[cfg(target_pointer_width = "32")]
 680     type Bigger = u64;
 681     #[cfg(target_pointer_width = "64")]
 682     type Bigger = u128;
 683
 684     #[derive(Clone)]
 685     struct Test(Bigger);
 686     impl Iterator for &mut Test {
 687         type Item = i32;
 688         fn next(&mut self) -> Option<Self::Item> {
 689             Some(21)
 690         }
 691         fn nth(&mut self, n: usize) -> Option<Self::Item> {
 692             self.0 += n as Bigger + 1;
 693             Some(42)
 694         }
 695     }
 696
 697     let mut it = Test(0);
 698     let root = usize::MAX >> (usize::BITS / 2);
 699     let n = root + 20;
 700     (&mut it).step_by(n).nth(n);
 701     assert_eq!(it.0, n as Bigger * n as Bigger);
 702
 703     // large step
 704     let mut it = Test(0);
 705     (&mut it).step_by(usize::MAX).nth(5);
 706     assert_eq!(it.0, (usize::MAX as Bigger) * 5);
 707
 708     // n + 1 overflows
 709     let mut it = Test(0);
 710     (&mut it).step_by(2).nth(usize::MAX);
 711     assert_eq!(it.0, (usize::MAX as Bigger) * 2);
 712
 713     // n + 1 overflows
 714     let mut it = Test(0);
 715     (&mut it).step_by(1).nth(usize::MAX);
 716     assert_eq!(it.0, (usize::MAX as Bigger) * 1);
 717 }
 718
 719 #[test]
 720 fn test_iterator_step_by_nth_try_fold() {
 721     let mut it = (0..).step_by(10);
 722     assert_eq!(it.try_fold(0, i8::checked_add), None);
 723     assert_eq!(it.next(), Some(60));
 724     assert_eq!(it.try_fold(0, i8::checked_add), None);
 725     assert_eq!(it.next(), Some(90));
 726
 727     let mut it = (100..).step_by(10);
 728     assert_eq!(it.try_fold(50, i8::checked_add), None);
 729     assert_eq!(it.next(), Some(110));
 730
 731     let mut it = (100..=100).step_by(10);
 732     assert_eq!(it.next(), Some(100));
 733     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
 734 }
 735
 736 #[test]
 737 fn test_iterator_step_by_nth_back() {
 738     let mut it = (0..16).step_by(5);
 739     assert_eq!(it.nth_back(0), Some(15));
 740     assert_eq!(it.nth_back(0), Some(10));
 741     assert_eq!(it.nth_back(0), Some(5));
 742     assert_eq!(it.nth_back(0), Some(0));
 743     assert_eq!(it.nth_back(0), None);
 744
 745     let mut it = (0..16).step_by(5);
 746     assert_eq!(it.next(), Some(0)); // to set `first_take` to `false`
 747     assert_eq!(it.nth_back(0), Some(15));
 748     assert_eq!(it.nth_back(0), Some(10));
 749     assert_eq!(it.nth_back(0), Some(5));
 750     assert_eq!(it.nth_back(0), None);
 751
 752     let it = || (0..18).step_by(5);
 753     assert_eq!(it().nth_back(0), Some(15));
 754     assert_eq!(it().nth_back(1), Some(10));
 755     assert_eq!(it().nth_back(2), Some(5));
 756     assert_eq!(it().nth_back(3), Some(0));
 757     assert_eq!(it().nth_back(4), None);
 758     assert_eq!(it().nth_back(42), None);
 759 }
 760
 761 #[test]
 762 fn test_iterator_step_by_nth_try_rfold() {
 763     let mut it = (0..100).step_by(10);
 764     assert_eq!(it.try_rfold(0, i8::checked_add), None);
 765     assert_eq!(it.next_back(), Some(70));
 766     assert_eq!(it.next(), Some(0));
 767     assert_eq!(it.try_rfold(0, i8::checked_add), None);
 768     assert_eq!(it.next_back(), Some(30));
 769
 770     let mut it = (0..100).step_by(10);
 771     assert_eq!(it.try_rfold(50, i8::checked_add), None);
 772     assert_eq!(it.next_back(), Some(80));
 773
 774     let mut it = (100..=100).step_by(10);
 775     assert_eq!(it.next_back(), Some(100));
 776     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
 777 }
 778
 779 #[test]
 780 #[should_panic]
 781 fn test_iterator_step_by_zero() {
 782     let mut it = (0..).step_by(0);
 783     it.next();
 784 }
 785
 786 #[test]
 787 fn test_iterator_step_by_size_hint() {
 788     struct StubSizeHint(usize, Option<usize>);
 789     impl Iterator for StubSizeHint {
 790         type Item = ();
 791         fn next(&mut self) -> Option<()> {
 792             self.0 -= 1;
 793             if let Some(ref mut upper) = self.1 {
 794                 *upper -= 1;
 795             }
 796             Some(())
 797         }
 798         fn size_hint(&self) -> (usize, Option<usize>) {
 799             (self.0, self.1)
 800         }
 801     }
 802
 803     // The two checks in each case are needed because the logic
 804     // is different before the first call to `next()`.
 805
 806     let mut it = StubSizeHint(10, Some(10)).step_by(1);
 807     assert_eq!(it.size_hint(), (10, Some(10)));
 808     it.next();
 809     assert_eq!(it.size_hint(), (9, Some(9)));
 810
 811     // exact multiple
 812     let mut it = StubSizeHint(10, Some(10)).step_by(3);
 813     assert_eq!(it.size_hint(), (4, Some(4)));
 814     it.next();
 815     assert_eq!(it.size_hint(), (3, Some(3)));
 816
 817     // larger base range, but not enough to get another element
 818     let mut it = StubSizeHint(12, Some(12)).step_by(3);
 819     assert_eq!(it.size_hint(), (4, Some(4)));
 820     it.next();
 821     assert_eq!(it.size_hint(), (3, Some(3)));
 822
 823     // smaller base range, so fewer resulting elements
 824     let mut it = StubSizeHint(9, Some(9)).step_by(3);
 825     assert_eq!(it.size_hint(), (3, Some(3)));
 826     it.next();
 827     assert_eq!(it.size_hint(), (2, Some(2)));
 828
 829     // infinite upper bound
 830     let mut it = StubSizeHint(usize::MAX, None).step_by(1);
 831     assert_eq!(it.size_hint(), (usize::MAX, None));
 832     it.next();
 833     assert_eq!(it.size_hint(), (usize::MAX - 1, None));
 834
 835     // still infinite with larger step
 836     let mut it = StubSizeHint(7, None).step_by(3);
 837     assert_eq!(it.size_hint(), (3, None));
 838     it.next();
 839     assert_eq!(it.size_hint(), (2, None));
 840
 841     // propagates ExactSizeIterator
 842     let a = [1, 2, 3, 4, 5];
 843     let it = a.iter().step_by(2);
 844     assert_eq!(it.len(), 3);
 845
 846     // Cannot be TrustedLen as a step greater than one makes an iterator
 847     // with (usize::MAX, None) no longer meet the safety requirements
 848     trait TrustedLenCheck {
 849         fn test(self) -> bool;
 850     }
 851     impl<T: Iterator> TrustedLenCheck for T {
 852         default fn test(self) -> bool {
 853             false
 854         }
 855     }
 856     impl<T: TrustedLen> TrustedLenCheck for T {
 857         fn test(self) -> bool {
 858             true
 859         }
 860     }
 861     assert!(TrustedLenCheck::test(a.iter()));
 862     assert!(!TrustedLenCheck::test(a.iter().step_by(1)));
 863 }
 864
 865 #[test]
 866 fn test_filter_map() {
 867     let it = (0..).step_by(1).take(10).filter_map(|x| if x % 2 == 0 { Some(x * x) } else { None });
 868     assert_eq!(it.collect::<Vec<usize>>(), [0 * 0, 2 * 2, 4 * 4, 6 * 6, 8 * 8]);
 869 }
 870
 871 #[test]
 872 fn test_filter_map_fold() {
 873     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 874     let ys = [0 * 0, 2 * 2, 4 * 4, 6 * 6, 8 * 8];
 875     let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x * x) } else { None });
 876     let i = it.fold(0, |i, x| {
 877         assert_eq!(x, ys[i]);
 878         i + 1
 879     });
 880     assert_eq!(i, ys.len());
 881
 882     let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x * x) } else { None });
 883     let i = it.rfold(ys.len(), |i, x| {
 884         assert_eq!(x, ys[i - 1]);
 885         i - 1
 886     });
 887     assert_eq!(i, 0);
 888 }
 889
 890 #[test]
 891 fn test_iterator_enumerate() {
 892     let xs = [0, 1, 2, 3, 4, 5];
 893     let it = xs.iter().enumerate();
 894     for (i, &x) in it {
 895         assert_eq!(i, x);
 896     }
 897 }
 898
 899 #[test]
 900 fn test_iterator_enumerate_nth() {
 901     let xs = [0, 1, 2, 3, 4, 5];
 902     for (i, &x) in xs.iter().enumerate() {
 903         assert_eq!(i, x);
 904     }
 905
 906     let mut it = xs.iter().enumerate();
 907     while let Some((i, &x)) = it.nth(0) {
 908         assert_eq!(i, x);
 909     }
 910
 911     let mut it = xs.iter().enumerate();
 912     while let Some((i, &x)) = it.nth(1) {
 913         assert_eq!(i, x);
 914     }
 915
 916     let (i, &x) = xs.iter().enumerate().nth(3).unwrap();
 917     assert_eq!(i, x);
 918     assert_eq!(i, 3);
 919 }
 920
 921 #[test]
 922 fn test_iterator_enumerate_nth_back() {
 923     let xs = [0, 1, 2, 3, 4, 5];
 924     let mut it = xs.iter().enumerate();
 925     while let Some((i, &x)) = it.nth_back(0) {
 926         assert_eq!(i, x);
 927     }
 928
 929     let mut it = xs.iter().enumerate();
 930     while let Some((i, &x)) = it.nth_back(1) {
 931         assert_eq!(i, x);
 932     }
 933
 934     let (i, &x) = xs.iter().enumerate().nth_back(3).unwrap();
 935     assert_eq!(i, x);
 936     assert_eq!(i, 2);
 937 }
 938
 939 #[test]
 940 fn test_iterator_enumerate_count() {
 941     let xs = [0, 1, 2, 3, 4, 5];
 942     assert_eq!(xs.iter().enumerate().count(), 6);
 943 }
 944
 945 #[test]
 946 fn test_iterator_enumerate_fold() {
 947     let xs = [0, 1, 2, 3, 4, 5];
 948     let mut it = xs.iter().enumerate();
 949     // steal a couple to get an interesting offset
 950     assert_eq!(it.next(), Some((0, &0)));
 951     assert_eq!(it.next(), Some((1, &1)));
 952     let i = it.fold(2, |i, (j, &x)| {
 953         assert_eq!(i, j);
 954         assert_eq!(x, xs[j]);
 955         i + 1
 956     });
 957     assert_eq!(i, xs.len());
 958
 959     let mut it = xs.iter().enumerate();
 960     assert_eq!(it.next(), Some((0, &0)));
 961     let i = it.rfold(xs.len() - 1, |i, (j, &x)| {
 962         assert_eq!(i, j);
 963         assert_eq!(x, xs[j]);
 964         i - 1
 965     });
 966     assert_eq!(i, 0);
 967 }
 968
 969 #[test]
 970 fn test_iterator_filter_count() {
 971     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 972     assert_eq!(xs.iter().filter(|&&x| x % 2 == 0).count(), 5);
 973 }
 974
 975 #[test]
 976 fn test_iterator_filter_fold() {
 977     let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
 978     let ys = [0, 2, 4, 6, 8];
 979     let it = xs.iter().filter(|&&x| x % 2 == 0);
 980     let i = it.fold(0, |i, &x| {
 981         assert_eq!(x, ys[i]);
 982         i + 1
 983     });
 984     assert_eq!(i, ys.len());
 985
 986     let it = xs.iter().filter(|&&x| x % 2 == 0);
 987     let i = it.rfold(ys.len(), |i, &x| {
 988         assert_eq!(x, ys[i - 1]);
 989         i - 1
 990     });
 991     assert_eq!(i, 0);
 992 }
 993
 994 #[test]
 995 fn test_iterator_peekable() {
 996     let xs = vec![0, 1, 2, 3, 4, 5];
 997
 998     let mut it = xs.iter().cloned().peekable();
 999     assert_eq!(it.len(), 6);
1000     assert_eq!(it.peek().unwrap(), &0);
1001     assert_eq!(it.len(), 6);
1002     assert_eq!(it.next().unwrap(), 0);
1003     assert_eq!(it.len(), 5);
1004     assert_eq!(it.next().unwrap(), 1);
1005     assert_eq!(it.len(), 4);
1006     assert_eq!(it.next().unwrap(), 2);
1007     assert_eq!(it.len(), 3);
1008     assert_eq!(it.peek().unwrap(), &3);
1009     assert_eq!(it.len(), 3);
1010     assert_eq!(it.peek().unwrap(), &3);
1011     assert_eq!(it.len(), 3);
1012     assert_eq!(it.next().unwrap(), 3);
1013     assert_eq!(it.len(), 2);
1014     assert_eq!(it.next().unwrap(), 4);
1015     assert_eq!(it.len(), 1);
1016     assert_eq!(it.peek().unwrap(), &5);
1017     assert_eq!(it.len(), 1);
1018     assert_eq!(it.next().unwrap(), 5);
1019     assert_eq!(it.len(), 0);
1020     assert!(it.peek().is_none());
1021     assert_eq!(it.len(), 0);
1022     assert!(it.next().is_none());
1023     assert_eq!(it.len(), 0);
1024
1025     let mut it = xs.iter().cloned().peekable();
1026     assert_eq!(it.len(), 6);
1027     assert_eq!(it.peek().unwrap(), &0);
1028     assert_eq!(it.len(), 6);
1029     assert_eq!(it.next_back().unwrap(), 5);
1030     assert_eq!(it.len(), 5);
1031     assert_eq!(it.next_back().unwrap(), 4);
1032     assert_eq!(it.len(), 4);
1033     assert_eq!(it.next_back().unwrap(), 3);
1034     assert_eq!(it.len(), 3);
1035     assert_eq!(it.peek().unwrap(), &0);
1036     assert_eq!(it.len(), 3);
1037     assert_eq!(it.peek().unwrap(), &0);
1038     assert_eq!(it.len(), 3);
1039     assert_eq!(it.next_back().unwrap(), 2);
1040     assert_eq!(it.len(), 2);
1041     assert_eq!(it.next_back().unwrap(), 1);
1042     assert_eq!(it.len(), 1);
1043     assert_eq!(it.peek().unwrap(), &0);
1044     assert_eq!(it.len(), 1);
1045     assert_eq!(it.next_back().unwrap(), 0);
1046     assert_eq!(it.len(), 0);
1047     assert!(it.peek().is_none());
1048     assert_eq!(it.len(), 0);
1049     assert!(it.next_back().is_none());
1050     assert_eq!(it.len(), 0);
1051 }
1052
1053 #[test]
1054 fn test_iterator_peekable_count() {
1055     let xs = [0, 1, 2, 3, 4, 5];
1056     let ys = [10];
1057     let zs: [i32; 0] = [];
1058
1059     assert_eq!(xs.iter().peekable().count(), 6);
1060
1061     let mut it = xs.iter().peekable();
1062     assert_eq!(it.peek(), Some(&&0));
1063     assert_eq!(it.count(), 6);
1064
1065     assert_eq!(ys.iter().peekable().count(), 1);
1066
1067     let mut it = ys.iter().peekable();
1068     assert_eq!(it.peek(), Some(&&10));
1069     assert_eq!(it.count(), 1);
1070
1071     assert_eq!(zs.iter().peekable().count(), 0);
1072
1073     let mut it = zs.iter().peekable();
1074     assert_eq!(it.peek(), None);
1075 }
1076
1077 #[test]
1078 fn test_iterator_peekable_nth() {
1079     let xs = [0, 1, 2, 3, 4, 5];
1080     let mut it = xs.iter().peekable();
1081
1082     assert_eq!(it.peek(), Some(&&0));
1083     assert_eq!(it.nth(0), Some(&0));
1084     assert_eq!(it.peek(), Some(&&1));
1085     assert_eq!(it.nth(1), Some(&2));
1086     assert_eq!(it.peek(), Some(&&3));
1087     assert_eq!(it.nth(2), Some(&5));
1088     assert_eq!(it.next(), None);
1089 }
1090
1091 #[test]
1092 fn test_iterator_peekable_last() {
1093     let xs = [0, 1, 2, 3, 4, 5];
1094     let ys = [0];
1095
1096     let mut it = xs.iter().peekable();
1097     assert_eq!(it.peek(), Some(&&0));
1098     assert_eq!(it.last(), Some(&5));
1099
1100     let mut it = ys.iter().peekable();
1101     assert_eq!(it.peek(), Some(&&0));
1102     assert_eq!(it.last(), Some(&0));
1103
1104     let mut it = ys.iter().peekable();
1105     assert_eq!(it.next(), Some(&0));
1106     assert_eq!(it.peek(), None);
1107     assert_eq!(it.last(), None);
1108 }
1109
1110 #[test]
1111 fn test_iterator_peekable_fold() {
1112     let xs = [0, 1, 2, 3, 4, 5];
1113     let mut it = xs.iter().peekable();
1114     assert_eq!(it.peek(), Some(&&0));
1115     let i = it.fold(0, |i, &x| {
1116         assert_eq!(x, xs[i]);
1117         i + 1
1118     });
1119     assert_eq!(i, xs.len());
1120 }
1121
1122 #[test]
1123 fn test_iterator_peekable_rfold() {
1124     let xs = [0, 1, 2, 3, 4, 5];
1125     let mut it = xs.iter().peekable();
1126     assert_eq!(it.peek(), Some(&&0));
1127     let i = it.rfold(0, |i, &x| {
1128         assert_eq!(x, xs[xs.len() - 1 - i]);
1129         i + 1
1130     });
1131     assert_eq!(i, xs.len());
1132 }
1133
1134 #[test]
1135 fn test_iterator_peekable_next_if_eq() {
1136     // first, try on references
1137     let xs = vec!["Heart", "of", "Gold"];
1138     let mut it = xs.into_iter().peekable();
1139     // try before `peek()`
1140     assert_eq!(it.next_if_eq(&"trillian"), None);
1141     assert_eq!(it.next_if_eq(&"Heart"), Some("Heart"));
1142     // try after peek()
1143     assert_eq!(it.peek(), Some(&"of"));
1144     assert_eq!(it.next_if_eq(&"of"), Some("of"));
1145     assert_eq!(it.next_if_eq(&"zaphod"), None);
1146     // make sure `next()` still behaves
1147     assert_eq!(it.next(), Some("Gold"));
1148
1149     // make sure comparison works for owned values
1150     let xs = vec![String::from("Ludicrous"), "speed".into()];
1151     let mut it = xs.into_iter().peekable();
1152     // make sure basic functionality works
1153     assert_eq!(it.next_if_eq("Ludicrous"), Some("Ludicrous".into()));
1154     assert_eq!(it.next_if_eq("speed"), Some("speed".into()));
1155     assert_eq!(it.next_if_eq(""), None);
1156 }
1157
1158 #[test]
1159 fn test_iterator_peekable_mut() {
1160     let mut it = vec![1, 2, 3].into_iter().peekable();
1161     if let Some(p) = it.peek_mut() {
1162         if *p == 1 {
1163             *p = 5;
1164         }
1165     }
1166     assert_eq!(it.collect::<Vec<_>>(), vec![5, 2, 3]);
1167 }
1168
1169 /// This is an iterator that follows the Iterator contract,
1170 /// but it is not fused. After having returned None once, it will start
1171 /// producing elements if .next() is called again.
1172 pub struct CycleIter<'a, T> {
1173     index: usize,
1174     data: &'a [T],
1175 }
1176
1177 pub fn cycle<T>(data: &[T]) -> CycleIter<'_, T> {
1178     CycleIter { index: 0, data }
1179 }
1180
1181 impl<'a, T> Iterator for CycleIter<'a, T> {
1182     type Item = &'a T;
1183     fn next(&mut self) -> Option<Self::Item> {
1184         let elt = self.data.get(self.index);
1185         self.index += 1;
1186         self.index %= 1 + self.data.len();
1187         elt
1188     }
1189 }
1190
1191 #[test]
1192 fn test_iterator_peekable_remember_peek_none_1() {
1193     // Check that the loop using .peek() terminates
1194     let data = [1, 2, 3];
1195     let mut iter = cycle(&data).peekable();
1196
1197     let mut n = 0;
1198     while let Some(_) = iter.next() {
1199         let is_the_last = iter.peek().is_none();
1200         assert_eq!(is_the_last, n == data.len() - 1);
1201         n += 1;
1202         if n > data.len() {
1203             break;
1204         }
1205     }
1206     assert_eq!(n, data.len());
1207 }
1208
1209 #[test]
1210 fn test_iterator_peekable_remember_peek_none_2() {
1211     let data = [0];
1212     let mut iter = cycle(&data).peekable();
1213     iter.next();
1214     assert_eq!(iter.peek(), None);
1215     assert_eq!(iter.last(), None);
1216 }
1217
1218 #[test]
1219 fn test_iterator_peekable_remember_peek_none_3() {
1220     let data = [0];
1221     let mut iter = cycle(&data).peekable();
1222     iter.peek();
1223     assert_eq!(iter.nth(0), Some(&0));
1224
1225     let mut iter = cycle(&data).peekable();
1226     iter.next();
1227     assert_eq!(iter.peek(), None);
1228     assert_eq!(iter.nth(0), None);
1229 }
1230
1231 #[test]
1232 fn test_iterator_take_while() {
1233     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1234     let ys = [0, 1, 2, 3, 5, 13];
1235     let it = xs.iter().take_while(|&x| *x < 15);
1236     let mut i = 0;
1237     for x in it {
1238         assert_eq!(*x, ys[i]);
1239         i += 1;
1240     }
1241     assert_eq!(i, ys.len());
1242 }
1243
1244 #[test]
1245 fn test_iterator_skip_while() {
1246     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1247     let ys = [15, 16, 17, 19];
1248     let it = xs.iter().skip_while(|&x| *x < 15);
1249     let mut i = 0;
1250     for x in it {
1251         assert_eq!(*x, ys[i]);
1252         i += 1;
1253     }
1254     assert_eq!(i, ys.len());
1255 }
1256
1257 #[test]
1258 fn test_iterator_skip_while_fold() {
1259     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1260     let ys = [15, 16, 17, 19];
1261     let it = xs.iter().skip_while(|&x| *x < 15);
1262     let i = it.fold(0, |i, &x| {
1263         assert_eq!(x, ys[i]);
1264         i + 1
1265     });
1266     assert_eq!(i, ys.len());
1267
1268     let mut it = xs.iter().skip_while(|&x| *x < 15);
1269     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1270     let i = it.fold(1, |i, &x| {
1271         assert_eq!(x, ys[i]);
1272         i + 1
1273     });
1274     assert_eq!(i, ys.len());
1275 }
1276
1277 #[test]
1278 fn test_iterator_skip() {
1279     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1280     let ys = [13, 15, 16, 17, 19, 20, 30];
1281     let mut it = xs.iter().skip(5);
1282     let mut i = 0;
1283     while let Some(&x) = it.next() {
1284         assert_eq!(x, ys[i]);
1285         i += 1;
1286         assert_eq!(it.len(), xs.len() - 5 - i);
1287     }
1288     assert_eq!(i, ys.len());
1289     assert_eq!(it.len(), 0);
1290 }
1291
1292 #[test]
1293 fn test_iterator_skip_doubleended() {
1294     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1295     let mut it = xs.iter().rev().skip(5);
1296     assert_eq!(it.next(), Some(&15));
1297     assert_eq!(it.by_ref().rev().next(), Some(&0));
1298     assert_eq!(it.next(), Some(&13));
1299     assert_eq!(it.by_ref().rev().next(), Some(&1));
1300     assert_eq!(it.next(), Some(&5));
1301     assert_eq!(it.by_ref().rev().next(), Some(&2));
1302     assert_eq!(it.next(), Some(&3));
1303     assert_eq!(it.next(), None);
1304     let mut it = xs.iter().rev().skip(5).rev();
1305     assert_eq!(it.next(), Some(&0));
1306     assert_eq!(it.rev().next(), Some(&15));
1307     let mut it_base = xs.iter();
1308     {
1309         let mut it = it_base.by_ref().skip(5).rev();
1310         assert_eq!(it.next(), Some(&30));
1311         assert_eq!(it.next(), Some(&20));
1312         assert_eq!(it.next(), Some(&19));
1313         assert_eq!(it.next(), Some(&17));
1314         assert_eq!(it.next(), Some(&16));
1315         assert_eq!(it.next(), Some(&15));
1316         assert_eq!(it.next(), Some(&13));
1317         assert_eq!(it.next(), None);
1318     }
1319     // make sure the skipped parts have not been consumed
1320     assert_eq!(it_base.next(), Some(&0));
1321     assert_eq!(it_base.next(), Some(&1));
1322     assert_eq!(it_base.next(), Some(&2));
1323     assert_eq!(it_base.next(), Some(&3));
1324     assert_eq!(it_base.next(), Some(&5));
1325     assert_eq!(it_base.next(), None);
1326     let it = xs.iter().skip(5).rev();
1327     assert_eq!(it.last(), Some(&13));
1328 }
1329
1330 #[test]
1331 fn test_iterator_skip_nth() {
1332     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1333
1334     let mut it = xs.iter().skip(0);
1335     assert_eq!(it.nth(0), Some(&0));
1336     assert_eq!(it.nth(1), Some(&2));
1337
1338     let mut it = xs.iter().skip(5);
1339     assert_eq!(it.nth(0), Some(&13));
1340     assert_eq!(it.nth(1), Some(&16));
1341
1342     let mut it = xs.iter().skip(12);
1343     assert_eq!(it.nth(0), None);
1344 }
1345
1346 #[test]
1347 fn test_iterator_skip_count() {
1348     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1349
1350     assert_eq!(xs.iter().skip(0).count(), 12);
1351     assert_eq!(xs.iter().skip(1).count(), 11);
1352     assert_eq!(xs.iter().skip(11).count(), 1);
1353     assert_eq!(xs.iter().skip(12).count(), 0);
1354     assert_eq!(xs.iter().skip(13).count(), 0);
1355 }
1356
1357 #[test]
1358 fn test_iterator_skip_last() {
1359     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1360
1361     assert_eq!(xs.iter().skip(0).last(), Some(&30));
1362     assert_eq!(xs.iter().skip(1).last(), Some(&30));
1363     assert_eq!(xs.iter().skip(11).last(), Some(&30));
1364     assert_eq!(xs.iter().skip(12).last(), None);
1365     assert_eq!(xs.iter().skip(13).last(), None);
1366
1367     let mut it = xs.iter().skip(5);
1368     assert_eq!(it.next(), Some(&13));
1369     assert_eq!(it.last(), Some(&30));
1370 }
1371
1372 #[test]
1373 fn test_iterator_skip_fold() {
1374     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
1375     let ys = [13, 15, 16, 17, 19, 20, 30];
1376
1377     let it = xs.iter().skip(5);
1378     let i = it.fold(0, |i, &x| {
1379         assert_eq!(x, ys[i]);
1380         i + 1
1381     });
1382     assert_eq!(i, ys.len());
1383
1384     let mut it = xs.iter().skip(5);
1385     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1386     let i = it.fold(1, |i, &x| {
1387         assert_eq!(x, ys[i]);
1388         i + 1
1389     });
1390     assert_eq!(i, ys.len());
1391
1392     let it = xs.iter().skip(5);
1393     let i = it.rfold(ys.len(), |i, &x| {
1394         let i = i - 1;
1395         assert_eq!(x, ys[i]);
1396         i
1397     });
1398     assert_eq!(i, 0);
1399
1400     let mut it = xs.iter().skip(5);
1401     assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
1402     let i = it.rfold(ys.len(), |i, &x| {
1403         let i = i - 1;
1404         assert_eq!(x, ys[i]);
1405         i
1406     });
1407     assert_eq!(i, 1);
1408 }
1409
1410 #[test]
1411 fn test_iterator_take() {
1412     let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19];
1413     let ys = [0, 1, 2, 3, 5];
1414
1415     let mut it = xs.iter().take(ys.len());
1416     let mut i = 0;
1417     assert_eq!(it.len(), ys.len());
1418     while let Some(&x) = it.next() {
1419         assert_eq!(x, ys[i]);
1420         i += 1;
1421         assert_eq!(it.len(), ys.len() - i);
1422     }
1423     assert_eq!(i, ys.len());
1424     assert_eq!(it.len(), 0);
1425
1426     let mut it = xs.iter().take(ys.len());
1427     let mut i = 0;
1428     assert_eq!(it.len(), ys.len());
1429     while let Some(&x) = it.next_back() {
1430         i += 1;
1431         assert_eq!(x, ys[ys.len() - i]);
1432         assert_eq!(it.len(), ys.len() - i);
1433     }
1434     assert_eq!(i, ys.len());
1435     assert_eq!(it.len(), 0);
1436 }
1437
1438 #[test]
1439 fn test_iterator_take_nth() {
1440     let xs = [0, 1, 2, 4, 5];
1441     let mut it = xs.iter();
1442     {
1443         let mut take = it.by_ref().take(3);
1444         let mut i = 0;
1445         while let Some(&x) = take.nth(0) {
1446             assert_eq!(x, i);
1447             i += 1;
1448         }
1449     }
1450     assert_eq!(it.nth(1), Some(&5));
1451     assert_eq!(it.nth(0), None);
1452
1453     let xs = [0, 1, 2, 3, 4];
1454     let mut it = xs.iter().take(7);
1455     let mut i = 1;
1456     while let Some(&x) = it.nth(1) {
1457         assert_eq!(x, i);
1458         i += 2;
1459     }
1460 }
1461
1462 #[test]
1463 fn test_iterator_take_nth_back() {
1464     let xs = [0, 1, 2, 4, 5];
1465     let mut it = xs.iter();
1466     {
1467         let mut take = it.by_ref().take(3);
1468         let mut i = 0;
1469         while let Some(&x) = take.nth_back(0) {
1470             i += 1;
1471             assert_eq!(x, 3 - i);
1472         }
1473     }
1474     assert_eq!(it.nth_back(0), None);
1475
1476     let xs = [0, 1, 2, 3, 4];
1477     let mut it = xs.iter().take(7);
1478     assert_eq!(it.nth_back(1), Some(&3));
1479     assert_eq!(it.nth_back(1), Some(&1));
1480     assert_eq!(it.nth_back(1), None);
1481 }
1482
1483 #[test]
1484 fn test_iterator_take_short() {
1485     let xs = [0, 1, 2, 3];
1486
1487     let mut it = xs.iter().take(5);
1488     let mut i = 0;
1489     assert_eq!(it.len(), xs.len());
1490     while let Some(&x) = it.next() {
1491         assert_eq!(x, xs[i]);
1492         i += 1;
1493         assert_eq!(it.len(), xs.len() - i);
1494     }
1495     assert_eq!(i, xs.len());
1496     assert_eq!(it.len(), 0);
1497
1498     let mut it = xs.iter().take(5);
1499     let mut i = 0;
1500     assert_eq!(it.len(), xs.len());
1501     while let Some(&x) = it.next_back() {
1502         i += 1;
1503         assert_eq!(x, xs[xs.len() - i]);
1504         assert_eq!(it.len(), xs.len() - i);
1505     }
1506     assert_eq!(i, xs.len());
1507     assert_eq!(it.len(), 0);
1508 }
1509
1510 #[test]
1511 fn test_iterator_scan() {
1512     // test the type inference
1513     fn add(old: &mut isize, new: &usize) -> Option<f64> {
1514         *old += *new as isize;
1515         Some(*old as f64)
1516     }
1517     let xs = [0, 1, 2, 3, 4];
1518     let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
1519
1520     let it = xs.iter().scan(0, add);
1521     let mut i = 0;
1522     for x in it {
1523         assert_eq!(x, ys[i]);
1524         i += 1;
1525     }
1526     assert_eq!(i, ys.len());
1527 }
1528
1529 #[test]
1530 fn test_iterator_flat_map() {
1531     let xs = [0, 3, 6];
1532     let ys = [0, 1, 2, 3, 4, 5, 6, 7, 8];
1533     let it = xs.iter().flat_map(|&x| (x..).step_by(1).take(3));
1534     let mut i = 0;
1535     for x in it {
1536         assert_eq!(x, ys[i]);
1537         i += 1;
1538     }
1539     assert_eq!(i, ys.len());
1540 }
1541
1542 /// Tests `FlatMap::fold` with items already picked off the front and back,
1543 /// to make sure all parts of the `FlatMap` are folded correctly.
1544 #[test]
1545 fn test_iterator_flat_map_fold() {
1546     let xs = [0, 3, 6];
1547     let ys = [1, 2, 3, 4, 5, 6, 7];
1548     let mut it = xs.iter().flat_map(|&x| x..x + 3);
1549     assert_eq!(it.next(), Some(0));
1550     assert_eq!(it.next_back(), Some(8));
1551     let i = it.fold(0, |i, x| {
1552         assert_eq!(x, ys[i]);
1553         i + 1
1554     });
1555     assert_eq!(i, ys.len());
1556
1557     let mut it = xs.iter().flat_map(|&x| x..x + 3);
1558     assert_eq!(it.next(), Some(0));
1559     assert_eq!(it.next_back(), Some(8));
1560     let i = it.rfold(ys.len(), |i, x| {
1561         assert_eq!(x, ys[i - 1]);
1562         i - 1
1563     });
1564     assert_eq!(i, 0);
1565 }
1566
1567 #[test]
1568 fn test_iterator_flatten() {
1569     let xs = [0, 3, 6];
1570     let ys = [0, 1, 2, 3, 4, 5, 6, 7, 8];
1571     let it = xs.iter().map(|&x| (x..).step_by(1).take(3)).flatten();
1572     let mut i = 0;
1573     for x in it {
1574         assert_eq!(x, ys[i]);
1575         i += 1;
1576     }
1577     assert_eq!(i, ys.len());
1578 }
1579
1580 /// Tests `Flatten::fold` with items already picked off the front and back,
1581 /// to make sure all parts of the `Flatten` are folded correctly.
1582 #[test]
1583 fn test_iterator_flatten_fold() {
1584     let xs = [0, 3, 6];
1585     let ys = [1, 2, 3, 4, 5, 6, 7];
1586     let mut it = xs.iter().map(|&x| x..x + 3).flatten();
1587     assert_eq!(it.next(), Some(0));
1588     assert_eq!(it.next_back(), Some(8));
1589     let i = it.fold(0, |i, x| {
1590         assert_eq!(x, ys[i]);
1591         i + 1
1592     });
1593     assert_eq!(i, ys.len());
1594
1595     let mut it = xs.iter().map(|&x| x..x + 3).flatten();
1596     assert_eq!(it.next(), Some(0));
1597     assert_eq!(it.next_back(), Some(8));
1598     let i = it.rfold(ys.len(), |i, x| {
1599         assert_eq!(x, ys[i - 1]);
1600         i - 1
1601     });
1602     assert_eq!(i, 0);
1603 }
1604
1605 #[test]
1606 fn test_inspect() {
1607     let xs = [1, 2, 3, 4];
1608     let mut n = 0;
1609
1610     let ys = xs.iter().cloned().inspect(|_| n += 1).collect::<Vec<usize>>();
1611
1612     assert_eq!(n, xs.len());
1613     assert_eq!(&xs[..], &ys[..]);
1614 }
1615
1616 #[test]
1617 fn test_inspect_fold() {
1618     let xs = [1, 2, 3, 4];
1619     let mut n = 0;
1620     {
1621         let it = xs.iter().inspect(|_| n += 1);
1622         let i = it.fold(0, |i, &x| {
1623             assert_eq!(x, xs[i]);
1624             i + 1
1625         });
1626         assert_eq!(i, xs.len());
1627     }
1628     assert_eq!(n, xs.len());
1629
1630     let mut n = 0;
1631     {
1632         let it = xs.iter().inspect(|_| n += 1);
1633         let i = it.rfold(xs.len(), |i, &x| {
1634             assert_eq!(x, xs[i - 1]);
1635             i - 1
1636         });
1637         assert_eq!(i, 0);
1638     }
1639     assert_eq!(n, xs.len());
1640 }
1641
1642 #[test]
1643 fn test_cycle() {
1644     let cycle_len = 3;
1645     let it = (0..).step_by(1).take(cycle_len).cycle();
1646     assert_eq!(it.size_hint(), (usize::MAX, None));
1647     for (i, x) in it.take(100).enumerate() {
1648         assert_eq!(i % cycle_len, x);
1649     }
1650
1651     let mut it = (0..).step_by(1).take(0).cycle();
1652     assert_eq!(it.size_hint(), (0, Some(0)));
1653     assert_eq!(it.next(), None);
1654
1655     assert_eq!(empty::<i32>().cycle().fold(0, |acc, x| acc + x), 0);
1656
1657     assert_eq!(once(1).cycle().skip(1).take(4).fold(0, |acc, x| acc + x), 4);
1658
1659     assert_eq!((0..10).cycle().take(5).sum::<i32>(), 10);
1660     assert_eq!((0..10).cycle().take(15).sum::<i32>(), 55);
1661     assert_eq!((0..10).cycle().take(25).sum::<i32>(), 100);
1662
1663     let mut iter = (0..10).cycle();
1664     iter.nth(14);
1665     assert_eq!(iter.take(8).sum::<i32>(), 38);
1666
1667     let mut iter = (0..10).cycle();
1668     iter.nth(9);
1669     assert_eq!(iter.take(3).sum::<i32>(), 3);
1670 }
1671
1672 #[test]
1673 fn test_iterator_nth() {
1674     let v: &[_] = &[0, 1, 2, 3, 4];
1675     for i in 0..v.len() {
1676         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
1677     }
1678     assert_eq!(v.iter().nth(v.len()), None);
1679 }
1680
1681 #[test]
1682 fn test_iterator_nth_back() {
1683     let v: &[_] = &[0, 1, 2, 3, 4];
1684     for i in 0..v.len() {
1685         assert_eq!(v.iter().nth_back(i).unwrap(), &v[v.len() - 1 - i]);
1686     }
1687     assert_eq!(v.iter().nth_back(v.len()), None);
1688 }
1689
1690 #[test]
1691 fn test_iterator_rev_nth_back() {
1692     let v: &[_] = &[0, 1, 2, 3, 4];
1693     for i in 0..v.len() {
1694         assert_eq!(v.iter().rev().nth_back(i).unwrap(), &v[i]);
1695     }
1696     assert_eq!(v.iter().rev().nth_back(v.len()), None);
1697 }
1698
1699 #[test]
1700 fn test_iterator_rev_nth() {
1701     let v: &[_] = &[0, 1, 2, 3, 4];
1702     for i in 0..v.len() {
1703         assert_eq!(v.iter().rev().nth(i).unwrap(), &v[v.len() - 1 - i]);
1704     }
1705     assert_eq!(v.iter().rev().nth(v.len()), None);
1706 }
1707
1708 #[test]
1709 fn test_iterator_advance_by() {
1710     let v: &[_] = &[0, 1, 2, 3, 4];
1711
1712     for i in 0..v.len() {
1713         let mut iter = v.iter();
1714         assert_eq!(iter.advance_by(i), Ok(()));
1715         assert_eq!(iter.next().unwrap(), &v[i]);
1716         assert_eq!(iter.advance_by(100), Err(v.len() - 1 - i));
1717     }
1718
1719     assert_eq!(v.iter().advance_by(v.len()), Ok(()));
1720     assert_eq!(v.iter().advance_by(100), Err(v.len()));
1721 }
1722
1723 #[test]
1724 fn test_iterator_advance_back_by() {
1725     let v: &[_] = &[0, 1, 2, 3, 4];
1726
1727     for i in 0..v.len() {
1728         let mut iter = v.iter();
1729         assert_eq!(iter.advance_back_by(i), Ok(()));
1730         assert_eq!(iter.next_back().unwrap(), &v[v.len() - 1 - i]);
1731         assert_eq!(iter.advance_back_by(100), Err(v.len() - 1 - i));
1732     }
1733
1734     assert_eq!(v.iter().advance_back_by(v.len()), Ok(()));
1735     assert_eq!(v.iter().advance_back_by(100), Err(v.len()));
1736 }
1737
1738 #[test]
1739 fn test_iterator_rev_advance_by() {
1740     let v: &[_] = &[0, 1, 2, 3, 4];
1741
1742     for i in 0..v.len() {
1743         let mut iter = v.iter().rev();
1744         assert_eq!(iter.advance_by(i), Ok(()));
1745         assert_eq!(iter.next().unwrap(), &v[v.len() - 1 - i]);
1746         assert_eq!(iter.advance_by(100), Err(v.len() - 1 - i));
1747     }
1748
1749     assert_eq!(v.iter().rev().advance_by(v.len()), Ok(()));
1750     assert_eq!(v.iter().rev().advance_by(100), Err(v.len()));
1751 }
1752
1753 #[test]
1754 fn test_iterator_rev_advance_back_by() {
1755     let v: &[_] = &[0, 1, 2, 3, 4];
1756
1757     for i in 0..v.len() {
1758         let mut iter = v.iter().rev();
1759         assert_eq!(iter.advance_back_by(i), Ok(()));
1760         assert_eq!(iter.next_back().unwrap(), &v[i]);
1761         assert_eq!(iter.advance_back_by(100), Err(v.len() - 1 - i));
1762     }
1763
1764     assert_eq!(v.iter().rev().advance_back_by(v.len()), Ok(()));
1765     assert_eq!(v.iter().rev().advance_back_by(100), Err(v.len()));
1766 }
1767
1768 #[test]
1769 fn test_iterator_last() {
1770     let v: &[_] = &[0, 1, 2, 3, 4];
1771     assert_eq!(v.iter().last().unwrap(), &4);
1772     assert_eq!(v[..1].iter().last().unwrap(), &0);
1773 }
1774
1775 #[test]
1776 fn test_iterator_len() {
1777     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1778     assert_eq!(v[..4].iter().count(), 4);
1779     assert_eq!(v[..10].iter().count(), 10);
1780     assert_eq!(v[..0].iter().count(), 0);
1781 }
1782
1783 #[test]
1784 fn test_iterator_sum() {
1785     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1786     assert_eq!(v[..4].iter().cloned().sum::<i32>(), 6);
1787     assert_eq!(v.iter().cloned().sum::<i32>(), 55);
1788     assert_eq!(v[..0].iter().cloned().sum::<i32>(), 0);
1789 }
1790
1791 #[test]
1792 fn test_iterator_sum_result() {
1793     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1794     assert_eq!(v.iter().cloned().sum::<Result<i32, _>>(), Ok(10));
1795     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1796     assert_eq!(v.iter().cloned().sum::<Result<i32, _>>(), Err(()));
1797
1798     #[derive(PartialEq, Debug)]
1799     struct S(Result<i32, ()>);
1800
1801     impl Sum<Result<i32, ()>> for S {
1802         fn sum<I: Iterator<Item = Result<i32, ()>>>(mut iter: I) -> Self {
1803             // takes the sum by repeatedly calling `next` on `iter`,
1804             // thus testing that repeated calls to `ResultShunt::try_fold`
1805             // produce the expected results
1806             Self(iter.by_ref().sum())
1807         }
1808     }
1809
1810     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1811     assert_eq!(v.iter().cloned().sum::<S>(), S(Ok(10)));
1812     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1813     assert_eq!(v.iter().cloned().sum::<S>(), S(Err(())));
1814 }
1815
1816 #[test]
1817 fn test_iterator_sum_option() {
1818     let v: &[Option<i32>] = &[Some(1), Some(2), Some(3), Some(4)];
1819     assert_eq!(v.iter().cloned().sum::<Option<i32>>(), Some(10));
1820     let v: &[Option<i32>] = &[Some(1), None, Some(3), Some(4)];
1821     assert_eq!(v.iter().cloned().sum::<Option<i32>>(), None);
1822 }
1823
1824 #[test]
1825 fn test_iterator_product() {
1826     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1827     assert_eq!(v[..4].iter().cloned().product::<i32>(), 0);
1828     assert_eq!(v[1..5].iter().cloned().product::<i32>(), 24);
1829     assert_eq!(v[..0].iter().cloned().product::<i32>(), 1);
1830 }
1831
1832 #[test]
1833 fn test_iterator_product_result() {
1834     let v: &[Result<i32, ()>] = &[Ok(1), Ok(2), Ok(3), Ok(4)];
1835     assert_eq!(v.iter().cloned().product::<Result<i32, _>>(), Ok(24));
1836     let v: &[Result<i32, ()>] = &[Ok(1), Err(()), Ok(3), Ok(4)];
1837     assert_eq!(v.iter().cloned().product::<Result<i32, _>>(), Err(()));
1838 }
1839
1840 /// A wrapper struct that implements `Eq` and `Ord` based on the wrapped
1841 /// integer modulo 3. Used to test that `Iterator::max` and `Iterator::min`
1842 /// return the correct element if some of them are equal.
1843 #[derive(Debug)]
1844 struct Mod3(i32);
1845
1846 impl PartialEq for Mod3 {
1847     fn eq(&self, other: &Self) -> bool {
1848         self.0 % 3 == other.0 % 3
1849     }
1850 }
1851
1852 impl Eq for Mod3 {}
1853
1854 impl PartialOrd for Mod3 {
1855     fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1856         Some(self.cmp(other))
1857     }
1858 }
1859
1860 impl Ord for Mod3 {
1861     fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1862         (self.0 % 3).cmp(&(other.0 % 3))
1863     }
1864 }
1865
1866 #[test]
1867 fn test_iterator_product_option() {
1868     let v: &[Option<i32>] = &[Some(1), Some(2), Some(3), Some(4)];
1869     assert_eq!(v.iter().cloned().product::<Option<i32>>(), Some(24));
1870     let v: &[Option<i32>] = &[Some(1), None, Some(3), Some(4)];
1871     assert_eq!(v.iter().cloned().product::<Option<i32>>(), None);
1872 }
1873
1874 #[test]
1875 fn test_iterator_max() {
1876     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1877     assert_eq!(v[..4].iter().cloned().max(), Some(3));
1878     assert_eq!(v.iter().cloned().max(), Some(10));
1879     assert_eq!(v[..0].iter().cloned().max(), None);
1880     assert_eq!(v.iter().cloned().map(Mod3).max().map(|x| x.0), Some(8));
1881 }
1882
1883 #[test]
1884 fn test_iterator_min() {
1885     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1886     assert_eq!(v[..4].iter().cloned().min(), Some(0));
1887     assert_eq!(v.iter().cloned().min(), Some(0));
1888     assert_eq!(v[..0].iter().cloned().min(), None);
1889     assert_eq!(v.iter().cloned().map(Mod3).min().map(|x| x.0), Some(0));
1890 }
1891
1892 #[test]
1893 fn test_iterator_size_hint() {
1894     let c = (0..).step_by(1);
1895     let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
1896     let v2 = &[10, 11, 12];
1897     let vi = v.iter();
1898
1899     assert_eq!((0..).size_hint(), (usize::MAX, None));
1900     assert_eq!(c.size_hint(), (usize::MAX, None));
1901     assert_eq!(vi.clone().size_hint(), (10, Some(10)));
1902
1903     assert_eq!(c.clone().take(5).size_hint(), (5, Some(5)));
1904     assert_eq!(c.clone().skip(5).size_hint().1, None);
1905     assert_eq!(c.clone().take_while(|_| false).size_hint(), (0, None));
1906     assert_eq!(c.clone().map_while(|_| None::<()>).size_hint(), (0, None));
1907     assert_eq!(c.clone().skip_while(|_| false).size_hint(), (0, None));
1908     assert_eq!(c.clone().enumerate().size_hint(), (usize::MAX, None));
1909     assert_eq!(c.clone().chain(vi.clone().cloned()).size_hint(), (usize::MAX, None));
1910     assert_eq!(c.clone().zip(vi.clone()).size_hint(), (10, Some(10)));
1911     assert_eq!(c.clone().scan(0, |_, _| Some(0)).size_hint(), (0, None));
1912     assert_eq!(c.clone().filter(|_| false).size_hint(), (0, None));
1913     assert_eq!(c.clone().map(|_| 0).size_hint(), (usize::MAX, None));
1914     assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
1915
1916     assert_eq!(vi.clone().take(5).size_hint(), (5, Some(5)));
1917     assert_eq!(vi.clone().take(12).size_hint(), (10, Some(10)));
1918     assert_eq!(vi.clone().skip(3).size_hint(), (7, Some(7)));
1919     assert_eq!(vi.clone().skip(12).size_hint(), (0, Some(0)));
1920     assert_eq!(vi.clone().take_while(|_| false).size_hint(), (0, Some(10)));
1921     assert_eq!(vi.clone().map_while(|_| None::<()>).size_hint(), (0, Some(10)));
1922     assert_eq!(vi.clone().skip_while(|_| false).size_hint(), (0, Some(10)));
1923     assert_eq!(vi.clone().enumerate().size_hint(), (10, Some(10)));
1924     assert_eq!(vi.clone().chain(v2).size_hint(), (13, Some(13)));
1925     assert_eq!(vi.clone().zip(v2).size_hint(), (3, Some(3)));
1926     assert_eq!(vi.clone().scan(0, |_, _| Some(0)).size_hint(), (0, Some(10)));
1927     assert_eq!(vi.clone().filter(|_| false).size_hint(), (0, Some(10)));
1928     assert_eq!(vi.clone().map(|&i| i + 1).size_hint(), (10, Some(10)));
1929     assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
1930 }
1931
1932 #[test]
1933 fn test_collect() {
1934     let a = vec![1, 2, 3, 4, 5];
1935     let b: Vec<isize> = a.iter().cloned().collect();
1936     assert!(a == b);
1937 }
1938
1939 #[test]
1940 fn test_all() {
1941     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1942     assert!(v.iter().all(|&x| x < 10));
1943     assert!(!v.iter().all(|&x| x % 2 == 0));
1944     assert!(!v.iter().all(|&x| x > 100));
1945     assert!(v[..0].iter().all(|_| panic!()));
1946 }
1947
1948 #[test]
1949 fn test_any() {
1950     let v: Box<[isize]> = Box::new([1, 2, 3, 4, 5]);
1951     assert!(v.iter().any(|&x| x < 10));
1952     assert!(v.iter().any(|&x| x % 2 == 0));
1953     assert!(!v.iter().any(|&x| x > 100));
1954     assert!(!v[..0].iter().any(|_| panic!()));
1955 }
1956
1957 #[test]
1958 fn test_find() {
1959     let v: &[isize] = &[1, 3, 9, 27, 103, 14, 11];
1960     assert_eq!(*v.iter().find(|&&x| x & 1 == 0).unwrap(), 14);
1961     assert_eq!(*v.iter().find(|&&x| x % 3 == 0).unwrap(), 3);
1962     assert!(v.iter().find(|&&x| x % 12 == 0).is_none());
1963 }
1964
1965 #[test]
1966 fn test_find_map() {
1967     let xs: &[isize] = &[];
1968     assert_eq!(xs.iter().find_map(half_if_even), None);
1969     let xs: &[isize] = &[3, 5];
1970     assert_eq!(xs.iter().find_map(half_if_even), None);
1971     let xs: &[isize] = &[4, 5];
1972     assert_eq!(xs.iter().find_map(half_if_even), Some(2));
1973     let xs: &[isize] = &[3, 6];
1974     assert_eq!(xs.iter().find_map(half_if_even), Some(3));
1975
1976     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1977     let mut iter = xs.iter();
1978     assert_eq!(iter.find_map(half_if_even), Some(1));
1979     assert_eq!(iter.find_map(half_if_even), Some(2));
1980     assert_eq!(iter.find_map(half_if_even), Some(3));
1981     assert_eq!(iter.next(), Some(&7));
1982
1983     fn half_if_even(x: &isize) -> Option<isize> {
1984         if x % 2 == 0 { Some(x / 2) } else { None }
1985     }
1986 }
1987
1988 #[test]
1989 fn test_try_find() {
1990     let xs: &[isize] = &[];
1991     assert_eq!(xs.iter().try_find(testfn), Ok(None));
1992     let xs: &[isize] = &[1, 2, 3, 4];
1993     assert_eq!(xs.iter().try_find(testfn), Ok(Some(&2)));
1994     let xs: &[isize] = &[1, 3, 4];
1995     assert_eq!(xs.iter().try_find(testfn), Err(()));
1996
1997     let xs: &[isize] = &[1, 2, 3, 4, 5, 6, 7];
1998     let mut iter = xs.iter();
1999     assert_eq!(iter.try_find(testfn), Ok(Some(&2)));
2000     assert_eq!(iter.try_find(testfn), Err(()));
2001     assert_eq!(iter.next(), Some(&5));
2002
2003     fn testfn(x: &&isize) -> Result<bool, ()> {
2004         if **x == 2 {
2005             return Ok(true);
2006         }
2007         if **x == 4 {
2008             return Err(());
2009         }
2010         Ok(false)
2011     }
2012 }
2013
2014 #[test]
2015 fn test_try_find_api_usability() -> Result<(), Box<dyn std::error::Error>> {
2016     let a = ["1", "2"];
2017
2018     let is_my_num = |s: &str, search: i32| -> Result<bool, std::num::ParseIntError> {
2019         Ok(s.parse::<i32>()? == search)
2020     };
2021
2022     let val = a.iter().try_find(|&&s| is_my_num(s, 2))?;
2023     assert_eq!(val, Some(&"2"));
2024
2025     Ok(())
2026 }
2027
2028 #[test]
2029 fn test_position() {
2030     let v = &[1, 3, 9, 27, 103, 14, 11];
2031     assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2032     assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2033     assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2034 }
2035
2036 #[test]
2037 fn test_count() {
2038     let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2039     assert_eq!(xs.iter().filter(|x| **x == 2).count(), 3);
2040     assert_eq!(xs.iter().filter(|x| **x == 5).count(), 1);
2041     assert_eq!(xs.iter().filter(|x| **x == 95).count(), 0);
2042 }
2043
2044 #[test]
2045 fn test_max_by_key() {
2046     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2047     assert_eq!(*xs.iter().max_by_key(|x| x.abs()).unwrap(), -10);
2048 }
2049
2050 #[test]
2051 fn test_max_by() {
2052     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2053     assert_eq!(*xs.iter().max_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), -10);
2054 }
2055
2056 #[test]
2057 fn test_min_by_key() {
2058     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2059     assert_eq!(*xs.iter().min_by_key(|x| x.abs()).unwrap(), 0);
2060 }
2061
2062 #[test]
2063 fn test_min_by() {
2064     let xs: &[isize] = &[-3, 0, 1, 5, -10];
2065     assert_eq!(*xs.iter().min_by(|x, y| x.abs().cmp(&y.abs())).unwrap(), 0);
2066 }
2067
2068 #[test]
2069 fn test_by_ref() {
2070     let mut xs = 0..10;
2071     // sum the first five values
2072     let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2073     assert_eq!(partial_sum, 10);
2074     assert_eq!(xs.next(), Some(5));
2075 }
2076
2077 #[test]
2078 fn test_rev() {
2079     let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2080     let mut it = xs.iter();
2081     it.next();
2082     it.next();
2083     assert!(it.rev().cloned().collect::<Vec<isize>>() == vec![16, 14, 12, 10, 8, 6]);
2084 }
2085
2086 #[test]
2087 fn test_copied() {
2088     let xs = [2, 4, 6, 8];
2089
2090     let mut it = xs.iter().copied();
2091     assert_eq!(it.len(), 4);
2092     assert_eq!(it.next(), Some(2));
2093     assert_eq!(it.len(), 3);
2094     assert_eq!(it.next(), Some(4));
2095     assert_eq!(it.len(), 2);
2096     assert_eq!(it.next_back(), Some(8));
2097     assert_eq!(it.len(), 1);
2098     assert_eq!(it.next_back(), Some(6));
2099     assert_eq!(it.len(), 0);
2100     assert_eq!(it.next_back(), None);
2101 }
2102
2103 #[test]
2104 fn test_cloned() {
2105     let xs = [2, 4, 6, 8];
2106
2107     let mut it = xs.iter().cloned();
2108     assert_eq!(it.len(), 4);
2109     assert_eq!(it.next(), Some(2));
2110     assert_eq!(it.len(), 3);
2111     assert_eq!(it.next(), Some(4));
2112     assert_eq!(it.len(), 2);
2113     assert_eq!(it.next_back(), Some(8));
2114     assert_eq!(it.len(), 1);
2115     assert_eq!(it.next_back(), Some(6));
2116     assert_eq!(it.len(), 0);
2117     assert_eq!(it.next_back(), None);
2118 }
2119
2120 #[test]
2121 fn test_cloned_side_effects() {
2122     let mut count = 0;
2123     {
2124         let iter = [1, 2, 3]
2125             .iter()
2126             .map(|x| {
2127                 count += 1;
2128                 x
2129             })
2130             .cloned()
2131             .zip(&[1]);
2132         for _ in iter {}
2133     }
2134     assert_eq!(count, 2);
2135 }
2136
2137 #[test]
2138 fn test_double_ended_map() {
2139     let xs = [1, 2, 3, 4, 5, 6];
2140     let mut it = xs.iter().map(|&x| x * -1);
2141     assert_eq!(it.next(), Some(-1));
2142     assert_eq!(it.next(), Some(-2));
2143     assert_eq!(it.next_back(), Some(-6));
2144     assert_eq!(it.next_back(), Some(-5));
2145     assert_eq!(it.next(), Some(-3));
2146     assert_eq!(it.next_back(), Some(-4));
2147     assert_eq!(it.next(), None);
2148 }
2149
2150 #[test]
2151 fn test_double_ended_enumerate() {
2152     let xs = [1, 2, 3, 4, 5, 6];
2153     let mut it = xs.iter().cloned().enumerate();
2154     assert_eq!(it.next(), Some((0, 1)));
2155     assert_eq!(it.next(), Some((1, 2)));
2156     assert_eq!(it.next_back(), Some((5, 6)));
2157     assert_eq!(it.next_back(), Some((4, 5)));
2158     assert_eq!(it.next_back(), Some((3, 4)));
2159     assert_eq!(it.next_back(), Some((2, 3)));
2160     assert_eq!(it.next(), None);
2161 }
2162
2163 #[test]
2164 fn test_double_ended_zip() {
2165     let xs = [1, 2, 3, 4, 5, 6];
2166     let ys = [1, 2, 3, 7];
2167     let a = xs.iter().cloned();
2168     let b = ys.iter().cloned();
2169     let mut it = a.zip(b);
2170     assert_eq!(it.next(), Some((1, 1)));
2171     assert_eq!(it.next(), Some((2, 2)));
2172     assert_eq!(it.next_back(), Some((4, 7)));
2173     assert_eq!(it.next_back(), Some((3, 3)));
2174     assert_eq!(it.next(), None);
2175 }
2176
2177 #[test]
2178 fn test_double_ended_filter() {
2179     let xs = [1, 2, 3, 4, 5, 6];
2180     let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2181     assert_eq!(it.next_back().unwrap(), &6);
2182     assert_eq!(it.next_back().unwrap(), &4);
2183     assert_eq!(it.next().unwrap(), &2);
2184     assert_eq!(it.next_back(), None);
2185 }
2186
2187 #[test]
2188 fn test_double_ended_filter_map() {
2189     let xs = [1, 2, 3, 4, 5, 6];
2190     let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2191     assert_eq!(it.next_back().unwrap(), 12);
2192     assert_eq!(it.next_back().unwrap(), 8);
2193     assert_eq!(it.next().unwrap(), 4);
2194     assert_eq!(it.next_back(), None);
2195 }
2196
2197 #[test]
2198 fn test_double_ended_chain() {
2199     let xs = [1, 2, 3, 4, 5];
2200     let ys = [7, 9, 11];
2201     let mut it = xs.iter().chain(&ys).rev();
2202     assert_eq!(it.next().unwrap(), &11);
2203     assert_eq!(it.next().unwrap(), &9);
2204     assert_eq!(it.next_back().unwrap(), &1);
2205     assert_eq!(it.next_back().unwrap(), &2);
2206     assert_eq!(it.next_back().unwrap(), &3);
2207     assert_eq!(it.next_back().unwrap(), &4);
2208     assert_eq!(it.next_back().unwrap(), &5);
2209     assert_eq!(it.next_back().unwrap(), &7);
2210     assert_eq!(it.next_back(), None);
2211
2212     // test that .chain() is well behaved with an unfused iterator
2213     struct CrazyIterator(bool);
2214     impl CrazyIterator {
2215         fn new() -> CrazyIterator {
2216             CrazyIterator(false)
2217         }
2218     }
2219     impl Iterator for CrazyIterator {
2220         type Item = i32;
2221         fn next(&mut self) -> Option<i32> {
2222             if self.0 {
2223                 Some(99)
2224             } else {
2225                 self.0 = true;
2226                 None
2227             }
2228         }
2229     }
2230
2231     impl DoubleEndedIterator for CrazyIterator {
2232         fn next_back(&mut self) -> Option<i32> {
2233             self.next()
2234         }
2235     }
2236
2237     assert_eq!(CrazyIterator::new().chain(0..10).rev().last(), Some(0));
2238     assert!((0..10).chain(CrazyIterator::new()).rev().any(|i| i == 0));
2239 }
2240
2241 #[test]
2242 fn test_rposition() {
2243     fn f(xy: &(isize, char)) -> bool {
2244         let (_x, y) = *xy;
2245         y == 'b'
2246     }
2247     fn g(xy: &(isize, char)) -> bool {
2248         let (_x, y) = *xy;
2249         y == 'd'
2250     }
2251     let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2252
2253     assert_eq!(v.iter().rposition(f), Some(3));
2254     assert!(v.iter().rposition(g).is_none());
2255 }
2256
2257 #[test]
2258 fn test_rev_rposition() {
2259     let v = [0, 0, 1, 1];
2260     assert_eq!(v.iter().rev().rposition(|&x| x == 1), Some(1));
2261 }
2262
2263 #[test]
2264 #[should_panic]
2265 fn test_rposition_panic() {
2266     let v: [(Box<_>, Box<_>); 4] = [(box 0, box 0), (box 0, box 0), (box 0, box 0), (box 0, box 0)];
2267     let mut i = 0;
2268     v.iter().rposition(|_elt| {
2269         if i == 2 {
2270             panic!()
2271         }
2272         i += 1;
2273         false
2274     });
2275 }
2276
2277 #[test]
2278 fn test_double_ended_flat_map() {
2279     let u = [0, 1];
2280     let v = [5, 6, 7, 8];
2281     let mut it = u.iter().flat_map(|x| &v[*x..v.len()]);
2282     assert_eq!(it.next_back().unwrap(), &8);
2283     assert_eq!(it.next().unwrap(), &5);
2284     assert_eq!(it.next_back().unwrap(), &7);
2285     assert_eq!(it.next_back().unwrap(), &6);
2286     assert_eq!(it.next_back().unwrap(), &8);
2287     assert_eq!(it.next().unwrap(), &6);
2288     assert_eq!(it.next_back().unwrap(), &7);
2289     assert_eq!(it.next_back(), None);
2290     assert_eq!(it.next(), None);
2291     assert_eq!(it.next_back(), None);
2292 }
2293
2294 #[test]
2295 fn test_double_ended_flatten() {
2296     let u = [0, 1];
2297     let v = [5, 6, 7, 8];
2298     let mut it = u.iter().map(|x| &v[*x..v.len()]).flatten();
2299     assert_eq!(it.next_back().unwrap(), &8);
2300     assert_eq!(it.next().unwrap(), &5);
2301     assert_eq!(it.next_back().unwrap(), &7);
2302     assert_eq!(it.next_back().unwrap(), &6);
2303     assert_eq!(it.next_back().unwrap(), &8);
2304     assert_eq!(it.next().unwrap(), &6);
2305     assert_eq!(it.next_back().unwrap(), &7);
2306     assert_eq!(it.next_back(), None);
2307     assert_eq!(it.next(), None);
2308     assert_eq!(it.next_back(), None);
2309 }
2310
2311 #[test]
2312 fn test_double_ended_range() {
2313     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
2314     for _ in (10..0).rev() {
2315         panic!("unreachable");
2316     }
2317
2318     assert_eq!((11..14).rev().collect::<Vec<_>>(), [13, 12, 11]);
2319     for _ in (10..0).rev() {
2320         panic!("unreachable");
2321     }
2322 }
2323
2324 #[test]
2325 fn test_range() {
2326     assert_eq!((0..5).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
2327     assert_eq!((-10..-1).collect::<Vec<_>>(), [-10, -9, -8, -7, -6, -5, -4, -3, -2]);
2328     assert_eq!((0..5).rev().collect::<Vec<_>>(), [4, 3, 2, 1, 0]);
2329     assert_eq!((200..-5).count(), 0);
2330     assert_eq!((200..-5).rev().count(), 0);
2331     assert_eq!((200..200).count(), 0);
2332     assert_eq!((200..200).rev().count(), 0);
2333
2334     assert_eq!((0..100).size_hint(), (100, Some(100)));
2335     // this test is only meaningful when sizeof usize < sizeof u64
2336     assert_eq!((usize::MAX - 1..usize::MAX).size_hint(), (1, Some(1)));
2337     assert_eq!((-10..-1).size_hint(), (9, Some(9)));
2338     assert_eq!((-1..-10).size_hint(), (0, Some(0)));
2339
2340     assert_eq!((-70..58).size_hint(), (128, Some(128)));
2341     assert_eq!((-128..127).size_hint(), (255, Some(255)));
2342     assert_eq!(
2343         (-2..isize::MAX).size_hint(),
2344         (isize::MAX as usize + 2, Some(isize::MAX as usize + 2))
2345     );
2346 }
2347
2348 #[test]
2349 fn test_char_range() {
2350     use std::char;
2351     // Miri is too slow
2352     let from = if cfg!(miri) { char::from_u32(0xD800 - 10).unwrap() } else { '\0' };
2353     let to = if cfg!(miri) { char::from_u32(0xDFFF + 10).unwrap() } else { char::MAX };
2354     assert!((from..=to).eq((from as u32..=to as u32).filter_map(char::from_u32)));
2355     assert!((from..=to).rev().eq((from as u32..=to as u32).filter_map(char::from_u32).rev()));
2356
2357     assert_eq!(('\u{D7FF}'..='\u{E000}').count(), 2);
2358     assert_eq!(('\u{D7FF}'..='\u{E000}').size_hint(), (2, Some(2)));
2359     assert_eq!(('\u{D7FF}'..'\u{E000}').count(), 1);
2360     assert_eq!(('\u{D7FF}'..'\u{E000}').size_hint(), (1, Some(1)));
2361 }
2362
2363 #[test]
2364 fn test_range_exhaustion() {
2365     let mut r = 10..10;
2366     assert!(r.is_empty());
2367     assert_eq!(r.next(), None);
2368     assert_eq!(r.next_back(), None);
2369     assert_eq!(r, 10..10);
2370
2371     let mut r = 10..12;
2372     assert_eq!(r.next(), Some(10));
2373     assert_eq!(r.next(), Some(11));
2374     assert!(r.is_empty());
2375     assert_eq!(r, 12..12);
2376     assert_eq!(r.next(), None);
2377
2378     let mut r = 10..12;
2379     assert_eq!(r.next_back(), Some(11));
2380     assert_eq!(r.next_back(), Some(10));
2381     assert!(r.is_empty());
2382     assert_eq!(r, 10..10);
2383     assert_eq!(r.next_back(), None);
2384
2385     let mut r = 100..10;
2386     assert!(r.is_empty());
2387     assert_eq!(r.next(), None);
2388     assert_eq!(r.next_back(), None);
2389     assert_eq!(r, 100..10);
2390 }
2391
2392 #[test]
2393 fn test_range_inclusive_exhaustion() {
2394     let mut r = 10..=10;
2395     assert_eq!(r.next(), Some(10));
2396     assert!(r.is_empty());
2397     assert_eq!(r.next(), None);
2398     assert_eq!(r.next(), None);
2399
2400     assert_eq!(*r.start(), 10);
2401     assert_eq!(*r.end(), 10);
2402     assert_ne!(r, 10..=10);
2403
2404     let mut r = 10..=10;
2405     assert_eq!(r.next_back(), Some(10));
2406     assert!(r.is_empty());
2407     assert_eq!(r.next_back(), None);
2408
2409     assert_eq!(*r.start(), 10);
2410     assert_eq!(*r.end(), 10);
2411     assert_ne!(r, 10..=10);
2412
2413     let mut r = 10..=12;
2414     assert_eq!(r.next(), Some(10));
2415     assert_eq!(r.next(), Some(11));
2416     assert_eq!(r.next(), Some(12));
2417     assert!(r.is_empty());
2418     assert_eq!(r.next(), None);
2419
2420     let mut r = 10..=12;
2421     assert_eq!(r.next_back(), Some(12));
2422     assert_eq!(r.next_back(), Some(11));
2423     assert_eq!(r.next_back(), Some(10));
2424     assert!(r.is_empty());
2425     assert_eq!(r.next_back(), None);
2426
2427     let mut r = 10..=12;
2428     assert_eq!(r.nth(2), Some(12));
2429     assert!(r.is_empty());
2430     assert_eq!(r.next(), None);
2431
2432     let mut r = 10..=12;
2433     assert_eq!(r.nth(5), None);
2434     assert!(r.is_empty());
2435     assert_eq!(r.next(), None);
2436
2437     let mut r = 100..=10;
2438     assert_eq!(r.next(), None);
2439     assert!(r.is_empty());
2440     assert_eq!(r.next(), None);
2441     assert_eq!(r.next(), None);
2442     assert_eq!(r, 100..=10);
2443
2444     let mut r = 100..=10;
2445     assert_eq!(r.next_back(), None);
2446     assert!(r.is_empty());
2447     assert_eq!(r.next_back(), None);
2448     assert_eq!(r.next_back(), None);
2449     assert_eq!(r, 100..=10);
2450 }
2451
2452 #[test]
2453 fn test_range_nth() {
2454     assert_eq!((10..15).nth(0), Some(10));
2455     assert_eq!((10..15).nth(1), Some(11));
2456     assert_eq!((10..15).nth(4), Some(14));
2457     assert_eq!((10..15).nth(5), None);
2458
2459     let mut r = 10..20;
2460     assert_eq!(r.nth(2), Some(12));
2461     assert_eq!(r, 13..20);
2462     assert_eq!(r.nth(2), Some(15));
2463     assert_eq!(r, 16..20);
2464     assert_eq!(r.nth(10), None);
2465     assert_eq!(r, 20..20);
2466 }
2467
2468 #[test]
2469 fn test_range_nth_back() {
2470     assert_eq!((10..15).nth_back(0), Some(14));
2471     assert_eq!((10..15).nth_back(1), Some(13));
2472     assert_eq!((10..15).nth_back(4), Some(10));
2473     assert_eq!((10..15).nth_back(5), None);
2474     assert_eq!((-120..80_i8).nth_back(199), Some(-120));
2475
2476     let mut r = 10..20;
2477     assert_eq!(r.nth_back(2), Some(17));
2478     assert_eq!(r, 10..17);
2479     assert_eq!(r.nth_back(2), Some(14));
2480     assert_eq!(r, 10..14);
2481     assert_eq!(r.nth_back(10), None);
2482     assert_eq!(r, 10..10);
2483 }
2484
2485 #[test]
2486 fn test_range_from_nth() {
2487     assert_eq!((10..).nth(0), Some(10));
2488     assert_eq!((10..).nth(1), Some(11));
2489     assert_eq!((10..).nth(4), Some(14));
2490
2491     let mut r = 10..;
2492     assert_eq!(r.nth(2), Some(12));
2493     assert_eq!(r, 13..);
2494     assert_eq!(r.nth(2), Some(15));
2495     assert_eq!(r, 16..);
2496     assert_eq!(r.nth(10), Some(26));
2497     assert_eq!(r, 27..);
2498
2499     assert_eq!((0..).size_hint(), (usize::MAX, None));
2500 }
2501
2502 fn is_trusted_len<I: TrustedLen>(_: I) {}
2503
2504 #[test]
2505 fn test_range_from_take() {
2506     let mut it = (0..).take(3);
2507     assert_eq!(it.next(), Some(0));
2508     assert_eq!(it.next(), Some(1));
2509     assert_eq!(it.next(), Some(2));
2510     assert_eq!(it.next(), None);
2511     is_trusted_len((0..).take(3));
2512     assert_eq!((0..).take(3).size_hint(), (3, Some(3)));
2513     assert_eq!((0..).take(0).size_hint(), (0, Some(0)));
2514     assert_eq!((0..).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2515 }
2516
2517 #[test]
2518 fn test_range_from_take_collect() {
2519     let v: Vec<_> = (0..).take(3).collect();
2520     assert_eq!(v, vec![0, 1, 2]);
2521 }
2522
2523 #[test]
2524 fn test_range_inclusive_nth() {
2525     assert_eq!((10..=15).nth(0), Some(10));
2526     assert_eq!((10..=15).nth(1), Some(11));
2527     assert_eq!((10..=15).nth(5), Some(15));
2528     assert_eq!((10..=15).nth(6), None);
2529
2530     let mut exhausted_via_next = 10_u8..=20;
2531     while exhausted_via_next.next().is_some() {}
2532
2533     let mut r = 10_u8..=20;
2534     assert_eq!(r.nth(2), Some(12));
2535     assert_eq!(r, 13..=20);
2536     assert_eq!(r.nth(2), Some(15));
2537     assert_eq!(r, 16..=20);
2538     assert_eq!(r.is_empty(), false);
2539     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2540     assert_eq!(r.nth(10), None);
2541     assert_eq!(r.is_empty(), true);
2542     assert_eq!(r, exhausted_via_next);
2543     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2544 }
2545
2546 #[test]
2547 fn test_range_inclusive_nth_back() {
2548     assert_eq!((10..=15).nth_back(0), Some(15));
2549     assert_eq!((10..=15).nth_back(1), Some(14));
2550     assert_eq!((10..=15).nth_back(5), Some(10));
2551     assert_eq!((10..=15).nth_back(6), None);
2552     assert_eq!((-120..=80_i8).nth_back(200), Some(-120));
2553
2554     let mut exhausted_via_next_back = 10_u8..=20;
2555     while exhausted_via_next_back.next_back().is_some() {}
2556
2557     let mut r = 10_u8..=20;
2558     assert_eq!(r.nth_back(2), Some(18));
2559     assert_eq!(r, 10..=17);
2560     assert_eq!(r.nth_back(2), Some(15));
2561     assert_eq!(r, 10..=14);
2562     assert_eq!(r.is_empty(), false);
2563     assert_eq!(ExactSizeIterator::is_empty(&r), false);
2564     assert_eq!(r.nth_back(10), None);
2565     assert_eq!(r.is_empty(), true);
2566     assert_eq!(r, exhausted_via_next_back);
2567     assert_eq!(ExactSizeIterator::is_empty(&r), true);
2568 }
2569
2570 #[test]
2571 fn test_range_len() {
2572     assert_eq!((0..10_u8).len(), 10);
2573     assert_eq!((9..10_u8).len(), 1);
2574     assert_eq!((10..10_u8).len(), 0);
2575     assert_eq!((11..10_u8).len(), 0);
2576     assert_eq!((100..10_u8).len(), 0);
2577 }
2578
2579 #[test]
2580 fn test_range_inclusive_len() {
2581     assert_eq!((0..=10_u8).len(), 11);
2582     assert_eq!((9..=10_u8).len(), 2);
2583     assert_eq!((10..=10_u8).len(), 1);
2584     assert_eq!((11..=10_u8).len(), 0);
2585     assert_eq!((100..=10_u8).len(), 0);
2586 }
2587
2588 #[test]
2589 fn test_range_step() {
2590     #![allow(deprecated)]
2591
2592     assert_eq!((0..20).step_by(5).collect::<Vec<isize>>(), [0, 5, 10, 15]);
2593     assert_eq!((1..21).rev().step_by(5).collect::<Vec<isize>>(), [20, 15, 10, 5]);
2594     assert_eq!((1..21).rev().step_by(6).collect::<Vec<isize>>(), [20, 14, 8, 2]);
2595     assert_eq!((200..255).step_by(50).collect::<Vec<u8>>(), [200, 250]);
2596     assert_eq!((200..-5).step_by(1).collect::<Vec<isize>>(), []);
2597     assert_eq!((200..200).step_by(1).collect::<Vec<isize>>(), []);
2598
2599     assert_eq!((0..20).step_by(1).size_hint(), (20, Some(20)));
2600     assert_eq!((0..20).step_by(21).size_hint(), (1, Some(1)));
2601     assert_eq!((0..20).step_by(5).size_hint(), (4, Some(4)));
2602     assert_eq!((1..21).rev().step_by(5).size_hint(), (4, Some(4)));
2603     assert_eq!((1..21).rev().step_by(6).size_hint(), (4, Some(4)));
2604     assert_eq!((20..-5).step_by(1).size_hint(), (0, Some(0)));
2605     assert_eq!((20..20).step_by(1).size_hint(), (0, Some(0)));
2606     assert_eq!((i8::MIN..i8::MAX).step_by(-(i8::MIN as i32) as usize).size_hint(), (2, Some(2)));
2607     assert_eq!((i16::MIN..i16::MAX).step_by(i16::MAX as usize).size_hint(), (3, Some(3)));
2608     assert_eq!((isize::MIN..isize::MAX).step_by(1).size_hint(), (usize::MAX, Some(usize::MAX)));
2609 }
2610
2611 #[test]
2612 fn test_step_by_skip() {
2613     assert_eq!((0..640).step_by(128).skip(1).collect::<Vec<_>>(), [128, 256, 384, 512]);
2614     assert_eq!((0..=50).step_by(10).nth(3), Some(30));
2615     assert_eq!((200..=255u8).step_by(10).nth(3), Some(230));
2616 }
2617
2618 #[test]
2619 fn test_range_inclusive_step() {
2620     assert_eq!((0..=50).step_by(10).collect::<Vec<_>>(), [0, 10, 20, 30, 40, 50]);
2621     assert_eq!((0..=5).step_by(1).collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5]);
2622     assert_eq!((200..=255u8).step_by(10).collect::<Vec<_>>(), [200, 210, 220, 230, 240, 250]);
2623     assert_eq!((250..=255u8).step_by(1).collect::<Vec<_>>(), [250, 251, 252, 253, 254, 255]);
2624 }
2625
2626 #[test]
2627 fn test_range_last_max() {
2628     assert_eq!((0..20).last(), Some(19));
2629     assert_eq!((-20..0).last(), Some(-1));
2630     assert_eq!((5..5).last(), None);
2631
2632     assert_eq!((0..20).max(), Some(19));
2633     assert_eq!((-20..0).max(), Some(-1));
2634     assert_eq!((5..5).max(), None);
2635 }
2636
2637 #[test]
2638 fn test_range_inclusive_last_max() {
2639     assert_eq!((0..=20).last(), Some(20));
2640     assert_eq!((-20..=0).last(), Some(0));
2641     assert_eq!((5..=5).last(), Some(5));
2642     let mut r = 10..=10;
2643     r.next();
2644     assert_eq!(r.last(), None);
2645
2646     assert_eq!((0..=20).max(), Some(20));
2647     assert_eq!((-20..=0).max(), Some(0));
2648     assert_eq!((5..=5).max(), Some(5));
2649     let mut r = 10..=10;
2650     r.next();
2651     assert_eq!(r.max(), None);
2652 }
2653
2654 #[test]
2655 fn test_range_min() {
2656     assert_eq!((0..20).min(), Some(0));
2657     assert_eq!((-20..0).min(), Some(-20));
2658     assert_eq!((5..5).min(), None);
2659 }
2660
2661 #[test]
2662 fn test_range_inclusive_min() {
2663     assert_eq!((0..=20).min(), Some(0));
2664     assert_eq!((-20..=0).min(), Some(-20));
2665     assert_eq!((5..=5).min(), Some(5));
2666     let mut r = 10..=10;
2667     r.next();
2668     assert_eq!(r.min(), None);
2669 }
2670
2671 #[test]
2672 fn test_range_inclusive_folds() {
2673     assert_eq!((1..=10).sum::<i32>(), 55);
2674     assert_eq!((1..=10).rev().sum::<i32>(), 55);
2675
2676     let mut it = 44..=50;
2677     assert_eq!(it.try_fold(0, i8::checked_add), None);
2678     assert_eq!(it, 47..=50);
2679     assert_eq!(it.try_fold(0, i8::checked_add), None);
2680     assert_eq!(it, 50..=50);
2681     assert_eq!(it.try_fold(0, i8::checked_add), Some(50));
2682     assert!(it.is_empty());
2683     assert_eq!(it.try_fold(0, i8::checked_add), Some(0));
2684     assert!(it.is_empty());
2685
2686     let mut it = 40..=47;
2687     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2688     assert_eq!(it, 40..=44);
2689     assert_eq!(it.try_rfold(0, i8::checked_add), None);
2690     assert_eq!(it, 40..=41);
2691     assert_eq!(it.try_rfold(0, i8::checked_add), Some(81));
2692     assert!(it.is_empty());
2693     assert_eq!(it.try_rfold(0, i8::checked_add), Some(0));
2694     assert!(it.is_empty());
2695
2696     let mut it = 10..=20;
2697     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(165));
2698     assert!(it.is_empty());
2699     assert_eq!(it.try_fold(0, |a, b| Some(a + b)), Some(0));
2700     assert!(it.is_empty());
2701
2702     let mut it = 10..=20;
2703     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(165));
2704     assert!(it.is_empty());
2705     assert_eq!(it.try_rfold(0, |a, b| Some(a + b)), Some(0));
2706     assert!(it.is_empty());
2707 }
2708
2709 #[test]
2710 fn test_range_size_hint() {
2711     assert_eq!((0..0usize).size_hint(), (0, Some(0)));
2712     assert_eq!((0..100usize).size_hint(), (100, Some(100)));
2713     assert_eq!((0..usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2714
2715     let umax = u128::try_from(usize::MAX).unwrap();
2716     assert_eq!((0..0u128).size_hint(), (0, Some(0)));
2717     assert_eq!((0..100u128).size_hint(), (100, Some(100)));
2718     assert_eq!((0..umax).size_hint(), (usize::MAX, Some(usize::MAX)));
2719     assert_eq!((0..umax + 1).size_hint(), (usize::MAX, None));
2720
2721     assert_eq!((0..0isize).size_hint(), (0, Some(0)));
2722     assert_eq!((-100..100isize).size_hint(), (200, Some(200)));
2723     assert_eq!((isize::MIN..isize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2724
2725     let imin = i128::try_from(isize::MIN).unwrap();
2726     let imax = i128::try_from(isize::MAX).unwrap();
2727     assert_eq!((0..0i128).size_hint(), (0, Some(0)));
2728     assert_eq!((-100..100i128).size_hint(), (200, Some(200)));
2729     assert_eq!((imin..imax).size_hint(), (usize::MAX, Some(usize::MAX)));
2730     assert_eq!((imin..imax + 1).size_hint(), (usize::MAX, None));
2731 }
2732
2733 #[test]
2734 fn test_range_inclusive_size_hint() {
2735     assert_eq!((1..=0usize).size_hint(), (0, Some(0)));
2736     assert_eq!((0..=0usize).size_hint(), (1, Some(1)));
2737     assert_eq!((0..=100usize).size_hint(), (101, Some(101)));
2738     assert_eq!((0..=usize::MAX - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2739     assert_eq!((0..=usize::MAX).size_hint(), (usize::MAX, None));
2740
2741     let umax = u128::try_from(usize::MAX).unwrap();
2742     assert_eq!((1..=0u128).size_hint(), (0, Some(0)));
2743     assert_eq!((0..=0u128).size_hint(), (1, Some(1)));
2744     assert_eq!((0..=100u128).size_hint(), (101, Some(101)));
2745     assert_eq!((0..=umax - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2746     assert_eq!((0..=umax).size_hint(), (usize::MAX, None));
2747     assert_eq!((0..=umax + 1).size_hint(), (usize::MAX, None));
2748
2749     assert_eq!((0..=-1isize).size_hint(), (0, Some(0)));
2750     assert_eq!((0..=0isize).size_hint(), (1, Some(1)));
2751     assert_eq!((-100..=100isize).size_hint(), (201, Some(201)));
2752     assert_eq!((isize::MIN..=isize::MAX - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2753     assert_eq!((isize::MIN..=isize::MAX).size_hint(), (usize::MAX, None));
2754
2755     let imin = i128::try_from(isize::MIN).unwrap();
2756     let imax = i128::try_from(isize::MAX).unwrap();
2757     assert_eq!((0..=-1i128).size_hint(), (0, Some(0)));
2758     assert_eq!((0..=0i128).size_hint(), (1, Some(1)));
2759     assert_eq!((-100..=100i128).size_hint(), (201, Some(201)));
2760     assert_eq!((imin..=imax - 1).size_hint(), (usize::MAX, Some(usize::MAX)));
2761     assert_eq!((imin..=imax).size_hint(), (usize::MAX, None));
2762     assert_eq!((imin..=imax + 1).size_hint(), (usize::MAX, None));
2763 }
2764
2765 #[test]
2766 fn test_repeat() {
2767     let mut it = repeat(42);
2768     assert_eq!(it.next(), Some(42));
2769     assert_eq!(it.next(), Some(42));
2770     assert_eq!(it.next(), Some(42));
2771     assert_eq!(repeat(42).size_hint(), (usize::MAX, None));
2772 }
2773
2774 #[test]
2775 fn test_repeat_take() {
2776     let mut it = repeat(42).take(3);
2777     assert_eq!(it.next(), Some(42));
2778     assert_eq!(it.next(), Some(42));
2779     assert_eq!(it.next(), Some(42));
2780     assert_eq!(it.next(), None);
2781     is_trusted_len(repeat(42).take(3));
2782     assert_eq!(repeat(42).take(3).size_hint(), (3, Some(3)));
2783     assert_eq!(repeat(42).take(0).size_hint(), (0, Some(0)));
2784     assert_eq!(repeat(42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2785 }
2786
2787 #[test]
2788 fn test_repeat_take_collect() {
2789     let v: Vec<_> = repeat(42).take(3).collect();
2790     assert_eq!(v, vec![42, 42, 42]);
2791 }
2792
2793 #[test]
2794 fn test_repeat_with() {
2795     #[derive(PartialEq, Debug)]
2796     struct NotClone(usize);
2797     let mut it = repeat_with(|| NotClone(42));
2798     assert_eq!(it.next(), Some(NotClone(42)));
2799     assert_eq!(it.next(), Some(NotClone(42)));
2800     assert_eq!(it.next(), Some(NotClone(42)));
2801     assert_eq!(repeat_with(|| NotClone(42)).size_hint(), (usize::MAX, None));
2802 }
2803
2804 #[test]
2805 fn test_repeat_with_take() {
2806     let mut it = repeat_with(|| 42).take(3);
2807     assert_eq!(it.next(), Some(42));
2808     assert_eq!(it.next(), Some(42));
2809     assert_eq!(it.next(), Some(42));
2810     assert_eq!(it.next(), None);
2811     is_trusted_len(repeat_with(|| 42).take(3));
2812     assert_eq!(repeat_with(|| 42).take(3).size_hint(), (3, Some(3)));
2813     assert_eq!(repeat_with(|| 42).take(0).size_hint(), (0, Some(0)));
2814     assert_eq!(repeat_with(|| 42).take(usize::MAX).size_hint(), (usize::MAX, Some(usize::MAX)));
2815 }
2816
2817 #[test]
2818 fn test_repeat_with_take_collect() {
2819     let mut curr = 1;
2820     let v: Vec<_> = repeat_with(|| {
2821         let tmp = curr;
2822         curr *= 2;
2823         tmp
2824     })
2825     .take(5)
2826     .collect();
2827     assert_eq!(v, vec![1, 2, 4, 8, 16]);
2828 }
2829
2830 #[test]
2831 fn test_successors() {
2832     let mut powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
2833     assert_eq!(powers_of_10.by_ref().collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
2834     assert_eq!(powers_of_10.next(), None);
2835
2836     let mut empty = successors(None::<u32>, |_| unimplemented!());
2837     assert_eq!(empty.next(), None);
2838     assert_eq!(empty.next(), None);
2839 }
2840
2841 #[test]
2842 fn test_fuse() {
2843     let mut it = 0..3;
2844     assert_eq!(it.len(), 3);
2845     assert_eq!(it.next(), Some(0));
2846     assert_eq!(it.len(), 2);
2847     assert_eq!(it.next(), Some(1));
2848     assert_eq!(it.len(), 1);
2849     assert_eq!(it.next(), Some(2));
2850     assert_eq!(it.len(), 0);
2851     assert_eq!(it.next(), None);
2852     assert_eq!(it.len(), 0);
2853     assert_eq!(it.next(), None);
2854     assert_eq!(it.len(), 0);
2855     assert_eq!(it.next(), None);
2856     assert_eq!(it.len(), 0);
2857 }
2858
2859 #[test]
2860 fn test_fuse_nth() {
2861     let xs = [0, 1, 2];
2862     let mut it = xs.iter();
2863
2864     assert_eq!(it.len(), 3);
2865     assert_eq!(it.nth(2), Some(&2));
2866     assert_eq!(it.len(), 0);
2867     assert_eq!(it.nth(2), None);
2868     assert_eq!(it.len(), 0);
2869 }
2870
2871 #[test]
2872 fn test_fuse_last() {
2873     let xs = [0, 1, 2];
2874     let it = xs.iter();
2875
2876     assert_eq!(it.len(), 3);
2877     assert_eq!(it.last(), Some(&2));
2878 }
2879
2880 #[test]
2881 fn test_fuse_count() {
2882     let xs = [0, 1, 2];
2883     let it = xs.iter();
2884
2885     assert_eq!(it.len(), 3);
2886     assert_eq!(it.count(), 3);
2887     // Can't check len now because count consumes.
2888 }
2889
2890 #[test]
2891 fn test_fuse_fold() {
2892     let xs = [0, 1, 2];
2893     let it = xs.iter(); // `FusedIterator`
2894     let i = it.fuse().fold(0, |i, &x| {
2895         assert_eq!(x, xs[i]);
2896         i + 1
2897     });
2898     assert_eq!(i, xs.len());
2899
2900     let it = xs.iter(); // `FusedIterator`
2901     let i = it.fuse().rfold(xs.len(), |i, &x| {
2902         assert_eq!(x, xs[i - 1]);
2903         i - 1
2904     });
2905     assert_eq!(i, 0);
2906
2907     let it = xs.iter().scan((), |_, &x| Some(x)); // `!FusedIterator`
2908     let i = it.fuse().fold(0, |i, x| {
2909         assert_eq!(x, xs[i]);
2910         i + 1
2911     });
2912     assert_eq!(i, xs.len());
2913 }
2914
2915 #[test]
2916 fn test_once() {
2917     let mut it = once(42);
2918     assert_eq!(it.next(), Some(42));
2919     assert_eq!(it.next(), None);
2920 }
2921
2922 #[test]
2923 fn test_once_with() {
2924     let count = Cell::new(0);
2925     let mut it = once_with(|| {
2926         count.set(count.get() + 1);
2927         42
2928     });
2929
2930     assert_eq!(count.get(), 0);
2931     assert_eq!(it.next(), Some(42));
2932     assert_eq!(count.get(), 1);
2933     assert_eq!(it.next(), None);
2934     assert_eq!(count.get(), 1);
2935     assert_eq!(it.next(), None);
2936     assert_eq!(count.get(), 1);
2937 }
2938
2939 #[test]
2940 fn test_empty() {
2941     let mut it = empty::<i32>();
2942     assert_eq!(it.next(), None);
2943 }
2944
2945 #[test]
2946 fn test_chain_fold() {
2947     let xs = [1, 2, 3];
2948     let ys = [1, 2, 0];
2949
2950     let mut iter = xs.iter().chain(&ys);
2951     iter.next();
2952     let mut result = Vec::new();
2953     iter.fold((), |(), &elt| result.push(elt));
2954     assert_eq!(&[2, 3, 1, 2, 0], &result[..]);
2955 }
2956
2957 #[test]
2958 fn test_steps_between() {
2959     assert_eq!(Step::steps_between(&20_u8, &200_u8), Some(180_usize));
2960     assert_eq!(Step::steps_between(&-20_i8, &80_i8), Some(100_usize));
2961     assert_eq!(Step::steps_between(&-120_i8, &80_i8), Some(200_usize));
2962     assert_eq!(Step::steps_between(&20_u32, &4_000_100_u32), Some(4_000_080_usize));
2963     assert_eq!(Step::steps_between(&-20_i32, &80_i32), Some(100_usize));
2964     assert_eq!(Step::steps_between(&-2_000_030_i32, &2_000_050_i32), Some(4_000_080_usize));
2965
2966     // Skip u64/i64 to avoid differences with 32-bit vs 64-bit platforms
2967
2968     assert_eq!(Step::steps_between(&20_u128, &200_u128), Some(180_usize));
2969     assert_eq!(Step::steps_between(&-20_i128, &80_i128), Some(100_usize));
2970     if cfg!(target_pointer_width = "64") {
2971         assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_0009_u128), Some(usize::MAX));
2972     }
2973     assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_000a_u128), None);
2974     assert_eq!(Step::steps_between(&10_i128, &0x1_0000_0000_0000_000a_i128), None);
2975     assert_eq!(
2976         Step::steps_between(&-0x1_0000_0000_0000_0000_i128, &0x1_0000_0000_0000_0000_i128,),
2977         None,
2978     );
2979 }
2980
2981 #[test]
2982 fn test_step_forward() {
2983     assert_eq!(Step::forward_checked(55_u8, 200_usize), Some(255_u8));
2984     assert_eq!(Step::forward_checked(252_u8, 200_usize), None);
2985     assert_eq!(Step::forward_checked(0_u8, 256_usize), None);
2986     assert_eq!(Step::forward_checked(-110_i8, 200_usize), Some(90_i8));
2987     assert_eq!(Step::forward_checked(-110_i8, 248_usize), None);
2988     assert_eq!(Step::forward_checked(-126_i8, 256_usize), None);
2989
2990     assert_eq!(Step::forward_checked(35_u16, 100_usize), Some(135_u16));
2991     assert_eq!(Step::forward_checked(35_u16, 65500_usize), Some(u16::MAX));
2992     assert_eq!(Step::forward_checked(36_u16, 65500_usize), None);
2993     assert_eq!(Step::forward_checked(-110_i16, 200_usize), Some(90_i16));
2994     assert_eq!(Step::forward_checked(-20_030_i16, 50_050_usize), Some(30_020_i16));
2995     assert_eq!(Step::forward_checked(-10_i16, 40_000_usize), None);
2996     assert_eq!(Step::forward_checked(-10_i16, 70_000_usize), None);
2997
2998     assert_eq!(Step::forward_checked(10_u128, 70_000_usize), Some(70_010_u128));
2999     assert_eq!(Step::forward_checked(10_i128, 70_030_usize), Some(70_040_i128));
3000     assert_eq!(
3001         Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0xff_usize),
3002         Some(u128::MAX),
3003     );
3004     assert_eq!(
3005         Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0x100_usize),
3006         None
3007     );
3008     assert_eq!(
3009         Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0xff_usize),
3010         Some(i128::MAX),
3011     );
3012     assert_eq!(
3013         Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
3014         None
3015     );
3016 }
3017
3018 #[test]
3019 fn test_step_backward() {
3020     assert_eq!(Step::backward_checked(255_u8, 200_usize), Some(55_u8));
3021     assert_eq!(Step::backward_checked(100_u8, 200_usize), None);
3022     assert_eq!(Step::backward_checked(255_u8, 256_usize), None);
3023     assert_eq!(Step::backward_checked(90_i8, 200_usize), Some(-110_i8));
3024     assert_eq!(Step::backward_checked(110_i8, 248_usize), None);
3025     assert_eq!(Step::backward_checked(127_i8, 256_usize), None);
3026
3027     assert_eq!(Step::backward_checked(135_u16, 100_usize), Some(35_u16));
3028     assert_eq!(Step::backward_checked(u16::MAX, 65500_usize), Some(35_u16));
3029     assert_eq!(Step::backward_checked(10_u16, 11_usize), None);
3030     assert_eq!(Step::backward_checked(90_i16, 200_usize), Some(-110_i16));
3031     assert_eq!(Step::backward_checked(30_020_i16, 50_050_usize), Some(-20_030_i16));
3032     assert_eq!(Step::backward_checked(-10_i16, 40_000_usize), None);
3033     assert_eq!(Step::backward_checked(-10_i16, 70_000_usize), None);
3034
3035     assert_eq!(Step::backward_checked(70_010_u128, 70_000_usize), Some(10_u128));
3036     assert_eq!(Step::backward_checked(70_020_i128, 70_030_usize), Some(-10_i128));
3037     assert_eq!(Step::backward_checked(10_u128, 7_usize), Some(3_u128));
3038     assert_eq!(Step::backward_checked(10_u128, 11_usize), None);
3039     assert_eq!(
3040         Step::backward_checked(-0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
3041         Some(i128::MIN)
3042     );
3043 }
3044
3045 #[test]
3046 fn test_rev_try_folds() {
3047     let f = &|acc, x| i32::checked_add(2 * acc, x);
3048     assert_eq!((1..10).rev().try_fold(7, f), (1..10).try_rfold(7, f));
3049     assert_eq!((1..10).rev().try_rfold(7, f), (1..10).try_fold(7, f));
3050
3051     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
3052     let mut iter = a.iter().rev();
3053     assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
3054     assert_eq!(iter.next(), Some(&70));
3055     let mut iter = a.iter().rev();
3056     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
3057     assert_eq!(iter.next_back(), Some(&60));
3058 }
3059
3060 #[test]
3061 fn test_cloned_try_folds() {
3062     let a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
3063     let f = &|acc, x| i32::checked_add(2 * acc, x);
3064     let f_ref = &|acc, &x| i32::checked_add(2 * acc, x);
3065     assert_eq!(a.iter().cloned().try_fold(7, f), a.iter().try_fold(7, f_ref));
3066     assert_eq!(a.iter().cloned().try_rfold(7, f), a.iter().try_rfold(7, f_ref));
3067
3068     let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
3069     let mut iter = a.iter().cloned();
3070     assert_eq!(iter.try_fold(0_i8, |acc, x| acc.checked_add(x)), None);
3071     assert_eq!(iter.next(), Some(60));
3072     let mut iter = a.iter().cloned();
3073     assert_eq!(iter.try_rfold(0_i8, |acc, x| acc.checked_add(x)), None);
3074     assert_eq!(iter.next_back(), Some(70));
3075 }
3076
3077 #[test]
3078 fn test_chain_try_folds() {
3079     let c = || (0..10).chain(10..20);
3080
3081     let f = &|acc, x| i32::checked_add(2 * acc, x);
3082     assert_eq!(c().try_fold(7, f), (0..20).try_fold(7, f));
3083     assert_eq!(c().try_rfold(7, f), (0..20).rev().try_fold(7, f));
3084
3085     let mut iter = c();
3086     assert_eq!(iter.position(|x| x == 5), Some(5));
3087     assert_eq!(iter.next(), Some(6), "stopped in front, state Both");
3088     assert_eq!(iter.position(|x| x == 13), Some(6));
3089     assert_eq!(iter.next(), Some(14), "stopped in back, state Back");
3090     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((15..20).sum()));
3091
3092     let mut iter = c().rev(); // use rev to access try_rfold
3093     assert_eq!(iter.position(|x| x == 15), Some(4));
3094     assert_eq!(iter.next(), Some(14), "stopped in back, state Both");
3095     assert_eq!(iter.position(|x| x == 5), Some(8));
3096     assert_eq!(iter.next(), Some(4), "stopped in front, state Front");
3097     assert_eq!(iter.try_fold(0, |acc, x| Some(acc + x)), Some((0..4).sum()));
3098
3099     let mut iter = c();
3100     iter.by_ref().rev().nth(14); // skip the last 15, ending in state Front
3101     assert_eq!(iter.try_fold(7, f), (0..5).try_fold(7, f));
3102
3103     let mut iter = c();
3104     iter.nth(14); // skip the first 15, ending in state Back
3105     assert_eq!(iter.try_rfold(7, f), (15..20).try_rfold(7, f));
3106 }
3107
3108 #[test]
3109 fn test_map_try_folds() {
3110     let f = &|acc, x| i32::checked_add(2 * acc, x);
3111     assert_eq!((0..10).map(|x| x + 3).try_fold(7, f), (3..13).try_fold(7, f));
3112     assert_eq!((0..10).map(|x| x + 3).try_rfold(7, f), (3..13).try_rfold(7, f));
3113
3114     let mut iter = (0..40).map(|x| x + 10);
3115     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3116     assert_eq!(iter.next(), Some(20));
3117     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3118     assert_eq!(iter.next_back(), Some(46));
3119 }
3120
3121 #[test]
3122 fn test_filter_try_folds() {
3123     fn p(&x: &i32) -> bool {
3124         0 <= x && x < 10
3125     }
3126     let f = &|acc, x| i32::checked_add(2 * acc, x);
3127     assert_eq!((-10..20).filter(p).try_fold(7, f), (0..10).try_fold(7, f));
3128     assert_eq!((-10..20).filter(p).try_rfold(7, f), (0..10).try_rfold(7, f));
3129
3130     let mut iter = (0..40).filter(|&x| x % 2 == 1);
3131     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3132     assert_eq!(iter.next(), Some(25));
3133     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3134     assert_eq!(iter.next_back(), Some(31));
3135 }
3136
3137 #[test]
3138 fn test_filter_map_try_folds() {
3139     let mp = &|x| if 0 <= x && x < 10 { Some(x * 2) } else { None };
3140     let f = &|acc, x| i32::checked_add(2 * acc, x);
3141     assert_eq!((-9..20).filter_map(mp).try_fold(7, f), (0..10).map(|x| 2 * x).try_fold(7, f));
3142     assert_eq!((-9..20).filter_map(mp).try_rfold(7, f), (0..10).map(|x| 2 * x).try_rfold(7, f));
3143
3144     let mut iter = (0..40).filter_map(|x| if x % 2 == 1 { None } else { Some(x * 2 + 10) });
3145     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3146     assert_eq!(iter.next(), Some(38));
3147     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3148     assert_eq!(iter.next_back(), Some(78));
3149 }
3150
3151 #[test]
3152 fn test_enumerate_try_folds() {
3153     let f = &|acc, (i, x)| usize::checked_add(2 * acc, x / (i + 1) + i);
3154     assert_eq!((9..18).enumerate().try_fold(7, f), (0..9).map(|i| (i, i + 9)).try_fold(7, f));
3155     assert_eq!((9..18).enumerate().try_rfold(7, f), (0..9).map(|i| (i, i + 9)).try_rfold(7, f));
3156
3157     let mut iter = (100..200).enumerate();
3158     let f = &|acc, (i, x)| u8::checked_add(acc, u8::checked_div(x, i as u8 + 1)?);
3159     assert_eq!(iter.try_fold(0, f), None);
3160     assert_eq!(iter.next(), Some((7, 107)));
3161     assert_eq!(iter.try_rfold(0, f), None);
3162     assert_eq!(iter.next_back(), Some((11, 111)));
3163 }
3164
3165 #[test]
3166 fn test_peek_try_folds() {
3167     let f = &|acc, x| i32::checked_add(2 * acc, x);
3168
3169     assert_eq!((1..20).peekable().try_fold(7, f), (1..20).try_fold(7, f));
3170     assert_eq!((1..20).peekable().try_rfold(7, f), (1..20).try_rfold(7, f));
3171
3172     let mut iter = (1..20).peekable();
3173     assert_eq!(iter.peek(), Some(&1));
3174     assert_eq!(iter.try_fold(7, f), (1..20).try_fold(7, f));
3175
3176     let mut iter = (1..20).peekable();
3177     assert_eq!(iter.peek(), Some(&1));
3178     assert_eq!(iter.try_rfold(7, f), (1..20).try_rfold(7, f));
3179
3180     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
3181     assert_eq!(iter.peek(), Some(&100));
3182     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3183     assert_eq!(iter.peek(), Some(&40));
3184
3185     let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
3186     assert_eq!(iter.peek(), Some(&100));
3187     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3188     assert_eq!(iter.peek(), Some(&100));
3189     assert_eq!(iter.next_back(), Some(50));
3190
3191     let mut iter = (2..5).peekable();
3192     assert_eq!(iter.peek(), Some(&2));
3193     assert_eq!(iter.try_for_each(Err), Err(2));
3194     assert_eq!(iter.peek(), Some(&3));
3195     assert_eq!(iter.try_for_each(Err), Err(3));
3196     assert_eq!(iter.peek(), Some(&4));
3197     assert_eq!(iter.try_for_each(Err), Err(4));
3198     assert_eq!(iter.peek(), None);
3199     assert_eq!(iter.try_for_each(Err), Ok(()));
3200
3201     let mut iter = (2..5).peekable();
3202     assert_eq!(iter.peek(), Some(&2));
3203     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(4));
3204     assert_eq!(iter.peek(), Some(&2));
3205     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(3));
3206     assert_eq!(iter.peek(), Some(&2));
3207     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Err(2));
3208     assert_eq!(iter.peek(), None);
3209     assert_eq!(iter.try_rfold((), |(), x| Err(x)), Ok(()));
3210 }
3211
3212 #[test]
3213 fn test_skip_while_try_fold() {
3214     let f = &|acc, x| i32::checked_add(2 * acc, x);
3215     fn p(&x: &i32) -> bool {
3216         (x % 10) <= 5
3217     }
3218     assert_eq!((1..20).skip_while(p).try_fold(7, f), (6..20).try_fold(7, f));
3219     let mut iter = (1..20).skip_while(p);
3220     assert_eq!(iter.nth(5), Some(11));
3221     assert_eq!(iter.try_fold(7, f), (12..20).try_fold(7, f));
3222
3223     let mut iter = (0..50).skip_while(|&x| (x % 20) < 15);
3224     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3225     assert_eq!(iter.next(), Some(23));
3226 }
3227
3228 #[test]
3229 fn test_take_while_folds() {
3230     let f = &|acc, x| i32::checked_add(2 * acc, x);
3231     assert_eq!((1..20).take_while(|&x| x != 10).try_fold(7, f), (1..10).try_fold(7, f));
3232     let mut iter = (1..20).take_while(|&x| x != 10);
3233     assert_eq!(iter.try_fold(0, |x, y| Some(x + y)), Some((1..10).sum()));
3234     assert_eq!(iter.next(), None, "flag should be set");
3235     let iter = (1..20).take_while(|&x| x != 10);
3236     assert_eq!(iter.fold(0, |x, y| x + y), (1..10).sum());
3237
3238     let mut iter = (10..50).take_while(|&x| x != 40);
3239     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3240     assert_eq!(iter.next(), Some(20));
3241 }
3242
3243 #[test]
3244 fn test_skip_try_folds() {
3245     let f = &|acc, x| i32::checked_add(2 * acc, x);
3246     assert_eq!((1..20).skip(9).try_fold(7, f), (10..20).try_fold(7, f));
3247     assert_eq!((1..20).skip(9).try_rfold(7, f), (10..20).try_rfold(7, f));
3248
3249     let mut iter = (0..30).skip(10);
3250     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3251     assert_eq!(iter.next(), Some(20));
3252     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3253     assert_eq!(iter.next_back(), Some(24));
3254 }
3255
3256 #[test]
3257 fn test_skip_nth_back() {
3258     let xs = [0, 1, 2, 3, 4, 5];
3259     let mut it = xs.iter().skip(2);
3260     assert_eq!(it.nth_back(0), Some(&5));
3261     assert_eq!(it.nth_back(1), Some(&3));
3262     assert_eq!(it.nth_back(0), Some(&2));
3263     assert_eq!(it.nth_back(0), None);
3264
3265     let ys = [2, 3, 4, 5];
3266     let mut ity = ys.iter();
3267     let mut it = xs.iter().skip(2);
3268     assert_eq!(it.nth_back(1), ity.nth_back(1));
3269     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3270     assert_eq!(it.nth_back(0), ity.nth_back(0));
3271     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3272     assert_eq!(it.nth_back(0), ity.nth_back(0));
3273     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3274     assert_eq!(it.nth_back(0), ity.nth_back(0));
3275     assert_eq!(it.clone().nth(0), ity.clone().nth(0));
3276
3277     let mut it = xs.iter().skip(2);
3278     assert_eq!(it.nth_back(4), None);
3279     assert_eq!(it.nth_back(0), None);
3280
3281     let mut it = xs.iter();
3282     it.by_ref().skip(2).nth_back(3);
3283     assert_eq!(it.next_back(), Some(&1));
3284
3285     let mut it = xs.iter();
3286     it.by_ref().skip(2).nth_back(10);
3287     assert_eq!(it.next_back(), Some(&1));
3288 }
3289
3290 #[test]
3291 fn test_take_try_folds() {
3292     let f = &|acc, x| i32::checked_add(2 * acc, x);
3293     assert_eq!((10..30).take(10).try_fold(7, f), (10..20).try_fold(7, f));
3294     assert_eq!((10..30).take(10).try_rfold(7, f), (10..20).try_rfold(7, f));
3295
3296     let mut iter = (10..30).take(20);
3297     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3298     assert_eq!(iter.next(), Some(20));
3299     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3300     assert_eq!(iter.next_back(), Some(24));
3301
3302     let mut iter = (2..20).take(3);
3303     assert_eq!(iter.try_for_each(Err), Err(2));
3304     assert_eq!(iter.try_for_each(Err), Err(3));
3305     assert_eq!(iter.try_for_each(Err), Err(4));
3306     assert_eq!(iter.try_for_each(Err), Ok(()));
3307
3308     let mut iter = (2..20).take(3).rev();
3309     assert_eq!(iter.try_for_each(Err), Err(4));
3310     assert_eq!(iter.try_for_each(Err), Err(3));
3311     assert_eq!(iter.try_for_each(Err), Err(2));
3312     assert_eq!(iter.try_for_each(Err), Ok(()));
3313 }
3314
3315 #[test]
3316 fn test_flat_map_try_folds() {
3317     let f = &|acc, x| i32::checked_add(acc * 2 / 3, x);
3318     let mr = &|x| (5 * x)..(5 * x + 5);
3319     assert_eq!((0..10).flat_map(mr).try_fold(7, f), (0..50).try_fold(7, f));
3320     assert_eq!((0..10).flat_map(mr).try_rfold(7, f), (0..50).try_rfold(7, f));
3321     let mut iter = (0..10).flat_map(mr);
3322     iter.next();
3323     iter.next_back(); // have front and back iters in progress
3324     assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
3325
3326     let mut iter = (0..10).flat_map(|x| (4 * x)..(4 * x + 4));
3327     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3328     assert_eq!(iter.next(), Some(17));
3329     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3330     assert_eq!(iter.next_back(), Some(35));
3331 }
3332
3333 #[test]
3334 fn test_flatten_try_folds() {
3335     let f = &|acc, x| i32::checked_add(acc * 2 / 3, x);
3336     let mr = &|x| (5 * x)..(5 * x + 5);
3337     assert_eq!((0..10).map(mr).flatten().try_fold(7, f), (0..50).try_fold(7, f));
3338     assert_eq!((0..10).map(mr).flatten().try_rfold(7, f), (0..50).try_rfold(7, f));
3339     let mut iter = (0..10).map(mr).flatten();
3340     iter.next();
3341     iter.next_back(); // have front and back iters in progress
3342     assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
3343
3344     let mut iter = (0..10).map(|x| (4 * x)..(4 * x + 4)).flatten();
3345     assert_eq!(iter.try_fold(0, i8::checked_add), None);
3346     assert_eq!(iter.next(), Some(17));
3347     assert_eq!(iter.try_rfold(0, i8::checked_add), None);
3348     assert_eq!(iter.next_back(), Some(35));
3349 }
3350
3351 #[test]
3352 fn test_functor_laws() {
3353     // identity:
3354     fn identity<T>(x: T) -> T {
3355         x
3356     }
3357     assert_eq!((0..10).map(identity).sum::<usize>(), (0..10).sum());
3358
3359     // composition:
3360     fn f(x: usize) -> usize {
3361         x + 3
3362     }
3363     fn g(x: usize) -> usize {
3364         x * 2
3365     }
3366     fn h(x: usize) -> usize {
3367         g(f(x))
3368     }
3369     assert_eq!((0..10).map(f).map(g).sum::<usize>(), (0..10).map(h).sum());
3370 }
3371
3372 #[test]
3373 fn test_monad_laws_left_identity() {
3374     fn f(x: usize) -> impl Iterator<Item = usize> {
3375         (0..10).map(move |y| x * y)
3376     }
3377     assert_eq!(once(42).flat_map(f.clone()).sum::<usize>(), f(42).sum());
3378 }
3379
3380 #[test]
3381 fn test_monad_laws_right_identity() {
3382     assert_eq!((0..10).flat_map(|x| once(x)).sum::<usize>(), (0..10).sum());
3383 }
3384
3385 #[test]
3386 fn test_monad_laws_associativity() {
3387     fn f(x: usize) -> impl Iterator<Item = usize> {
3388         0..x
3389     }
3390     fn g(x: usize) -> impl Iterator<Item = usize> {
3391         (0..x).rev()
3392     }
3393     assert_eq!(
3394         (0..10).flat_map(f).flat_map(g).sum::<usize>(),
3395         (0..10).flat_map(|x| f(x).flat_map(g)).sum::<usize>()
3396     );
3397 }
3398
3399 #[test]
3400 fn test_is_sorted() {
3401     assert!([1, 2, 2, 9].iter().is_sorted());
3402     assert!(![1, 3, 2].iter().is_sorted());
3403     assert!([0].iter().is_sorted());
3404     assert!(std::iter::empty::<i32>().is_sorted());
3405     assert!(![0.0, 1.0, f32::NAN].iter().is_sorted());
3406     assert!([-2, -1, 0, 3].iter().is_sorted());
3407     assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
3408     assert!(!["c", "bb", "aaa"].iter().is_sorted());
3409     assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
3410 }
3411
3412 #[test]
3413 fn test_partition() {
3414     fn check(xs: &mut [i32], ref p: impl Fn(&i32) -> bool, expected: usize) {
3415         let i = xs.iter_mut().partition_in_place(p);
3416         assert_eq!(expected, i);
3417         assert!(xs[..i].iter().all(p));
3418         assert!(!xs[i..].iter().any(p));
3419         assert!(xs.iter().is_partitioned(p));
3420         if i == 0 || i == xs.len() {
3421             assert!(xs.iter().rev().is_partitioned(p));
3422         } else {
3423             assert!(!xs.iter().rev().is_partitioned(p));
3424         }
3425     }
3426
3427     check(&mut [], |_| true, 0);
3428     check(&mut [], |_| false, 0);
3429
3430     check(&mut [0], |_| true, 1);
3431     check(&mut [0], |_| false, 0);
3432
3433     check(&mut [-1, 1], |&x| x > 0, 1);
3434     check(&mut [-1, 1], |&x| x < 0, 1);
3435
3436     let ref mut xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
3437     check(xs, |_| true, 10);
3438     check(xs, |_| false, 0);
3439     check(xs, |&x| x % 2 == 0, 5); // evens
3440     check(xs, |&x| x % 2 == 1, 5); // odds
3441     check(xs, |&x| x % 3 == 0, 4); // multiple of 3
3442     check(xs, |&x| x % 4 == 0, 3); // multiple of 4
3443     check(xs, |&x| x % 5 == 0, 2); // multiple of 5
3444     check(xs, |&x| x < 3, 3); // small
3445     check(xs, |&x| x > 6, 3); // large
3446 }
3447
3448 /// An iterator that panics whenever `next` or next_back` is called
3449 /// after `None` has already been returned. This does not violate
3450 /// `Iterator`'s contract. Used to test that iterator adaptors don't
3451 /// poll their inner iterators after exhausting them.
3452 struct NonFused<I> {
3453     iter: I,
3454     done: bool,
3455 }
3456
3457 impl<I> NonFused<I> {
3458     fn new(iter: I) -> Self {
3459         Self { iter, done: false }
3460     }
3461 }
3462
3463 impl<I> Iterator for NonFused<I>
3464 where
3465     I: Iterator,
3466 {
3467     type Item = I::Item;
3468
3469     fn next(&mut self) -> Option<Self::Item> {
3470         assert!(!self.done, "this iterator has already returned None");
3471         self.iter.next().or_else(|| {
3472             self.done = true;
3473             None
3474         })
3475     }
3476 }
3477
3478 impl<I> DoubleEndedIterator for NonFused<I>
3479 where
3480     I: DoubleEndedIterator,
3481 {
3482     fn next_back(&mut self) -> Option<Self::Item> {
3483         assert!(!self.done, "this iterator has already returned None");
3484         self.iter.next_back().or_else(|| {
3485             self.done = true;
3486             None
3487         })
3488     }
3489 }
3490
3491 #[test]
3492 fn test_peekable_non_fused() {
3493     let mut iter = NonFused::new(empty::<i32>()).peekable();
3494
3495     assert_eq!(iter.peek(), None);
3496     assert_eq!(iter.next_back(), None);
3497 }
3498
3499 #[test]
3500 fn test_flatten_non_fused_outer() {
3501     let mut iter = NonFused::new(once(0..2)).flatten();
3502
3503     assert_eq!(iter.next_back(), Some(1));
3504     assert_eq!(iter.next(), Some(0));
3505     assert_eq!(iter.next(), None);
3506 }
3507
3508 #[test]
3509 fn test_flatten_non_fused_inner() {
3510     let mut iter = once(0..1).chain(once(1..3)).flat_map(NonFused::new);
3511
3512     assert_eq!(iter.next_back(), Some(2));
3513     assert_eq!(iter.next(), Some(0));
3514     assert_eq!(iter.next(), Some(1));
3515     assert_eq!(iter.next(), None);
3516 }
3517
3518 #[test]
3519 pub fn extend_for_unit() {
3520     let mut x = 0;
3521     {
3522         let iter = (0..5).map(|_| {
3523             x += 1;
3524         });
3525         ().extend(iter);
3526     }
3527     assert_eq!(x, 5);
3528 }
3529
3530 #[test]
3531 fn test_intersperse() {
3532     let v = std::iter::empty().intersperse(0u32).collect::<Vec<_>>();
3533     assert_eq!(v, vec![]);
3534
3535     let v = std::iter::once(1).intersperse(0).collect::<Vec<_>>();
3536     assert_eq!(v, vec![1]);
3537
3538     let xs = ["a", "", "b", "c"];
3539     let v: Vec<&str> = xs.iter().map(|x| x.clone()).intersperse(", ").collect();
3540     let text: String = v.concat();
3541     assert_eq!(text, "a, , b, c".to_string());
3542
3543     let ys = [0, 1, 2, 3];
3544     let mut it = ys[..0].iter().map(|x| *x).intersperse(1);
3545     assert!(it.next() == None);
3546 }
3547
3548 #[test]
3549 fn test_intersperse_size_hint() {
3550     let iter = std::iter::empty::<i32>().intersperse(0);
3551     assert_eq!(iter.size_hint(), (0, Some(0)));
3552
3553     let xs = ["a", "", "b", "c"];
3554     let mut iter = xs.iter().map(|x| x.clone()).intersperse(", ");
3555     assert_eq!(iter.size_hint(), (7, Some(7)));
3556
3557     assert_eq!(iter.next(), Some("a"));
3558     assert_eq!(iter.size_hint(), (6, Some(6)));
3559     assert_eq!(iter.next(), Some(", "));
3560     assert_eq!(iter.size_hint(), (5, Some(5)));
3561
3562     assert_eq!([].iter().intersperse(&()).size_hint(), (0, Some(0)));
3563 }
3564
3565 #[test]
3566 fn test_fold_specialization_intersperse() {
3567     let mut iter = (1..2).intersperse(0);
3568     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3569
3570     let mut iter = (1..3).intersperse(0);
3571     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3572
3573     let mut iter = (1..4).intersperse(0);
3574     iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
3575 }
3576
3577 #[test]
3578 fn test_try_fold_specialization_intersperse_ok() {
3579     let mut iter = (1..2).intersperse(0);
3580     iter.clone().try_for_each(|x| {
3581         assert_eq!(Some(x), iter.next());
3582         Some(())
3583     });
3584
3585     let mut iter = (1..3).intersperse(0);
3586     iter.clone().try_for_each(|x| {
3587         assert_eq!(Some(x), iter.next());
3588         Some(())
3589     });
3590
3591     let mut iter = (1..4).intersperse(0);
3592     iter.clone().try_for_each(|x| {
3593         assert_eq!(Some(x), iter.next());
3594         Some(())
3595     });
3596 }
3597
3598 #[test]
3599 fn test_try_fold_specialization_intersperse_err() {
3600     let orig_iter = ["a", "b"].iter().copied().intersperse("-");
3601
3602     // Abort after the first item.
3603     let mut iter = orig_iter.clone();
3604     iter.try_for_each(|_| None::<()>);
3605     assert_eq!(iter.next(), Some("-"));
3606     assert_eq!(iter.next(), Some("b"));
3607     assert_eq!(iter.next(), None);
3608
3609     // Abort after the second item.
3610     let mut iter = orig_iter.clone();
3611     iter.try_for_each(|item| if item == "-" { None } else { Some(()) });
3612     assert_eq!(iter.next(), Some("b"));
3613     assert_eq!(iter.next(), None);
3614
3615     // Abort after the third item.
3616     let mut iter = orig_iter.clone();
3617     iter.try_for_each(|item| if item == "b" { None } else { Some(()) });
3618     assert_eq!(iter.next(), None);
3619 }
3620
3621 #[test]
3622 fn test_intersperse_with() {
3623     #[derive(PartialEq, Debug)]
3624     struct NotClone {
3625         u: u32,
3626     }
3627     let r = vec![NotClone { u: 0 }, NotClone { u: 1 }]
3628         .into_iter()
3629         .intersperse_with(|| NotClone { u: 2 })
3630         .collect::<Vec<_>>();
3631     assert_eq!(r, vec![NotClone { u: 0 }, NotClone { u: 2 }, NotClone { u: 1 }]);
3632
3633     let mut ctr = 100;
3634     let separator = || {
3635         ctr *= 2;
3636         ctr
3637     };
3638     let r = (0..3).intersperse_with(separator).collect::<Vec<_>>();
3639     assert_eq!(r, vec![0, 200, 1, 400, 2]);
3640 }