Avoid unused clones in Cloned<I> and Copied<I>

Avoid cloning in `Cloned<I>` or copying in `Copied<I>` when elements are
only needed by reference or not at all. There is already some precedent
for this, given that `__iterator_get_unchecked` is implemented, which
can skip elements. The reduced clones are technically observable by a
user impl of `Clone`.

2 files changed, 163 insertions, 20 deletions

diff --git a/library/core/src/iter/adapters/cloned.rs b/library/core/src/iter/adapters/cloned.rs
index aea6d64281a..72d74628971 100644
--- a/library/core/src/iter/adapters/cloned.rs
+++ b/library/core/src/iter/adapters/cloned.rs
@@ -1,5 +1,6 @@
 use core::num::NonZero;
 
+use crate::cmp::Ordering;
 use crate::iter::adapters::zip::try_get_unchecked;
 use crate::iter::adapters::{SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
 use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen, UncheckedIterator};
@@ -41,13 +42,31 @@ where
         self.it.next().cloned()
     }
 
+    #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.it.size_hint()
     }
 
+    #[inline]
+    fn count(self) -> usize {
+        self.it.count()
+    }
+
+    fn last(self) -> Option<T> {
+        self.it.last().cloned()
+    }
+
+    #[inline]
+    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
+        self.it.advance_by(n)
+    }
+
+    fn nth(&mut self, n: usize) -> Option<T> {
+        self.it.nth(n).cloned()
+    }
+
     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
     where
-        Self: Sized,
         F: FnMut(B, Self::Item) -> R,
         R: Try<Output = B>,
     {
@@ -61,6 +80,58 @@ where
         self.it.map(T::clone).fold(init, f)
     }
 
+    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
+    where
+        P: FnMut(&Self::Item) -> bool,
+    {
+        self.it.find(move |x| predicate(&x)).cloned()
+    }
+
+    fn max_by<F>(self, mut compare: F) -> Option<Self::Item>
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        self.it.max_by(move |&x, &y| compare(x, y)).cloned()
+    }
+
+    fn min_by<F>(self, mut compare: F) -> Option<Self::Item>
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        self.it.min_by(move |&x, &y| compare(x, y)).cloned()
+    }
+
+    fn cmp<O>(self, other: O) -> Ordering
+    where
+        O: IntoIterator<Item = Self::Item>,
+        Self::Item: Ord,
+    {
+        self.it.cmp_by(other, |x, y| x.cmp(&y))
+    }
+
+    fn partial_cmp<O>(self, other: O) -> Option<Ordering>
+    where
+        O: IntoIterator,
+        Self::Item: PartialOrd<O::Item>,
+    {
+        self.it.partial_cmp_by(other, |x, y| x.partial_cmp(&y))
+    }
+
+    fn eq<O>(self, other: O) -> bool
+    where
+        O: IntoIterator,
+        Self::Item: PartialEq<O::Item>,
+    {
+        self.it.eq_by(other, |x, y| x == &y)
+    }
+
+    fn is_sorted_by<F>(self, mut compare: F) -> bool
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> bool,
+    {
+        self.it.is_sorted_by(move |&x, &y| compare(x, y))
+    }
+
     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T
     where
         Self: TrustedRandomAccessNoCoerce,
@@ -81,9 +152,13 @@ where
         self.it.next_back().cloned()
     }
 
