Rollup merge of #60130 - khuey:efficient_last, r=sfackler

Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators

Provided a `DoubleEndedIterator` has finite length, `Iterator::last` is equivalent to `DoubleEndedIterator::next_back`. But searching forwards through the iterator when it's unnecessary is obviously not good for performance. I ran into this on one of the collection iterators.

I tried adding appropriate overloads for a bunch of the iterator adapters like filter, map, etc, but I ran into a lot of type inference failures after doing so.

The other interesting case is what to do with `Repeat`. Do we consider it part of the contract that `Iterator::last` will loop forever on it? The docs do say that the iterator will be evaluated until it returns None. This is also relevant for the adapters, it's trivially easy to observe whether a `Map` adapter invoked its closure a zillion times or just once for the last element.

14 files changed, 159 insertions, 0 deletions

diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index c355361b53c..39fcfaa7893 100644
--- a/src/liballoc/collections/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
@@ -992,6 +992,11 @@ impl<'a, T> Iterator for Iter<'a, T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1047,6 +1052,11 @@ impl<T> Iterator for IntoIter<T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1093,6 +1103,11 @@ impl<T> Iterator for Drain<'_, T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "drain", since = "1.6.0")]
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 6b079fc87cc..414abb00ef1 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -1193,6 +1193,11 @@ impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         (self.length, Some(self.length))
     }
+
+    #[inline]
+    fn last(mut self) -> Option<(&'a K, &'a V)> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "fused", since = "1.26.0")]
@@ -1253,6 +1258,11 @@ impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         (self.length, Some(self.length))
     }
+
+    #[inline]
+    fn last(mut self) -> Option<(&'a K, &'a mut V)> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1359,6 +1369,11 @@ impl<K, V> Iterator for IntoIter<K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         (self.length, Some(self.length))
     }
+
+    #[inline]
+    fn last(mut self) -> Option<(K, V)> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1421,6 +1436,11 @@ impl<'a, K, V> Iterator for Keys<'a, K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a K> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1458,6 +1478,11 @@ impl<'a, K, V> Iterator for Values<'a, K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a V> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1495,6 +1520,11 @@ impl<'a, K, V> Iterator for Range<'a, K, V> {
             unsafe { Some(self.next_unchecked()) }
         }
     }
+
+    #[inline]
+    fn last(mut self) -> Option<(&'a K, &'a V)> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "map_values_mut", since = "1.10.0")]
@@ -1508,6 +1538,11 @@ impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a mut V> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "map_values_mut", since = "1.10.0")]
@@ -1626,6 +1661,11 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
             unsafe { Some(self.next_unchecked()) }
         }
     }
+
+    #[inline]
+    fn last(mut self) -> Option<(&'a K, &'a mut V)> {
+        self.next_back()
+    }
 }
 
 impl<'a, K, V> RangeMut<'a, K, V> {
diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs
index 16a96ca19b8..6f2467dfd6b 100644
--- a/src/liballoc/collections/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -1019,6 +1019,11 @@ impl<'a, T> Iterator for Iter<'a, T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a T> {
+        self.next_back()
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
@@ -1044,6 +1049,11 @@ impl<T> Iterator for IntoIter<T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<T> {
+        self.next_back()
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> DoubleEndedIterator for IntoIter<T> {
@@ -1073,6 +1083,11 @@ impl<'a, T> Iterator for Range<'a, T> {
     fn next(&mut self) -> Option<&'a T> {
         self.iter.next().map(|(k, _)| k)
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "btree_range", since = "1.17.0")]
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 3fdcf95ccaa..63f7769fee5 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -2377,6 +2377,10 @@ impl Iterator for Drain<'_> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+    #[inline]
+    fn last(mut self) -> Option<char> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "drain", since = "1.6.0")]
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index 073d3ab5937..c0cdffe596b 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -2395,6 +2395,11 @@ impl<T> Iterator for IntoIter<T> {
     fn count(self) -> usize {
         self.len()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -2514,6 +2519,11 @@ impl<T> Iterator for Drain<'_, T> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<T> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "drain", since = "1.6.0")]
@@ -2583,6 +2593,10 @@ impl<I: Iterator> Iterator for Splice<'_, I> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.drain.size_hint()
     }
+
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "vec_splice", since = "1.21.0")]
diff --git a/src/libcore/ascii.rs b/src/libcore/ascii.rs
index c0ab364380f..ddee02ea232 100644
--- a/src/libcore/ascii.rs
+++ b/src/libcore/ascii.rs
@@ -117,6 +117,8 @@ impl Iterator for EscapeDefault {
     type Item = u8;
     fn next(&mut self) -> Option<u8> { self.range.next().map(|i| self.data[i]) }
     fn size_hint(&self) -> (usize, Option<usize>) { self.range.size_hint() }
+    #[inline]
+    fn last(mut self) -> Option<u8> { self.next_back() }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl DoubleEndedIterator for EscapeDefault {
diff --git a/src/libcore/iter/adapters/mod.rs b/src/libcore/iter/adapters/mod.rs
index 518442efe74..64e588f65b4 100644
--- a/src/libcore/iter/adapters/mod.rs
+++ b/src/libcore/iter/adapters/mod.rs
@@ -73,6 +73,11 @@ impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
     {
         self.iter.position(predicate)
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 8731f486753..4066e2f0a84 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -3541,6 +3541,11 @@ impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
             (1, Some(self.v.len() + 1))
         }
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -3639,6 +3644,11 @@ impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
             (1, Some(self.v.len() + 1))
         }
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -3704,6 +3714,11 @@ impl<'a, T, P> Iterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "slice_rsplit", since = "1.27.0")]
@@ -3768,6 +3783,11 @@ impl<'a, T, P> Iterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "slice_rsplit", since = "1.27.0")]
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 45421848cec..84079a7a433 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -1333,6 +1333,11 @@ impl<'a> Iterator for Lines<'a> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.0.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1379,6 +1384,11 @@ impl<'a> Iterator for LinesAny<'a> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.0.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -4217,6 +4227,11 @@ impl<'a> Iterator for SplitWhitespace<'a> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "split_whitespace", since = "1.1.0")]
@@ -4243,6 +4258,11 @@ impl<'a> Iterator for SplitAsciiWhitespace<'a> {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "split_ascii_whitespace", since = "1.34.0")]
diff --git a/src/libstd/env.rs b/src/libstd/env.rs
index c0d0c23e469..39896ac2fcd 100644
--- a/src/libstd/env.rs
+++ b/src/libstd/env.rs
@@ -746,6 +746,10 @@ impl Iterator for Args {
         self.inner.next().map(|s| s.into_string().unwrap())
     }
     fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
