Auto merge of #45595 - scottmcm:iter-try-fold, r=dtolnay

Short-circuiting internal iteration with Iterator::try_fold & try_rfold

These are the core methods in terms of which the other methods (`fold`, `all`, `any`, `find`, `position`, `nth`, ...) can be implemented, allowing Iterator implementors to get the full goodness of internal iteration by only overriding one method (per direction).

Based off the `Try` trait, so works with both `Result` and `Option` (:tada: https://github.com/rust-lang/rust/pull/42526).  The `try_fold` rustdoc examples use `Option` and the `try_rfold` ones use `Result`.

AKA continuing in the vein of PRs https://github.com/rust-lang/rust/pull/44682 & https://github.com/rust-lang/rust/pull/44856 for more of `Iterator`.

New bench following the pattern from the latter of those:
```
test iter::bench_take_while_chain_ref_sum          ... bench:   1,130,843 ns/iter (+/- 25,110)
test iter::bench_take_while_chain_sum              ... bench:     362,530 ns/iter (+/- 391)
```

I also ran the benches without the `fold` & `rfold` overrides to test their new default impls, with basically no change.  I left them there, though, to take advantage of existing overrides and because `AlwaysOk` has some sub-optimality due to https://github.com/rust-lang/rust/issues/43278 (which 45225 should fix).

If you're wondering why there are three type parameters, see issue https://github.com/rust-lang/rust/issues/45462

Thanks for @bluss for the [original IRLO thread](https://internals.rust-lang.org/t/pre-rfc-fold-ok-is-composable-internal-iteration/4434) and the rfold PR and to @cuviper for adding so many folds, [encouraging me](https://github.com/rust-lang/rust/pull/45379#issuecomment-339424670) to make this PR, and finding a catastrophic bug in a pre-review.

8 files changed, 929 insertions, 182 deletions

diff --git a/src/libcore/benches/iter.rs b/src/libcore/benches/iter.rs
index 1f16f5b1df3..b284d855c45 100644
--- a/src/libcore/benches/iter.rs
+++ b/src/libcore/benches/iter.rs
@@ -275,3 +275,9 @@ bench_sums! {
     bench_skip_while_chain_ref_sum,
     (0i64..1000000).chain(0..1000000).skip_while(|&x| x < 1000)
 }
+
+bench_sums! {
+    bench_take_while_chain_sum,
+    bench_take_while_chain_ref_sum,
+    (0i64..1000000).chain(1000000..).take_while(|&x| x < 1111111)
+}
diff --git a/src/libcore/iter/iterator.rs b/src/libcore/iter/iterator.rs
index 79767b37601..6a4dba31b62 100644
--- a/src/libcore/iter/iterator.rs
+++ b/src/libcore/iter/iterator.rs
@@ -9,7 +9,9 @@
 // except according to those terms.
 
 use cmp::Ordering;
+use ops::Try;
 
+use super::{AlwaysOk, LoopState};
 use super::{Chain, Cycle, Cloned, Enumerate, Filter, FilterMap, FlatMap, Fuse};
 use super::{Inspect, Map, Peekable, Scan, Skip, SkipWhile, StepBy, Take, TakeWhile, Rev};
 use super::{Zip, Sum, Product};
@@ -251,12 +253,8 @@ pub trait Iterator {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
-        for x in self {
-            if n == 0 { return Some(x) }
-            n -= 1;
-        }
-        None
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        self.spec_nth(n)
     }
 
     /// Creates an iterator starting at the same point, but stepping by
@@ -1337,6 +1335,78 @@ pub trait Iterator {
         (left, right)
     }
 
+    /// An iterator method that applies a function as long as it returns
+    /// successfully, producing a single, final value.
+    ///
+    /// `try_fold()` takes two arguments: an initial value, and a closure with
+    /// two arguments: an 'accumulator', and an element. The closure either
+    /// returns successfully, with the value that the accumulator should have
+    /// for the next iteration, or it returns failure, with an error value that
+    /// is propagated back to the caller immediately (short-circuiting).
+    ///
+    /// The initial value is the value the accumulator will have on the first
+    /// call.  If applying the closure succeeded against every element of the
+    /// iterator, `try_fold()` returns the final accumulator as success.
+    ///
+    /// Folding is useful whenever you have a collection of something, and want
+    /// to produce a single value from it.
+    ///
+    /// # Note to Implementors
+    ///
+    /// Most 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 `try_fold()` on the internal parts
+    /// from which this iterator is composed.  If multiple calls are needed,
+    /// the `?` operator be convenient for chaining the accumulator value along,
+    /// but beware any invariants that need to be upheld before those early
+    /// returns.  This is a `&mut self` method, so iteration needs to be
+    /// resumable after hitting an error here.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(iterator_try_fold)]
+    /// let a = [1, 2, 3];
+    ///
+    /// // the checked sum of all of the elements of the array
+    /// let sum = a.iter()
+    ///            .try_fold(0i8, |acc, &x| acc.checked_add(x));
+    ///
+    /// assert_eq!(sum, Some(6));
+    /// ```
+    ///
+    /// Short-circuiting:
+    ///
+    /// ```
+    /// #![feature(iterator_try_fold)]
+    /// let a = [10, 20, 30, 100, 40, 50];
+    /// let mut it = a.iter();
+    ///
+    /// // This sum overflows when adding the 100 element
+    /// let sum = it.try_fold(0i8, |acc, &x| acc.checked_add(x));
+    /// assert_eq!(sum, None);
+    ///
+    /// // Because it short-circuited, the remaining elements are still
+    /// // available through the iterator.
+    /// assert_eq!(it.len(), 2);
+    /// assert_eq!(it.next(), Some(&40));
+    /// ```
+    #[inline]
+    #[unstable(feature = "iterator_try_fold", issue = "45594")]
+    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    {
+        let mut accum = init;
+        while let Some(x) = self.next() {
+            accum = f(accum, x)?;
+        }
+        Try::from_ok(accum)
+    }
+
     /// An iterator method that applies a function, producing a single, final value.
     ///
     /// `fold()` takes two arguments: an initial value, and a closure with two
@@ -1361,7 +1431,7 @@ pub trait Iterator {
     /// ```
     /// let a = [1, 2, 3];
     ///
-    /// // the sum of all of the elements of a
+    /// // the sum of all of the elements of the array
     /// let sum = a.iter()
     ///            .fold(0, |acc, &x| acc + x);
     ///
@@ -1403,14 +1473,10 @@ pub trait Iterator {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn fold<B, F>(self, init: B, mut f: F) -> B where
+    fn fold<B, F>(mut self, init: B, mut f: F) -> B where
         Self: Sized, F: FnMut(B, Self::Item) -> B,
     {
-        let mut accum = init;
-        for x in self {
-            accum = f(accum, x);
-        }
-        accum
+        self.try_fold(init, move |acc, x| AlwaysOk(f(acc, x))).0
     }
 
     /// Tests if every element of the iterator matches a predicate.
@@ -1455,12 +1521,10 @@ pub trait Iterator {
     fn all<F>(&mut self, mut f: F) -> bool where
         Self: Sized, F: FnMut(Self::Item) -> bool
     {
-        for x in self {
-            if !f(x) {
-                return false;
-            }
-        }
-        true
+        self.try_fold((), move |(), x| {
+            if f(x) { LoopState::Continue(()) }
+            else { LoopState::Break(()) }
+        }) == LoopState::Continue(())
     }
 
     /// Tests if any element of the iterator matches a predicate.
@@ -1506,12 +1570,10 @@ pub trait Iterator {
         Self: Sized,
         F: FnMut(Self::Item) -> bool
     {
-        for x in self {
-            if f(x) {
-                return true;
-            }
-        }
-        false
+        self.try_fold((), move |(), x| {
+            if f(x) { LoopState::Break(()) }
+            else { LoopState::Continue(()) }
+        }) == LoopState::Break(())
     }
 
     /// Searches for an element of an iterator that satisfies a predicate.
@@ -1562,10 +1624,10 @@ pub trait Iterator {
         Self: Sized,
         P: FnMut(&Self::Item) -> bool,
     {
-        for x in self {
-            if predicate(&x) { return Some(x) }
-        }
-        None
+        self.try_fold((), move |(), x| {
+            if predicate(&x) { LoopState::Break(x) }
+            else { LoopState::Continue(()) }
+        }).break_value()
     }
 
     /// Searches for an element in an iterator, returning its index.
@@ -1623,18 +1685,17 @@ 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
         Self: Sized,
         P: FnMut(Self::Item) -> bool,
     {
-        // `enumerate` might overflow.
-        for (i, x) in self.enumerate() {
-            if predicate(x) {
-                return Some(i);
-            }
-        }
-        None
+        // 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()
     }
 
     /// Searches for an element in an iterator from the right, returning its
@@ -1681,17 +1742,14 @@ pub trait Iterator {
         P: FnMut(Self::Item) -> bool,
         Self: Sized + ExactSizeIterator + DoubleEndedIterator
     {
-        let mut i = self.len();
-
-        while let Some(v) = self.next_back() {
-            // No need for an overflow check here, because `ExactSizeIterator`
-            // implies that the number of elements fits into a `usize`.
-            i -= 1;
-            if predicate(v) {
-                return Some(i);
-            }
-        }
-        None
+        // No need for an overflow check here, because `ExactSizeIterator`
+        // implies that the number of elements fits into a `usize`.
+        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()
     }
 
     /// Returns the maximum element of an iterator.
@@ -1922,10 +1980,10 @@ pub trait Iterator {
         let mut ts: FromA = Default::default();
         let mut us: FromB = Default::default();
 
-        for (t, u) in self {
+        self.for_each(|(t, u)| {
             ts.extend(Some(t));
             us.extend(Some(u));
-        }
+        });
 
         (ts, us)
     }
@@ -2300,17 +2358,17 @@ fn select_fold1<I, B, FProj, FCmp>(mut it: I,
     // 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(|mut sel| {
-        let mut sel_p = f_proj(&sel);
+    it.next().map(|first| {
+        let first_p = f_proj(&first);
 
-        for x in it {
+        it.fold((first_p, first), |(sel_p, sel), x| {
             let x_p = f_proj(&x);
             if f_cmp(&sel_p, &sel, &x_p, &x) {
-                sel = x;
-                sel_p = x_p;
+                (x_p, x)
+            } else {
+                (sel_p, sel)
             }
-        }
-        (sel_p, sel)
+        })
     })
 }
 
@@ -2323,3 +2381,27 @@ impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
         (**self).nth(n)
     }
 }
+
+
+trait SpecIterator : Iterator {
+    fn spec_nth(&mut self, n: usize) -> Option<Self::Item>;
+}
+
+impl<I: Iterator + ?Sized> SpecIterator for I {
+    default fn spec_nth(&mut self, mut n: usize) -> Option<Self::Item> {
+        for x in self {
+            if n == 0 { return Some(x) }
+            n -= 1;
+        }
+        None
+   }
+}
+
+impl<I: Iterator + Sized> SpecIterator for I {
+    fn spec_nth(&mut self, n: usize) -> Option<Self::Item> {
+        self.try_fold(n, move |i, x| {
+            if i == 0 { LoopState::Break(x) }
+            else { LoopState::Continue(i - 1) }
+        }).break_value()
+   }
+}
diff --git a/src/libcore/iter/mod.rs b/src/libcore/iter/mod.rs
index 8d2521b053e..e173f43b5e6 100644
--- a/src/libcore/iter/mod.rs
+++ b/src/libcore/iter/mod.rs
@@ -305,6 +305,7 @@
 use cmp;
 use fmt;
 use iter_private::TrustedRandomAccess;
+use ops::Try;
 use usize;
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -336,6 +337,71 @@ mod range;
 mod sources;
 mod traits;
 
+/// Transparent newtype used to implement foo methods in terms of try_foo.
+/// Important until #43278 is fixed; might be better as `Result<T, !>` later.
+struct AlwaysOk<T>(pub T);
+
+impl<T> Try for AlwaysOk<T> {
+    type Ok = T;
+    type Error = !;
+    #[inline]
+    fn into_result(self) -> Result<Self::Ok, Self::Error> { Ok(self.0) }
+    #[inline]
+    fn from_error(v: Self::Error) -> Self { v }
+    #[inline]
+    fn from_ok(v: Self::Ok) -> Self { AlwaysOk(v) }
+}
+
+/// Used to make try_fold closures more like normal loops
+#[derive(PartialEq)]
+enum LoopState<C, B> {
+    Continue(C),
+    Break(B),
+}
+
+impl<C, B> Try for LoopState<C, B> {
+    type Ok = C;
+    type Error = B;
+    #[inline]
+    fn into_result(self) -> Result<Self::Ok, Self::Error> {
+        match self {
+            LoopState::Continue(y) => Ok(y),
+            LoopState::Break(x) => Err(x),
+        }
+    }
+    #[inline]
+    fn from_error(v: Self::Error) -> Self { LoopState::Break(v) }
+    #[inline]
+    fn from_ok(v: Self::Ok) -> Self { LoopState::Continue(v) }
+}
+
+impl<C, B> LoopState<C, B> {
+    #[inline]
+    fn break_value(self) -> Option<B> {
+        match self {
+            LoopState::Continue(..) => None,
+            LoopState::Break(x) => Some(x),
+        }
+    }
+}
+
+impl<R: Try> LoopState<R::Ok, R> {
+    #[inline]
+    fn from_try(r: R) -> Self {
+        match Try::into_result(r) {
+            Ok(v) => LoopState::Continue(v),
+            Err(v) => LoopState::Break(Try::from_error(v)),
+        }
+    }
+    #[inline]
+    fn into_try(self) -> R {
+        match self {
+            LoopState::Continue(v) => Try::from_ok(v),
+            LoopState::Break(v) => v,
+        }
+    }
+}
+
 /// A double-ended iterator with the direction inverted.
 ///
 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
@@ -359,6 +425,12 @@ impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 
+    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.iter.try_rfold(init, f)
+    }
+
     fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -385,6 +457,12 @@ impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
     #[inline]
     fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
 
+    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.iter.try_fold(init, f)
+    }
+
     fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -447,6 +525,12 @@ 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
+        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    {
+        self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
+    }
+
     fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -462,6 +546,12 @@ 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
+        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    {
+        self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
+    }
+
     fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -683,6 +773,25 @@ impl<A, B> Iterator for Chain<A, B> where
         }
     }
 
+    fn try_fold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
+        Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
+    {
+        let mut accum = init;
+        match self.state {
+            ChainState::Both | ChainState::Front => {
+                accum = self.a.try_fold(accum, &mut f)?;
+                if let ChainState::Both = self.state {
+                    self.state = ChainState::Back;
+                }
+            }
+            _ => { }
+        }
+        if let ChainState::Back = self.state {
+            accum = self.b.try_fold(accum, &mut f)?;
+        }
+        Try::from_ok(accum)
+    }
+
     fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -792,6 +901,25 @@ impl<A, B> DoubleEndedIterator for Chain<A, B> where
         }
     }
 