+    #[inline]
+    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
+        self.it.advance_back_by(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<Output = B>,
     {
@@ -96,6 +171,13 @@ where
     {
         self.it.map(T::clone).rfold(init, f)
     }
+
+    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
+    where
+        P: FnMut(&Self::Item) -> bool,
+    {
+        self.it.rfind(move |x| predicate(&x)).cloned()
+    }
 }
 
 #[stable(feature = "iter_cloned", since = "1.1.0")]
@@ -104,10 +186,12 @@ where
     I: ExactSizeIterator<Item = &'a T>,
     T: Clone,
 {
+    #[inline]
     fn len(&self) -> usize {
         self.it.len()
     }
 
+    #[inline]
     fn is_empty(&self) -> bool {
         self.it.is_empty()
     }
diff --git a/library/core/src/iter/adapters/copied.rs b/library/core/src/iter/adapters/copied.rs
index 23e4e25ab53..73913aa34a9 100644
--- a/library/core/src/iter/adapters/copied.rs
+++ b/library/core/src/iter/adapters/copied.rs
@@ -1,3 +1,4 @@
+use crate::cmp::Ordering;
 use crate::iter::adapters::zip::try_get_unchecked;
 use crate::iter::adapters::{SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
 use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen};
@@ -48,20 +49,35 @@ where
 
     fn next_chunk<const N: usize>(
         &mut self,
-    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>>
-    where
-        Self: Sized,
-    {
+    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> {
         <I as SpecNextChunk<'_, N, T>>::spec_next_chunk(&mut self.it)
     }
 
+    #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.it.size_hint()
     }
 
+    #[inline]
+    fn count(self) -> usize {
+        self.it.count()
+    }
+
+    fn last(self) -> Option<T> {
+        self.it.last().copied()
+    }
+
+    #[inline]
+    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
+        self.it.advance_by(n)
+    }
+
+    fn nth(&mut self, n: usize) -> Option<T> {
+        self.it.nth(n).copied()
+    }
+
     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
     where
-        Self: Sized,
         F: FnMut(B, Self::Item) -> R,
         R: Try<Output = B>,
     {
@@ -75,21 +91,56 @@ where
         self.it.fold(init, copy_fold(f))
     }
 
-    fn nth(&mut self, n: usize) -> Option<T> {
-        self.it.nth(n).copied()
+    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
+    where
+        P: FnMut(&Self::Item) -> bool,
+    {
+        self.it.find(move |x| predicate(&x)).copied()
     }
 
-    fn last(self) -> Option<T> {
-        self.it.last().copied()
+    fn max_by<F>(self, mut compare: F) -> Option<Self::Item>
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        self.it.max_by(move |&x, &y| compare(x, y)).copied()
     }
 
-    fn count(self) -> usize {
-        self.it.count()
+    fn min_by<F>(self, mut compare: F) -> Option<Self::Item>
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        self.it.min_by(move |&x, &y| compare(x, y)).copied()
     }
 
-    #[inline]
-    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
-        self.it.advance_by(n)
+    fn cmp<O>(self, other: O) -> Ordering
+    where
+        O: IntoIterator<Item = Self::Item>,
+        Self::Item: Ord,
+    {
+        self.it.cmp_by(other, |x, y| x.cmp(&y))
+    }
+
+    fn partial_cmp<O>(self, other: O) -> Option<Ordering>
+    where
+        O: IntoIterator,
+        Self::Item: PartialOrd<O::Item>,
+    {
+        self.it.partial_cmp_by(other, |x, y| x.partial_cmp(&y))
+    }
+
+    fn eq<O>(self, other: O) -> bool
+    where
+        O: IntoIterator,
+        Self::Item: PartialEq<O::Item>,
+    {
+        self.it.eq_by(other, |x, y| x == &y)
+    }
+
+    fn is_sorted_by<F>(self, mut compare: F) -> bool
+    where
+        F: FnMut(&Self::Item, &Self::Item) -> bool,
+    {
+        self.it.is_sorted_by(move |&x, &y| compare(x, y))
     }
 
     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T
@@ -112,9 +163,13 @@ where
         self.it.next_back().copied()
     }
 
+    #[inline]
+    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
+        self.it.advance_back_by(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<Output = B>,
     {
@@ -128,9 +183,11 @@ where
         self.it.rfold(init, copy_fold(f))
     }
 
-    #[inline]
-    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
-        self.it.advance_back_by(n)
+    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
+    where
+        P: FnMut(&Self::Item) -> bool,
+    {
+        self.it.rfind(move |x| predicate(&x)).copied()
     }
 }
 
@@ -140,10 +197,12 @@ where
     I: ExactSizeIterator<Item = &'a T>,
     T: Copy,
 {
+    #[inline]
     fn len(&self) -> usize {
         self.it.len()
     }
 
+    #[inline]
     fn is_empty(&self) -> bool {
         self.it.is_empty()
     }