Rollup merge of #47333 - arthurprs:iter-position-bounds-check, r=dtolnay

Optimize slice.{r}position result bounds check

Second attempt of https://github.com/rust-lang/rust/pull/45501
Fixes https://github.com/rust-lang/rust/issues/45964

Demo: https://godbolt.org/g/N4mBHp

1 files changed, 37 insertions, 0 deletions

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 48e82666d35..5bf73014347 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -1237,6 +1237,43 @@ macro_rules! iterator {
                 }
                 accum
             }
+
+            #[inline]
+            #[rustc_inherit_overflow_checks]
+            fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
+                Self: Sized,
+                P: FnMut(Self::Item) -> bool,
+            {
+                // The addition might panic on overflow
+                let n = self.len();
+                self.try_fold(0, move |i, x| {
+                    if predicate(x) { Err(i) }
+                    else { Ok(i + 1) }
+                }).err()
+                    .map(|i| {
+                        unsafe { assume(i < n) };
+                        i
+                    })
+            }
+
+            #[inline]
+            fn rposition<P>(&mut self, mut 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`.
+                let n = self.len();
+                self.try_rfold(n, move |i, x| {
+                    let i = i - 1;
+                    if predicate(x) { Err(i) }
+                    else { Ok(i) }
+                }).err()
+                    .map(|i| {
+                        unsafe { assume(i < n) };
+                        i
+                    })
+            }
         }
 
         #[stable(feature = "rust1", since = "1.0.0")]