Rollup merge of #81607 - the8472:trustedrandomaccess-all-the-things, r=m-ou-se

Implement TrustedLen and TrustedRandomAccess for Range<integer>, array::IntoIter, VecDequeue's iterators

This should make some `FromIterator` and `.zip()` specializations applicable in a few more cases.

``@rustbot`` label libs-impl

6 files changed, 144 insertions, 6 deletions

diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs
index 465b058cd98..1c635dd4f27 100644
--- a/library/alloc/src/collections/vec_deque/into_iter.rs
+++ b/library/alloc/src/collections/vec_deque/into_iter.rs
@@ -1,5 +1,5 @@
 use core::fmt;
-use core::iter::FusedIterator;
+use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess};
 
 use super::VecDeque;
 
@@ -36,6 +36,22 @@ impl<T> Iterator for IntoIter<T> {
         let len = self.inner.len();
         (len, Some(len))
     }
+
+    #[inline]
+    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
+    where
+        Self: TrustedRandomAccess,
+    {
+        // Safety: The TrustedRandomAccess contract requires that callers only pass an index
+        // that is in bounds.
+        // Additionally Self: TrustedRandomAccess is only implemented for T: Copy which means even
+        // multiple repeated reads of the same index would be safe and the
+        // values are !Drop, thus won't suffer from double drops.
+        unsafe {
+            let idx = self.inner.wrap_add(self.inner.tail, idx);
+            self.inner.buffer_read(idx)
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -55,3 +71,17 @@ impl<T> ExactSizeIterator for IntoIter<T> {
 
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T> TrustedLen for IntoIter<T> {}
+
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+// T: Copy as approximation for !Drop since get_unchecked does not update the pointers
+// and thus we can't implement drop-handling
+unsafe impl<T> TrustedRandomAccess for IntoIter<T>
+where
+    T: Copy,
+{
+    const MAY_HAVE_SIDE_EFFECT: bool = false;
+}
diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs
index ad31b991cb6..e4cfb3acdfd 100644
--- a/library/alloc/src/collections/vec_deque/iter.rs
+++ b/library/alloc/src/collections/vec_deque/iter.rs
@@ -1,5 +1,5 @@
 use core::fmt;
-use core::iter::FusedIterator;
+use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess};
 use core::ops::Try;
 
 use super::{count, wrap_index, RingSlices};
@@ -101,6 +101,19 @@ impl<'a, T> Iterator for Iter<'a, T> {
     fn last(mut self) -> Option<&'a T> {
         self.next_back()
     }
+
+    #[inline]
+    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
+    where
+        Self: TrustedRandomAccess,
+    {
+        // Safety: The TrustedRandomAccess contract requires that callers only  pass an index
+        // that is in bounds.
+        unsafe {
+            let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
+            self.ring.get_unchecked(idx)
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -157,3 +170,12 @@ impl<T> ExactSizeIterator for Iter<'_, T> {
 
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Iter<'_, T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T> TrustedLen for Iter<'_, T> {}
+
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {
+    const MAY_HAVE_SIDE_EFFECT: bool = false;
+}
diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs
index 3d0c3094e26..9493676e66b 100644
--- a/library/alloc/src/collections/vec_deque/iter_mut.rs
+++ b/library/alloc/src/collections/vec_deque/iter_mut.rs
@@ -1,5 +1,5 @@
 use core::fmt;
-use core::iter::FusedIterator;
+use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess};
 use core::marker::PhantomData;
 
 use super::{count, wrap_index, RingSlices};
@@ -87,6 +87,19 @@ impl<'a, T> Iterator for IterMut<'a, T> {
     fn last(mut self) -> Option<&'a mut T> {
         self.next_back()
     }
+
+    #[inline]
+    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
+    where
+        Self: TrustedRandomAccess,
+    {
+        // Safety: The TrustedRandomAccess contract requires that callers only  pass an index
+        // that is in bounds.
+        unsafe {
+            let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
+            &mut *self.ring.get_unchecked_mut(idx)
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -126,3 +139,12 @@ impl<T> ExactSizeIterator for IterMut<'_, T> {
 
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IterMut<'_, T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T> TrustedLen for IterMut<'_, T> {}
+
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+unsafe impl<T> TrustedRandomAccess for IterMut<'_, T> {
+    const MAY_HAVE_SIDE_EFFECT: bool = false;
+}
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 7a0de74eb23..d3e70991ad5 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -58,7 +58,7 @@ mod tests;
 const INITIAL_CAPACITY: usize = 7; // 2^3 - 1
 const MINIMUM_CAPACITY: usize = 1; // 2 - 1
 
-const MAXIMUM_ZST_CAPACITY: usize = 1 << (core::mem::size_of::<usize>() * 8 - 1); // Largest possible power of two
+const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible power of two
 
 /// A double-ended queue implemented with a growable ring buffer.
 ///
diff --git a/library/core/src/array/iter.rs b/library/core/src/array/iter.rs
index 4472fba26b9..f82454addd0 100644
--- a/library/core/src/array/iter.rs
+++ b/library/core/src/array/iter.rs
@@ -2,7 +2,7 @@
 
 use crate::{
     fmt,
-    iter::{ExactSizeIterator, FusedIterator, TrustedLen},
+    iter::{ExactSizeIterator, FusedIterator, TrustedLen, TrustedRandomAccess},
     mem::{self, MaybeUninit},
     ops::Range,
     ptr,
@@ -130,6 +130,18 @@ impl<T, const N: usize> Iterator for IntoIter<T, N> {
     fn last(mut self) -> Option<Self::Item> {
         self.next_back()
     }
+
+    #[inline]
+    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
+    where
+        Self: TrustedRandomAccess,
+    {
+        // SAFETY: Callers are only allowed to pass an index that is in bounds
+        // Additionally Self: TrustedRandomAccess is only implemented for T: Copy which means even
+        // multiple repeated reads of the same index would be safe and the
+        // values aree !Drop, thus won't suffer from double drops.
+        unsafe { self.data.get_unchecked(self.alive.start + idx).assume_init_read() }
+    }
 }
 
 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
@@ -184,6 +196,17 @@ impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {}
 
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+// T: Copy as approximation for !Drop since get_unchecked does not update the pointers
+// and thus we can't implement drop-handling
+unsafe impl<T, const N: usize> TrustedRandomAccess for IntoIter<T, N>
+where
+    T: Copy,
+{
+    const MAY_HAVE_SIDE_EFFECT: bool = false;
+}
+
 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 impl<T: Clone, const N: usize> Clone for IntoIter<T, N> {
     fn clone(&self) -> Self {
diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs
index cc80e06decd..4b293c596e7 100644
--- a/library/core/src/iter/range.rs
+++ b/library/core/src/iter/range.rs
@@ -3,7 +3,7 @@ use crate::convert::TryFrom;
 use crate::mem;
 use crate::ops::{self, Try};
 
-use super::{FusedIterator, TrustedLen};
+use super::{FusedIterator, TrustedLen, TrustedRandomAccess};
 
 /// Objects that have a notion of *successor* and *predecessor* operations.
 ///
@@ -493,6 +493,18 @@ macro_rules! range_exact_iter_impl {
     )*)
 }
 
+/// Safety: This macro must only be used on types that are `Copy` and result in ranges
+/// which have an exact `size_hint()` where the upper bound must not be `None`.
+macro_rules! unsafe_range_trusted_random_access_impl {
+    ($($t:ty)*) => ($(
+        #[doc(hidden)]
+        #[unstable(feature = "trusted_random_access", issue = "none")]
+        unsafe impl TrustedRandomAccess for ops::Range<$t> {
+            const MAY_HAVE_SIDE_EFFECT: bool = false;
+        }
+    )*)
+}
+
 macro_rules! range_incl_exact_iter_impl {
     ($($t:ty)*) => ($(
         #[stable(feature = "inclusive_range", since = "1.26.0")]
@@ -553,6 +565,18 @@ impl<A: Step> Iterator for ops::Range<A> {
     fn max(mut self) -> Option<A> {
         self.next_back()
     }
+
+    #[inline]
+    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
+    where
+        Self: TrustedRandomAccess,
+    {
+        // SAFETY: The TrustedRandomAccess contract requires that callers only  pass an index
+        // that is in bounds.
+        // Additionally Self: TrustedRandomAccess is only implemented for Copy types
+        // which means even repeated reads of the same index would be safe.
+        unsafe { Step::forward_unchecked(self.start.clone(), idx) }
+    }
 }
 
 // These macros generate `ExactSizeIterator` impls for various range types.
@@ -574,6 +598,23 @@ range_exact_iter_impl! {
     u32
     i32
 }
+
+unsafe_range_trusted_random_access_impl! {
+    usize u8 u16
+    isize i8 i16
+}
+
+#[cfg(target_pointer_width = "32")]
+unsafe_range_trusted_random_access_impl! {
+    u32 i32
+}
+
+#[cfg(target_pointer_width = "64")]
+unsafe_range_trusted_random_access_impl! {
+    u32 i32
+    u64 i64
+}
+
 range_incl_exact_iter_impl! {
     u8
     i8