diff options
| -rw-r--r-- | src/libcore/iter/adapters/flatten.rs | 78 | ||||
| -rw-r--r-- | src/libcore/iter/adapters/mod.rs | 536 | ||||
| -rw-r--r-- | src/libcore/iter/adapters/zip.rs | 8 | ||||
| -rw-r--r-- | src/libcore/iter/sources.rs | 10 | ||||
| -rw-r--r-- | src/libcore/iter/traits/accum.rs | 8 | ||||
| -rw-r--r-- | src/libcore/iter/traits/double_ended.rs | 25 | ||||
| -rw-r--r-- | src/libcore/iter/traits/iterator.rs | 249 | ||||
| -rw-r--r-- | src/test/codegen/iter-fold-closure-no-dupes.rs | 14 | ||||
| -rw-r--r-- | src/test/codegen/iter-fold-closure-no-iterator.rs | 10 | ||||
| -rw-r--r-- | src/test/ui/iterators/iter-count-overflow-debug.rs | 16 | ||||
| -rw-r--r-- | src/test/ui/iterators/iter-count-overflow-ndebug.rs | 11 | ||||
| -rw-r--r-- | src/test/ui/iterators/iter-map-fold-type-length.rs | 38 | ||||
| -rw-r--r-- | src/test/ui/iterators/iter-position-overflow-debug.rs | 22 | ||||
| -rw-r--r-- | src/test/ui/iterators/iter-position-overflow-ndebug.rs | 13 |
14 files changed, 714 insertions, 324 deletions
diff --git a/src/libcore/iter/adapters/flatten.rs b/src/libcore/iter/adapters/flatten.rs index d8d41a2a31e..e3c85656116 100644 --- a/src/libcore/iter/adapters/flatten.rs +++ b/src/libcore/iter/adapters/flatten.rs @@ -229,7 +229,7 @@ where if let elt@Some(_) = inner.next() { return elt } } match self.iter.next() { - None => return self.backiter.as_mut().and_then(|it| it.next()), + None => return self.backiter.as_mut()?.next(), Some(inner) => self.frontiter = Some(inner.into_iter()), } } @@ -237,8 +237,8 @@ where #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint()); - let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint()); + let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint); + let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint); let lo = flo.saturating_add(blo); match (self.iter.size_hint(), fhi, bhi) { ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)), @@ -250,20 +250,25 @@ where fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { + #[inline] + fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>( + frontiter: &'a mut Option<T::IntoIter>, + fold: &'a mut impl FnMut(Acc, T::Item) -> R, + ) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, x| { + let mut mid = x.into_iter(); + let r = mid.try_fold(acc, &mut *fold); + *frontiter = Some(mid); + r + } + } + if let Some(ref mut front) = self.frontiter { init = front.try_fold(init, &mut fold)?; } self.frontiter = None; - { - let frontiter = &mut self.frontiter; - init = self.iter.try_fold(init, |acc, x| { - let mut mid = x.into_iter(); - let r = mid.try_fold(acc, &mut fold); - *frontiter = Some(mid); - r - })?; - } + init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?; self.frontiter = None; if let Some(ref mut back) = self.backiter { @@ -275,13 +280,20 @@ where } #[inline] - fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { + #[inline] + fn flatten<U: Iterator, Acc>( + fold: &mut impl FnMut(Acc, U::Item) -> Acc, + ) -> impl FnMut(Acc, U) -> Acc + '_ { + move |acc, iter| iter.fold(acc, &mut *fold) + } + self.frontiter.into_iter() .chain(self.iter.map(IntoIterator::into_iter)) .chain(self.backiter) - .fold(init, |acc, iter| iter.fold(acc, &mut fold)) + .fold(init, flatten(fold)) } } @@ -297,7 +309,7 @@ where if let elt@Some(_) = inner.next_back() { return elt } } match self.iter.next_back() { - None => return self.frontiter.as_mut().and_then(|it| it.next_back()), + None => return self.frontiter.as_mut()?.next_back(), next => self.backiter = next.map(IntoIterator::into_iter), } } @@ -307,20 +319,27 @@ where fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - if let Some(ref mut back) = self.backiter { - init = back.try_rfold(init, &mut fold)?; - } - self.backiter = None; - + #[inline] + fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>( + backiter: &'a mut Option<T::IntoIter>, + fold: &'a mut impl FnMut(Acc, T::Item) -> R, + ) -> impl FnMut(Acc, T) -> R + 'a where + T::IntoIter: DoubleEndedIterator, { - let backiter = &mut self.backiter; - init = self.iter.try_rfold(init, |acc, x| { + move |acc, x| { let mut mid = x.into_iter(); - let r = mid.try_rfold(acc, &mut fold); + let r = mid.try_rfold(acc, &mut *fold); *backiter = Some(mid); r - })?; + } } + + if let Some(ref mut back) = self.backiter { + init = back.try_rfold(init, &mut fold)?; + } + self.backiter = None; + + init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?; self.backiter = None; if let Some(ref mut front) = self.frontiter { @@ -332,12 +351,19 @@ where } #[inline] - fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { + #[inline] + fn flatten<U: DoubleEndedIterator, Acc>( + fold: &mut impl FnMut(Acc, U::Item) -> Acc, + ) -> impl FnMut(Acc, U) -> Acc + '_ { + move |acc, iter| iter.rfold(acc, &mut *fold) + } + self.frontiter.into_iter() .chain(self.iter.map(IntoIterator::into_iter)) .chain(self.backiter) - .rfold(init, |acc, iter| iter.rfold(acc, &mut fold)) + .rfold(init, flatten(fold)) } } diff --git a/src/libcore/iter/adapters/mod.rs b/src/libcore/iter/adapters/mod.rs index b2702902956..58e0a70cefb 100644 --- a/src/libcore/iter/adapters/mod.rs +++ b/src/libcore/iter/adapters/mod.rs @@ -1,6 +1,6 @@ use crate::cmp; use crate::fmt; -use crate::ops::Try; +use crate::ops::{Add, AddAssign, Try}; use crate::usize; use crate::intrinsics; @@ -143,6 +143,18 @@ impl<I> Copied<I> { } } +fn copy_fold<T: Copy, Acc>( + mut f: impl FnMut(Acc, T) -> Acc, +) -> impl FnMut(Acc, &T) -> Acc { + move |acc, &elt| f(acc, elt) +} + +fn copy_try_fold<T: Copy, Acc, R>( + mut f: impl FnMut(Acc, T) -> R, +) -> impl FnMut(Acc, &T) -> R { + move |acc, &elt| f(acc, elt) +} + #[stable(feature = "iter_copied", since = "1.36.0")] impl<'a, I, T: 'a> Iterator for Copied<I> where I: Iterator<Item=&'a T>, T: Copy @@ -157,16 +169,16 @@ impl<'a, I, T: 'a> Iterator for Copied<I> self.it.size_hint() } - fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where + fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B> { - self.it.try_fold(init, move |acc, &elt| f(acc, elt)) + self.it.try_fold(init, copy_try_fold(f)) } - fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc + fn fold<Acc, F>(self, init: Acc, f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - self.it.fold(init, move |acc, &elt| f(acc, elt)) + self.it.fold(init, copy_fold(f)) } } @@ -178,16 +190,16 @@ impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I> self.it.next_back().copied() } - fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where + fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B> { - self.it.try_rfold(init, move |acc, &elt| f(acc, elt)) + self.it.try_rfold(init, copy_try_fold(f)) } - fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc + fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - self.it.rfold(init, move |acc, &elt| f(acc, elt)) + self.it.rfold(init, copy_fold(f)) } } @@ -248,6 +260,12 @@ impl<I> Cloned<I> { } } +fn clone_try_fold<T: Clone, Acc, R>( + mut f: impl FnMut(Acc, T) -> R, +) -> impl FnMut(Acc, &T) -> R { + move |acc, elt| f(acc, elt.clone()) +} + #[stable(feature = "iter_cloned", since = "1.1.0")] impl<'a, I, T: 'a> Iterator for Cloned<I> where I: Iterator<Item=&'a T>, T: Clone @@ -262,16 +280,16 @@ impl<'a, I, T: 'a> Iterator for Cloned<I> self.it.size_hint() } - fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where + fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B> { - self.it.try_fold(init, move |acc, elt| f(acc, elt.clone())) + self.it.try_fold(init, clone_try_fold(f)) } - fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc + fn fold<Acc, F>(self, init: Acc, f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - self.it.fold(init, move |acc, elt| f(acc, elt.clone())) + self.it.map(T::clone).fold(init, f) } } @@ -283,16 +301,16 @@ impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I> self.it.next_back().cloned() } - fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where + fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B> { - self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone())) + self.it.try_rfold(init, clone_try_fold(f)) } - fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc + fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - self.it.rfold(init, move |acc, elt| f(acc, elt.clone())) + self.it.map(T::clone).rfold(init, f) } } @@ -430,14 +448,24 @@ impl<I> Iterator for StepBy<I> where I: Iterator { #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - let inner_hint = self.iter.size_hint(); + #[inline] + fn first_size(step: usize) -> impl Fn(usize) -> usize { + move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) } + } + + #[inline] + fn other_size(step: usize) -> impl Fn(usize) -> usize { + move |n| n / (step + 1) + } + + let (low, high) = self.iter.size_hint(); if self.first_take { - let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) }; - (f(inner_hint.0), inner_hint.1.map(f)) + let f = first_size(self.step); + (f(low), high.map(f)) } else { - let f = |n| n / (self.step+1); - (f(inner_hint.0), inner_hint.1.map(f)) + let f = other_size(self.step); + (f(low), high.map(f)) } } @@ -594,6 +622,20 @@ impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> { } } +fn map_fold<T, B, Acc>( + mut f: impl FnMut(T) -> B, + mut g: impl FnMut(Acc, B) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, elt| g(acc, f(elt)) +} + +fn map_try_fold<'a, T, B, Acc, R>( + f: &'a mut impl FnMut(T) -> B, + mut g: impl FnMut(Acc, B) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, elt| g(acc, f(elt)) +} + #[stable(feature = "rust1", since = "1.0.0")] impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B { type Item = B; @@ -608,18 +650,16 @@ impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B { self.iter.size_hint() } - fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where + fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R where Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_fold(init, move |acc, elt| g(acc, f(elt))) + self.iter.try_fold(init, map_try_fold(&mut self.f, g)) } - fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc + fn fold<Acc, G>(self, init: Acc, g: G) -> Acc where G: FnMut(Acc, Self::Item) -> Acc, { - let mut f = self.f; - self.iter.fold(init, move |acc, elt| g(acc, f(elt))) + self.iter.fold(init, map_fold(self.f, g)) } } @@ -632,18 +672,16 @@ impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where self.iter.next_back().map(&mut self.f) } - fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where + fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R where Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt))) + self.iter.try_rfold(init, map_try_fold(&mut self.f, g)) } - fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc + fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc where G: FnMut(Acc, Self::Item) -> Acc, { - let mut f = self.f; - self.iter.rfold(init, move |acc, elt| g(acc, f(elt))) + self.iter.rfold(init, map_fold(self.f, g)) } } @@ -710,13 +748,27 @@ impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> { } } +fn filter_fold<T, Acc>( + mut predicate: impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| if predicate(&item) { fold(acc, item) } else { acc } +} + +fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>( + predicate: &'a mut impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| if predicate(&item) { fold(acc, item) } else { R::from_ok(acc) } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool { type Item = I::Item; #[inline] fn next(&mut self) -> Option<I::Item> { - self.try_for_each(Err).err() + self.iter.find(&mut self.predicate) } #[inline] @@ -738,32 +790,26 @@ impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool // leaving more budget for LLVM optimizations. #[inline] fn count(self) -> usize { - let mut predicate = self.predicate; - self.iter.map(|x| predicate(&x) as usize).sum() + #[inline] + fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize { + move |x| predicate(&x) as usize + } + + self.iter.map(to_usize(self.predicate)).sum() } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let predicate = &mut self.predicate; - self.iter.try_fold(init, move |acc, item| if predicate(&item) { - fold(acc, item) - } else { - Try::from_ok(acc) - }) + self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold)) } #[inline] - fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, 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 - }) + self.iter.fold(init, filter_fold(self.predicate, fold)) } } @@ -773,31 +819,21 @@ impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P> { #[inline] fn next_back(&mut self) -> Option<I::Item> { - self.try_rfold((), |_, x| Err(x)).err() + self.iter.rfind(&mut self.predicate) } #[inline] - fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let predicate = &mut self.predicate; - self.iter.try_rfold(init, move |acc, item| if predicate(&item) { - fold(acc, item) - } else { - Try::from_ok(acc) - }) + self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold)) } #[inline] - fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, 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 - }) + self.iter.rfold(init, filter_fold(self.predicate, fold)) } } @@ -834,6 +870,26 @@ impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> { } } +fn filter_map_fold<T, B, Acc>( + mut f: impl FnMut(T) -> Option<B>, + mut fold: impl FnMut(Acc, B) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => acc, + } +} + +fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>( + f: &'a mut impl FnMut(T) -> Option<B>, + mut fold: impl FnMut(Acc, B) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => R::from_ok(acc), + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<B, I: Iterator, F> Iterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B>, @@ -842,7 +898,7 @@ impl<B, I: Iterator, F> Iterator for FilterMap<I, F> #[inline] fn next(&mut self) -> Option<B> { - self.try_for_each(Err).err() + self.iter.find_map(&mut self.f) } #[inline] @@ -852,25 +908,17 @@ impl<B, I: Iterator, F> Iterator for FilterMap<I, F> } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_fold(init, move |acc, item| match f(item) { - Some(x) => fold(acc, x), - None => Try::from_ok(acc), - }) + self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold)) } #[inline] - fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, 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, - }) + self.iter.fold(init, filter_map_fold(self.f, fold)) } } @@ -880,29 +928,31 @@ impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F> { #[inline] fn next_back(&mut self) -> Option<B> { - self.try_rfold((), |_, x| Err(x)).err() + #[inline] + fn find<T, B>( + f: &mut impl FnMut(T) -> Option<B> + ) -> impl FnMut((), T) -> LoopState<(), B> + '_ { + move |(), x| match f(x) { + Some(x) => LoopState::Break(x), + None => LoopState::Continue(()), + } + } + + self.iter.try_rfold((), find(&mut self.f)).break_value() } #[inline] - fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_rfold(init, move |acc, item| match f(item) { - Some(x) => fold(acc, x), - None => Try::from_ok(acc), - }) + self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold)) } #[inline] - fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, 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, - }) + self.iter.rfold(init, filter_map_fold(self.f, fold)) } } @@ -944,14 +994,12 @@ impl<I> Iterator for Enumerate<I> where I: Iterator { /// /// Might panic if the index of the element overflows a `usize`. #[inline] - #[rustc_inherit_overflow_checks] fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> { - self.iter.next().map(|a| { - let ret = (self.count, a); - // Possible undefined overflow. - self.count += 1; - ret - }) + let a = self.iter.next()?; + let i = self.count; + // Possible undefined overflow. + AddAssign::add_assign(&mut self.count, 1); + Some((i, a)) } #[inline] @@ -960,13 +1008,12 @@ impl<I> Iterator for Enumerate<I> where I: Iterator { } #[inline] - #[rustc_inherit_overflow_checks] fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> { - self.iter.nth(n).map(|a| { - let i = self.count + n; - self.count = i + 1; - (i, a) - }) + let a = self.iter.nth(n)?; + // Possible undefined overflow. + let i = Add::add(self.count, n); + self.count = Add::add(i, 1); + Some((i, a)) } #[inline] @@ -975,29 +1022,43 @@ impl<I> Iterator for Enumerate<I> where I: Iterator { } #[inline] - #[rustc_inherit_overflow_checks] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let count = &mut self.count; - self.iter.try_fold(init, move |acc, item| { - let acc = fold(acc, (*count, item)); - *count += 1; - acc - }) + #[inline] + fn enumerate<'a, T, Acc, R>( + count: &'a mut usize, + mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a, + ) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| { + let acc = fold(acc, (*count, item)); + // Possible undefined overflow. + AddAssign::add_assign(count, 1); + acc + } + } + + self.iter.try_fold(init, enumerate(&mut self.count, fold)) } #[inline] - #[rustc_inherit_overflow_checks] - fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, 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 - }) + #[inline] + fn enumerate<T, Acc>( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { + let acc = fold(acc, (count, item)); + // Possible undefined overflow. + AddAssign::add_assign(&mut count, 1); + acc + } + } + + self.iter.fold(init, enumerate(self.count, fold)) } } @@ -1007,48 +1068,60 @@ impl<I> DoubleEndedIterator for Enumerate<I> where { #[inline] fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> { - self.iter.next_back().map(|a| { - let len = self.iter.len(); - // Can safely add, `ExactSizeIterator` promises that the number of - // elements fits into a `usize`. - (self.count + len, a) - }) + let a = self.iter.next_back()?; + let len = self.iter.len(); + // Can safely add, `ExactSizeIterator` promises that the number of + // elements fits into a `usize`. + Some((self.count + len, a)) } #[inline] fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> { - self.iter.nth_back(n).map(|a| { - let len = self.iter.len(); - // Can safely add, `ExactSizeIterator` promises that the number of - // elements fits into a `usize`. - (self.count + len, a) - }) + let a = self.iter.nth_back(n)?; + let len = self.iter.len(); + // Can safely add, `ExactSizeIterator` promises that the number of + // elements fits into a `usize`. + Some((self.count + len, a)) } #[inline] - fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=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.try_rfold(init, move |acc, item| { - count -= 1; - fold(acc, (count, item)) - }) + fn enumerate<T, Acc, R>( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> R, + ) -> impl FnMut(Acc, T) -> R { + move |acc, item| { + count -= 1; + fold(acc, (count, item)) + } + } + + let count = self.count + self.iter.len(); + self.iter.try_rfold(init, enumerate(count, fold)) } #[inline] - fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, 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)) - }) + fn enumerate<T, Acc>( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { + count -= 1; + fold(acc, (count, item)) + } + } + + let count = self.count + self.iter.len(); + self.iter.rfold(init, enumerate(count, fold)) } } @@ -1162,7 +1235,10 @@ impl<I: Iterator> Iterator for Peekable<I> { }; let (lo, hi) = self.iter.size_hint(); let lo = lo.saturating_add(peek_len); - let hi = hi.and_then(|x| x.checked_add(peek_len)); + let hi = match hi { + Some(x) => x.checked_add(peek_len), + None => None, + }; (lo, hi) } @@ -1321,16 +1397,23 @@ impl<I: Iterator, P> Iterator for SkipWhile<I, P> #[inline] fn next(&mut self) -> Option<I::Item> { + fn check<'a, T>( + flag: &'a mut bool, + pred: &'a mut impl FnMut(&T) -> bool, + ) -> impl FnMut(&T) -> bool + 'a { + move |x| { + if *flag || !pred(x) { + *flag = true; + true + } else { + false + } + } + } + let flag = &mut self.flag; let pred = &mut self.predicate; - self.iter.find(move |x| { - if *flag || !pred(x) { - *flag = true; - true - } else { - false - } - }) + self.iter.find(check(flag, pred)) } #[inline] @@ -1412,14 +1495,13 @@ impl<I: Iterator, P> Iterator for TakeWhile<I, P> if self.flag { None } else { - self.iter.next().and_then(|x| { - if (self.predicate)(&x) { - Some(x) - } else { - self.flag = true; - None - } - }) + let x = self.iter.next()?; + if (self.predicate)(&x) { + Some(x) + } else { + self.flag = true; + None + } } } @@ -1434,22 +1516,30 @@ impl<I: Iterator, P> Iterator for TakeWhile<I, P> } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - if self.flag { - Try::from_ok(init) - } else { - let flag = &mut self.flag; - let p = &mut self.predicate; - self.iter.try_fold(init, move |acc, x|{ + fn check<'a, T, Acc, R: Try<Ok = Acc>>( + flag: &'a mut bool, + p: &'a mut impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> R + 'a, + ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a { + move |acc, x| { if p(&x) { LoopState::from_try(fold(acc, x)) } else { *flag = true; LoopState::Break(Try::from_ok(acc)) } - }).into_try() + } + } + + if self.flag { + Try::from_ok(init) + } else { + let flag = &mut self.flag; + let p = &mut self.predicate; + self.iter.try_fold(init, check(flag, p, fold)).into_try() } } } @@ -1534,7 +1624,10 @@ impl<I> Iterator for Skip<I> where I: Iterator { let (lower, upper) = self.iter.size_hint(); let lower = lower.saturating_sub(self.n); - let upper = upper.map(|x| x.saturating_sub(self.n)); + let upper = match upper { + Some(x) => Some(x.saturating_sub(self.n)), + None => None, + }; (lower, upper) } @@ -1595,19 +1688,26 @@ impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSize } } - fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let mut n = self.len(); - if n == 0 { - Try::from_ok(init) - } else { - self.iter.try_rfold(init, move |acc, x| { + fn check<T, Acc, R: Try<Ok = Acc>>( + mut n: usize, + mut fold: impl FnMut(Acc, T) -> R, + ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> { + move |acc, x| { n -= 1; let r = fold(acc, x); if n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) } - }).into_try() + } + } + + let n = self.len(); + if n == 0 { + Try::from_ok(init) + } else { + self.iter.try_rfold(init, check(n, fold)).into_try() } } } @@ -1682,19 +1782,26 @@ impl<I> Iterator for Take<I> where I: Iterator{ } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - if self.n == 0 { - Try::from_ok(init) - } else { - let n = &mut self.n; - self.iter.try_fold(init, move |acc, x| { + fn check<'a, T, Acc, R: Try<Ok = Acc>>( + n: &'a mut usize, + mut fold: impl FnMut(Acc, T) -> R + 'a, + ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a { + move |acc, x| { *n -= 1; let r = fold(acc, x); if *n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) } - }).into_try() + } + } + + if self.n == 0 { + Try::from_ok(init) + } else { + let n = &mut self.n; + self.iter.try_fold(init, check(n, fold)).into_try() } } } @@ -1793,7 +1900,8 @@ impl<B, I, St, F> Iterator for Scan<I, St, F> where #[inline] fn next(&mut self) -> Option<B> { - self.iter.next().and_then(|a| (self.f)(&mut self.state, a)) + let a = self.iter.next()?; + (self.f)(&mut self.state, a) } #[inline] @@ -1803,17 +1911,25 @@ impl<B, I, St, F> Iterator for Scan<I, St, F> where } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { + fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>( + state: &'a mut St, + f: &'a mut impl FnMut(&mut St, T) -> Option<B>, + mut fold: impl FnMut(Acc, B) -> R + 'a, + ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a { + move |acc, x| { + match f(state, x) { + None => LoopState::Break(Try::from_ok(acc)), + Some(x) => LoopState::from_try(fold(acc, x)), + } + } + } + let state = &mut self.state; let f = &mut self.f; - self.iter.try_fold(init, move |acc, x| { - match f(state, x) { - None => LoopState::Break(Try::from_ok(acc)), - Some(x) => LoopState::from_try(fold(acc, x)), - } - }).into_try() + self.iter.try_fold(init, scan(state, f, fold)).into_try() } } @@ -2104,6 +2220,20 @@ impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) { } } +fn inspect_fold<T, Acc>( + mut f: impl FnMut(&T), + mut fold: impl FnMut(Acc, T) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { f(&item); fold(acc, item) } +} + +fn inspect_try_fold<'a, T, Acc, R>( + f: &'a mut impl FnMut(&T), + mut fold: impl FnMut(Acc, T) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| { f(&item); fold(acc, item) } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) { type Item = I::Item; @@ -2120,19 +2250,17 @@ impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) { } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) }) + self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold)) } #[inline] - fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, 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) }) + self.iter.fold(init, inspect_fold(self.f, fold)) } } @@ -2147,19 +2275,17 @@ impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F> } #[inline] - fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc> { - let f = &mut self.f; - self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) }) + self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold)) } #[inline] - fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, 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) }) + self.iter.rfold(init, inspect_fold(self.f, fold)) } } diff --git a/src/libcore/iter/adapters/zip.rs b/src/libcore/iter/adapters/zip.rs index 06f047d9287..430ceacdd9f 100644 --- a/src/libcore/iter/adapters/zip.rs +++ b/src/libcore/iter/adapters/zip.rs @@ -94,11 +94,9 @@ impl<A, B> ZipImpl<A, B> for Zip<A, B> #[inline] default fn next(&mut self) -> Option<(A::Item, B::Item)> { - self.a.next().and_then(|x| { - self.b.next().and_then(|y| { - Some((x, y)) - }) - }) + let x = self.a.next()?; + let y = self.b.next()?; + Some((x, y)) } #[inline] diff --git a/src/libcore/iter/sources.rs b/src/libcore/iter/sources.rs index 70a3b70c180..183176005ed 100644 --- a/src/libcore/iter/sources.rs +++ b/src/libcore/iter/sources.rs @@ -394,7 +394,8 @@ impl<A, F: FnOnce() -> A> Iterator for OnceWith<F> { #[inline] fn next(&mut self) -> Option<A> { - self.gen.take().map(|f| f()) + let f = self.gen.take()?; + Some(f()) } #[inline] @@ -608,10 +609,9 @@ impl<T, F> Iterator for Successors<T, F> #[inline] fn next(&mut self) -> Option<Self::Item> { - self.next.take().map(|item| { - self.next = (self.succ)(&item); - item - }) + let item = self.next.take()?; + self.next = (self.succ)(&item); + Some(item) } #[inline] diff --git a/src/libcore/iter/traits/accum.rs b/src/libcore/iter/traits/accum.rs index 812463e77f9..818f0330329 100644 --- a/src/libcore/iter/traits/accum.rs +++ b/src/libcore/iter/traits/accum.rs @@ -85,28 +85,28 @@ macro_rules! float_sum_product { #[stable(feature = "iter_arith_traits", since = "1.12.0")] impl Sum for $a { fn sum<I: Iterator<Item=$a>>(iter: I) -> $a { - iter.fold(0.0, |a, b| a + b) + iter.fold(0.0, Add::add) } } #[stable(feature = "iter_arith_traits", since = "1.12.0")] impl Product for $a { fn product<I: Iterator<Item=$a>>(iter: I) -> $a { - iter.fold(1.0, |a, b| a * b) + iter.fold(1.0, Mul::mul) } } #[stable(feature = "iter_arith_traits", since = "1.12.0")] impl<'a> Sum<&'a $a> for $a { fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a { - iter.fold(0.0, |a, b| a + *b) + iter.fold(0.0, Add::add) } } #[stable(feature = "iter_arith_traits", since = "1.12.0")] impl<'a> Product<&'a $a> for $a { fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a { - iter.fold(1.0, |a, b| a * *b) + iter.fold(1.0, Mul::mul) } } )*) diff --git a/src/libcore/iter/traits/double_ended.rs b/src/libcore/iter/traits/double_ended.rs index 2c1aeb5690a..8e5bc9b664c 100644 --- a/src/libcore/iter/traits/double_ended.rs +++ b/src/libcore/iter/traits/double_ended.rs @@ -219,12 +219,17 @@ pub trait DoubleEndedIterator: Iterator { /// ``` #[inline] #[stable(feature = "iter_rfold", since = "1.27.0")] - fn rfold<B, F>(mut self, accum: B, mut f: F) -> B + fn rfold<B, F>(mut self, accum: B, f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> B, { - self.try_rfold(accum, move |acc, x| Ok::<B, !>(f(acc, x))).unwrap() + #[inline] + fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> { + move |acc, x| Ok(f(acc, x)) + } + + self.try_rfold(accum, ok(f)).unwrap() } /// Searches for an element of an iterator from the back that satisfies a predicate. @@ -271,15 +276,21 @@ pub trait DoubleEndedIterator: Iterator { /// ``` #[inline] #[stable(feature = "iter_rfind", since = "1.27.0")] - fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item> + fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where Self: Sized, P: FnMut(&Self::Item) -> bool { - self.try_rfold((), move |(), x| { - if predicate(&x) { LoopState::Break(x) } - else { LoopState::Continue(()) } - }).break_value() + #[inline] + fn check<T>( + mut predicate: impl FnMut(&T) -> bool, + ) -> impl FnMut((), T) -> LoopState<(), T> { + move |(), x| { + if predicate(&x) { LoopState::Break(x) } else { LoopState::Continue(()) } + } + } + + self.try_rfold((), check(predicate)).break_value() } } diff --git a/src/libcore/iter/traits/iterator.rs b/src/libcore/iter/traits/iterator.rs index 7e941267ce8..d644787d2c4 100644 --- a/src/libcore/iter/traits/iterator.rs +++ b/src/libcore/iter/traits/iterator.rs @@ -1,5 +1,5 @@ use crate::cmp::Ordering; -use crate::ops::Try; +use crate::ops::{Add, Try}; use super::super::LoopState; use super::super::{Chain, Cycle, Copied, Cloned, Enumerate, Filter, FilterMap, Fuse}; @@ -234,11 +234,15 @@ pub trait Iterator { /// assert_eq!(a.iter().count(), 5); /// ``` #[inline] - #[rustc_inherit_overflow_checks] #[stable(feature = "rust1", since = "1.0.0")] fn count(self) -> usize where Self: Sized { - // Might overflow. - self.fold(0, |cnt, _| cnt + 1) + #[inline] + fn add1<T>(count: usize, _: T) -> usize { + // Might overflow. + Add::add(count, 1) + } + + self.fold(0, add1) } /// Consumes the iterator, returning the last element. @@ -263,7 +267,12 @@ pub trait Iterator { #[inline] #[stable(feature = "rust1", since = "1.0.0")] fn last(self) -> Option<Self::Item> where Self: Sized { - self.fold(None, |_, x| Some(x)) + #[inline] + fn some<T>(_: Option<T>, x: T) -> Option<T> { + Some(x) + } + + self.fold(None, some) } /// Returns the `n`th element of the iterator. @@ -596,10 +605,15 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_for_each", since = "1.21.0")] - fn for_each<F>(self, mut f: F) where + fn for_each<F>(self, f: F) where Self: Sized, F: FnMut(Self::Item), { - self.fold((), move |(), item| f(item)); + #[inline] + fn call<T>(mut f: impl FnMut(T)) -> impl FnMut((), T) { + move |(), item| f(item) + } + + self.fold((), call(f)); } /// Creates an iterator which uses a closure to determine if an element @@ -1490,21 +1504,30 @@ pub trait Iterator { /// assert_eq!(odd, vec![1, 3]); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - fn partition<B, F>(self, mut f: F) -> (B, B) where + fn partition<B, F>(self, f: F) -> (B, B) where Self: Sized, B: Default + Extend<Self::Item>, F: FnMut(&Self::Item) -> bool { + #[inline] + fn extend<'a, T, B: Extend<T>>( + mut f: impl FnMut(&T) -> bool + 'a, + left: &'a mut B, + right: &'a mut B, + ) -> impl FnMut(T) + 'a { + move |x| { + if f(&x) { + left.extend(Some(x)); + } else { + right.extend(Some(x)); + } + } + } + let mut left: B = Default::default(); let mut right: B = Default::default(); - self.for_each(|x| { - if f(&x) { - left.extend(Some(x)) - } else { - right.extend(Some(x)) - } - }); + self.for_each(extend(f, &mut left, &mut right)); (left, right) } @@ -1702,10 +1725,15 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_try_fold", since = "1.27.0")] - fn try_for_each<F, R>(&mut self, mut f: F) -> R where + fn try_for_each<F, R>(&mut self, f: F) -> R where Self: Sized, F: FnMut(Self::Item) -> R, R: Try<Ok=()> { - self.try_fold((), move |(), x| f(x)) + #[inline] + fn call<T, R>(mut f: impl FnMut(T) -> R) -> impl FnMut((), T) -> R { + move |(), x| f(x) + } + + self.try_fold((), call(f)) } /// An iterator method that applies a function, producing a single, final value. @@ -1777,10 +1805,15 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn fold<B, F>(mut self, init: B, mut f: F) -> B where + fn fold<B, F>(mut self, init: B, f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> B, { - self.try_fold(init, move |acc, x| Ok::<B, !>(f(acc, x))).unwrap() + #[inline] + fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> { + move |acc, x| Ok(f(acc, x)) + } + + self.try_fold(init, ok(f)).unwrap() } /// Tests if every element of the iterator matches a predicate. @@ -1822,13 +1855,18 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn all<F>(&mut self, mut f: F) -> bool where + fn all<F>(&mut self, f: F) -> bool where Self: Sized, F: FnMut(Self::Item) -> bool { - self.try_for_each(move |x| { - if f(x) { LoopState::Continue(()) } - else { LoopState::Break(()) } - }) == LoopState::Continue(()) + #[inline] + fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut(T) -> LoopState<(), ()> { + move |x| { + if f(x) { LoopState::Continue(()) } + else { LoopState::Break(()) } + } + } + + self.try_for_each(check(f)) == LoopState::Continue(()) } /// Tests if any element of the iterator matches a predicate. @@ -1870,14 +1908,19 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn any<F>(&mut self, mut f: F) -> bool where + fn any<F>(&mut self, f: F) -> bool where Self: Sized, F: FnMut(Self::Item) -> bool { - self.try_for_each(move |x| { - if f(x) { LoopState::Break(()) } - else { LoopState::Continue(()) } - }) == LoopState::Break(()) + #[inline] + fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut(T) -> LoopState<(), ()> { + move |x| { + if f(x) { LoopState::Break(()) } + else { LoopState::Continue(()) } + } + } + + self.try_for_each(check(f)) == LoopState::Break(()) } /// Searches for an element of an iterator that satisfies a predicate. @@ -1924,14 +1967,19 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where + fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where Self: Sized, P: FnMut(&Self::Item) -> bool, { - self.try_for_each(move |x| { - if predicate(&x) { LoopState::Break(x) } - else { LoopState::Continue(()) } - }).break_value() + #[inline] + fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> LoopState<(), T> { + move |x| { + if predicate(&x) { LoopState::Break(x) } + else { LoopState::Continue(()) } + } + } + + self.try_for_each(check(predicate)).break_value() } /// Applies function to the elements of iterator and returns @@ -1951,16 +1999,19 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_find_map", since = "1.30.0")] - fn find_map<B, F>(&mut self, mut f: F) -> Option<B> where + fn find_map<B, F>(&mut self, f: F) -> Option<B> where Self: Sized, F: FnMut(Self::Item) -> Option<B>, { - self.try_for_each(move |x| { - match f(x) { + #[inline] + fn check<T, B>(mut f: impl FnMut(T) -> Option<B>) -> impl FnMut(T) -> LoopState<(), B> { + move |x| match f(x) { Some(x) => LoopState::Break(x), None => LoopState::Continue(()), } - }).break_value() + } + + self.try_for_each(check(f)).break_value() } /// Searches for an element in an iterator, returning its index. @@ -2018,17 +2069,23 @@ pub trait Iterator { /// /// ``` #[inline] - #[rustc_inherit_overflow_checks] #[stable(feature = "rust1", since = "1.0.0")] - fn position<P>(&mut self, mut predicate: P) -> Option<usize> where + fn position<P>(&mut self, predicate: P) -> Option<usize> where Self: Sized, P: FnMut(Self::Item) -> bool, { - // The addition might panic on overflow - self.try_fold(0, move |i, x| { - if predicate(x) { LoopState::Break(i) } - else { LoopState::Continue(i + 1) } - }).break_value() + #[inline] + fn check<T>( + mut predicate: impl FnMut(T) -> bool, + ) -> impl FnMut(usize, T) -> LoopState<usize, usize> { + // The addition might panic on overflow + move |i, x| { + if predicate(x) { LoopState::Break(i) } + else { LoopState::Continue(Add::add(i, 1)) } + } + } + + self.try_fold(0, check(predicate)).break_value() } /// Searches for an element in an iterator from the right, returning its @@ -2071,18 +2128,25 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where + fn rposition<P>(&mut self, predicate: P) -> Option<usize> where P: FnMut(Self::Item) -> bool, Self: Sized + ExactSizeIterator + DoubleEndedIterator { // No need for an overflow check here, because `ExactSizeIterator` // implies that the number of elements fits into a `usize`. + #[inline] + fn check<T>( + mut predicate: impl FnMut(T) -> bool, + ) -> impl FnMut(usize, T) -> LoopState<usize, usize> { + move |i, x| { + let i = i - 1; + if predicate(x) { LoopState::Break(i) } + else { LoopState::Continue(i) } + } + } + let n = self.len(); - self.try_rfold(n, move |i, x| { - let i = i - 1; - if predicate(x) { LoopState::Break(i) } - else { LoopState::Continue(i) } - }).break_value() + self.try_rfold(n, check(predicate)).break_value() } /// Returns the maximum element of an iterator. @@ -2151,11 +2215,22 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_cmp_by_key", since = "1.6.0")] - fn max_by_key<B: Ord, F>(self, mut f: F) -> Option<Self::Item> + fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item> where Self: Sized, F: FnMut(&Self::Item) -> B, { + #[inline] + fn key<T, B>(mut f: impl FnMut(&T) -> B) -> impl FnMut(T) -> (B, T) { + move |x| (f(&x), x) + } + // switch to y even if it is only equal, to preserve stability. - select_fold1(self.map(|x| (f(&x), x)), |(x_p, _), (y_p, _)| x_p <= y_p).map(|(_, x)| x) + #[inline] + fn select<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> bool { + x_p <= y_p + } + + let (_, x) = select_fold1(self.map(key(f)), select)?; + Some(x) } /// Returns the element that gives the maximum value with respect to the @@ -2174,11 +2249,16 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_max_by", since = "1.15.0")] - fn max_by<F>(self, mut compare: F) -> Option<Self::Item> + fn max_by<F>(self, compare: F) -> Option<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering, { // switch to y even if it is only equal, to preserve stability. - select_fold1(self, |x, y| compare(x, y) != Ordering::Greater) + #[inline] + fn select<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(&T, &T) -> bool { + move |x, y| compare(x, y) != Ordering::Greater + } + + select_fold1(self, select(compare)) } /// Returns the element that gives the minimum value from the @@ -2195,12 +2275,24 @@ pub trait Iterator { /// let a = [-3_i32, 0, 1, 5, -10]; /// assert_eq!(*a.iter().min_by_key(|x| x.abs()).unwrap(), 0); /// ``` + #[inline] #[stable(feature = "iter_cmp_by_key", since = "1.6.0")] - fn min_by_key<B: Ord, F>(self, mut f: F) -> Option<Self::Item> + fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item> where Self: Sized, F: FnMut(&Self::Item) -> B, { + #[inline] + fn key<T, B>(mut f: impl FnMut(&T) -> B) -> impl FnMut(T) -> (B, T) { + move |x| (f(&x), x) + } + // only switch to y if it is strictly smaller, to preserve stability. - select_fold1(self.map(|x| (f(&x), x)), |(x_p, _), (y_p, _)| x_p > y_p).map(|(_, x)| x) + #[inline] + fn select<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> bool { + x_p > y_p + } + + let (_, x) = select_fold1(self.map(key(f)), select)?; + Some(x) } /// Returns the element that gives the minimum value with respect to the @@ -2219,11 +2311,16 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_min_by", since = "1.15.0")] - fn min_by<F>(self, mut compare: F) -> Option<Self::Item> + fn min_by<F>(self, compare: F) -> Option<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering, { // only switch to y if it is strictly smaller, to preserve stability. - select_fold1(self, |x, y| compare(x, y) == Ordering::Greater) + #[inline] + fn select<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(&T, &T) -> bool { + move |x, y| compare(x, y) == Ordering::Greater + } + + select_fold1(self, select(compare)) } @@ -2284,13 +2381,20 @@ pub trait Iterator { FromB: Default + Extend<B>, Self: Sized + Iterator<Item=(A, B)>, { + fn extend<'a, A, B>( + ts: &'a mut impl Extend<A>, + us: &'a mut impl Extend<B>, + ) -> impl FnMut((A, B)) + 'a { + move |(t, u)| { + ts.extend(Some(t)); + us.extend(Some(u)); + } + } + let mut ts: FromA = Default::default(); let mut us: FromB = Default::default(); - self.for_each(|(t, u)| { - ts.extend(Some(t)); - us.extend(Some(u)); - }); + self.for_each(extend(&mut ts, &mut us)); (ts, us) } @@ -2617,7 +2721,7 @@ pub trait Iterator { Self: Sized, Self::Item: PartialOrd, { - self.is_sorted_by(|a, b| a.partial_cmp(b)) + self.is_sorted_by(PartialOrd::partial_cmp) } /// Checks if the elements of this iterator are sorted using the given comparator function. @@ -2639,10 +2743,7 @@ pub trait Iterator { }; while let Some(curr) = self.next() { - if compare(&last, &curr) - .map(|o| o == Ordering::Greater) - .unwrap_or(true) - { + if let Some(Ordering::Greater) | None = compare(&last, &curr) { return false; } last = curr; @@ -2687,17 +2788,21 @@ pub trait Iterator { /// commonalities of {max,min}{,_by}. In particular, this avoids /// having to implement optimizations several times. #[inline] -fn select_fold1<I, F>(mut it: I, mut f: F) -> Option<I::Item> +fn select_fold1<I, F>(mut it: I, f: F) -> Option<I::Item> where I: Iterator, F: FnMut(&I::Item, &I::Item) -> bool, { + #[inline] + fn select<T>(mut f: impl FnMut(&T, &T) -> bool) -> impl FnMut(T, T) -> T { + move |sel, x| if f(&sel, &x) { x } else { sel } + } + // start with the first element as our selection. This avoids // having to use `Option`s inside the loop, translating to a // sizeable performance gain (6x in one case). - it.next().map(|first| { - it.fold(first, |sel, x| if f(&sel, &x) { x } else { sel }) - }) + let first = it.next()?; + Some(it.fold(first, select(f))) } #[stable(feature = "rust1", since = "1.0.0")] diff --git a/src/test/codegen/iter-fold-closure-no-dupes.rs b/src/test/codegen/iter-fold-closure-no-dupes.rs new file mode 100644 index 00000000000..ec58f7068ab --- /dev/null +++ b/src/test/codegen/iter-fold-closure-no-dupes.rs @@ -0,0 +1,14 @@ +//! Check that fold closures aren't duplicated for each iterator type. +// compile-flags: -C opt-level=0 + +fn main() { + (0i32..10).by_ref().count(); + (0i32..=10).by_ref().count(); +} + +// `count` calls `fold`, which calls `try_fold` -- find the `fold` closure: +// CHECK: {{^define.*Iterator::fold::.*closure}} +// +// Only one closure is needed for both `count` calls, even from different +// monomorphized iterator types, as it's only generic over the item type. +// CHECK-NOT: {{^define.*Iterator::fold::.*closure}} diff --git a/src/test/codegen/iter-fold-closure-no-iterator.rs b/src/test/codegen/iter-fold-closure-no-iterator.rs new file mode 100644 index 00000000000..fbeafd5f395 --- /dev/null +++ b/src/test/codegen/iter-fold-closure-no-iterator.rs @@ -0,0 +1,10 @@ +//! Check that fold closures aren't generic in the iterator type. +// compile-flags: -C opt-level=0 + +fn main() { + (0i32..10).by_ref().count(); +} + +// `count` calls `fold`, which calls `try_fold` -- that `fold` closure should +// not be generic in the iterator type, only in the item type. +// CHECK-NOT: {{^define.*Iterator::fold::.*closure.*Range}} diff --git a/src/test/ui/iterators/iter-count-overflow-debug.rs b/src/test/ui/iterators/iter-count-overflow-debug.rs new file mode 100644 index 00000000000..d6612035750 --- /dev/null +++ b/src/test/ui/iterators/iter-count-overflow-debug.rs @@ -0,0 +1,16 @@ +// run-pass +// only-32bit too impatient for 2⁶⁴ items +// ignore-wasm32-bare compiled with panic=abort by default +// compile-flags: -C debug_assertions=yes -C opt-level=3 + +use std::panic; +use std::usize::MAX; + +fn main() { + assert_eq!((0..MAX).by_ref().count(), MAX); + + let r = panic::catch_unwind(|| { + (0..=MAX).by_ref().count() + }); + assert!(r.is_err()); +} diff --git a/src/test/ui/iterators/iter-count-overflow-ndebug.rs b/src/test/ui/iterators/iter-count-overflow-ndebug.rs new file mode 100644 index 00000000000..b755bb554f4 --- /dev/null +++ b/src/test/ui/iterators/iter-count-overflow-ndebug.rs @@ -0,0 +1,11 @@ +// run-pass +// only-32bit too impatient for 2⁶⁴ items +// compile-flags: -C debug_assertions=no -C opt-level=3 + +use std::panic; +use std::usize::MAX; + +fn main() { + assert_eq!((0..MAX).by_ref().count(), MAX); + assert_eq!((0..=MAX).by_ref().count(), 0); +} diff --git a/src/test/ui/iterators/iter-map-fold-type-length.rs b/src/test/ui/iterators/iter-map-fold-type-length.rs new file mode 100644 index 00000000000..8ce4fcd8731 --- /dev/null +++ b/src/test/ui/iterators/iter-map-fold-type-length.rs @@ -0,0 +1,38 @@ +// run-pass +//! Check that type lengths don't explode with `Map` folds. +//! +//! The normal limit is a million, and this test used to exceed 1.5 million, but +//! now we can survive an even tighter limit. Still seems excessive though... +#![type_length_limit = "256000"] + +// Custom wrapper so Iterator methods aren't specialized. +struct Iter<I>(I); + +impl<I> Iterator for Iter<I> +where + I: Iterator +{ + type Item = I::Item; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next() + } +} + +fn main() { + let c = Iter(0i32..10) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .map(|x| x) + .count(); + assert_eq!(c, 10); +} diff --git a/src/test/ui/iterators/iter-position-overflow-debug.rs b/src/test/ui/iterators/iter-position-overflow-debug.rs new file mode 100644 index 00000000000..f1eded31702 --- /dev/null +++ b/src/test/ui/iterators/iter-position-overflow-debug.rs @@ -0,0 +1,22 @@ +// run-pass +// only-32bit too impatient for 2⁶⁴ items +// ignore-wasm32-bare compiled with panic=abort by default +// compile-flags: -C debug_assertions=yes -C opt-level=3 + +use std::panic; +use std::usize::MAX; + +fn main() { + let n = MAX as u64; + assert_eq!((0..).by_ref().position(|i| i >= n), Some(MAX)); + + let r = panic::catch_unwind(|| { + (0..).by_ref().position(|i| i > n) + }); + assert!(r.is_err()); + + let r = panic::catch_unwind(|| { + (0..=n + 1).by_ref().position(|_| false) + }); + assert!(r.is_err()); +} diff --git a/src/test/ui/iterators/iter-position-overflow-ndebug.rs b/src/test/ui/iterators/iter-position-overflow-ndebug.rs new file mode 100644 index 00000000000..368f9c0c02b --- /dev/null +++ b/src/test/ui/iterators/iter-position-overflow-ndebug.rs @@ -0,0 +1,13 @@ +// run-pass +// only-32bit too impatient for 2⁶⁴ items +// compile-flags: -C debug_assertions=no -C opt-level=3 + +use std::panic; +use std::usize::MAX; + +fn main() { + let n = MAX as u64; + assert_eq!((0..).by_ref().position(|i| i >= n), Some(MAX)); + assert_eq!((0..).by_ref().position(|i| i > n), Some(0)); + assert_eq!((0..=n + 1).by_ref().position(|_| false), None); +} |