Rollup merge of #60772 - timvermeulen:slice_iter_nth_back, r=scottmcm

Implement nth_back for slice::{Iter, IterMut}

Part of #54054.

I implemented `nth_back` as straightforwardly as I could, and then slightly changed `nth` to match `nth_back`. I believe I did so correctly, but please double-check 🙂

I also added the helper methods `zst_shrink`, `next_unchecked`, and `next_back_unchecked` to get rid of some duplicated code. These changes hopefully make this code easier to understand for new contributors like me.

I noticed the `is_empty!` and `len!` macros which sole purpose seems to be inlining, according to the comment right above them, but the `is_empty` and `len` methods are already marked with `#[inline(always)]`. Does that mean we could replace these macros with method calls, without affecting anything? I'd love to get rid of them.

2 files changed, 68 insertions, 21 deletions

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index af1b20a4c10..c6d44324ef5 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -3019,6 +3019,28 @@ macro_rules! iterator {
         {$( $mut_:tt )*},
         {$($extra:tt)*}
     ) => {
+        // Returns the first element and moves the start of the iterator forwards by 1.
+        // Greatly improves performance compared to an inlined function. The iterator
+        // must not be empty.
+        macro_rules! next_unchecked {
+            ($self: ident) => {& $( $mut_ )* *$self.post_inc_start(1)}
+        }
+
+        // Returns the last element and moves the end of the iterator backwards by 1.
+        // Greatly improves performance compared to an inlined function. The iterator
+        // must not be empty.
+        macro_rules! next_back_unchecked {
+            ($self: ident) => {& $( $mut_ )* *$self.pre_dec_end(1)}
+        }
+
+        // Shrinks the iterator when T is a ZST, by moving the end of the iterator
+        // backwards by `n`. `n` must not exceed `self.len()`.
+        macro_rules! zst_shrink {
+            ($self: ident, $n: ident) => {
+                $self.end = ($self.end as * $raw_mut u8).wrapping_offset(-$n) as * $raw_mut T;
+            }
+        }
+
         impl<'a, T> $name<'a, T> {
             // Helper function for creating a slice from the iterator.
             #[inline(always)]
@@ -3028,12 +3050,11 @@ macro_rules! iterator {
 
             // Helper function for moving the start of the iterator forwards by `offset` elements,
             // returning the old start.
-            // Unsafe because the offset must be in-bounds or one-past-the-end.
+            // Unsafe because the offset must not exceed `self.len()`.
             #[inline(always)]
             unsafe fn post_inc_start(&mut self, offset: isize) -> * $raw_mut T {
                 if mem::size_of::<T>() == 0 {
-                    // This is *reducing* the length.  `ptr` never changes with ZST.
-                    self.end = (self.end as * $raw_mut u8).wrapping_offset(-offset) as * $raw_mut T;
+                    zst_shrink!(self, offset);
                     self.ptr
                 } else {
                     let old = self.ptr;
@@ -3044,11 +3065,11 @@ macro_rules! iterator {
 
             // Helper function for moving the end of the iterator backwards by `offset` elements,
             // returning the new end.
-            // Unsafe because the offset must be in-bounds or one-past-the-end.
+            // Unsafe because the offset must not exceed `self.len()`.
             #[inline(always)]
             unsafe fn pre_dec_end(&mut self, offset: isize) -> * $raw_mut T {
                 if mem::size_of::<T>() == 0 {
-                    self.end = (self.end as * $raw_mut u8).wrapping_offset(-offset) as * $raw_mut T;
+                    zst_shrink!(self, offset);
                     self.ptr
                 } else {
                     self.end = self.end.offset(-offset);
@@ -3085,7 +3106,7 @@ macro_rules! iterator {
                     if is_empty!(self) {
                         None
                     } else {
-                        Some(& $( $mut_ )* *self.post_inc_start(1))
+                        Some(next_unchecked!(self))
                     }
                 }
             }
@@ -3114,11 +3135,10 @@ macro_rules! iterator {
                     }
                     return None;
                 }
-                // We are in bounds. `offset` does the right thing even for ZSTs.
+                // We are in bounds. `post_inc_start` does the right thing even for ZSTs.
                 unsafe {
-                    let elem = Some(& $( $mut_ )* *self.ptr.add(n));
-                    self.post_inc_start((n as isize).wrapping_add(1));
-                    elem
+                    self.post_inc_start(n as isize);
+                    Some(next_unchecked!(self))
                 }
             }
 
@@ -3135,13 +3155,13 @@ macro_rules! iterator {
                 let mut accum = init;
                 unsafe {
                     while len!(self) >= 4 {
-                        accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
+                        accum = f(accum, next_unchecked!(self))?;
+                        accum = f(accum, next_unchecked!(self))?;
+                        accum = f(accum, next_unchecked!(self))?;
+                        accum = f(accum, next_unchecked!(self))?;
                     }
                     while !is_empty!(self) {
-                        accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
+                        accum = f(accum, next_unchecked!(self))?;
                     }
                 }
                 Try::from_ok(accum)
@@ -3212,12 +3232,26 @@ macro_rules! iterator {
                     if is_empty!(self) {
                         None
                     } else {
-                        Some(& $( $mut_ )* *self.pre_dec_end(1))
+                        Some(next_back_unchecked!(self))
                     }
                 }
             }
 
             #[inline]
+            fn nth_back(&mut self, n: usize) -> Option<$elem> {
+                if n >= len!(self) {
+                    // This iterator is now empty.
+                    self.end = self.ptr;
+                    return None;
+                }
+                // We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
+                unsafe {
+                    self.pre_dec_end(n as isize);
+                    Some(next_back_unchecked!(self))
+                }
+            }
+
+            #[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>
             {
@@ -3225,14 +3259,14 @@ macro_rules! iterator {
                 let mut accum = init;
                 unsafe {
                     while len!(self) >= 4 {
-                        accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
-                        accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
+                        accum = f(accum, next_back_unchecked!(self))?;
+                        accum = f(accum, next_back_unchecked!(self))?;
+                        accum = f(accum, next_back_unchecked!(self))?;
+                        accum = f(accum, next_back_unchecked!(self))?;
                     }
                     // inlining is_empty everywhere makes a huge performance difference
                     while !is_empty!(self) {
-                        accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
+                        accum = f(accum, next_back_unchecked!(self))?;
                     }
                 }
                 Try::from_ok(accum)
diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs
index eaa799fa96e..03e65d2fe0b 100644
--- a/src/libcore/tests/slice.rs
+++ b/src/libcore/tests/slice.rs
@@ -89,6 +89,19 @@ fn test_iterator_nth() {
 }
 
 #[test]
+fn test_iterator_nth_back() {
+    let v: &[_] = &[0, 1, 2, 3, 4];
+    for i in 0..v.len() {
+        assert_eq!(v.iter().nth_back(i).unwrap(), &v[v.len() - i - 1]);
+    }
+    assert_eq!(v.iter().nth_back(v.len()), None);
+
+    let mut iter = v.iter();
+    assert_eq!(iter.nth_back(2).unwrap(), &v[2]);
+    assert_eq!(iter.nth_back(1).unwrap(), &v[0]);
+}
+
+#[test]
 fn test_iterator_last() {
     let v: &[_] = &[0, 1, 2, 3, 4];
     assert_eq!(v.iter().last().unwrap(), &4);