Make `fold` standalone.

`fold` is currently implemented via `try_fold`, but implementing it
directly results in slightly less LLVM IR being generated, speeding up
compilation of some benchmarks.

(And likewise for `rfold`.)

The commit adds `fold` implementations to all the iterators that lack
one but do have a `try_fold` implementation. Most of these just call the
`try_fold` implementation directly.

6 files changed, 124 insertions, 37 deletions

diff --git a/src/libcore/iter/adapters/mod.rs b/src/libcore/iter/adapters/mod.rs
index e9fc1b612dd..939a26cb702 100644
--- a/src/libcore/iter/adapters/mod.rs
+++ b/src/libcore/iter/adapters/mod.rs
@@ -512,6 +512,9 @@ where
             acc = self.iter.try_fold(acc, &mut f)?;
         }
     }
+
+    // No `fold` override, because `fold` doesn't make much sense for `Cycle`,
+    // and we can't do anything better than the default.
 }
 
 #[stable(feature = "fused", since = "1.26.0")]
@@ -643,6 +646,25 @@ where
         }
         from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
     }
+
+    fn fold<Acc, F>(mut self, mut acc: Acc, mut f: F) -> Acc
+    where
+        F: FnMut(Acc, Self::Item) -> Acc,
+    {
+        #[inline]
+        fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
+            move || iter.nth(step)
+        }
+
+        if self.first_take {
+            self.first_take = false;
+            match self.iter.next() {
+                None => return acc,
+                Some(x) => acc = f(acc, x),
+            }
+        }
+        from_fn(nth(&mut self.iter, self.step)).fold(acc, f)
+    }
 }
 
 impl<I> StepBy<I>
@@ -1767,6 +1789,20 @@ where
             self.iter.try_fold(init, check(flag, p, fold)).into_try()
         }
     }
+
+    #[inline]
+    fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
+    where
+        Self: Sized,
+        Fold: FnMut(Acc, Self::Item) -> Acc,
+    {
+        #[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(fold)).unwrap()
+    }
 }
 
 #[stable(feature = "fused", since = "1.26.0")]
@@ -1838,6 +1874,20 @@ where
         })
         .into_try()
     }
+
+    #[inline]
+    fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
+    where
+        Self: Sized,
+        Fold: FnMut(Acc, Self::Item) -> Acc,
+    {
+        #[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(fold)).unwrap()
+    }
 }
 
 /// An iterator that skips over `n` elements of `iter`.
@@ -2105,6 +2155,20 @@ where
             self.iter.try_fold(init, check(n, fold)).into_try()
         }
     }
+
+    #[inline]
+    fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
+    where
+        Self: Sized,
+        Fold: FnMut(Acc, Self::Item) -> Acc,
+    {
+        #[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(fold)).unwrap()
+    }
 }
 
 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
@@ -2237,6 +2301,20 @@ where
         let f = &mut self.f;
         self.iter.try_fold(init, scan(state, f, fold)).into_try()
     }
+
+    #[inline]
+    fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
+    where
+        Self: Sized,
+        Fold: FnMut(Acc, Self::Item) -> Acc,
+    {
+        #[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(fold)).unwrap()
+    }
 }
 
 /// An iterator that calls a function with a reference to each element before
@@ -2444,4 +2522,17 @@ where
             })
             .into_try()
     }
+
+    fn fold<B, F>(mut self, init: B, fold: F) -> B
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> B,
+    {
+        #[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(fold)).unwrap()
+    }
 }
diff --git a/src/libcore/iter/range.rs b/src/libcore/iter/range.rs
index d74df82bddd..6ac9576a46d 100644
--- a/src/libcore/iter/range.rs
+++ b/src/libcore/iter/range.rs
@@ -659,6 +659,19 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
     }
 
     #[inline]
+    fn fold<B, F>(mut self, init: B, f: F) -> B
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> B,
+    {
+        #[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()
+    }
+    #[inline]
     fn last(mut self) -> Option<A> {
         self.next_back()
     }
diff --git a/src/libcore/iter/traits/double_ended.rs b/src/libcore/iter/traits/double_ended.rs
index 104724d9fb6..cceb373d552 100644
--- a/src/libcore/iter/traits/double_ended.rs
+++ b/src/libcore/iter/traits/double_ended.rs
@@ -221,17 +221,16 @@ pub trait DoubleEndedIterator: Iterator {
     /// ```
     #[inline]
     #[stable(feature = "iter_rfold", since = "1.27.0")]
-    fn rfold<B, F>(mut self, accum: B, f: F) -> B
+    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
     where
         Self: Sized,
         F: FnMut(B, Self::Item) -> B,
     {
-        #[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))
+        let mut accum = init;
+        while let Some(x) = self.next_back() {
+            accum = f(accum, x);
         }
-
-        self.try_rfold(accum, ok(f)).unwrap()
+        accum
     }
 
     /// Searches for an element of an iterator from the back that satisfies a predicate.
diff --git a/src/libcore/iter/traits/iterator.rs b/src/libcore/iter/traits/iterator.rs
index 447db405c02..d20c6790d4a 100644
--- a/src/libcore/iter/traits/iterator.rs
+++ b/src/libcore/iter/traits/iterator.rs
@@ -1826,7 +1826,7 @@ pub trait Iterator {
     ///
     /// # Note to Implementors
     ///
-    /// Most of the other (forward) methods have default implementations in
+    /// Several of the other (forward) methods have default implementations in
     /// terms of this one, so try to implement this explicitly if it can
     /// do something better than the default `for` loop implementation.
     ///
@@ -1944,6 +1944,15 @@ pub trait Iterator {
     /// may not terminate for infinite iterators, even on traits for which a
     /// result is determinable in finite time.
     ///
+    /// # Note to Implementors
+    ///
+    /// Several of the other (forward) methods have default implementations in
+    /// terms of this one, so try to implement this explicitly if it can
+    /// do something better than the default `for` loop implementation.
+    ///
+    /// In particular, try to have this call `fold()` on the internal parts
+    /// from which this iterator is composed.
+    ///
     /// # Examples
     ///
     /// Basic usage:
@@ -1992,17 +2001,16 @@ pub trait Iterator {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn fold<B, F>(mut self, init: B, f: F) -> B
+    fn fold<B, F>(mut self, init: B, mut f: F) -> B
     where
         Self: Sized,
         F: FnMut(B, Self::Item) -> B,
     {
-        #[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))
+        let mut accum = init;
+        while let Some(x) = self.next() {
+            accum = f(accum, x);
         }
-
-        self.try_fold(init, ok(f)).unwrap()
+        accum
     }
 
     /// The same as [`fold()`](#method.fold), but uses the first element in the
diff --git a/src/test/codegen/iter-fold-closure-no-dupes.rs b/src/test/codegen/iter-fold-closure-no-dupes.rs
deleted file mode 100644
index ec58f7068ab..00000000000
--- a/src/test/codegen/iter-fold-closure-no-dupes.rs
+++ /dev/null
@@ -1,14 +0,0 @@
-//! 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
deleted file mode 100644
index fbeafd5f395..00000000000
--- a/src/test/codegen/iter-fold-closure-no-iterator.rs
+++ /dev/null
@@ -1,10 +0,0 @@
-//! 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}}