Optimize slice.{r}position result bounds check

2 files changed, 56 insertions, 0 deletions

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index e6b79314aa9..d088d4e6634 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -1215,6 +1215,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")]
diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs
index 40e5fe5758a..d6bff43bc72 100644
--- a/src/libcore/tests/slice.rs
+++ b/src/libcore/tests/slice.rs
@@ -10,6 +10,25 @@
 
 use core::result::Result::{Ok, Err};
 
+
+#[test]
+fn test_position() {
+    let b = [1, 2, 3, 5, 5];
+    assert!(b.iter().position(|&v| v == 9) == None);
+    assert!(b.iter().position(|&v| v == 5) == Some(3));
+    assert!(b.iter().position(|&v| v == 3) == Some(2));
+    assert!(b.iter().position(|&v| v == 0) == None);
+}
+
+#[test]
+fn test_rposition() {
+    let b = [1, 2, 3, 5, 5];
+    assert!(b.iter().rposition(|&v| v == 9) == None);
+    assert!(b.iter().rposition(|&v| v == 5) == Some(4));
+    assert!(b.iter().rposition(|&v| v == 3) == Some(2));
+    assert!(b.iter().rposition(|&v| v == 0) == None);
+}
+
 #[test]
 fn test_binary_search() {
     let b: [i32; 0] = [];