Auto merge of #33289 - birkenfeld:chain-find, r=bluss

Implement find() on Chain iterators

This results in a roughly 2x speedup compared to the default impl
"inherited" from Iterator.

Benchmark: https://gist.github.com/birkenfeld/aa9b92cb7d55666dd4821207527eaf5b

2 files changed, 30 insertions, 0 deletions

diff --git a/src/libcore/iter/mod.rs b/src/libcore/iter/mod.rs
index abc199cd182..17f7c0a773e 100644
--- a/src/libcore/iter/mod.rs
+++ b/src/libcore/iter/mod.rs
@@ -542,6 +542,23 @@ impl<A, B> Iterator for Chain<A, B> where
     }
 
     #[inline]
+    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
+        P: FnMut(&Self::Item) -> bool,
+    {
+        match self.state {
+            ChainState::Both => match self.a.find(&mut predicate) {
+                None => {
+                    self.state = ChainState::Back;
+                    self.b.find(predicate)
+                }
+                v => v
+            },
+            ChainState::Front => self.a.find(predicate),
+            ChainState::Back => self.b.find(predicate),
+        }
+    }
+
+    #[inline]
     fn last(self) -> Option<A::Item> {
         match self.state {
             ChainState::Both => {
diff --git a/src/libcoretest/iter.rs b/src/libcoretest/iter.rs
index 6c0cb03b5f7..56b10d0b79b 100644
--- a/src/libcoretest/iter.rs
+++ b/src/libcoretest/iter.rs
@@ -134,6 +134,19 @@ fn test_iterator_chain_count() {
 }
 
 #[test]
+fn test_iterator_chain_find() {
+    let xs = [0, 1, 2, 3, 4, 5];
+    let ys = [30, 40, 50, 60];
+    let mut iter = xs.iter().chain(&ys);
+    assert_eq!(iter.find(|&&i| i == 4), Some(&4));
+    assert_eq!(iter.next(), Some(&5));
+    assert_eq!(iter.find(|&&i| i == 40), Some(&40));
+    assert_eq!(iter.next(), Some(&50));
+    assert_eq!(iter.find(|&&i| i == 100), None);
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
 fn test_filter_map() {
     let it = (0..).step_by(1).take(10)
         .filter_map(|x| if x % 2 == 0 { Some(x*x) } else { None });