Merge branch 'master' into copied

3 files changed, 103 insertions, 32 deletions

diff --git a/src/libcore/iter/iterator.rs b/src/libcore/iter/iterator.rs
index 80bd5698c47..d0b0fd1ab31 100644
--- a/src/libcore/iter/iterator.rs
+++ b/src/libcore/iter/iterator.rs
@@ -87,7 +87,7 @@ fn _assert_is_object_safe(_: &dyn Iterator<Item=()>) {}
     on(
         _Self="[]",
         label="borrow the array with `&` or call `.iter()` on it to iterate over it",
-        note="arrays are not an iterators, but slices like the following are: `&[1, 2, 3]`"
+        note="arrays are not iterators, but slices like the following are: `&[1, 2, 3]`"
     ),
     on(
         _Self="{integral}",
@@ -98,6 +98,7 @@ fn _assert_is_object_safe(_: &dyn Iterator<Item=()>) {}
     message="`{Self}` is not an iterator"
 )]
 #[doc(spotlight)]
+#[must_use]
 pub trait Iterator {
     /// The type of the elements being iterated over.
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -154,7 +155,7 @@ pub trait Iterator {
     ///
     /// `size_hint()` is primarily intended to be used for optimizations such as
     /// reserving space for the elements of the iterator, but must not be
-    /// trusted to e.g. omit bounds checks in unsafe code. An incorrect
+    /// trusted to e.g., omit bounds checks in unsafe code. An incorrect
     /// implementation of `size_hint()` should not lead to memory safety
     /// violations.
     ///
diff --git a/src/libcore/iter/mod.rs b/src/libcore/iter/mod.rs
index de1a318cfb2..aa130754f83 100644
--- a/src/libcore/iter/mod.rs
+++ b/src/libcore/iter/mod.rs
@@ -429,6 +429,9 @@ impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth_back(n) }
+
     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>
     {
@@ -461,6 +464,9 @@ impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
     #[inline]
     fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
 
+    #[inline]
+    fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth(n) }
+
     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>
     {
@@ -702,7 +708,9 @@ unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
     }
 
     #[inline]
-    fn may_have_side_effect() -> bool { false }
+    fn may_have_side_effect() -> bool {
+        I::may_have_side_effect()
+    }
 }
 
 #[unstable(feature = "trusted_len", issue = "37572")]
@@ -1953,18 +1961,11 @@ impl<I: Iterator> Iterator for Peekable<I> {
 
     #[inline]
     fn nth(&mut self, n: usize) -> Option<I::Item> {
-        // FIXME(#43234): merge these when borrow-checking gets better.
-        if n == 0 {
-            match self.peeked.take() {
-                Some(v) => v,
-                None => self.iter.nth(n),
-            }
-        } else {
-            match self.peeked.take() {
-                Some(None) => None,
-                Some(Some(_)) => self.iter.nth(n - 1),
-                None => self.iter.nth(n),
-            }
+        match self.peeked.take() {
+            Some(None) => None,
+            Some(v @ Some(_)) if n == 0 => v,
+            Some(Some(_)) => self.iter.nth(n - 1),
+            None => self.iter.nth(n),
         }
     }
 
@@ -2063,14 +2064,8 @@ impl<I: Iterator> Peekable<I> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn peek(&mut self) -> Option<&I::Item> {
-        if self.peeked.is_none() {
-            self.peeked = Some(self.iter.next());
-        }
-        match self.peeked {
-            Some(Some(ref value)) => Some(value),
-            Some(None) => None,
-            _ => unreachable!(),
-        }
+        let iter = &mut self.iter;
+        self.peeked.get_or_insert_with(|| iter.next()).as_ref()
     }
 }
 
@@ -2207,8 +2202,12 @@ impl<I: Iterator, P> Iterator for TakeWhile<I, P>
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let (_, upper) = self.iter.size_hint();
-        (0, upper) // can't know a lower bound, due to the predicate
+        if self.flag {
+            (0, Some(0))
+        } else {
+            let (_, upper) = self.iter.size_hint();
+            (0, upper) // can't know a lower bound, due to the predicate
+        }
     }
 
     #[inline]