+    fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
+        Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
+    {
+        let mut accum = init;
+        match self.state {
+            ChainState::Both | ChainState::Back => {
+                accum = self.b.try_rfold(accum, &mut f)?;
+                if let ChainState::Both = self.state {
+                    self.state = ChainState::Front;
+                }
+            }
+            _ => { }
+        }
+        if let ChainState::Front = self.state {
+            accum = self.a.try_rfold(accum, &mut f)?;
+        }
+        Try::from_ok(accum)
+    }
+
     fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
         where F: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1128,6 +1256,13 @@ 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
+        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)))
+    }
+
     fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
         where G: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1145,6 +1280,13 @@ 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
+        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)))
+    }
+
     fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
         where G: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1252,6 +1394,18 @@ impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool
     }
 
     #[inline]
+    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut 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)
+        })
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1279,6 +1433,18 @@ impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
     }
 
     #[inline]
+    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut 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)
+        })
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1342,6 +1508,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
+        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),
+        })
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1368,6 +1545,17 @@ impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
     }
 
     #[inline]
+    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut 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),
+        })
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1444,6 +1632,19 @@ 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
+        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]
+    #[rustc_inherit_overflow_checks]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1471,6 +1672,19 @@ impl<I> DoubleEndedIterator for Enumerate<I> where
     }
 
     #[inline]
