diff options
| -rw-r--r-- | src/libcore/benches/iter.rs | 151 | ||||
| -rw-r--r-- | src/libcore/iter/mod.rs | 172 | ||||
| -rw-r--r-- | src/libcore/tests/iter.rs | 180 | ||||
| -rw-r--r-- | src/libcore/tests/lib.rs | 1 |
4 files changed, 471 insertions, 33 deletions
diff --git a/src/libcore/benches/iter.rs b/src/libcore/benches/iter.rs index 827c6354c60..1f16f5b1df3 100644 --- a/src/libcore/benches/iter.rs +++ b/src/libcore/benches/iter.rs @@ -147,40 +147,131 @@ fn bench_for_each_chain_ref_fold(b: &mut Bencher) { }); } -#[bench] -fn bench_flat_map_sum(b: &mut Bencher) { - b.iter(|| -> i64 { - (0i64..1000).flat_map(|x| x..x+1000) - .map(black_box) - .sum() - }); + +/// Helper to benchmark `sum` for iterators taken by value which +/// can optimize `fold`, and by reference which cannot. +macro_rules! bench_sums { + ($bench_sum:ident, $bench_ref_sum:ident, $iter:expr) => { + #[bench] + fn $bench_sum(b: &mut Bencher) { + b.iter(|| -> i64 { + $iter.map(black_box).sum() + }); + } + + #[bench] + fn $bench_ref_sum(b: &mut Bencher) { + b.iter(|| -> i64 { + $iter.map(black_box).by_ref().sum() + }); + } + } } -#[bench] -fn bench_flat_map_ref_sum(b: &mut Bencher) { - b.iter(|| -> i64 { - (0i64..1000).flat_map(|x| x..x+1000) - .map(black_box) - .by_ref() - .sum() - }); +bench_sums! { + bench_flat_map_sum, + bench_flat_map_ref_sum, + (0i64..1000).flat_map(|x| x..x+1000) } -#[bench] -fn bench_flat_map_chain_sum(b: &mut Bencher) { - b.iter(|| -> i64 { - (0i64..1000000).flat_map(|x| once(x).chain(once(x))) - .map(black_box) - .sum() - }); +bench_sums! { + bench_flat_map_chain_sum, + bench_flat_map_chain_ref_sum, + (0i64..1000000).flat_map(|x| once(x).chain(once(x))) } -#[bench] -fn bench_flat_map_chain_ref_sum(b: &mut Bencher) { - b.iter(|| -> i64 { - (0i64..1000000).flat_map(|x| once(x).chain(once(x))) - .map(black_box) - .by_ref() - .sum() - }); +bench_sums! { + bench_enumerate_sum, + bench_enumerate_ref_sum, + (0i64..1000000).enumerate().map(|(i, x)| x * i as i64) +} + +bench_sums! { + bench_enumerate_chain_sum, + bench_enumerate_chain_ref_sum, + (0i64..1000000).chain(0..1000000).enumerate().map(|(i, x)| x * i as i64) +} + +bench_sums! { + bench_filter_sum, + bench_filter_ref_sum, + (0i64..1000000).filter(|x| x % 2 == 0) +} + +bench_sums! { + bench_filter_chain_sum, + bench_filter_chain_ref_sum, + (0i64..1000000).chain(0..1000000).filter(|x| x % 2 == 0) +} + +bench_sums! { + bench_filter_map_sum, + bench_filter_map_ref_sum, + (0i64..1000000).filter_map(|x| x.checked_mul(x)) +} + +bench_sums! { + bench_filter_map_chain_sum, + bench_filter_map_chain_ref_sum, + (0i64..1000000).chain(0..1000000).filter_map(|x| x.checked_mul(x)) +} + +bench_sums! { + bench_fuse_sum, + bench_fuse_ref_sum, + (0i64..1000000).fuse() +} + +bench_sums! { + bench_fuse_chain_sum, + bench_fuse_chain_ref_sum, + (0i64..1000000).chain(0..1000000).fuse() +} + +bench_sums! { + bench_inspect_sum, + bench_inspect_ref_sum, + (0i64..1000000).inspect(|_| {}) +} + +bench_sums! { + bench_inspect_chain_sum, + bench_inspect_chain_ref_sum, + (0i64..1000000).chain(0..1000000).inspect(|_| {}) +} + +bench_sums! { + bench_peekable_sum, + bench_peekable_ref_sum, + (0i64..1000000).peekable() +} + +bench_sums! { + bench_peekable_chain_sum, + bench_peekable_chain_ref_sum, + (0i64..1000000).chain(0..1000000).peekable() +} + +bench_sums! { + bench_skip_sum, + bench_skip_ref_sum, + (0i64..1000000).skip(1000) +} + +bench_sums! { + bench_skip_chain_sum, + bench_skip_chain_ref_sum, + (0i64..1000000).chain(0..1000000).skip(1000) +} + +bench_sums! { + bench_skip_while_sum, + bench_skip_while_ref_sum, + (0i64..1000000).skip_while(|&x| x < 1000) +} + +bench_sums! { + bench_skip_while_chain_sum, + bench_skip_while_chain_ref_sum, + (0i64..1000000).chain(0..1000000).skip_while(|&x| x < 1000) } diff --git a/src/libcore/iter/mod.rs b/src/libcore/iter/mod.rs index 2d3ff6a348d..ed39324d488 100644 --- a/src/libcore/iter/mod.rs +++ b/src/libcore/iter/mod.rs @@ -1250,6 +1250,18 @@ impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool } count } + + #[inline] + fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut predicate = self.predicate; + self.iter.fold(init, move |acc, item| if predicate(&item) { + fold(acc, item) + } else { + acc + }) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1265,6 +1277,18 @@ impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P> } None } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut predicate = self.predicate; + self.iter.rfold(init, move |acc, item| if predicate(&item) { + fold(acc, item) + } else { + acc + }) + } } #[unstable(feature = "fused", issue = "35602")] @@ -1316,6 +1340,17 @@ impl<B, I: Iterator, F> Iterator for FilterMap<I, F> let (_, upper) = self.iter.size_hint(); (0, upper) // can't know a lower bound, due to the predicate } + + #[inline] + fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.fold(init, move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => acc, + }) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1331,6 +1366,17 @@ impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F> } None } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.rfold(init, move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => acc, + }) + } } #[unstable(feature = "fused", issue = "35602")] @@ -1395,6 +1441,19 @@ impl<I> Iterator for Enumerate<I> where I: Iterator { fn count(self) -> usize { self.iter.count() } + + #[inline] + #[rustc_inherit_overflow_checks] + fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut count = self.count; + self.iter.fold(init, move |acc, item| { + let acc = fold(acc, (count, item)); + count += 1; + acc + }) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1410,6 +1469,19 @@ impl<I> DoubleEndedIterator for Enumerate<I> where (self.count + len, a) }) } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + // Can safely add and subtract the count, as `ExactSizeIterator` promises + // that the number of elements fits into a `usize`. + let mut count = self.count + self.iter.len(); + self.iter.rfold(init, move |acc, item| { + count -= 1; + fold(acc, (count, item)) + }) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1521,6 +1593,18 @@ impl<I: Iterator> Iterator for Peekable<I> { let hi = hi.and_then(|x| x.checked_add(peek_len)); (lo, hi) } + + #[inline] + fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let acc = match self.peeked { + Some(None) => return init, + Some(Some(v)) => fold(init, v), + None => init, + }; + self.iter.fold(acc, fold) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1629,6 +1713,19 @@ impl<I: Iterator, P> Iterator for SkipWhile<I, P> let (_, upper) = self.iter.size_hint(); (0, upper) // can't know a lower bound, due to the predicate } + + #[inline] + fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + if !self.flag { + match self.next() { + Some(v) => init = fold(init, v), + None => return init, + } + } + self.iter.fold(init, fold) + } } #[unstable(feature = "fused", issue = "35602")] @@ -1769,6 +1866,19 @@ impl<I> Iterator for Skip<I> where I: Iterator { (lower, upper) } + + #[inline] + fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + if self.n > 0 { + // nth(n) skips n+1 + if self.iter.nth(self.n - 1).is_none() { + return init; + } + } + self.iter.fold(init, fold) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1991,6 +2101,16 @@ impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> wher } } } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.frontiter.into_iter() + .chain(self.iter.map(self.f).map(U::into_iter)) + .chain(self.backiter) + .rfold(init, |acc, iter| iter.rfold(acc, &mut fold)) + } } #[unstable(feature = "fused", issue = "35602")] @@ -2068,6 +2188,17 @@ impl<I> Iterator for Fuse<I> where I: Iterator { self.iter.size_hint() } } + + #[inline] + default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + if self.done { + init + } else { + self.iter.fold(init, fold) + } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -2082,6 +2213,17 @@ impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator { next } } + + #[inline] + default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + if self.done { + init + } else { + self.iter.rfold(init, fold) + } + } } unsafe impl<I> TrustedRandomAccess for Fuse<I> @@ -2122,6 +2264,13 @@ impl<I> Iterator for Fuse<I> where I: FusedIterator { fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + + #[inline] + fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, fold) + } } #[unstable(feature = "fused", reason = "recently added", issue = "35602")] @@ -2132,6 +2281,13 @@ impl<I> DoubleEndedIterator for Fuse<I> fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, fold) + } } @@ -2196,6 +2352,14 @@ impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) { fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + + #[inline] + fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) }) + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -2207,6 +2371,14 @@ impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F> let next = self.iter.next_back(); self.do_inspect(next) } + + #[inline] + fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + where Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) }) + } } #[stable(feature = "rust1", since = "1.0.0")] diff --git a/src/libcore/tests/iter.rs b/src/libcore/tests/iter.rs index 3c4ea974fc9..f8c6fc5c8fa 100644 --- a/src/libcore/tests/iter.rs +++ b/src/libcore/tests/iter.rs @@ -249,6 +249,25 @@ fn test_filter_map() { } #[test] +fn test_filter_map_fold() { + let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8]; + let ys = [0*0, 2*2, 4*4, 6*6, 8*8]; + let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x*x) } else { None }); + let i = it.fold(0, |i, x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); + + let it = xs.iter().filter_map(|&x| if x % 2 == 0 { Some(x*x) } else { None }); + let i = it.rfold(ys.len(), |i, x| { + assert_eq!(x, ys[i - 1]); + i - 1 + }); + assert_eq!(i, 0); +} + +#[test] fn test_iterator_enumerate() { let xs = [0, 1, 2, 3, 4, 5]; let it = xs.iter().enumerate(); @@ -282,7 +301,31 @@ fn test_iterator_enumerate_nth() { #[test] fn test_iterator_enumerate_count() { let xs = [0, 1, 2, 3, 4, 5]; - assert_eq!(xs.iter().count(), 6); + assert_eq!(xs.iter().enumerate().count(), 6); +} + +#[test] +fn test_iterator_enumerate_fold() { + let xs = [0, 1, 2, 3, 4, 5]; + let mut it = xs.iter().enumerate(); + // steal a couple to get an interesting offset + assert_eq!(it.next(), Some((0, &0))); + assert_eq!(it.next(), Some((1, &1))); + let i = it.fold(2, |i, (j, &x)| { + assert_eq!(i, j); + assert_eq!(x, xs[j]); + i + 1 + }); + assert_eq!(i, xs.len()); + + let mut it = xs.iter().enumerate(); + assert_eq!(it.next(), Some((0, &0))); + let i = it.rfold(xs.len() - 1, |i, (j, &x)| { + assert_eq!(i, j); + assert_eq!(x, xs[j]); + i - 1 + }); + assert_eq!(i, 0); } #[test] @@ -292,6 +335,25 @@ fn test_iterator_filter_count() { } #[test] +fn test_iterator_filter_fold() { + let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8]; + let ys = [0, 2, 4, 6, 8]; + let it = xs.iter().filter(|&&x| x % 2 == 0); + let i = it.fold(0, |i, &x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); + + let it = xs.iter().filter(|&&x| x % 2 == 0); + let i = it.rfold(ys.len(), |i, &x| { + assert_eq!(x, ys[i - 1]); + i - 1 + }); + assert_eq!(i, 0); +} + +#[test] fn test_iterator_peekable() { let xs = vec![0, 1, 2, 3, 4, 5]; let mut it = xs.iter().cloned().peekable(); @@ -381,6 +443,18 @@ fn test_iterator_peekable_last() { assert_eq!(it.last(), None); } +#[test] +fn test_iterator_peekable_fold() { + let xs = [0, 1, 2, 3, 4, 5]; + let mut it = xs.iter().peekable(); + assert_eq!(it.peek(), Some(&&0)); + let i = it.fold(0, |i, &x| { + assert_eq!(x, xs[i]); + i + 1 + }); + assert_eq!(i, xs.len()); +} + /// This is an iterator that follows the Iterator contract, /// but it is not fused. After having returned None once, it will start /// producing elements if .next() is called again. @@ -471,6 +545,26 @@ fn test_iterator_skip_while() { } #[test] +fn test_iterator_skip_while_fold() { + let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19]; + let ys = [15, 16, 17, 19]; + let it = xs.iter().skip_while(|&x| *x < 15); + let i = it.fold(0, |i, &x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); + + let mut it = xs.iter().skip_while(|&x| *x < 15); + assert_eq!(it.next(), Some(&ys[0])); // process skips before folding + let i = it.fold(1, |i, &x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); +} + +#[test] fn test_iterator_skip() { let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30]; let ys = [13, 15, 16, 17, 19, 20, 30]; @@ -567,6 +661,26 @@ fn test_iterator_skip_last() { } #[test] +fn test_iterator_skip_fold() { + let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30]; + let ys = [13, 15, 16, 17, 19, 20, 30]; + let it = xs.iter().skip(5); + let i = it.fold(0, |i, &x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); + + let mut it = xs.iter().skip(5); + assert_eq!(it.next(), Some(&ys[0])); // process skips before folding + let i = it.fold(1, |i, &x| { + assert_eq!(x, ys[i]); + i + 1 + }); + assert_eq!(i, ys.len()); +} + +#[test] fn test_iterator_take() { let xs = [0, 1, 2, 3, 5, 13, 15, 16, 17, 19]; let ys = [0, 1, 2, 3, 5]; @@ -661,13 +775,22 @@ fn test_iterator_flat_map_fold() { let xs = [0, 3, 6]; let ys = [1, 2, 3, 4, 5, 6, 7]; let mut it = xs.iter().flat_map(|&x| x..x+3); - it.next(); - it.next_back(); + assert_eq!(it.next(), Some(0)); + assert_eq!(it.next_back(), Some(8)); let i = it.fold(0, |i, x| { assert_eq!(x, ys[i]); i + 1 }); assert_eq!(i, ys.len()); + + let mut it = xs.iter().flat_map(|&x| x..x+3); + assert_eq!(it.next(), Some(0)); + assert_eq!(it.next_back(), Some(8)); + let i = it.rfold(ys.len(), |i, x| { + assert_eq!(x, ys[i - 1]); + i - 1 + }); + assert_eq!(i, 0); } #[test] @@ -685,6 +808,32 @@ fn test_inspect() { } #[test] +fn test_inspect_fold() { + let xs = [1, 2, 3, 4]; + let mut n = 0; + { + let it = xs.iter().inspect(|_| n += 1); + let i = it.fold(0, |i, &x| { + assert_eq!(x, xs[i]); + i + 1 + }); + assert_eq!(i, xs.len()); + } + assert_eq!(n, xs.len()); + + let mut n = 0; + { + let it = xs.iter().inspect(|_| n += 1); + let i = it.rfold(xs.len(), |i, &x| { + assert_eq!(x, xs[i - 1]); + i - 1 + }); + assert_eq!(i, 0); + } + assert_eq!(n, xs.len()); +} + +#[test] fn test_cycle() { let cycle_len = 3; let it = (0..).step_by(1).take(cycle_len).cycle(); @@ -1242,6 +1391,31 @@ fn test_fuse_count() { } #[test] +fn test_fuse_fold() { + let xs = [0, 1, 2]; + let it = xs.iter(); // `FusedIterator` + let i = it.fuse().fold(0, |i, &x| { + assert_eq!(x, xs[i]); + i + 1 + }); + assert_eq!(i, xs.len()); + + let it = xs.iter(); // `FusedIterator` + let i = it.fuse().rfold(xs.len(), |i, &x| { + assert_eq!(x, xs[i - 1]); + i - 1 + }); + assert_eq!(i, 0); + + let it = xs.iter().scan((), |_, &x| Some(x)); // `!FusedIterator` + let i = it.fuse().fold(0, |i, x| { + assert_eq!(x, xs[i]); + i + 1 + }); + assert_eq!(i, xs.len()); +} + +#[test] fn test_once() { let mut it = once(42); assert_eq!(it.next(), Some(42)); diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs index 47995597a0a..d928276ad2f 100644 --- a/src/libcore/tests/lib.rs +++ b/src/libcore/tests/lib.rs @@ -25,6 +25,7 @@ #![feature(inclusive_range)] #![feature(inclusive_range_syntax)] #![feature(iter_rfind)] +#![feature(iter_rfold)] #![feature(nonzero)] #![feature(rand)] #![feature(raw)] |