@@ -2419,6 +2418,10 @@ impl<I> Iterator for Take<I> where I: Iterator{
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
+        if self.n == 0 {
+            return (0, Some(0));
+        }
+
         let (lower, upper) = self.iter.size_hint();
 
         let lower = cmp::min(lower, self.n);
diff --git a/src/libcore/iter/traits.rs b/src/libcore/iter/traits.rs
index d2c5a3bed28..727a60e3596 100644
--- a/src/libcore/iter/traits.rs
+++ b/src/libcore/iter/traits.rs
@@ -427,6 +427,62 @@ pub trait DoubleEndedIterator: Iterator {
     #[stable(feature = "rust1", since = "1.0.0")]
     fn next_back(&mut self) -> Option<Self::Item>;
 
+    /// Returns the `n`th element from the end of the iterator.
+    ///
+    /// This is essentially the reversed version of [`nth`]. Although like most indexing
+    /// operations, the count starts from zero, so `nth_back(0)` returns the first value fro
+    /// the end, `nth_back(1)` the second, and so on.
+    ///
+    /// Note that all elements between the end and the returned element will be
+    /// consumed, including the returned element. This also means that calling
+    /// `nth_back(0)` multiple times on the same iterator will return different
+    /// elements.
+    ///
+    /// `nth_back()` will return [`None`] if `n` is greater than or equal to the length of the
+    /// iterator.
+    ///
+    /// [`None`]: ../../std/option/enum.Option.html#variant.None
+    /// [`nth`]: ../../std/iter/trait.Iterator.html#method.nth
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(iter_nth_back)]
+    /// let a = [1, 2, 3];
+    /// assert_eq!(a.iter().nth_back(2), Some(&1));
+    /// ```
+    ///
+    /// Calling `nth_back()` multiple times doesn't rewind the iterator:
+    ///
+    /// ```
+    /// #![feature(iter_nth_back)]
+    /// let a = [1, 2, 3];
+    ///
+    /// let mut iter = a.iter();
+    ///
+    /// assert_eq!(iter.nth_back(1), Some(&2));
+    /// assert_eq!(iter.nth_back(1), None);
+    /// ```
+    ///
+    /// Returning `None` if there are less than `n + 1` elements:
+    ///
+    /// ```
+    /// #![feature(iter_nth_back)]
+    /// let a = [1, 2, 3];
+    /// assert_eq!(a.iter().nth_back(10), None);
+    /// ```
+    #[inline]
+    #[unstable(feature = "iter_nth_back", issue = "56995")]
+    fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
+        for x in self.rev() {
+            if n == 0 { return Some(x) }
+            n -= 1;
+        }
+        None
+    }
+
     /// This is the reverse version of [`try_fold()`]: it takes elements
     /// starting from the back of the iterator.
     ///
@@ -461,8 +517,11 @@ pub trait DoubleEndedIterator: Iterator {
     /// ```
     #[inline]
     #[stable(feature = "iterator_try_fold", since = "1.27.0")]
-    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>
+    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() {
@@ -524,8 +583,10 @@ 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 where
-        Self: Sized, F: FnMut(B, Self::Item) -> B,
+    fn rfold<B, F>(mut self, accum: B, mut 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()
     }
@@ -574,7 +635,8 @@ pub trait DoubleEndedIterator: Iterator {
     /// ```
     #[inline]
     #[stable(feature = "iter_rfind", since = "1.27.0")]
-    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
+    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
+    where
         Self: Sized,
         P: FnMut(&Self::Item) -> bool
     {
@@ -587,7 +649,12 @@ pub trait DoubleEndedIterator: Iterator {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
-    fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
+    fn next_back(&mut self) -> Option<I::Item> {
+        (**self).next_back()
+    }
+    fn nth_back(&mut self, n: usize) -> Option<I::Item> {
+        (**self).nth_back(n)
+    }
 }
 
 /// An iterator that knows its exact length.
@@ -770,7 +837,7 @@ pub trait Product<A = Self>: Sized {
     fn product<I: Iterator<Item=A>>(iter: I) -> Self;
 }
 
-// NB: explicitly use Add and Mul here to inherit overflow checks
+// N.B., explicitly use Add and Mul here to inherit overflow checks
 macro_rules! integer_sum_product {
     (@impls $zero:expr, $one:expr, #[$attr:meta], $($a:ty)*) => ($(
         #[$attr]