+    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut 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))
+        })
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1595,6 +1809,18 @@ impl<I: Iterator> Iterator for Peekable<I> {
     }
 
     #[inline]
+    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    {
+        let acc = match self.peeked.take() {
+            Some(None) => return Try::from_ok(init),
+            Some(Some(v)) => f(init, v)?,
+            None => init,
+        };
+        self.iter.try_fold(acc, f)
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1699,13 +1925,16 @@ impl<I: Iterator, P> Iterator for SkipWhile<I, P>
 
     #[inline]
     fn next(&mut self) -> Option<I::Item> {
-        for x in self.iter.by_ref() {
-            if self.flag || !(self.predicate)(&x) {
-                self.flag = true;
-                return Some(x);
+        let flag = &mut self.flag;
+        let pred = &mut self.predicate;
+        self.iter.find(move |x| {
+            if *flag || !pred(x) {
+                *flag = true;
+                true
+            } else {
+                false
             }
-        }
-        None
+        })
     }
 
     #[inline]
@@ -1715,6 +1944,19 @@ impl<I: Iterator, P> Iterator for SkipWhile<I, P>
     }
 
     #[inline]
+    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>
+    {
+        if !self.flag {
+            match self.next() {
+                Some(v) => init = fold(init, v)?,
+                None => return Try::from_ok(init),
+            }
+        }
+        self.iter.try_fold(init, fold)
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1785,6 +2027,26 @@ impl<I: Iterator, P> Iterator for TakeWhile<I, P>
         let (_, upper) = self.iter.size_hint();
         (0, upper) // can't know a lower bound, due to the predicate
     }
+
+    #[inline]
+    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut 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|{
+                if p(&x) {
+                    LoopState::from_try(fold(acc, x))
+                } else {
+                    *flag = true;
+                    LoopState::Break(Try::from_ok(acc))
+                }
+            }).into_try()
+        }
+    }
 }
 
 #[unstable(feature = "fused", issue = "35602")]