+    #[inline]
+    fn last(mut self) -> Option<String> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "env", since = "1.0.0")]
@@ -781,6 +785,8 @@ impl Iterator for ArgsOs {
     type Item = OsString;
     fn next(&mut self) -> Option<OsString> { self.inner.next() }
     fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
+    #[inline]
+    fn last(mut self) -> Option<OsString> { self.next_back() }
 }
 
 #[stable(feature = "env", since = "1.0.0")]
diff --git a/src/libstd/path.rs b/src/libstd/path.rs
index 126bc3754da..59f9e439add 100644
--- a/src/libstd/path.rs
+++ b/src/libstd/path.rs
@@ -888,6 +888,11 @@ impl<'a> Iterator for Iter<'a> {
     fn next(&mut self) -> Option<&'a OsStr> {
         self.inner.next().map(Component::as_os_str)
     }
+
+    #[inline]
+    fn last(mut self) -> Option<&'a OsStr> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -951,6 +956,11 @@ impl<'a> Iterator for Components<'a> {
         }
         None
     }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libstd/sys/unix/args.rs b/src/libstd/sys/unix/args.rs
index 18de1096df2..f0594bb21bd 100644
--- a/src/libstd/sys/unix/args.rs
+++ b/src/libstd/sys/unix/args.rs
@@ -35,6 +35,8 @@ impl Iterator for Args {
     type Item = OsString;
     fn next(&mut self) -> Option<OsString> { self.iter.next() }
     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
+    #[inline]
+    fn last(mut self) -> Option<OsString> { self.next_back() }
 }
 
 impl ExactSizeIterator for Args {
diff --git a/src/libstd/sys/wasm/args.rs b/src/libstd/sys/wasm/args.rs
index b3c77b86995..6766099c1ec 100644
--- a/src/libstd/sys/wasm/args.rs
+++ b/src/libstd/sys/wasm/args.rs
@@ -37,6 +37,10 @@ impl Iterator for Args {
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.iter.size_hint()
     }
+    #[inline]
+    fn last(mut self) -> Option<OsString> {
+        self.next_back()
+    }
 }
 
 impl ExactSizeIterator for Args {
diff --git a/src/libstd/sys/windows/args.rs b/src/libstd/sys/windows/args.rs
index b04bb484eed..744d7ec59d3 100644
--- a/src/libstd/sys/windows/args.rs
+++ b/src/libstd/sys/windows/args.rs
@@ -181,6 +181,8 @@ impl Iterator for Args {
     type Item = OsString;
     fn next(&mut self) -> Option<OsString> { self.parsed_args_list.next() }
     fn size_hint(&self) -> (usize, Option<usize>) { self.parsed_args_list.size_hint() }
+    #[inline]
+    fn last(mut self) -> Option<OsString> { self.next_back() }
 }
 
 impl DoubleEndedIterator for Args {