@@ -1868,6 +2130,21 @@ impl<I> Iterator for Skip<I> where I: Iterator {
     }
 
     #[inline]
+    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 n = self.n;
+        self.n = 0;
+        if n > 0 {
+            // nth(n) skips n+1
+            if self.iter.nth(n - 1).is_none() {
+                return Try::from_ok(init);
+            }
+        }
+        self.iter.try_fold(init, fold)
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -1893,6 +2170,22 @@ impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSize
             None
         }
     }
+
+    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut 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| {
+                n -= 1;
+                let r = fold(acc, x);
+                if n == 0 { LoopState::Break(r) }
+                else { LoopState::from_try(r) }
+            }).into_try()
+        }
+    }
 }
 
 #[unstable(feature = "fused", issue = "35602")]
@@ -1954,6 +2247,23 @@ impl<I> Iterator for Take<I> where I: Iterator{
 
         (lower, upper)
     }
+
+    #[inline]
+    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut 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| {
+                *n -= 1;
+                let r = fold(acc, x);
+                if *n == 0 { LoopState::Break(r) }
+                else { LoopState::from_try(r) }
+            }).into_try()
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -2005,6 +2315,20 @@ impl<B, I, St, F> Iterator for Scan<I, St, F> where
         let (_, upper) = self.iter.size_hint();
         (0, upper) // can't know a lower bound, due to the scan function
     }
+
+    #[inline]
+    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
+        Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
+    {
+        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()
+    }
 }
 
 /// An iterator that maps each element to an iterator, and yields the elements
@@ -2071,6 +2395,35 @@ impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
     }
 
     #[inline]
+    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>
+    {
+        if let Some(ref mut front) = self.frontiter {
+            init = front.try_fold(init, &mut fold)?;
+        }
+        self.frontiter = None;
+
+        {
+            let f = &mut self.f;
+            let frontiter = &mut self.frontiter;
+            init = self.iter.try_fold(init, |acc, x| {
+                let mut mid = f(x).into_iter();
+                let r = mid.try_fold(acc, &mut fold);
+                *frontiter = Some(mid);
+                r
+            })?;
+        }
+        self.frontiter = None;
+
+        if let Some(ref mut back) = self.backiter {
+            init = back.try_fold(init, &mut fold)?;
+        }
+        self.backiter = None;
+
+        Try::from_ok(init)
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2103,6 +2456,35 @@ impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> wher
     }
 
     #[inline]
+    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;
+
+        {
+            let f = &mut self.f;
+            let backiter = &mut self.backiter;
+            init = self.iter.try_rfold(init, |acc, x| {
+                let mut mid = f(x).into_iter();
+                let r = mid.try_rfold(acc, &mut fold);
+                *backiter = Some(mid);
+                r
+            })?;
+        }
+        self.backiter = None;
+
+        if let Some(ref mut front) = self.frontiter {
+            init = front.try_rfold(init, &mut fold)?;
+        }
+        self.frontiter = None;
+
+        Try::from_ok(init)
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2190,6 +2572,19 @@ impl<I> Iterator for Fuse<I> where I: Iterator {
     }
 
     #[inline]
+    default 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.done {
+            Try::from_ok(init)
+        } else {
+            let acc = self.iter.try_fold(init, fold)?;
+            self.done = true;
+            Try::from_ok(acc)
+        }
+    }
+
+    #[inline]
     default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2215,6 +2610,19 @@ impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
     }
 
     #[inline]
+    default 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>
+    {
+        if self.done {
+            Try::from_ok(init)
+        } else {
+            let acc = self.iter.try_rfold(init, fold)?;
+            self.done = true;
+            Try::from_ok(acc)
+        }
+    }
+
+    #[inline]
     default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2266,6 +2674,13 @@ impl<I> Iterator for Fuse<I> where I: FusedIterator {
     }
 
     #[inline]
+    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>
+    {
+        self.iter.try_fold(init, fold)
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2283,6 +2698,13 @@ impl<I> DoubleEndedIterator for Fuse<I>
     }
 
     #[inline]
+    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>
+    {
+        self.iter.try_rfold(init, fold)
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2354,6 +2776,14 @@ 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
+        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) })
+    }
+
+    #[inline]
     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
@@ -2373,6 +2803,14 @@ 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
+        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) })
+    }
+
+    #[inline]
     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
         where Fold: FnMut(Acc, Self::Item) -> Acc,
     {
diff --git a/src/libcore/iter/traits.rs b/src/libcore/iter/traits.rs
index 28236d193c3..11e668d228c 100644
--- a/src/libcore/iter/traits.rs
+++ b/src/libcore/iter/traits.rs
@@ -7,9 +7,11 @@
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
-use ops::{Mul, Add};
+use ops::{Mul, Add, Try};
 use num::Wrapping;
 
+use super::{AlwaysOk, LoopState};
+
 /// Conversion from an `Iterator`.
 ///
 /// By implementing `FromIterator` for a type, you define how it will be
@@ -415,6 +417,52 @@ pub trait DoubleEndedIterator: Iterator {
     #[stable(feature = "rust1", since = "1.0.0")]
     fn next_back(&mut self) -> Option<Self::Item>;
 
+    /// This is the reverse version of [`try_fold()`]: it takes elements
+    /// starting from the back of the iterator.
+    ///
+    /// [`try_fold()`]: trait.Iterator.html#method.try_fold
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(iterator_try_fold)]
+    /// let a = ["1", "2", "3"];
+    /// let sum = a.iter()
+    ///     .map(|&s| s.parse::<i32>())
+    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
+    /// assert_eq!(sum, Ok(6));
+    /// ```
+    ///
+    /// Short-circuiting:
+    ///
+    /// ```
+    /// #![feature(iterator_try_fold)]
+    /// let a = ["1", "rust", "3"];
+    /// let mut it = a.iter();
+    /// let sum = it
+    ///     .by_ref()
+    ///     .map(|&s| s.parse::<i32>())
+    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
+    /// assert!(sum.is_err());
+    ///
+    /// // Because it short-circuited, the remaining elements are still
+    /// // available through the iterator.
+    /// assert_eq!(it.next_back(), Some(&"1"));
+    /// ```
+    #[inline]
+    #[unstable(feature = "iterator_try_fold", issue = "45594")]
+    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    {
+        let mut accum = init;
+        while let Some(x) = self.next_back() {
+            accum = f(accum, x)?;
+        }
+        Try::from_ok(accum)
+    }
+
     /// An iterator method that reduces the iterator's elements to a single,
     /// final value, starting from the back.
     ///
@@ -470,13 +518,10 @@ pub trait DoubleEndedIterator: Iterator {
     /// ```
     #[inline]
     #[unstable(feature = "iter_rfold", issue = "44705")]
-    fn rfold<B, F>(mut self, mut accum: B, mut f: F) -> B where
+    fn rfold<B, F>(mut self, accum: B, mut f: F) -> B where
         Self: Sized, F: FnMut(B, Self::Item) -> B,
     {
-        while let Some(x) = self.next_back() {
-            accum = f(accum, x);
-        }
-        accum
+        self.try_rfold(accum, move |acc, x| AlwaysOk(f(acc, x))).0
     }
 
     /// Searches for an element of an iterator from the right that satisfies a predicate.
@@ -531,10 +576,10 @@ pub trait DoubleEndedIterator: Iterator {
         Self: Sized,
         P: FnMut(&Self::Item) -> bool
     {
-        while let Some(x) = self.next_back() {
-            if predicate(&x) { return Some(x) }
-        }
-        None
+        self.try_rfold((), move |(), x| {
+            if predicate(&x) { LoopState::Break(x) }
+            else { LoopState::Continue(()) }
+        }).break_value()
     }
 }
 
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 74182f303c9..49c51f4f04f 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -40,7 +40,7 @@ use cmp;
 use fmt;
 use intrinsics::assume;
 use iter::*;
-use ops::{FnMut, self};
+use ops::{FnMut, Try, self};
 use option::Option;
 use option::Option::{None, Some};
 use result::Result;
@@ -1165,62 +1165,37 @@ macro_rules! iterator {
                 self.next_back()
             }
 
-            fn all<F>(&mut self, mut predicate: F) -> bool
-                where F: FnMut(Self::Item) -> bool,
-            {
-                self.search_while(true, move |elt| {
-                    if predicate(elt) {
-                        SearchWhile::Continue
-                    } else {
-                        SearchWhile::Done(false)
-                    }
-                })
-            }
-
-            fn any<F>(&mut self, mut predicate: F) -> bool
-                where F: FnMut(Self::Item) -> bool,
-            {
-                !self.all(move |elt| !predicate(elt))
-            }
-
-            fn find<F>(&mut self, mut predicate: F) -> Option<Self::Item>
-                where F: FnMut(&Self::Item) -> bool,
+            #[inline]
+            fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+                Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
             {
-                self.search_while(None, move |elt| {
-                    if predicate(&elt) {
-                        SearchWhile::Done(Some(elt))
-                    } else {
-                        SearchWhile::Continue
+                // manual unrolling is needed when there are conditional exits from the loop
+                let mut accum = init;
+                unsafe {
+                    while ptrdistance(self.ptr, self.end) >= 4 {
+                        accum = f(accum, $mkref!(self.ptr.post_inc()))?;
+                        accum = f(accum, $mkref!(self.ptr.post_inc()))?;
+                        accum = f(accum, $mkref!(self.ptr.post_inc()))?;
+                        accum = f(accum, $mkref!(self.ptr.post_inc()))?;
                     }
-                })
-            }
-
-            fn position<F>(&mut self, mut predicate: F) -> Option<usize>
-                where F: FnMut(Self::Item) -> bool,
-            {
-                let mut index = 0;
-                self.search_while(None, move |elt| {
-                    if predicate(elt) {
-                        SearchWhile::Done(Some(index))
-                    } else {
-                        index += 1;
-                        SearchWhile::Continue
+                    while self.ptr != self.end {
+                        accum = f(accum, $mkref!(self.ptr.post_inc()))?;
                     }
-                })
+                }
+                Try::from_ok(accum)
             }
 
-            fn rposition<F>(&mut self, mut predicate: F) -> Option<usize>
-                where F: FnMut(Self::Item) -> bool,
+            #[inline]
+            fn fold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
+                where Fold: FnMut(Acc, Self::Item) -> Acc,
             {
-                let mut index = self.len();
-                self.rsearch_while(None, move |elt| {
-                    index -= 1;
-                    if predicate(elt) {
-                        SearchWhile::Done(Some(index))
-                    } else {
-                        SearchWhile::Continue
-                    }
-                })
+                // Let LLVM unroll this, rather than using the default
+                // impl that would force the manual unrolling above
+                let mut accum = init;
+                while let Some(x) = self.next() {
+                    accum = f(accum, x);
+                }
+                accum
             }
         }
 
@@ -1242,59 +1217,37 @@ macro_rules! iterator {
                 }
             }
 
-            fn rfind<F>(&mut self, mut predicate: F) -> Option<Self::Item>
-                where F: FnMut(&Self::Item) -> bool,
-            {
-                self.rsearch_while(None, move |elt| {
-                    if predicate(&elt) {
-                        SearchWhile::Done(Some(elt))
-                    } else {
-                        SearchWhile::Continue
-                    }
-                })
-            }
-
-        }
-
-        // search_while is a generalization of the internal iteration methods.
-        impl<'a, T> $name<'a, T> {
-            // search through the iterator's element using the closure `g`.
-            // if no element was found, return `default`.
-            fn search_while<Acc, G>(&mut self, default: Acc, mut g: G) -> Acc
-                where Self: Sized,
-                      G: FnMut($elem) -> SearchWhile<Acc>
+            #[inline]
+            fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
+                Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
             {
                 // manual unrolling is needed when there are conditional exits from the loop
+                let mut accum = init;
                 unsafe {
                     while ptrdistance(self.ptr, self.end) >= 4 {
-                        search_while!(g($mkref!(self.ptr.post_inc())));
-                        search_while!(g($mkref!(self.ptr.post_inc())));
-                        search_while!(g($mkref!(self.ptr.post_inc())));
-                        search_while!(g($mkref!(self.ptr.post_inc())));
+                        accum = f(accum, $mkref!(self.end.pre_dec()))?;
+                        accum = f(accum, $mkref!(self.end.pre_dec()))?;
+                        accum = f(accum, $mkref!(self.end.pre_dec()))?;
+                        accum = f(accum, $mkref!(self.end.pre_dec()))?;
                     }
                     while self.ptr != self.end {
-                        search_while!(g($mkref!(self.ptr.post_inc())));
+                        accum = f(accum, $mkref!(self.end.pre_dec()))?;
                     }
                 }
-                default
+                Try::from_ok(accum)
             }
 
-            fn rsearch_while<Acc, G>(&mut self, default: Acc, mut g: G) -> Acc
-                where Self: Sized,
-                      G: FnMut($elem) -> SearchWhile<Acc>
+            #[inline]
+            fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
+                where Fold: FnMut(Acc, Self::Item) -> Acc,
             {
-                unsafe {
-                    while ptrdistance(self.ptr, self.end) >= 4 {
-                        search_while!(g($mkref!(self.end.pre_dec())));
-                        search_while!(g($mkref!(self.end.pre_dec())));
-                        search_while!(g($mkref!(self.end.pre_dec())));
-                        search_while!(g($mkref!(self.end.pre_dec())));
-                    }
-                    while self.ptr != self.end {
-                        search_while!(g($mkref!(self.end.pre_dec())));
-                    }
+                // Let LLVM unroll this, rather than using the default
+                // impl that would force the manual unrolling above
+                let mut accum = init;
+                while let Some(x) = self.next_back() {
+                    accum = f(accum, x);
                 }
-                default
+                accum
             }
         }
     }
@@ -1328,24 +1281,6 @@ macro_rules! make_mut_slice {
     }}
 }
 
-// An enum used for controlling the execution of `.search_while()`.
-enum SearchWhile<T> {
-    // Continue searching
-    Continue,
-    // Fold is complete and will return this value
-    Done(T),
-}
-
-// helper macro for search while's control flow
-macro_rules! search_while {
-    ($e:expr) => {
-        match $e {
-            SearchWhile::Continue => { }
-            SearchWhile::Done(done) => return done,
-        }
-    }
-}
-
 /// Immutable slice iterator
 ///
 /// This struct is created by the [`iter`] method on [slices].
diff --git a/src/libcore/tests/iter.rs b/src/libcore/tests/iter.rs
index f8c6fc5c8fa..5cac5b26d88 100644
--- a/src/libcore/tests/iter.rs
+++ b/src/libcore/tests/iter.rs
@@ -664,6 +664,7 @@ fn test_iterator_skip_last() {
 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]);
@@ -678,6 +679,24 @@ fn test_iterator_skip_fold() {
         i + 1
     });
     assert_eq!(i, ys.len());
+
+    let it = xs.iter().skip(5);
+    let i = it.rfold(ys.len(), |i, &x| {
+        let i = i - 1;
+        assert_eq!(x, ys[i]);
+        i
+    });
+    assert_eq!(i, 0);
+
+    let mut it = xs.iter().skip(5);
+    assert_eq!(it.next(), Some(&ys[0])); // process skips before folding
+    let i = it.rfold(ys.len(), |i, &x| {
+        let i = i - 1;
+        assert_eq!(x, ys[i]);
+        i
+    });
+    assert_eq!(i, 1);
+
 }
 
 #[test]
@@ -1478,3 +1497,207 @@ fn test_step_replace_no_between() {
     assert_eq!(x, 1);
     assert_eq!(y, 5);
 }
+
+#[test]
+fn test_rev_try_folds() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((1..10).rev().try_fold(7, f), (1..10).try_rfold(7, f));
+    assert_eq!((1..10).rev().try_rfold(7, f), (1..10).try_fold(7, f));
+
+    let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
+    let mut iter = a.iter().rev();
+    assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
+    assert_eq!(iter.next(), Some(&70));
+    let mut iter = a.iter().rev();
+    assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
+    assert_eq!(iter.next_back(), Some(&60));
+}
+
+#[test]
+fn test_cloned_try_folds() {
+    let a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    let f_ref = &|acc, &x| i32::checked_add(2*acc, x);
+    assert_eq!(a.iter().cloned().try_fold(7, f), a.iter().try_fold(7, f_ref));
+    assert_eq!(a.iter().cloned().try_rfold(7, f), a.iter().try_rfold(7, f_ref));
+
+    let a = [10, 20, 30, 40, 100, 60, 70, 80, 90];
+    let mut iter = a.iter().cloned();
+    assert_eq!(iter.try_fold(0_i8, |acc, x| acc.checked_add(x)), None);
+    assert_eq!(iter.next(), Some(60));
+    let mut iter = a.iter().cloned();
+    assert_eq!(iter.try_rfold(0_i8, |acc, x| acc.checked_add(x)), None);
+    assert_eq!(iter.next_back(), Some(70));
+}
+
+#[test]
+fn test_chain_try_folds() {
+    let c = || (0..10).chain(10..20);
+
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!(c().try_fold(7, f), (0..20).try_fold(7, f));
+    assert_eq!(c().try_rfold(7, f), (0..20).rev().try_fold(7, f));
+
+    let mut iter = c();
+    assert_eq!(iter.position(|x| x == 5), Some(5));
+    assert_eq!(iter.next(), Some(6), "stopped in front, state Both");
+    assert_eq!(iter.position(|x| x == 13), Some(6));
+    assert_eq!(iter.next(), Some(14), "stopped in back, state Back");
+    assert_eq!(iter.try_fold(0, |acc, x| Some(acc+x)), Some((15..20).sum()));
+
+    let mut iter = c().rev(); // use rev to access try_rfold
+    assert_eq!(iter.position(|x| x == 15), Some(4));
+    assert_eq!(iter.next(), Some(14), "stopped in back, state Both");
+    assert_eq!(iter.position(|x| x == 5), Some(8));
+    assert_eq!(iter.next(), Some(4), "stopped in front, state Front");
+    assert_eq!(iter.try_fold(0, |acc, x| Some(acc+x)), Some((0..4).sum()));
+
+    let mut iter = c();
+    iter.by_ref().rev().nth(14); // skip the last 15, ending in state Front
+    assert_eq!(iter.try_fold(7, f), (0..5).try_fold(7, f));
+
+    let mut iter = c();
+    iter.nth(14); // skip the first 15, ending in state Back
+    assert_eq!(iter.try_rfold(7, f), (15..20).try_rfold(7, f));
+}
+
+#[test]
+fn test_map_try_folds() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((0..10).map(|x| x+3).try_fold(7, f), (3..13).try_fold(7, f));
+    assert_eq!((0..10).map(|x| x+3).try_rfold(7, f), (3..13).try_rfold(7, f));
+
+    let mut iter = (0..40).map(|x| x+10);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(20));
+    assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    assert_eq!(iter.next_back(), Some(46));
+}
+
+#[test]
+fn test_filter_try_folds() {
+    fn p(&x: &i32) -> bool { 0 <= x && x < 10 }
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((-10..20).filter(p).try_fold(7, f), (0..10).try_fold(7, f));
+    assert_eq!((-10..20).filter(p).try_rfold(7, f), (0..10).try_rfold(7, f));
+
+    let mut iter = (0..40).filter(|&x| x % 2 == 1);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(25));
+    assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    assert_eq!(iter.next_back(), Some(31));
+}
+
+#[test]
+fn test_filter_map_try_folds() {
+    let mp = &|x| if 0 <= x && x < 10 { Some(x*2) } else { None };
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((-9..20).filter_map(mp).try_fold(7, f), (0..10).map(|x| 2*x).try_fold(7, f));
+    assert_eq!((-9..20).filter_map(mp).try_rfold(7, f), (0..10).map(|x| 2*x).try_rfold(7, f));
+
+    let mut iter = (0..40).filter_map(|x| if x%2 == 1 { None } else { Some(x*2 + 10) });
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(38));
+    assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    assert_eq!(iter.next_back(), Some(78));
+}
+
+#[test]
+fn test_enumerate_try_folds() {
+    let f = &|acc, (i, x)| usize::checked_add(2*acc, x/(i+1) + i);
+    assert_eq!((9..18).enumerate().try_fold(7, f), (0..9).map(|i| (i, i+9)).try_fold(7, f));
+    assert_eq!((9..18).enumerate().try_rfold(7, f), (0..9).map(|i| (i, i+9)).try_rfold(7, f));
+
+    let mut iter = (100..200).enumerate();
+    let f = &|acc, (i, x)| u8::checked_add(acc, u8::checked_div(x, i as u8 + 1)?);
+    assert_eq!(iter.try_fold(0, f), None);
+    assert_eq!(iter.next(), Some((7, 107)));
+    assert_eq!(iter.try_rfold(0, f), None);
+    assert_eq!(iter.next_back(), Some((11, 111)));
+}
+
+#[test]
+fn test_peek_try_fold() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((1..20).peekable().try_fold(7, f), (1..20).try_fold(7, f));
+    let mut iter = (1..20).peekable();
+    assert_eq!(iter.peek(), Some(&1));
+    assert_eq!(iter.try_fold(7, f), (1..20).try_fold(7, f));
+
+    let mut iter = [100, 20, 30, 40, 50, 60, 70].iter().cloned().peekable();
+    assert_eq!(iter.peek(), Some(&100));
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.peek(), Some(&40));
+}
+
+#[test]
+fn test_skip_while_try_fold() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    fn p(&x: &i32) -> bool { (x % 10) <= 5 }
+    assert_eq!((1..20).skip_while(p).try_fold(7, f), (6..20).try_fold(7, f));
+    let mut iter = (1..20).skip_while(p);
+    assert_eq!(iter.nth(5), Some(11));
+    assert_eq!(iter.try_fold(7, f), (12..20).try_fold(7, f));
+
+    let mut iter = (0..50).skip_while(|&x| (x % 20) < 15);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(23));
+}
+
+#[test]
+fn test_take_while_folds() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((1..20).take_while(|&x| x != 10).try_fold(7, f), (1..10).try_fold(7, f));
+    let mut iter = (1..20).take_while(|&x| x != 10);
+    assert_eq!(iter.try_fold(0, |x, y| Some(x+y)), Some((1..10).sum()));
+    assert_eq!(iter.next(), None, "flag should be set");
+    let iter = (1..20).take_while(|&x| x != 10);
+    assert_eq!(iter.fold(0, |x, y| x+y), (1..10).sum());
+
+    let mut iter = (10..50).take_while(|&x| x != 40);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(20));
+}
+
+#[test]
+fn test_skip_try_folds() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((1..20).skip(9).try_fold(7, f), (10..20).try_fold(7, f));
+    assert_eq!((1..20).skip(9).try_rfold(7, f), (10..20).try_rfold(7, f));
+
+    let mut iter = (0..30).skip(10);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(20));
+    assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    assert_eq!(iter.next_back(), Some(24));
+}
+
+#[test]
+fn test_take_try_folds() {
+    let f = &|acc, x| i32::checked_add(2*acc, x);
+    assert_eq!((10..30).take(10).try_fold(7, f), (10..20).try_fold(7, f));
+    //assert_eq!((10..30).take(10).try_rfold(7, f), (10..20).try_rfold(7, f));
+
+    let mut iter = (10..30).take(20);
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(20));
+    //assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    //assert_eq!(iter.next_back(), Some(24));
+}
+
+#[test]
+fn test_flat_map_try_folds() {
+    let f = &|acc, x| i32::checked_add(acc*2/3, x);
+    let mr = &|x| (5*x)..(5*x + 5);
+    assert_eq!((0..10).flat_map(mr).try_fold(7, f), (0..50).try_fold(7, f));
+    assert_eq!((0..10).flat_map(mr).try_rfold(7, f), (0..50).try_rfold(7, f));
+    let mut iter = (0..10).flat_map(mr);
+    iter.next(); iter.next_back(); // have front and back iters in progress
+    assert_eq!(iter.try_rfold(7, f), (1..49).try_rfold(7, f));
+
+    let mut iter = (0..10).flat_map(|x| (4*x)..(4*x + 4));
+    assert_eq!(iter.try_fold(0, i8::checked_add), None);
+    assert_eq!(iter.next(), Some(17));
+    assert_eq!(iter.try_rfold(0, i8::checked_add), None);
+    assert_eq!(iter.next_back(), Some(35));
+}
diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index afc5de7b0ee..96d83081c8f 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -24,6 +24,7 @@
 #![feature(i128_type)]
 #![feature(inclusive_range)]
 #![feature(inclusive_range_syntax)]
+#![feature(iterator_try_fold)]
 #![feature(iter_rfind)]
 #![feature(iter_rfold)]
 #![feature(nonzero)]
diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs
index 7835080db1d..37636837c07 100644
--- a/src/libcore/tests/slice.rs
+++ b/src/libcore/tests/slice.rs
@@ -276,6 +276,23 @@ fn test_find_rfind() {
 }
 
 #[test]
+fn test_iter_folds() {
+    let a = [1, 2, 3, 4, 5]; // len>4 so the unroll is used
+    assert_eq!(a.iter().fold(0, |acc, &x| 2*acc + x), 57);
+    assert_eq!(a.iter().rfold(0, |acc, &x| 2*acc + x), 129);
+    let fold = |acc: i32, &x| acc.checked_mul(2)?.checked_add(x);
+    assert_eq!(a.iter().try_fold(0, &fold), Some(57));
+    assert_eq!(a.iter().try_rfold(0, &fold), Some(129));
+
+    // short-circuiting try_fold, through other methods
+    let a = [0, 1, 2, 3, 5, 5, 5, 7, 8, 9];
+    let mut iter = a.iter();
+    assert_eq!(iter.position(|&x| x == 3), Some(3));
+    assert_eq!(iter.rfind(|&&x| x == 5), Some(&5));
+    assert_eq!(iter.len(), 2);
+}
+
+#[test]
 fn test_rotate() {
     const N: usize = 600;
     let a: &mut [_] = &mut [0; N];