Merge from rust-lang/rust

28 files changed, 2182 insertions, 480 deletions

diff --git a/library/alloc/src/borrow.rs b/library/alloc/src/borrow.rs
index f86face3f90..dbfd2e74abe 100644
--- a/library/alloc/src/borrow.rs
+++ b/library/alloc/src/borrow.rs
@@ -225,7 +225,6 @@ impl<B: ?Sized + ToOwned> Cow<'_, B> {
     /// assert!(!bull.is_borrowed());
     /// ```
     #[unstable(feature = "cow_is_borrowed", issue = "65143")]
-    #[rustc_const_unstable(feature = "const_cow_is_borrowed", issue = "65143")]
     pub const fn is_borrowed(&self) -> bool {
         match *self {
             Borrowed(_) => true,
@@ -248,7 +247,6 @@ impl<B: ?Sized + ToOwned> Cow<'_, B> {
     /// assert!(!bull.is_owned());
     /// ```
     #[unstable(feature = "cow_is_borrowed", issue = "65143")]
-    #[rustc_const_unstable(feature = "const_cow_is_borrowed", issue = "65143")]
     pub const fn is_owned(&self) -> bool {
         !self.is_borrowed()
     }
diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs
index 5f207295683..3e791416820 100644
--- a/library/alloc/src/boxed.rs
+++ b/library/alloc/src/boxed.rs
@@ -1688,7 +1688,7 @@ impl<T: Default> Default for Box<T> {
     /// Creates a `Box<T>`, with the `Default` value for T.
     #[inline]
     fn default() -> Self {
-        Box::new(T::default())
+        Box::write(Box::new_uninit(), T::default())
     }
 }
 
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index b1759a486ac..54739c50d1d 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -103,6 +103,7 @@ pub struct VecDeque<
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> {
+    #[track_caller]
     fn clone(&self) -> Self {
         let mut deq = Self::with_capacity_in(self.len(), self.allocator().clone());
         deq.extend(self.iter().cloned());
@@ -113,6 +114,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> {
     ///
     /// This method is preferred over simply assigning `source.clone()` to `self`,
     /// as it avoids reallocation if possible.
+    #[track_caller]
     fn clone_from(&mut self, source: &Self) {
         self.clear();
         self.extend(source.iter().cloned());
@@ -570,6 +572,7 @@ impl<T> VecDeque<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     #[must_use]
+    #[track_caller]
     pub fn with_capacity(capacity: usize) -> VecDeque<T> {
         Self::with_capacity_in(capacity, Global)
     }
@@ -625,6 +628,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// let deque: VecDeque<u32> = VecDeque::with_capacity(10);
     /// ```
     #[unstable(feature = "allocator_api", issue = "32838")]
+    #[track_caller]
     pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A> {
         VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) }
     }
@@ -789,6 +793,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// [`reserve`]: VecDeque::reserve
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn reserve_exact(&mut self, additional: usize) {
         let new_cap = self.len.checked_add(additional).expect("capacity overflow");
         let old_cap = self.capacity();
@@ -818,6 +823,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert!(buf.capacity() >= 11);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn reserve(&mut self, additional: usize) {
         let new_cap = self.len.checked_add(additional).expect("capacity overflow");
         let old_cap = self.capacity();
@@ -949,6 +955,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert!(buf.capacity() >= 4);
     /// ```
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
+    #[track_caller]
     pub fn shrink_to_fit(&mut self) {
         self.shrink_to(0);
     }
@@ -974,6 +981,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert!(buf.capacity() >= 4);
     /// ```
     #[stable(feature = "shrink_to", since = "1.56.0")]
+    #[track_caller]
     pub fn shrink_to(&mut self, min_capacity: usize) {
         let target_cap = min_capacity.max(self.len);
 
@@ -1740,6 +1748,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert_eq!(d.front(), Some(&2));
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn push_front(&mut self, value: T) {
         if self.is_full() {
             self.grow();
@@ -1767,6 +1776,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     #[rustc_confusables("push", "put", "append")]
+    #[track_caller]
     pub fn push_back(&mut self, value: T) {
         if self.is_full() {
             self.grow();
@@ -1876,6 +1886,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
     /// ```
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
+    #[track_caller]
     pub fn insert(&mut self, index: usize, value: T) {
         assert!(index <= self.len(), "index out of bounds");
         if self.is_full() {
@@ -1979,6 +1990,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[must_use = "use `.truncate()` if you don't need the other half"]
     #[stable(feature = "split_off", since = "1.4.0")]
+    #[track_caller]
     pub fn split_off(&mut self, at: usize) -> Self
     where
         A: Clone,
@@ -2045,6 +2057,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[inline]
     #[stable(feature = "append", since = "1.4.0")]
+    #[track_caller]
     pub fn append(&mut self, other: &mut Self) {
         if T::IS_ZST {
             self.len = self.len.checked_add(other.len).expect("capacity overflow");
@@ -2167,6 +2180,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     // be called in cold paths.
     // This may panic or abort
     #[inline(never)]
+    #[track_caller]
     fn grow(&mut self) {
         // Extend or possibly remove this assertion when valid use-cases for growing the
         // buffer without it being full emerge
@@ -2205,6 +2219,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// assert_eq!(buf, [5, 10, 101, 102, 103]);
     /// ```
     #[stable(feature = "vec_resize_with", since = "1.33.0")]
+    #[track_caller]
     pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
         let len = self.len;
 
@@ -2751,6 +2766,7 @@ impl<T: Clone, A: Allocator> VecDeque<T, A> {
     /// assert_eq!(buf, [5, 10, 20, 20, 20]);
     /// ```
     #[stable(feature = "deque_extras", since = "1.16.0")]
+    #[track_caller]
     pub fn resize(&mut self, new_len: usize, value: T) {
         if new_len > self.len() {
             let extra = new_len - self.len();
@@ -2870,6 +2886,7 @@ impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> FromIterator<T> for VecDeque<T> {
+    #[track_caller]
     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> {
         SpecFromIter::spec_from_iter(iter.into_iter())
     }
@@ -2909,16 +2926,19 @@ impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
+    #[track_caller]
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
     }
 
     #[inline]
+    #[track_caller]
     fn extend_one(&mut self, elem: T) {
         self.push_back(elem);
     }
 
     #[inline]
+    #[track_caller]
     fn extend_reserve(&mut self, additional: usize) {
         self.reserve(additional);
     }
@@ -2934,16 +2954,19 @@ impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
 
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
+    #[track_caller]
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
         self.spec_extend(iter.into_iter());
     }
 
     #[inline]
+    #[track_caller]
     fn extend_one(&mut self, &elem: &'a T) {
         self.push_back(elem);
     }
 
     #[inline]
+    #[track_caller]
     fn extend_reserve(&mut self, additional: usize) {
         self.reserve(additional);
     }
@@ -3041,6 +3064,7 @@ impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
     /// let deq2: VecDeque<_> = [1, 2, 3, 4].into();
     /// assert_eq!(deq1, deq2);
     /// ```
+    #[track_caller]
     fn from(arr: [T; N]) -> Self {
         let mut deq = VecDeque::with_capacity(N);
         let arr = ManuallyDrop::new(arr);
diff --git a/library/alloc/src/collections/vec_deque/spec_extend.rs b/library/alloc/src/collections/vec_deque/spec_extend.rs
index a9b0fd073b5..d246385ca84 100644
--- a/library/alloc/src/collections/vec_deque/spec_extend.rs
+++ b/library/alloc/src/collections/vec_deque/spec_extend.rs
@@ -7,6 +7,7 @@ use crate::vec;
 
 // Specialization trait used for VecDeque::extend
 pub(super) trait SpecExtend<T, I> {
+    #[track_caller]
     fn spec_extend(&mut self, iter: I);
 }
 
@@ -14,6 +15,7 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
 where
     I: Iterator<Item = T>,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, mut iter: I) {
         // This function should be the moral equivalent of:
         //
@@ -44,6 +46,7 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
 where
     I: TrustedLen<Item = T>,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, iter: I) {
         // This is the case for a TrustedLen iterator.
         let (low, high) = iter.size_hint();
@@ -76,6 +79,7 @@ where
 }
 
 impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> {
+    #[track_caller]
     fn spec_extend(&mut self, mut iterator: vec::IntoIter<T>) {
         let slice = iterator.as_slice();
         self.reserve(slice.len());
@@ -93,6 +97,7 @@ where
     I: Iterator<Item = &'a T>,
     T: Copy,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, iterator: I) {
         self.spec_extend(iterator.copied())
     }
@@ -102,6 +107,7 @@ impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for VecDeque
 where
     T: Copy,
 {
+    #[track_caller]
     fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
         let slice = iterator.as_slice();
         self.reserve(slice.len());
diff --git a/library/alloc/src/collections/vec_deque/spec_from_iter.rs b/library/alloc/src/collections/vec_deque/spec_from_iter.rs
index 2708c7fe102..1efe84d6d7d 100644
--- a/library/alloc/src/collections/vec_deque/spec_from_iter.rs
+++ b/library/alloc/src/collections/vec_deque/spec_from_iter.rs
@@ -9,6 +9,7 @@ impl<T, I> SpecFromIter<T, I> for VecDeque<T>
 where
     I: Iterator<Item = T>,
 {
+    #[track_caller]
     default fn spec_from_iter(iterator: I) -> Self {
         // Since converting is O(1) now, just re-use the `Vec` logic for
         // anything where we can't do something extra-special for `VecDeque`,
diff --git a/library/alloc/src/ffi/c_str.rs b/library/alloc/src/ffi/c_str.rs
index d496899e72b..d7e99f4a1a6 100644
--- a/library/alloc/src/ffi/c_str.rs
+++ b/library/alloc/src/ffi/c_str.rs
@@ -7,7 +7,7 @@ use core::borrow::Borrow;
 use core::ffi::{CStr, c_char};
 use core::num::NonZero;
 use core::slice::memchr;
-use core::str::{self, Utf8Error};
+use core::str::{self, FromStr, Utf8Error};
 use core::{fmt, mem, ops, ptr, slice};
 
 use crate::borrow::{Cow, ToOwned};
@@ -817,6 +817,30 @@ impl From<Vec<NonZero<u8>>> for CString {
     }
 }
 
+impl FromStr for CString {
+    type Err = NulError;
+
+    /// Converts a string `s` into a [`CString`].
+    ///
+    /// This method is equivalent to [`CString::new`].
+    #[inline]
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Self::new(s)
+    }
+}
+
+impl TryFrom<CString> for String {
+    type Error = IntoStringError;
+
+    /// Converts a [`CString`] into a [`String`] if it contains valid UTF-8 data.
+    ///
+    /// This method is equivalent to [`CString::into_string`].
+    #[inline]
+    fn try_from(value: CString) -> Result<Self, Self::Error> {
+        value.into_string()
+    }
+}
+
 #[cfg(not(test))]
 #[stable(feature = "more_box_slice_clone", since = "1.29.0")]
 impl Clone for Box<CStr> {
diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs
index c60c0743c7e..0a4a5160d82 100644
--- a/library/alloc/src/lib.rs
+++ b/library/alloc/src/lib.rs
@@ -104,15 +104,14 @@
 #![feature(async_closure)]
 #![feature(async_fn_traits)]
 #![feature(async_iterator)]
+#![feature(box_uninit_write)]
 #![feature(clone_to_uninit)]
 #![feature(coerce_unsized)]
 #![feature(const_align_of_val)]
 #![feature(const_box)]
-#![feature(const_cow_is_borrowed)]
 #![feature(const_eval_select)]
 #![feature(const_heap)]
 #![feature(const_maybe_uninit_write)]
-#![feature(const_option)]
 #![feature(const_pin)]
 #![feature(const_size_of_val)]
 #![feature(const_vec_string_slice)]
@@ -164,8 +163,6 @@
 //
 // Language features:
 // tidy-alphabetical-start
-#![cfg_attr(bootstrap, feature(const_mut_refs))]
-#![cfg_attr(bootstrap, feature(const_refs_to_cell))]
 #![cfg_attr(not(test), feature(coroutine_trait))]
 #![cfg_attr(test, feature(panic_update_hook))]
 #![cfg_attr(test, feature(test))]
@@ -173,7 +170,6 @@
 #![feature(allow_internal_unstable)]
 #![feature(cfg_sanitize)]
 #![feature(const_precise_live_drops)]
-#![feature(const_ptr_write)]
 #![feature(const_try)]
 #![feature(decl_macro)]
 #![feature(dropck_eyepatch)]
diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs
index 8fdca8c4200..45de0617f33 100644
--- a/library/alloc/src/raw_vec.rs
+++ b/library/alloc/src/raw_vec.rs
@@ -20,6 +20,7 @@ mod tests;
 // only one location which panics rather than a bunch throughout the module.
 #[cfg(not(no_global_oom_handling))]
 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
+#[track_caller]
 fn capacity_overflow() -> ! {
     panic!("capacity overflow");
 }
@@ -125,6 +126,7 @@ impl<T> RawVec<T, Global> {
     #[cfg(not(any(no_global_oom_handling, test)))]
     #[must_use]
     #[inline]
+    #[track_caller]
     pub fn with_capacity(capacity: usize) -> Self {
         Self { inner: RawVecInner::with_capacity(capacity, T::LAYOUT), _marker: PhantomData }
     }
@@ -133,6 +135,7 @@ impl<T> RawVec<T, Global> {
     #[cfg(not(any(no_global_oom_handling, test)))]
     #[must_use]
     #[inline]
+    #[track_caller]
     pub fn with_capacity_zeroed(capacity: usize) -> Self {
         Self {
             inner: RawVecInner::with_capacity_zeroed_in(capacity, Global, T::LAYOUT),
@@ -145,6 +148,7 @@ impl RawVecInner<Global> {
     #[cfg(not(any(no_global_oom_handling, test)))]
     #[must_use]
     #[inline]
+    #[track_caller]
     fn with_capacity(capacity: usize, elem_layout: Layout) -> Self {
         match Self::try_allocate_in(capacity, AllocInit::Uninitialized, Global, elem_layout) {
             Ok(res) => res,
@@ -184,6 +188,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     /// allocator for the returned `RawVec`.
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
         Self {
             inner: RawVecInner::with_capacity_in(capacity, alloc, T::LAYOUT),
@@ -205,6 +210,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     /// of allocator for the returned `RawVec`.
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     pub fn with_capacity_zeroed_in(capacity: usize, alloc: A) -> Self {
         Self {
             inner: RawVecInner::with_capacity_zeroed_in(capacity, alloc, T::LAYOUT),
@@ -324,6 +330,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     /// Aborts on OOM.
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     pub fn reserve(&mut self, len: usize, additional: usize) {
         self.inner.reserve(len, additional, T::LAYOUT)
     }
@@ -332,6 +339,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     /// caller to ensure `len == self.capacity()`.
     #[cfg(not(no_global_oom_handling))]
     #[inline(never)]
+    #[track_caller]
     pub fn grow_one(&mut self) {
         self.inner.grow_one(T::LAYOUT)
     }
@@ -359,6 +367,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     ///
     /// Aborts on OOM.
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     pub fn reserve_exact(&mut self, len: usize, additional: usize) {
         self.inner.reserve_exact(len, additional, T::LAYOUT)
     }
@@ -383,6 +392,7 @@ impl<T, A: Allocator> RawVec<T, A> {
     ///
     /// Aborts on OOM.
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     #[inline]
     pub fn shrink_to_fit(&mut self, cap: usize) {
         self.inner.shrink_to_fit(cap, T::LAYOUT)
@@ -408,6 +418,7 @@ impl<A: Allocator> RawVecInner<A> {
 
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     fn with_capacity_in(capacity: usize, alloc: A, elem_layout: Layout) -> Self {
         match Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc, elem_layout) {
             Ok(this) => {
@@ -432,6 +443,7 @@ impl<A: Allocator> RawVecInner<A> {
 
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     fn with_capacity_zeroed_in(capacity: usize, alloc: A, elem_layout: Layout) -> Self {
         match Self::try_allocate_in(capacity, AllocInit::Zeroed, alloc, elem_layout) {
             Ok(res) => res,
@@ -526,6 +538,7 @@ impl<A: Allocator> RawVecInner<A> {
 
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     fn reserve(&mut self, len: usize, additional: usize, elem_layout: Layout) {
         // Callers expect this function to be very cheap when there is already sufficient capacity.
         // Therefore, we move all the resizing and error-handling logic from grow_amortized and
@@ -550,6 +563,7 @@ impl<A: Allocator> RawVecInner<A> {
 
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     fn grow_one(&mut self, elem_layout: Layout) {
         if let Err(err) = self.grow_amortized(self.cap.0, 1, elem_layout) {
             handle_error(err);
@@ -573,6 +587,7 @@ impl<A: Allocator> RawVecInner<A> {
     }
 
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     fn reserve_exact(&mut self, len: usize, additional: usize, elem_layout: Layout) {
         if let Err(err) = self.try_reserve_exact(len, additional, elem_layout) {
             handle_error(err);
@@ -597,6 +612,7 @@ impl<A: Allocator> RawVecInner<A> {
 
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     fn shrink_to_fit(&mut self, cap: usize, elem_layout: Layout) {
         if let Err(err) = self.shrink(cap, elem_layout) {
             handle_error(err);
@@ -770,6 +786,7 @@ where
 #[cfg(not(no_global_oom_handling))]
 #[cold]
 #[optimize(size)]
+#[track_caller]
 fn handle_error(e: TryReserveError) -> ! {
     match e.kind() {
         CapacityOverflow => capacity_overflow(),
diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs
index 0e2c35845e8..e98ae7c31ad 100644
--- a/library/alloc/src/rc.rs
+++ b/library/alloc/src/rc.rs
@@ -282,19 +282,19 @@ mod tests;
 // would interfere with otherwise safe [into|from]_raw() of transmutable
 // inner types.
 #[repr(C)]
-struct RcBox<T: ?Sized> {
+struct RcInner<T: ?Sized> {
     strong: Cell<usize>,
     weak: Cell<usize>,
     value: T,
 }
 
-/// Calculate layout for `RcBox<T>` using the inner value's layout
-fn rcbox_layout_for_value_layout(layout: Layout) -> Layout {
+/// Calculate layout for `RcInner<T>` using the inner value's layout
+fn rc_inner_layout_for_value_layout(layout: Layout) -> Layout {
     // Calculate layout using the given value layout.
     // Previously, layout was calculated on the expression
-    // `&*(ptr as *const RcBox<T>)`, but this created a misaligned
+    // `&*(ptr as *const RcInner<T>)`, but this created a misaligned
     // reference (see #54908).
-    Layout::new::<RcBox<()>>().extend(layout).unwrap().0.pad_to_align()
+    Layout::new::<RcInner<()>>().extend(layout).unwrap().0.pad_to_align()
 }
 
 /// A single-threaded reference-counting pointer. 'Rc' stands for 'Reference
@@ -314,8 +314,8 @@ pub struct Rc<
     T: ?Sized,
     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
 > {
-    ptr: NonNull<RcBox<T>>,
-    phantom: PhantomData<RcBox<T>>,
+    ptr: NonNull<RcInner<T>>,
+    phantom: PhantomData<RcInner<T>>,
     alloc: A,
 }
 
@@ -343,37 +343,37 @@ impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Rc<U>> for Rc<T> {}
 
 impl<T: ?Sized> Rc<T> {
     #[inline]
-    unsafe fn from_inner(ptr: NonNull<RcBox<T>>) -> Self {
+    unsafe fn from_inner(ptr: NonNull<RcInner<T>>) -> Self {
         unsafe { Self::from_inner_in(ptr, Global) }
     }
 
     #[inline]
-    unsafe fn from_ptr(ptr: *mut RcBox<T>) -> Self {
+    unsafe fn from_ptr(ptr: *mut RcInner<T>) -> Self {
         unsafe { Self::from_inner(NonNull::new_unchecked(ptr)) }
     }
 }
 
 impl<T: ?Sized, A: Allocator> Rc<T, A> {
     #[inline(always)]
-    fn inner(&self) -> &RcBox<T> {
+    fn inner(&self) -> &RcInner<T> {
         // This unsafety is ok because while this Rc is alive we're guaranteed
         // that the inner pointer is valid.
         unsafe { self.ptr.as_ref() }
     }
 
     #[inline]
-    fn into_inner_with_allocator(this: Self) -> (NonNull<RcBox<T>>, A) {
+    fn into_inner_with_allocator(this: Self) -> (NonNull<RcInner<T>>, A) {
         let this = mem::ManuallyDrop::new(this);
         (this.ptr, unsafe { ptr::read(&this.alloc) })
     }
 
     #[inline]
-    unsafe fn from_inner_in(ptr: NonNull<RcBox<T>>, alloc: A) -> Self {
+    unsafe fn from_inner_in(ptr: NonNull<RcInner<T>>, alloc: A) -> Self {
         Self { ptr, phantom: PhantomData, alloc }
     }
 
     #[inline]
-    unsafe fn from_ptr_in(ptr: *mut RcBox<T>, alloc: A) -> Self {
+    unsafe fn from_ptr_in(ptr: *mut RcInner<T>, alloc: A) -> Self {
         unsafe { Self::from_inner_in(NonNull::new_unchecked(ptr), alloc) }
     }
 }
@@ -397,7 +397,7 @@ impl<T> Rc<T> {
         // if the weak pointer is stored inside the strong one.
         unsafe {
             Self::from_inner(
-                Box::leak(Box::new(RcBox { strong: Cell::new(1), weak: Cell::new(1), value }))
+                Box::leak(Box::new(RcInner { strong: Cell::new(1), weak: Cell::new(1), value }))
                     .into(),
             )
         }
@@ -546,8 +546,12 @@ impl<T> Rc<T> {
         // if the weak pointer is stored inside the strong one.
         unsafe {
             Ok(Self::from_inner(
-                Box::leak(Box::try_new(RcBox { strong: Cell::new(1), weak: Cell::new(1), value })?)
-                    .into(),
+                Box::leak(Box::try_new(RcInner {
+                    strong: Cell::new(1),
+                    weak: Cell::new(1),
+                    value,
+                })?)
+                .into(),
             ))
         }
     }
@@ -646,7 +650,7 @@ impl<T, A: Allocator> Rc<T, A> {
         // That would make code size bigger.
         match Self::try_new_in(value, alloc) {
             Ok(m) => m,
-            Err(_) => handle_alloc_error(Layout::new::<RcBox<T>>()),
+            Err(_) => handle_alloc_error(Layout::new::<RcInner<T>>()),
         }
     }
 
@@ -765,7 +769,7 @@ impl<T, A: Allocator> Rc<T, A> {
         // Construct the inner in the "uninitialized" state with a single
         // weak reference.
         let (uninit_raw_ptr, alloc) = Box::into_raw_with_allocator(Box::new_in(
-            RcBox {
+            RcInner {
                 strong: Cell::new(0),
                 weak: Cell::new(1),
                 value: mem::MaybeUninit::<T>::uninit(),
@@ -773,7 +777,7 @@ impl<T, A: Allocator> Rc<T, A> {
             alloc,
         ));
         let uninit_ptr: NonNull<_> = (unsafe { &mut *uninit_raw_ptr }).into();
-        let init_ptr: NonNull<RcBox<T>> = uninit_ptr.cast();
+        let init_ptr: NonNull<RcInner<T>> = uninit_ptr.cast();
 
         let weak = Weak { ptr: init_ptr, alloc: alloc };
 
@@ -826,7 +830,7 @@ impl<T, A: Allocator> Rc<T, A> {
         // the allocation while the strong destructor is running, even
         // if the weak pointer is stored inside the strong one.
         let (ptr, alloc) = Box::into_unique(Box::try_new_in(
-            RcBox { strong: Cell::new(1), weak: Cell::new(1), value },
+            RcInner { strong: Cell::new(1), weak: Cell::new(1), value },
             alloc,
         )?);
         Ok(unsafe { Self::from_inner_in(ptr.into(), alloc) })
@@ -1059,7 +1063,7 @@ impl<T> Rc<[T]> {
                 |layout| Global.allocate_zeroed(layout),
                 |mem| {
                     ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len)
-                        as *mut RcBox<[mem::MaybeUninit<T>]>
+                        as *mut RcInner<[mem::MaybeUninit<T>]>
                 },
             ))
         }
@@ -1132,7 +1136,7 @@ impl<T, A: Allocator> Rc<[T], A> {
                     |layout| alloc.allocate_zeroed(layout),
                     |mem| {
                         ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len)
-                            as *mut RcBox<[mem::MaybeUninit<T>]>
+                            as *mut RcInner<[mem::MaybeUninit<T>]>
                     },
                 ),
                 alloc,
@@ -1437,7 +1441,7 @@ impl<T: ?Sized, A: Allocator> Rc<T, A> {
     #[stable(feature = "weak_into_raw", since = "1.45.0")]
     #[rustc_never_returns_null_ptr]
     pub fn as_ptr(this: &Self) -> *const T {
-        let ptr: *mut RcBox<T> = NonNull::as_ptr(this.ptr);
+        let ptr: *mut RcInner<T> = NonNull::as_ptr(this.ptr);
 
         // SAFETY: This cannot go through Deref::deref or Rc::inner because
         // this is required to retain raw/mut provenance such that e.g. `get_mut` can
@@ -1516,8 +1520,8 @@ impl<T: ?Sized, A: Allocator> Rc<T, A> {
     pub unsafe fn from_raw_in(ptr: *const T, alloc: A) -> Self {
         let offset = unsafe { data_offset(ptr) };
 
-        // Reverse the offset to find the original RcBox.
-        let rc_ptr = unsafe { ptr.byte_sub(offset) as *mut RcBox<T> };
+        // Reverse the offset to find the original RcInner.
+        let rc_ptr = unsafe { ptr.byte_sub(offset) as *mut RcInner<T> };
 
         unsafe { Self::from_ptr_in(rc_ptr, alloc) }
     }
@@ -2002,43 +2006,43 @@ impl<A: Allocator> Rc<dyn Any, A> {
 }
 
 impl<T: ?Sized> Rc<T> {
-    /// Allocates an `RcBox<T>` with sufficient space for
+    /// Allocates an `RcInner<T>` with sufficient space for
     /// a possibly-unsized inner value where the value has the layout provided.
     ///
-    /// The function `mem_to_rcbox` is called with the data pointer
-    /// and must return back a (potentially fat)-pointer for the `RcBox<T>`.
+    /// The function `mem_to_rc_inner` is called with the data pointer
+    /// and must return back a (potentially fat)-pointer for the `RcInner<T>`.
     #[cfg(not(no_global_oom_handling))]
     unsafe fn allocate_for_layout(
         value_layout: Layout,
         allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocError>,
-        mem_to_rcbox: impl FnOnce(*mut u8) -> *mut RcBox<T>,
-    ) -> *mut RcBox<T> {
-        let layout = rcbox_layout_for_value_layout(value_layout);
+        mem_to_rc_inner: impl FnOnce(*mut u8) -> *mut RcInner<T>,
+    ) -> *mut RcInner<T> {
+        let layout = rc_inner_layout_for_value_layout(value_layout);
         unsafe {
-            Rc::try_allocate_for_layout(value_layout, allocate, mem_to_rcbox)
+            Rc::try_allocate_for_layout(value_layout, allocate, mem_to_rc_inner)
                 .unwrap_or_else(|_| handle_alloc_error(layout))
         }
     }
 
-    /// Allocates an `RcBox<T>` with sufficient space for
+    /// Allocates an `RcInner<T>` with sufficient space for
     /// a possibly-unsized inner value where the value has the layout provided,
     /// returning an error if allocation fails.
     ///
-    /// The function `mem_to_rcbox` is called with the data pointer
-    /// and must return back a (potentially fat)-pointer for the `RcBox<T>`.
+    /// The function `mem_to_rc_inner` is called with the data pointer
+    /// and must return back a (potentially fat)-pointer for the `RcInner<T>`.
     #[inline]
     unsafe fn try_allocate_for_layout(
         value_layout: Layout,
         allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocError>,
-        mem_to_rcbox: impl FnOnce(*mut u8) -> *mut RcBox<T>,
-    ) -> Result<*mut RcBox<T>, AllocError> {
-        let layout = rcbox_layout_for_value_layout(value_layout);
+        mem_to_rc_inner: impl FnOnce(*mut u8) -> *mut RcInner<T>,
+    ) -> Result<*mut RcInner<T>, AllocError> {
+        let layout = rc_inner_layout_for_value_layout(value_layout);
 
         // Allocate for the layout.
         let ptr = allocate(layout)?;
 
-        // Initialize the RcBox
-        let inner = mem_to_rcbox(ptr.as_non_null_ptr().as_ptr());
+        // Initialize the RcInner
+        let inner = mem_to_rc_inner(ptr.as_non_null_ptr().as_ptr());
         unsafe {
             debug_assert_eq!(Layout::for_value_raw(inner), layout);
 
@@ -2051,15 +2055,15 @@ impl<T: ?Sized> Rc<T> {
 }
 
 impl<T: ?Sized, A: Allocator> Rc<T, A> {
-    /// Allocates an `RcBox<T>` with sufficient space for an unsized inner value
+    /// Allocates an `RcInner<T>` with sufficient space for an unsized inner value
     #[cfg(not(no_global_oom_handling))]
-    unsafe fn allocate_for_ptr_in(ptr: *const T, alloc: &A) -> *mut RcBox<T> {
-        // Allocate for the `RcBox<T>` using the given value.
+    unsafe fn allocate_for_ptr_in(ptr: *const T, alloc: &A) -> *mut RcInner<T> {
+        // Allocate for the `RcInner<T>` using the given value.
         unsafe {
             Rc::<T>::allocate_for_layout(
                 Layout::for_value_raw(ptr),
                 |layout| alloc.allocate(layout),
-                |mem| mem.with_metadata_of(ptr as *const RcBox<T>),
+                |mem| mem.with_metadata_of(ptr as *const RcInner<T>),
             )
         }
     }
@@ -2088,14 +2092,14 @@ impl<T: ?Sized, A: Allocator> Rc<T, A> {
 }
 
 impl<T> Rc<[T]> {
-    /// Allocates an `RcBox<[T]>` with the given length.
+    /// Allocates an `RcInner<[T]>` with the given length.
     #[cfg(not(no_global_oom_handling))]
-    unsafe fn allocate_for_slice(len: usize) -> *mut RcBox<[T]> {
+    unsafe fn allocate_for_slice(len: usize) -> *mut RcInner<[T]> {
         unsafe {
             Self::allocate_for_layout(
                 Layout::array::<T>(len).unwrap(),
                 |layout| Global.allocate(layout),
-                |mem| ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len) as *mut RcBox<[T]>,
+                |mem| ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len) as *mut RcInner<[T]>,
             )
         }
     }
@@ -2119,7 +2123,7 @@ impl<T> Rc<[T]> {
     unsafe fn from_iter_exact(iter: impl Iterator<Item = T>, len: usize) -> Rc<[T]> {
         // Panic guard while cloning T elements.
         // In the event of a panic, elements that have been written
-        // into the new RcBox will be dropped, then the memory freed.
+        // into the new RcInner will be dropped, then the memory freed.
         struct Guard<T> {
             mem: NonNull<u8>,
             elems: *mut T,
@@ -2154,7 +2158,7 @@ impl<T> Rc<[T]> {
                 guard.n_elems += 1;
             }
 
-            // All clear. Forget the guard so it doesn't free the new RcBox.
+            // All clear. Forget the guard so it doesn't free the new RcInner.
             mem::forget(guard);
 
             Self::from_ptr(ptr)
@@ -2163,15 +2167,15 @@ impl<T> Rc<[T]> {
 }
 
 impl<T, A: Allocator> Rc<[T], A> {
-    /// Allocates an `RcBox<[T]>` with the given length.
+    /// Allocates an `RcInner<[T]>` with the given length.
     #[inline]
     #[cfg(not(no_global_oom_handling))]
-    unsafe fn allocate_for_slice_in(len: usize, alloc: &A) -> *mut RcBox<[T]> {
+    unsafe fn allocate_for_slice_in(len: usize, alloc: &A) -> *mut RcInner<[T]> {
         unsafe {
             Rc::<[T]>::allocate_for_layout(
                 Layout::array::<T>(len).unwrap(),
                 |layout| alloc.allocate(layout),
-                |mem| ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len) as *mut RcBox<[T]>,
+                |mem| ptr::slice_from_raw_parts_mut(mem.cast::<T>(), len) as *mut RcInner<[T]>,
             )
         }
     }
@@ -2901,9 +2905,9 @@ pub struct Weak<
     // but it is not necessarily a valid pointer.
     // `Weak::new` sets this to `usize::MAX` so that it doesn’t need
     // to allocate space on the heap. That's not a value a real pointer
-    // will ever have because RcBox has alignment at least 2.
+    // will ever have because RcInner has alignment at least 2.
     // This is only possible when `T: Sized`; unsized `T` never dangle.
-    ptr: NonNull<RcBox<T>>,
+    ptr: NonNull<RcInner<T>>,
     alloc: A,
 }
 
@@ -2939,7 +2943,7 @@ impl<T> Weak<T> {
     pub const fn new() -> Weak<T> {
         Weak {
             ptr: unsafe {
-                NonNull::new_unchecked(ptr::without_provenance_mut::<RcBox<T>>(usize::MAX))
+                NonNull::new_unchecked(ptr::without_provenance_mut::<RcInner<T>>(usize::MAX))
             },
             alloc: Global,
         }
@@ -2966,7 +2970,7 @@ impl<T, A: Allocator> Weak<T, A> {
     pub fn new_in(alloc: A) -> Weak<T, A> {
         Weak {
             ptr: unsafe {
-                NonNull::new_unchecked(ptr::without_provenance_mut::<RcBox<T>>(usize::MAX))
+                NonNull::new_unchecked(ptr::without_provenance_mut::<RcInner<T>>(usize::MAX))
             },
             alloc,
         }
@@ -3070,11 +3074,11 @@ impl<T: ?Sized, A: Allocator> Weak<T, A> {
     #[must_use]
     #[stable(feature = "rc_as_ptr", since = "1.45.0")]
     pub fn as_ptr(&self) -> *const T {
-        let ptr: *mut RcBox<T> = NonNull::as_ptr(self.ptr);
+        let ptr: *mut RcInner<T> = NonNull::as_ptr(self.ptr);
 
         if is_dangling(ptr) {
             // If the pointer is dangling, we return the sentinel directly. This cannot be
-            // a valid payload address, as the payload is at least as aligned as RcBox (usize).
+            // a valid payload address, as the payload is at least as aligned as RcInner (usize).
             ptr as *const T
         } else {
             // SAFETY: if is_dangling returns false, then the pointer is dereferenceable.
@@ -3206,14 +3210,14 @@ impl<T: ?Sized, A: Allocator> Weak<T, A> {
 
         let ptr = if is_dangling(ptr) {
             // This is a dangling Weak.
-            ptr as *mut RcBox<T>
+            ptr as *mut RcInner<T>
         } else {
             // Otherwise, we're guaranteed the pointer came from a nondangling Weak.
             // SAFETY: data_offset is safe to call, as ptr references a real (potentially dropped) T.
             let offset = unsafe { data_offset(ptr) };
-            // Thus, we reverse the offset to get the whole RcBox.
+            // Thus, we reverse the offset to get the whole RcInner.
             // SAFETY: the pointer originated from a Weak, so this offset is safe.
-            unsafe { ptr.byte_sub(offset) as *mut RcBox<T> }
+            unsafe { ptr.byte_sub(offset) as *mut RcInner<T> }
         };
 
         // SAFETY: we now have recovered the original Weak pointer, so can create the Weak.
@@ -3288,7 +3292,7 @@ impl<T: ?Sized, A: Allocator> Weak<T, A> {
         }
     }
 
-    /// Returns `None` when the pointer is dangling and there is no allocated `RcBox`,
+    /// Returns `None` when the pointer is dangling and there is no allocated `RcInner`,
     /// (i.e., when this `Weak` was created by `Weak::new`).
     #[inline]
     fn inner(&self) -> Option<WeakInner<'_>> {
@@ -3522,7 +3526,7 @@ trait RcInnerPtr {
     }
 }
 
-impl<T: ?Sized> RcInnerPtr for RcBox<T> {
+impl<T: ?Sized> RcInnerPtr for RcInner<T> {
     #[inline(always)]
     fn weak_ref(&self) -> &Cell<usize> {
         &self.weak
@@ -3563,15 +3567,15 @@ impl<T: ?Sized, A: Allocator> AsRef<T> for Rc<T, A> {
 #[stable(feature = "pin", since = "1.33.0")]
 impl<T: ?Sized, A: Allocator> Unpin for Rc<T, A> {}
 
-/// Gets the offset within an `RcBox` for the payload behind a pointer.
+/// Gets the offset within an `RcInner` for the payload behind a pointer.
 ///
 /// # Safety
 ///
 /// The pointer must point to (and have valid metadata for) a previously
 /// valid instance of T, but the T is allowed to be dropped.
 unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> usize {
-    // Align the unsized value to the end of the RcBox.
-    // Because RcBox is repr(C), it will always be the last field in memory.
+    // Align the unsized value to the end of the RcInner.
+    // Because RcInner is repr(C), it will always be the last field in memory.
     // SAFETY: since the only unsized types possible are slices, trait objects,
     // and extern types, the input safety requirement is currently enough to
     // satisfy the requirements of align_of_val_raw; this is an implementation
@@ -3581,7 +3585,7 @@ unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> usize {
 
 #[inline]
 fn data_offset_align(align: usize) -> usize {
-    let layout = Layout::new::<RcBox<()>>();
+    let layout = Layout::new::<RcInner<()>>();
     layout.size() + layout.padding_needed_for(align)
 }
 
@@ -3627,8 +3631,8 @@ pub struct UniqueRc<
     T: ?Sized,
     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
 > {
-    ptr: NonNull<RcBox<T>>,
-    phantom: PhantomData<RcBox<T>>,
+    ptr: NonNull<RcInner<T>>,
+    phantom: PhantomData<RcInner<T>>,
     alloc: A,
 }
 
@@ -3664,7 +3668,7 @@ impl<T, A: Allocator> UniqueRc<T, A> {
     #[unstable(feature = "unique_rc_arc", issue = "112566")]
     pub fn new_in(value: T, alloc: A) -> Self {
         let (ptr, alloc) = Box::into_unique(Box::new_in(
-            RcBox {
+            RcInner {
                 strong: Cell::new(0),
                 // keep one weak reference so if all the weak pointers that are created are dropped
                 // the UniqueRc still stays valid.
@@ -3759,7 +3763,7 @@ unsafe impl<#[may_dangle] T: ?Sized, A: Allocator> Drop for UniqueRc<T, A> {
     }
 }
 
-/// A unique owning pointer to a [`RcBox`] **that does not imply the contents are initialized,**
+/// A unique owning pointer to a [`RcInner`] **that does not imply the contents are initialized,**
 /// but will deallocate it (without dropping the value) when dropped.
 ///
 /// This is a helper for [`Rc::make_mut()`] to ensure correct cleanup on panic.
@@ -3767,21 +3771,21 @@ unsafe impl<#[may_dangle] T: ?Sized, A: Allocator> Drop for UniqueRc<T, A> {
 /// which `MaybeUninit` does not.
 #[cfg(not(no_global_oom_handling))]
 struct UniqueRcUninit<T: ?Sized, A: Allocator> {
-    ptr: NonNull<RcBox<T>>,
+    ptr: NonNull<RcInner<T>>,
     layout_for_value: Layout,
     alloc: Option<A>,
 }
 
 #[cfg(not(no_global_oom_handling))]
 impl<T: ?Sized, A: Allocator> UniqueRcUninit<T, A> {
-    /// Allocates a RcBox with layout suitable to contain `for_value` or a clone of it.
+    /// Allocates a RcInner with layout suitable to contain `for_value` or a clone of it.
     fn new(for_value: &T, alloc: A) -> UniqueRcUninit<T, A> {
         let layout = Layout::for_value(for_value);
         let ptr = unsafe {
             Rc::allocate_for_layout(
                 layout,
-                |layout_for_rcbox| alloc.allocate(layout_for_rcbox),
-                |mem| mem.with_metadata_of(ptr::from_ref(for_value) as *const RcBox<T>),
+                |layout_for_rc_inner| alloc.allocate(layout_for_rc_inner),
+                |mem| mem.with_metadata_of(ptr::from_ref(for_value) as *const RcInner<T>),
             )
         };
         Self { ptr: NonNull::new(ptr).unwrap(), layout_for_value: layout, alloc: Some(alloc) }
@@ -3816,10 +3820,10 @@ impl<T: ?Sized, A: Allocator> Drop for UniqueRcUninit<T, A> {
         // * new() produced a pointer safe to deallocate.
         // * We own the pointer unless into_rc() was called, which forgets us.
         unsafe {
-            self.alloc
-                .take()
-                .unwrap()
-                .deallocate(self.ptr.cast(), rcbox_layout_for_value_layout(self.layout_for_value));
+            self.alloc.take().unwrap().deallocate(
+                self.ptr.cast(),
+                rc_inner_layout_for_value_layout(self.layout_for_value),
+            );
         }
     }
 }
diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs
index a92d22b1c30..e3c7835f1d1 100644
--- a/library/alloc/src/slice.rs
+++ b/library/alloc/src/slice.rs
@@ -19,20 +19,6 @@ use core::cmp::Ordering::{self, Less};
 use core::mem::{self, MaybeUninit};
 #[cfg(not(no_global_oom_handling))]
 use core::ptr;
-#[cfg(not(no_global_oom_handling))]
-use core::slice::sort;
-
-use crate::alloc::Allocator;
-#[cfg(not(no_global_oom_handling))]
-use crate::alloc::Global;
-#[cfg(not(no_global_oom_handling))]
-use crate::borrow::ToOwned;
-use crate::boxed::Box;
-use crate::vec::Vec;
-
-#[cfg(test)]
-mod tests;
-
 #[unstable(feature = "array_chunks", issue = "74985")]
 pub use core::slice::ArrayChunks;
 #[unstable(feature = "array_chunks", issue = "74985")]
@@ -43,6 +29,8 @@ pub use core::slice::ArrayWindows;
 pub use core::slice::EscapeAscii;
 #[stable(feature = "slice_get_slice", since = "1.28.0")]
 pub use core::slice::SliceIndex;
+#[cfg(not(no_global_oom_handling))]
+use core::slice::sort;
 #[stable(feature = "slice_group_by", since = "1.77.0")]
 pub use core::slice::{ChunkBy, ChunkByMut};
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -83,6 +71,14 @@ pub use hack::into_vec;
 #[cfg(test)]
 pub use hack::to_vec;
 
+use crate::alloc::Allocator;
+#[cfg(not(no_global_oom_handling))]
+use crate::alloc::Global;
+#[cfg(not(no_global_oom_handling))]
+use crate::borrow::ToOwned;
+use crate::boxed::Box;
+use crate::vec::Vec;
+
 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
 // functions are actually methods that are in `impl [T]` but not in
 // `core::slice::SliceExt` - we need to supply these functions for the
diff --git a/library/alloc/src/slice/tests.rs b/library/alloc/src/slice/tests.rs
deleted file mode 100644
index 786704caeb0..00000000000
--- a/library/alloc/src/slice/tests.rs
+++ /dev/null
@@ -1,369 +0,0 @@
-use core::cell::Cell;
-use core::cmp::Ordering::{self, Equal, Greater, Less};
-use core::convert::identity;
-use core::sync::atomic::AtomicUsize;
-use core::sync::atomic::Ordering::Relaxed;
-use core::{fmt, mem};
-use std::panic;
-
-use rand::distributions::Standard;
-use rand::prelude::*;
-use rand::{Rng, RngCore};
-
-use crate::borrow::ToOwned;
-use crate::rc::Rc;
-use crate::string::ToString;
-use crate::test_helpers::test_rng;
-use crate::vec::Vec;
-
-macro_rules! do_test {
-    ($input:ident, $func:ident) => {
-        let len = $input.len();
-
-        // Work out the total number of comparisons required to sort
-        // this array...
-        let mut count = 0usize;
-        $input.to_owned().$func(|a, b| {
-            count += 1;
-            a.cmp(b)
-        });
-
-        // ... and then panic on each and every single one.
-        for panic_countdown in 0..count {
-            // Refresh the counters.
-            VERSIONS.store(0, Relaxed);
-            for i in 0..len {
-                DROP_COUNTS[i].store(0, Relaxed);
-            }
-
-            let v = $input.to_owned();
-            let _ = panic::catch_unwind(move || {
-                let mut v = v;
-                let mut panic_countdown = panic_countdown;
-                v.$func(|a, b| {
-                    if panic_countdown == 0 {
-                        SILENCE_PANIC.with(|s| s.set(true));
-                        panic!();
-                    }
-                    panic_countdown -= 1;
-                    a.cmp(b)
-                })
-            });
-
-            // Check that the number of things dropped is exactly
-            // what we expect (i.e., the contents of `v`).
-            for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
-                let count = c.load(Relaxed);
-                assert!(count == 1, "found drop count == {} for i == {}, len == {}", count, i, len);
-            }
-
-            // Check that the most recent versions of values were dropped.
-            assert_eq!(VERSIONS.load(Relaxed), 0);
-        }
-    };
-}
-
-const MAX_LEN: usize = 80;
-
-static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [
-    // FIXME(RFC 1109): AtomicUsize is not Copy.
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-    AtomicUsize::new(0),
-];
-
-static VERSIONS: AtomicUsize = AtomicUsize::new(0);
-
-#[derive(Clone, Eq)]
-struct DropCounter {
-    x: u32,
-    id: usize,
-    version: Cell<usize>,
-}
-
-impl PartialEq for DropCounter {
-    fn eq(&self, other: &Self) -> bool {
-        self.partial_cmp(other) == Some(Ordering::Equal)
-    }
-}
-
-impl PartialOrd for DropCounter {
-    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-        self.version.set(self.version.get() + 1);
-        other.version.set(other.version.get() + 1);
-        VERSIONS.fetch_add(2, Relaxed);
-        self.x.partial_cmp(&other.x)
-    }
-}
-
-impl Ord for DropCounter {
-    fn cmp(&self, other: &Self) -> Ordering {
-        self.partial_cmp(other).unwrap()
-    }
-}
-
-impl Drop for DropCounter {
-    fn drop(&mut self) {
-        DROP_COUNTS[self.id].fetch_add(1, Relaxed);
-        VERSIONS.fetch_sub(self.version.get(), Relaxed);
-    }
-}
-
-std::thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false));
-
-#[test]
-#[cfg_attr(target_os = "emscripten", ignore)] // no threads
-#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
-fn panic_safe() {
-    panic::update_hook(move |prev, info| {
-        if !SILENCE_PANIC.with(|s| s.get()) {
-            prev(info);
-        }
-    });
-
-    let mut rng = test_rng();
-
-    // Miri is too slow (but still need to `chain` to make the types match)
-    let lens = if cfg!(miri) { (1..10).chain(0..0) } else { (1..20).chain(70..MAX_LEN) };
-    let moduli: &[u32] = if cfg!(miri) { &[5] } else { &[5, 20, 50] };
-
-    for len in lens {
-        for &modulus in moduli {
-            for &has_runs in &[false, true] {
-                let mut input = (0..len)
-                    .map(|id| DropCounter {
-                        x: rng.next_u32() % modulus,
-                        id: id,
-                        version: Cell::new(0),
-                    })
-                    .collect::<Vec<_>>();
-
-                if has_runs {
-                    for c in &mut input {
-                        c.x = c.id as u32;
-                    }
-
-                    for _ in 0..5 {
-                        let a = rng.gen::<usize>() % len;
-                        let b = rng.gen::<usize>() % len;
-                        if a < b {
-                            input[a..b].reverse();
-                        } else {
-                            input.swap(a, b);
-                        }
-                    }
-                }
-
-                do_test!(input, sort_by);
-                do_test!(input, sort_unstable_by);
-            }
-        }
-    }
-
-    // Set default panic hook again.
-    drop(panic::take_hook());
-}
-
-#[test]
-#[cfg_attr(miri, ignore)] // Miri is too slow
-#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
-fn test_sort() {
-    let mut rng = test_rng();
-
-    for len in (2..25).chain(500..510) {
-        for &modulus in &[5, 10, 100, 1000] {
-            for _ in 0..10 {
-                let orig: Vec<_> = (&mut rng)
-                    .sample_iter::<i32, _>(&Standard)
-                    .map(|x| x % modulus)
-                    .take(len)
-                    .collect();
-
-                // Sort in default order.
-                let mut v = orig.clone();
-                v.sort();
-                assert!(v.windows(2).all(|w| w[0] <= w[1]));
-
-                // Sort in ascending order.
-                let mut v = orig.clone();
-                v.sort_by(|a, b| a.cmp(b));
-                assert!(v.windows(2).all(|w| w[0] <= w[1]));
-
-                // Sort in descending order.
-                let mut v = orig.clone();
-                v.sort_by(|a, b| b.cmp(a));
-                assert!(v.windows(2).all(|w| w[0] >= w[1]));
-
-                // Sort in lexicographic order.
-                let mut v1 = orig.clone();
-                let mut v2 = orig.clone();
-                v1.sort_by_key(|x| x.to_string());
-                v2.sort_by_cached_key(|x| x.to_string());
-                assert!(v1.windows(2).all(|w| w[0].to_string() <= w[1].to_string()));
-                assert!(v1 == v2);
-
-                // Sort with many pre-sorted runs.
-                let mut v = orig.clone();
-                v.sort();
-                v.reverse();
-                for _ in 0..5 {
-                    let a = rng.gen::<usize>() % len;
-                    let b = rng.gen::<usize>() % len;
-                    if a < b {
-                        v[a..b].reverse();
-                    } else {
-                        v.swap(a, b);
-                    }
-                }
-                v.sort();
-                assert!(v.windows(2).all(|w| w[0] <= w[1]));
-            }
-        }
-    }
-
-    const ORD_VIOLATION_MAX_LEN: usize = 500;
-    let mut v = [0; ORD_VIOLATION_MAX_LEN];
-    for i in 0..ORD_VIOLATION_MAX_LEN {
-        v[i] = i as i32;
-    }
-
-    // Sort using a completely random comparison function. This will reorder the elements *somehow*,
-    // it may panic but the original elements must still be present.
-    let _ = panic::catch_unwind(move || {
-        v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
-    });
-
-    v.sort();
-    for i in 0..ORD_VIOLATION_MAX_LEN {
-        assert_eq!(v[i], i as i32);
-    }
-
-    // Should not panic.
-    [0i32; 0].sort();
-    [(); 10].sort();
-    [(); 100].sort();
-
-    let mut v = [0xDEADBEEFu64];
-    v.sort();
-    assert!(v == [0xDEADBEEF]);
-}
-
-#[test]
-fn test_sort_stability() {
-    // Miri is too slow
-    let large_range = if cfg!(miri) { 0..0 } else { 500..510 };
-    let rounds = if cfg!(miri) { 1 } else { 10 };
-
-    let mut rng = test_rng();
-    for len in (2..25).chain(large_range) {
-        for _ in 0..rounds {
-            let mut counts = [0; 10];
-
-            // create a vector like [(6, 1), (5, 1), (6, 2), ...],
-            // where the first item of each tuple is random, but
-            // the second item represents which occurrence of that
-            // number this element is, i.e., the second elements
-            // will occur in sorted order.
-            let orig: Vec<_> = (0..len)
-                .map(|_| {
-                    let n = rng.gen::<usize>() % 10;
-                    counts[n] += 1;
-                    (n, counts[n])
-                })
-                .collect();
-
-            let mut v = orig.clone();
-            // Only sort on the first element, so an unstable sort
-            // may mix up the counts.
-            v.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
-
-            // This comparison includes the count (the second item
-            // of the tuple), so elements with equal first items
-            // will need to be ordered with increasing
-            // counts... i.e., exactly asserting that this sort is
-            // stable.
-            assert!(v.windows(2).all(|w| w[0] <= w[1]));
-
-            let mut v = orig.clone();
-            v.sort_by_cached_key(|&(x, _)| x);
-            assert!(v.windows(2).all(|w| w[0] <= w[1]));
-        }
-    }
-}
diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs
index 5d099a49854..acbc325a514 100644
--- a/library/alloc/src/sync.rs
+++ b/library/alloc/src/sync.rs
@@ -319,7 +319,7 @@ pub struct Weak<
     // but it is not necessarily a valid pointer.
     // `Weak::new` sets this to `usize::MAX` so that it doesn’t need
     // to allocate space on the heap. That's not a value a real pointer
-    // will ever have because RcBox has alignment at least 2.
+    // will ever have because RcInner has alignment at least 2.
     // This is only possible when `T: Sized`; unsized `T` never dangle.
     ptr: NonNull<ArcInner<T>>,
     alloc: A,
@@ -1581,7 +1581,7 @@ impl<T: ?Sized, A: Allocator> Arc<T, A> {
     pub fn as_ptr(this: &Self) -> *const T {
         let ptr: *mut ArcInner<T> = NonNull::as_ptr(this.ptr);
 
-        // SAFETY: This cannot go through Deref::deref or RcBoxPtr::inner because
+        // SAFETY: This cannot go through Deref::deref or RcInnerPtr::inner because
         // this is required to retain raw/mut provenance such that e.g. `get_mut` can
         // write through the pointer after the Rc is recovered through `from_raw`.
         unsafe { &raw mut (*ptr).data }
@@ -2936,7 +2936,7 @@ impl<T: ?Sized, A: Allocator> Weak<T, A> {
             // Otherwise, we're guaranteed the pointer came from a nondangling Weak.
             // SAFETY: data_offset is safe to call, as ptr references a real (potentially dropped) T.
             let offset = unsafe { data_offset(ptr) };
-            // Thus, we reverse the offset to get the whole RcBox.
+            // Thus, we reverse the offset to get the whole RcInner.
             // SAFETY: the pointer originated from a Weak, so this offset is safe.
             unsafe { ptr.byte_sub(offset) as *mut ArcInner<T> }
         };
@@ -3447,7 +3447,13 @@ impl<T: Default> Default for Arc<T> {
     /// assert_eq!(*x, 0);
     /// ```
     fn default() -> Arc<T> {
-        Arc::new(Default::default())
+        let x = Box::into_raw(Box::write(Box::new_uninit(), ArcInner {
+            strong: atomic::AtomicUsize::new(1),
+            weak: atomic::AtomicUsize::new(1),
+            data: T::default(),
+        }));
+        // SAFETY: `Box::into_raw` consumes the `Box` and never returns null
+        unsafe { Self::from_inner(NonNull::new_unchecked(x)) }
     }
 }
 
@@ -3861,7 +3867,7 @@ impl<T: ?Sized, A: Allocator> Unpin for Arc<T, A> {}
 /// valid instance of T, but the T is allowed to be dropped.
 unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> usize {
     // Align the unsized value to the end of the ArcInner.
-    // Because RcBox is repr(C), it will always be the last field in memory.
+    // Because RcInner is repr(C), it will always be the last field in memory.
     // SAFETY: since the only unsized types possible are slices, trait objects,
     // and extern types, the input safety requirement is currently enough to
     // satisfy the requirements of align_of_val_raw; this is an implementation
diff --git a/library/alloc/src/vec/cow.rs b/library/alloc/src/vec/cow.rs
index c18091705a6..4deb35efffc 100644
--- a/library/alloc/src/vec/cow.rs
+++ b/library/alloc/src/vec/cow.rs
@@ -58,6 +58,7 @@ impl<'a, T> FromIterator<T> for Cow<'a, [T]>
 where
     T: Clone,
 {
+    #[track_caller]
     fn from_iter<I: IntoIterator<Item = T>>(it: I) -> Cow<'a, [T]> {
         Cow::Owned(FromIterator::from_iter(it))
     }
diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs
index fd94bbbdeb1..a7dba16944e 100644
--- a/library/alloc/src/vec/in_place_collect.rs
+++ b/library/alloc/src/vec/in_place_collect.rs
@@ -229,6 +229,7 @@ where
     I: Iterator<Item = T> + InPlaceCollect,
     <I as SourceIter>::Source: AsVecIntoIter,
 {
+    #[track_caller]
     default fn from_iter(iterator: I) -> Self {
         // Select the implementation in const eval to avoid codegen of the dead branch to improve compile times.
         let fun: fn(I) -> Vec<T> = const {
@@ -246,6 +247,7 @@ where
     }
 }
 
+#[track_caller]
 fn from_iter_in_place<I, T>(mut iterator: I) -> Vec<T>
 where
     I: Iterator<Item = T> + InPlaceCollect,
diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs
index 830512ceee8..07a1bd49321 100644
--- a/library/alloc/src/vec/mod.rs
+++ b/library/alloc/src/vec/mod.rs
@@ -478,6 +478,7 @@ impl<T> Vec<T> {
     #[stable(feature = "rust1", since = "1.0.0")]
     #[must_use]
     #[cfg_attr(not(test), rustc_diagnostic_item = "vec_with_capacity")]
+    #[track_caller]
     pub fn with_capacity(capacity: usize) -> Self {
         Self::with_capacity_in(capacity, Global)
     }
@@ -797,6 +798,7 @@ impl<T, A: Allocator> Vec<T, A> {
     #[cfg(not(no_global_oom_handling))]
     #[inline]
     #[unstable(feature = "allocator_api", issue = "32838")]
+    #[track_caller]
     pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
         Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 }
     }
@@ -1264,6 +1266,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn reserve(&mut self, additional: usize) {
         self.buf.reserve(self.len, additional);
     }
@@ -1294,6 +1297,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn reserve_exact(&mut self, additional: usize) {
         self.buf.reserve_exact(self.len, additional);
     }
@@ -1397,6 +1401,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     #[inline]
     pub fn shrink_to_fit(&mut self) {
         // The capacity is never less than the length, and there's nothing to do when
@@ -1427,6 +1432,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "shrink_to", since = "1.56.0")]
+    #[track_caller]
     pub fn shrink_to(&mut self, min_capacity: usize) {
         if self.capacity() > min_capacity {
             self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
@@ -1460,6 +1466,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn into_boxed_slice(mut self) -> Box<[T], A> {
         unsafe {
             self.shrink_to_fit();
@@ -1958,6 +1965,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// the insertion index is 0.
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[track_caller]
     pub fn insert(&mut self, index: usize, element: T) {
         #[cold]
         #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
@@ -2397,6 +2405,7 @@ impl<T, A: Allocator> Vec<T, A> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     #[rustc_confusables("push_back", "put", "append")]
+    #[track_caller]
     pub fn push(&mut self, value: T) {
         // Inform codegen that the length does not change across grow_one().
         let len = self.len;
@@ -2538,6 +2547,7 @@ impl<T, A: Allocator> Vec<T, A> {
     #[cfg(not(no_global_oom_handling))]
     #[inline]
     #[stable(feature = "append", since = "1.4.0")]
+    #[track_caller]
     pub fn append(&mut self, other: &mut Self) {
         unsafe {
             self.append_elements(other.as_slice() as _);
@@ -2548,6 +2558,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// Appends elements to `self` from other buffer.
     #[cfg(not(no_global_oom_handling))]
     #[inline]
+    #[track_caller]
     unsafe fn append_elements(&mut self, other: *const [T]) {
         let count = unsafe { (*other).len() };
         self.reserve(count);
@@ -2711,6 +2722,7 @@ impl<T, A: Allocator> Vec<T, A> {
     #[inline]
     #[must_use = "use `.truncate()` if you don't need the other half"]
     #[stable(feature = "split_off", since = "1.4.0")]
+    #[track_caller]
     pub fn split_off(&mut self, at: usize) -> Self
     where
         A: Clone,
@@ -2768,6 +2780,7 @@ impl<T, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "vec_resize_with", since = "1.33.0")]
+    #[track_caller]
     pub fn resize_with<F>(&mut self, new_len: usize, f: F)
     where
         F: FnMut() -> T,
@@ -2973,6 +2986,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "vec_resize", since = "1.5.0")]
+    #[track_caller]
     pub fn resize(&mut self, new_len: usize, value: T) {
         let len = self.len();
 
@@ -3004,6 +3018,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
     /// [`extend`]: Vec::extend
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
+    #[track_caller]
     pub fn extend_from_slice(&mut self, other: &[T]) {
         self.spec_extend(other.iter())
     }
@@ -3031,6 +3046,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
     /// ```
     #[cfg(not(no_global_oom_handling))]
     #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
+    #[track_caller]
     pub fn extend_from_within<R>(&mut self, src: R)
     where
         R: RangeBounds<usize>,
@@ -3091,6 +3107,7 @@ impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
 
 impl<T: Clone, A: Allocator> Vec<T, A> {
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     /// Extend the vector by `n` clones of value.
     fn extend_with(&mut self, n: usize, value: T) {
         self.reserve(n);
@@ -3151,6 +3168,7 @@ impl<T: PartialEq, A: Allocator> Vec<T, A> {
 #[cfg(not(no_global_oom_handling))]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[cfg_attr(not(test), rustc_diagnostic_item = "vec_from_elem")]
+#[track_caller]
 pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
     <T as SpecFromElem>::from_elem(elem, n, Global)
 }
@@ -3158,6 +3176,7 @@ pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
 #[doc(hidden)]
 #[cfg(not(no_global_oom_handling))]
 #[unstable(feature = "allocator_api", issue = "32838")]
+#[track_caller]
 pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
     <T as SpecFromElem>::from_elem(elem, n, alloc)
 }
@@ -3249,6 +3268,7 @@ unsafe impl<T, A: Allocator> ops::DerefPure for Vec<T, A> {}
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
     #[cfg(not(test))]
+    #[track_caller]
     fn clone(&self) -> Self {
         let alloc = self.allocator().clone();
         <[T]>::to_vec_in(&**self, alloc)
@@ -3286,6 +3306,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
     /// // And no reallocation occurred
     /// assert_eq!(yp, y.as_ptr());
     /// ```
+    #[track_caller]
     fn clone_from(&mut self, source: &Self) {
         crate::slice::SpecCloneIntoVec::clone_into(source.as_slice(), self);
     }
@@ -3384,6 +3405,7 @@ impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> FromIterator<T> for Vec<T> {
     #[inline]
+    #[track_caller]
     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
         <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
     }
@@ -3452,16 +3474,19 @@ impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator> Extend<T> for Vec<T, A> {
     #[inline]
+    #[track_caller]
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
     }
 
     #[inline]
+    #[track_caller]
     fn extend_one(&mut self, item: T) {
         self.push(item);
     }
 
     #[inline]
+    #[track_caller]
     fn extend_reserve(&mut self, additional: usize) {
         self.reserve(additional);
     }
@@ -3481,6 +3506,7 @@ impl<T, A: Allocator> Vec<T, A> {
     // leaf method to which various SpecFrom/SpecExtend implementations delegate when
     // they have no further optimizations to apply
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
         // This is the case for a general iterator.
         //
@@ -3508,6 +3534,7 @@ impl<T, A: Allocator> Vec<T, A> {
     // specific extend for `TrustedLen` iterators, called both by the specializations
     // and internal places where resolving specialization makes compilation slower
     #[cfg(not(no_global_oom_handling))]
+    #[track_caller]
     fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
         let (low, high) = iterator.size_hint();
         if let Some(additional) = high {
@@ -3658,16 +3685,19 @@ impl<T, A: Allocator> Vec<T, A> {
 #[cfg(not(no_global_oom_handling))]
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
+    #[track_caller]
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
         self.spec_extend(iter.into_iter())
     }
 
     #[inline]
+    #[track_caller]
     fn extend_one(&mut self, &item: &'a T) {
         self.push(item);
     }
 
     #[inline]
+    #[track_caller]
     fn extend_reserve(&mut self, additional: usize) {
         self.reserve(additional);
     }
@@ -3778,6 +3808,7 @@ impl<T: Clone> From<&[T]> for Vec<T> {
     /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
     /// ```
     #[cfg(not(test))]
+    #[track_caller]
     fn from(s: &[T]) -> Vec<T> {
         s.to_vec()
     }
@@ -3798,6 +3829,7 @@ impl<T: Clone> From<&mut [T]> for Vec<T> {
     /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
     /// ```
     #[cfg(not(test))]
+    #[track_caller]
     fn from(s: &mut [T]) -> Vec<T> {
         s.to_vec()
     }
@@ -3817,6 +3849,7 @@ impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> {
     /// ```
     /// assert_eq!(Vec::from(&[1, 2, 3]), vec![1, 2, 3]);
     /// ```
+    #[track_caller]
     fn from(s: &[T; N]) -> Vec<T> {
         Self::from(s.as_slice())
     }
@@ -3832,6 +3865,7 @@ impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> {
     /// ```
     /// assert_eq!(Vec::from(&mut [1, 2, 3]), vec![1, 2, 3]);
     /// ```
+    #[track_caller]
     fn from(s: &mut [T; N]) -> Vec<T> {
         Self::from(s.as_mut_slice())
     }
@@ -3848,6 +3882,7 @@ impl<T, const N: usize> From<[T; N]> for Vec<T> {
     /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
     /// ```
     #[cfg(not(test))]
+    #[track_caller]
     fn from(s: [T; N]) -> Vec<T> {
         <[T]>::into_vec(Box::new(s))
     }
@@ -3877,6 +3912,7 @@ where
     /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]);
     /// assert_eq!(Vec::from(o), Vec::from(b));
     /// ```
+    #[track_caller]
     fn from(s: Cow<'a, [T]>) -> Vec<T> {
         s.into_owned()
     }
@@ -3925,6 +3961,7 @@ impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
     ///
     /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
     /// ```
+    #[track_caller]
     fn from(v: Vec<T, A>) -> Self {
         v.into_boxed_slice()
     }
@@ -3940,6 +3977,7 @@ impl From<&str> for Vec<u8> {
     /// ```
     /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
     /// ```
+    #[track_caller]
     fn from(s: &str) -> Vec<u8> {
         From::from(s.as_bytes())
     }
diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs
index 7085bceef5b..b98db669059 100644
--- a/library/alloc/src/vec/spec_extend.rs
+++ b/library/alloc/src/vec/spec_extend.rs
@@ -6,6 +6,7 @@ use crate::alloc::Allocator;
 
 // Specialization trait used for Vec::extend
 pub(super) trait SpecExtend<T, I> {
+    #[track_caller]
     fn spec_extend(&mut self, iter: I);
 }
 
@@ -13,6 +14,7 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
 where
     I: Iterator<Item = T>,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, iter: I) {
         self.extend_desugared(iter)
     }
@@ -22,12 +24,14 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
 where
     I: TrustedLen<Item = T>,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, iterator: I) {
         self.extend_trusted(iterator)
     }
 }
 
 impl<T, A: Allocator> SpecExtend<T, IntoIter<T>> for Vec<T, A> {
+    #[track_caller]
     fn spec_extend(&mut self, mut iterator: IntoIter<T>) {
         unsafe {
             self.append_elements(iterator.as_slice() as _);
@@ -41,6 +45,7 @@ where
     I: Iterator<Item = &'a T>,
     T: Clone,
 {
+    #[track_caller]
     default fn spec_extend(&mut self, iterator: I) {
         self.spec_extend(iterator.cloned())
     }
@@ -50,6 +55,7 @@ impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T, A
 where
     T: Copy,
 {
+    #[track_caller]
     fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
         let slice = iterator.as_slice();
         unsafe { self.append_elements(slice) };
diff --git a/library/alloc/src/vec/spec_from_elem.rs b/library/alloc/src/vec/spec_from_elem.rs
index 96d701e15d4..6c7b4d89f2d 100644
--- a/library/alloc/src/vec/spec_from_elem.rs
+++ b/library/alloc/src/vec/spec_from_elem.rs
@@ -10,6 +10,7 @@ pub(super) trait SpecFromElem: Sized {
 }
 
 impl<T: Clone> SpecFromElem for T {
+    #[track_caller]
     default fn from_elem<A: Allocator>(elem: Self, n: usize, alloc: A) -> Vec<Self, A> {
         let mut v = Vec::with_capacity_in(n, alloc);
         v.extend_with(n, elem);
@@ -19,6 +20,7 @@ impl<T: Clone> SpecFromElem for T {
 
 impl<T: Clone + IsZero> SpecFromElem for T {
     #[inline]
+    #[track_caller]
     default fn from_elem<A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
         if elem.is_zero() {
             return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n };
@@ -31,6 +33,7 @@ impl<T: Clone + IsZero> SpecFromElem for T {
 
 impl SpecFromElem for i8 {
     #[inline]
+    #[track_caller]
     fn from_elem<A: Allocator>(elem: i8, n: usize, alloc: A) -> Vec<i8, A> {
         if elem == 0 {
             return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n };
@@ -46,6 +49,7 @@ impl SpecFromElem for i8 {
 
 impl SpecFromElem for u8 {
     #[inline]
+    #[track_caller]
     fn from_elem<A: Allocator>(elem: u8, n: usize, alloc: A) -> Vec<u8, A> {
         if elem == 0 {
             return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n };
diff --git a/library/alloc/src/vec/spec_from_iter.rs b/library/alloc/src/vec/spec_from_iter.rs
index e1f0b639bdf..ad7688e1c59 100644
--- a/library/alloc/src/vec/spec_from_iter.rs
+++ b/library/alloc/src/vec/spec_from_iter.rs
@@ -29,12 +29,14 @@ impl<T, I> SpecFromIter<T, I> for Vec<T>
 where
     I: Iterator<Item = T>,
 {
+    #[track_caller]
     default fn from_iter(iterator: I) -> Self {
         SpecFromIterNested::from_iter(iterator)
     }
 }
 
 impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> {
+    #[track_caller]
     fn from_iter(iterator: IntoIter<T>) -> Self {
         // A common case is passing a vector into a function which immediately
         // re-collects into a vector. We can short circuit this if the IntoIter
diff --git a/library/alloc/src/vec/spec_from_iter_nested.rs b/library/alloc/src/vec/spec_from_iter_nested.rs
index 77f7761d22f..22eed238798 100644
--- a/library/alloc/src/vec/spec_from_iter_nested.rs
+++ b/library/alloc/src/vec/spec_from_iter_nested.rs
@@ -15,6 +15,7 @@ impl<T, I> SpecFromIterNested<T, I> for Vec<T>
 where
     I: Iterator<Item = T>,
 {
+    #[track_caller]
     default fn from_iter(mut iterator: I) -> Self {
         // Unroll the first iteration, as the vector is going to be
         // expanded on this iteration in every case when the iterable is not
@@ -47,6 +48,7 @@ impl<T, I> SpecFromIterNested<T, I> for Vec<T>
 where
     I: TrustedLen<Item = T>,
 {
+    #[track_caller]
     fn from_iter(iterator: I) -> Self {
         let mut vector = match iterator.size_hint() {
             (_, Some(upper)) => Vec::with_capacity(upper),
diff --git a/library/alloc/src/vec/splice.rs b/library/alloc/src/vec/splice.rs
index 9e36377c148..ca5cb17f8bf 100644
--- a/library/alloc/src/vec/splice.rs
+++ b/library/alloc/src/vec/splice.rs
@@ -52,6 +52,7 @@ impl<I: Iterator, A: Allocator> ExactSizeIterator for Splice<'_, I, A> {}
 
 #[stable(feature = "vec_splice", since = "1.21.0")]
 impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> {
+    #[track_caller]
     fn drop(&mut self) {
         self.drain.by_ref().for_each(drop);
         // At this point draining is done and the only remaining tasks are splicing
@@ -123,6 +124,7 @@ impl<T, A: Allocator> Drain<'_, T, A> {
     }
 
     /// Makes room for inserting more elements before the tail.
+    #[track_caller]
     unsafe fn move_tail(&mut self, additional: usize) {
         let vec = unsafe { self.vec.as_mut() };
         let len = self.tail_start + self.tail_len;
diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs
index 58d39416d95..301126b5d4d 100644
--- a/library/alloc/tests/lib.rs
+++ b/library/alloc/tests/lib.rs
@@ -4,10 +4,7 @@
 #![feature(assert_matches)]
 #![feature(btree_extract_if)]
 #![feature(cow_is_borrowed)]
-#![feature(const_cow_is_borrowed)]
 #![feature(const_heap)]
-#![cfg_attr(bootstrap, feature(const_mut_refs))]
-#![feature(const_ptr_write)]
 #![feature(const_try)]
 #![feature(core_intrinsics)]
 #![feature(extract_if)]
@@ -40,6 +37,7 @@
 #![feature(local_waker)]
 #![feature(vec_pop_if)]
 #![feature(unique_rc_arc)]
+#![feature(macro_metavar_expr_concat)]
 #![allow(internal_features)]
 #![deny(fuzzy_provenance_casts)]
 #![deny(unsafe_op_in_unsafe_fn)]
@@ -59,6 +57,7 @@ mod heap;
 mod linked_list;
 mod rc;
 mod slice;
+mod sort;
 mod str;
 mod string;
 mod task;
diff --git a/library/alloc/tests/sort/ffi_types.rs b/library/alloc/tests/sort/ffi_types.rs
new file mode 100644
index 00000000000..11515ea4769
--- /dev/null
+++ b/library/alloc/tests/sort/ffi_types.rs
@@ -0,0 +1,82 @@
+use std::cmp::Ordering;
+
+// Very large stack value.
+#[repr(C)]
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct FFIOneKibiByte {
+    values: [i64; 128],
+}
+
+impl FFIOneKibiByte {
+    pub fn new(val: i32) -> Self {
+        let mut values = [0i64; 128];
+        let mut val_i64 = val as i64;
+
+        for elem in &mut values {
+            *elem = val_i64;
+            val_i64 = std::hint::black_box(val_i64 + 1);
+        }
+        Self { values }
+    }
+
+    fn as_i64(&self) -> i64 {
+        self.values[11] + self.values[55] + self.values[77]
+    }
+}
+
+impl PartialOrd for FFIOneKibiByte {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for FFIOneKibiByte {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.as_i64().cmp(&other.as_i64())
+    }
+}
+
+// 16 byte stack value, with more expensive comparison.
+#[repr(C)]
+#[derive(PartialEq, Debug, Clone, Copy)]
+pub struct F128 {
+    x: f64,
+    y: f64,
+}
+
+impl F128 {
+    pub fn new(val: i32) -> Self {
+        let val_f = (val as f64) + (i32::MAX as f64) + 10.0;
+
+        let x = val_f + 0.1;
+        let y = val_f.log(4.1);
+
+        assert!(y < x);
+        assert!(x.is_normal() && y.is_normal());
+
+        Self { x, y }
+    }
+}
+
+// This is kind of hacky, but we know we only have normal comparable floats in there.
+impl Eq for F128 {}
+
+impl PartialOrd for F128 {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+// Goal is similar code-gen between Rust and C++
+// - Rust https://godbolt.org/z/3YM3xenPP
+// - C++ https://godbolt.org/z/178M6j1zz
+impl Ord for F128 {
+    fn cmp(&self, other: &Self) -> Ordering {
+        // Simulate expensive comparison function.
+        let this_div = self.x / self.y;
+        let other_div = other.x / other.y;
+
+        // SAFETY: We checked in the ctor that both are normal.
+        unsafe { this_div.partial_cmp(&other_div).unwrap_unchecked() }
+    }
+}
diff --git a/library/alloc/tests/sort/known_good_stable_sort.rs b/library/alloc/tests/sort/known_good_stable_sort.rs
new file mode 100644
index 00000000000..f8615435fc2
--- /dev/null
+++ b/library/alloc/tests/sort/known_good_stable_sort.rs
@@ -0,0 +1,192 @@
+// This module implements a known good stable sort implementation that helps provide better error
+// messages when the correctness tests fail, we can't use the stdlib sort functions because we are
+// testing them for correctness.
+//
+// Based on https://github.com/voultapher/tiny-sort-rs.
+
+use alloc::alloc::{Layout, alloc, dealloc};
+use std::{mem, ptr};
+
+/// Sort `v` preserving initial order of equal elements.
+///
+/// - Guaranteed O(N * log(N)) worst case perf
+/// - No adaptiveness
+/// - Branch miss-prediction not affected by outcome of comparison function
+/// - Uses `v.len()` auxiliary memory.
+///
+/// If `T: Ord` does not implement a total order the resulting order is
+/// unspecified. All original elements will remain in `v` and any possible modifications via
+/// interior mutability will be observable. Same is true if `T: Ord` panics.
+///
+/// Panics if allocating the auxiliary memory fails.
+#[inline(always)]
+pub fn sort<T: Ord>(v: &mut [T]) {
+    stable_sort(v, |a, b| a.lt(b))
+}
+
+#[inline(always)]
+fn stable_sort<T, F: FnMut(&T, &T) -> bool>(v: &mut [T], mut is_less: F) {
+    if mem::size_of::<T>() == 0 {
+        return;
+    }
+
+    let len = v.len();
+
+    // Inline the check for len < 2. This happens a lot, instrumenting the Rust compiler suggests
+    // len < 2 accounts for 94% of its calls to `slice::sort`.
+    if len < 2 {
+        return;
+    }
+
+    // SAFETY: We checked that len is > 0 and that T is not a ZST.
+    unsafe {
+        mergesort_main(v, &mut is_less);
+    }
+}
+
+/// The core logic should not be inlined.
+///
+/// SAFETY: The caller has to ensure that len is > 0 and that T is not a ZST.
+#[inline(never)]
+unsafe fn mergesort_main<T, F: FnMut(&T, &T) -> bool>(v: &mut [T], is_less: &mut F) {
+    // While it would be nice to have a merge implementation that only requires N / 2 auxiliary
+    // memory. Doing so would make the merge implementation significantly more complex and
+
+    // SAFETY: See function safety description.
+    let buf = unsafe { BufGuard::new(v.len()) };
+
+    // SAFETY: `scratch` has space for `v.len()` writes. And does not alias `v`.
+    unsafe {
+        mergesort_core(v, buf.buf_ptr.as_ptr(), is_less);
+    }
+}
+
+/// Tiny recursive top-down merge sort optimized for binary size. It has no adaptiveness whatsoever,
+/// no run detection, etc.
+///
+/// Buffer as pointed to by `scratch` must have space for `v.len()` writes. And must not alias `v`.
+#[inline(always)]
+unsafe fn mergesort_core<T, F: FnMut(&T, &T) -> bool>(
+    v: &mut [T],
+    scratch_ptr: *mut T,
+    is_less: &mut F,
+) {
+    let len = v.len();
+
+    if len > 2 {
+        // SAFETY: `mid` is guaranteed in-bounds. And caller has to ensure that `scratch_ptr` can
+        // hold `v.len()` values.
+        unsafe {
+            let mid = len / 2;
+            // Sort the left half recursively.
+            mergesort_core(v.get_unchecked_mut(..mid), scratch_ptr, is_less);
+            // Sort the right half recursively.
+            mergesort_core(v.get_unchecked_mut(mid..), scratch_ptr, is_less);
+            // Combine the two halves.
+            merge(v, scratch_ptr, is_less, mid);
+        }
+    } else if len == 2 {
+        if is_less(&v[1], &v[0]) {
+            v.swap(0, 1);
+        }
+    }
+}
+
+/// Branchless merge function.
+///
+/// SAFETY: The caller must ensure that `scratch_ptr` is valid for `v.len()` writes. And that mid is
+/// in-bounds.
+#[inline(always)]
+unsafe fn merge<T, F>(v: &mut [T], scratch_ptr: *mut T, is_less: &mut F, mid: usize)
+where
+    F: FnMut(&T, &T) -> bool,
+{
+    let len = v.len();
+    debug_assert!(mid > 0 && mid < len);
+
+    let len = v.len();
+
+    // Indexes to track the positions while merging.
+    let mut l = 0;
+    let mut r = mid;
+
+    // SAFETY: No matter what the result of is_less is we check that l and r remain in-bounds and if
+    // is_less panics the original elements remain in `v`.
+    unsafe {
+        let arr_ptr = v.as_ptr();
+
+        for i in 0..len {
+            let left_ptr = arr_ptr.add(l);
+            let right_ptr = arr_ptr.add(r);
+
+            let is_lt = !is_less(&*right_ptr, &*left_ptr);
+            let copy_ptr = if is_lt { left_ptr } else { right_ptr };
+            ptr::copy_nonoverlapping(copy_ptr, scratch_ptr.add(i), 1);
+
+            l += is_lt as usize;
+            r += !is_lt as usize;
+
+            // As long as neither side is exhausted merge left and right elements.
+            if ((l == mid) as u8 + (r == len) as u8) != 0 {
+                break;
+            }
+        }
+
+        // The left or right side is exhausted, drain the right side in one go.
+        let copy_ptr = if l == mid { arr_ptr.add(r) } else { arr_ptr.add(l) };
+        let i = l + (r - mid);
+        ptr::copy_nonoverlapping(copy_ptr, scratch_ptr.add(i), len - i);
+
+        // Now that scratch_ptr holds the full merged content, write it back on-top of v.
+        ptr::copy_nonoverlapping(scratch_ptr, v.as_mut_ptr(), len);
+    }
+}
+
+// SAFETY: The caller has to ensure that Option is Some, UB otherwise.
+unsafe fn unwrap_unchecked<T>(opt_val: Option<T>) -> T {
+    match opt_val {
+        Some(val) => val,
+        None => {
+            // SAFETY: See function safety description.
+            unsafe {
+                core::hint::unreachable_unchecked();
+            }
+        }
+    }
+}
+
+// Extremely basic versions of Vec.
+// Their use is super limited and by having the code here, it allows reuse between the sort
+// implementations.
+struct BufGuard<T> {
+    buf_ptr: ptr::NonNull<T>,
+    capacity: usize,
+}
+
+impl<T> BufGuard<T> {
+    // SAFETY: The caller has to ensure that len is not 0 and that T is not a ZST.
+    unsafe fn new(len: usize) -> Self {
+        debug_assert!(len > 0 && mem::size_of::<T>() > 0);
+
+        // SAFETY: See function safety description.
+        let layout = unsafe { unwrap_unchecked(Layout::array::<T>(len).ok()) };
+
+        // SAFETY: We checked that T is not a ZST.
+        let buf_ptr = unsafe { alloc(layout) as *mut T };
+
+        if buf_ptr.is_null() {
+            panic!("allocation failure");
+        }
+
+        Self { buf_ptr: ptr::NonNull::new(buf_ptr).unwrap(), capacity: len }
+    }
+}
+
+impl<T> Drop for BufGuard<T> {
+    fn drop(&mut self) {
+        // SAFETY: We checked that T is not a ZST.
+        unsafe {
+            dealloc(self.buf_ptr.as_ptr() as *mut u8, Layout::array::<T>(self.capacity).unwrap());
+        }
+    }
+}
diff --git a/library/alloc/tests/sort/mod.rs b/library/alloc/tests/sort/mod.rs
new file mode 100644
index 00000000000..0e2494ca9d3
--- /dev/null
+++ b/library/alloc/tests/sort/mod.rs
@@ -0,0 +1,17 @@
+pub trait Sort {
+    fn name() -> String;
+
+    fn sort<T>(v: &mut [T])
+    where
+        T: Ord;
+
+    fn sort_by<T, F>(v: &mut [T], compare: F)
+    where
+        F: FnMut(&T, &T) -> std::cmp::Ordering;
+}
+
+mod ffi_types;
+mod known_good_stable_sort;
+mod patterns;
+mod tests;
+mod zipf;
diff --git a/library/alloc/tests/sort/patterns.rs b/library/alloc/tests/sort/patterns.rs
new file mode 100644
index 00000000000..e5d31d868b2
--- /dev/null
+++ b/library/alloc/tests/sort/patterns.rs
@@ -0,0 +1,211 @@
+use std::env;
+use std::hash::Hash;
+use std::str::FromStr;
+use std::sync::OnceLock;
+
+use rand::prelude::*;
+use rand_xorshift::XorShiftRng;
+
+use crate::sort::zipf::ZipfDistribution;
+
+/// Provides a set of patterns useful for testing and benchmarking sorting algorithms.
+/// Currently limited to i32 values.
+
+// --- Public ---
+
+pub fn random(len: usize) -> Vec<i32> {
+    //     .
+    // : . : :
+    // :.:::.::
+
+    random_vec(len)
+}
+
+pub fn random_uniform<R>(len: usize, range: R) -> Vec<i32>
+where
+    R: Into<rand::distributions::Uniform<i32>> + Hash,
+{
+    // :.:.:.::
+
+    let mut rng: XorShiftRng = rand::SeedableRng::seed_from_u64(get_or_init_rand_seed());
+
+    // Abstracting over ranges in Rust :(
+    let dist: rand::distributions::Uniform<i32> = range.into();
+    (0..len).map(|_| dist.sample(&mut rng)).collect()
+}
+
+pub fn random_zipf(len: usize, exponent: f64) -> Vec<i32> {
+    // https://en.wikipedia.org/wiki/Zipf's_law
+
+    let mut rng: XorShiftRng = rand::SeedableRng::seed_from_u64(get_or_init_rand_seed());
+
+    // Abstracting over ranges in Rust :(
+    let dist = ZipfDistribution::new(len, exponent).unwrap();
+    (0..len).map(|_| dist.sample(&mut rng) as i32).collect()
+}
+
+pub fn random_sorted(len: usize, sorted_percent: f64) -> Vec<i32> {
+    //     .:
+    //   .:::. :
+    // .::::::.::
+    // [----][--]
+    //  ^      ^
+    //  |      |
+    // sorted  |
+    //     unsorted
+
+    // Simulate pre-existing sorted slice, where len - sorted_percent are the new unsorted values
+    // and part of the overall distribution.
+    let mut v = random_vec(len);
+    let sorted_len = ((len as f64) * (sorted_percent / 100.0)).round() as usize;
+
+    v[0..sorted_len].sort_unstable();
+
+    v
+}
+
+pub fn all_equal(len: usize) -> Vec<i32> {
+    // ......
+    // ::::::
+
+    (0..len).map(|_| 66).collect::<Vec<_>>()
+}
+
+pub fn ascending(len: usize) -> Vec<i32> {
+    //     .:
+    //   .:::
+    // .:::::
+
+    (0..len as i32).collect::<Vec<_>>()
+}
+
+pub fn descending(len: usize) -> Vec<i32> {
+    // :.
+    // :::.
+    // :::::.
+
+    (0..len as i32).rev().collect::<Vec<_>>()
+}
+
+pub fn saw_mixed(len: usize, saw_count: usize) -> Vec<i32> {
+    // :.  :.    .::.    .:
+    // :::.:::..::::::..:::
+
+    if len == 0 {
+        return Vec::new();
+    }
+
+    let mut vals = random_vec(len);
+    let chunks_size = len / saw_count.max(1);
+    let saw_directions = random_uniform((len / chunks_size) + 1, 0..=1);
+
+    for (i, chunk) in vals.chunks_mut(chunks_size).enumerate() {
+        if saw_directions[i] == 0 {
+            chunk.sort_unstable();
+        } else if saw_directions[i] == 1 {
+            chunk.sort_unstable_by_key(|&e| std::cmp::Reverse(e));
+        } else {
+            unreachable!();
+        }
+    }
+
+    vals
+}
+
+pub fn saw_mixed_range(len: usize, range: std::ops::Range<usize>) -> Vec<i32> {
+    //     :.
+    // :.  :::.    .::.      .:
+    // :::.:::::..::::::..:.:::
+
+    // ascending and descending randomly picked, with length in `range`.
+
+    if len == 0 {
+        return Vec::new();
+    }
+
+    let mut vals = random_vec(len);
+
+    let max_chunks = len / range.start;
+    let saw_directions = random_uniform(max_chunks + 1, 0..=1);
+    let chunk_sizes = random_uniform(max_chunks + 1, (range.start as i32)..(range.end as i32));
+
+    let mut i = 0;
+    let mut l = 0;
+    while l < len {
+        let chunk_size = chunk_sizes[i] as usize;
+        let chunk_end = std::cmp::min(l + chunk_size, len);
+        let chunk = &mut vals[l..chunk_end];
+
+        if saw_directions[i] == 0 {
+            chunk.sort_unstable();
+        } else if saw_directions[i] == 1 {
+            chunk.sort_unstable_by_key(|&e| std::cmp::Reverse(e));
+        } else {
+            unreachable!();
+        }
+
+        i += 1;
+        l += chunk_size;
+    }
+
+    vals
+}
+
+pub fn pipe_organ(len: usize) -> Vec<i32> {
+    //   .:.
+    // .:::::.
+
+    let mut vals = random_vec(len);
+
+    let first_half = &mut vals[0..(len / 2)];
+    first_half.sort_unstable();
+
+    let second_half = &mut vals[(len / 2)..len];
+    second_half.sort_unstable_by_key(|&e| std::cmp::Reverse(e));
+
+    vals
+}
+
+pub fn get_or_init_rand_seed() -> u64 {
+    *SEED_VALUE.get_or_init(|| {
+        env::var("OVERRIDE_SEED")
+            .ok()
+            .map(|seed| u64::from_str(&seed).unwrap())
+            .unwrap_or_else(rand_root_seed)
+    })
+}
+
+// --- Private ---
+
+static SEED_VALUE: OnceLock<u64> = OnceLock::new();
+
+#[cfg(not(miri))]
+fn rand_root_seed() -> u64 {
+    // Other test code hashes `panic::Location::caller()` and constructs a seed from that, in these
+    // tests we want to have a fuzzer like exploration of the test space, if we used the same caller
+    // based construction we would always test the same.
+    //
+    // Instead we use the seconds since UNIX epoch / 10, given CI log output this value should be
+    // reasonably easy to re-construct.
+
+    use std::time::{SystemTime, UNIX_EPOCH};
+
+    let epoch_seconds = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_secs();
+
+    epoch_seconds / 10
+}
+
+#[cfg(miri)]
+fn rand_root_seed() -> u64 {
+    // Miri is usually run with isolation with gives us repeatability but also permutations based on
+    // other code that runs before.
+    use core::hash::{BuildHasher, Hash, Hasher};
+    let mut hasher = std::hash::RandomState::new().build_hasher();
+    core::panic::Location::caller().hash(&mut hasher);
+    hasher.finish()
+}
+
+fn random_vec(len: usize) -> Vec<i32> {
+    let mut rng: XorShiftRng = rand::SeedableRng::seed_from_u64(get_or_init_rand_seed());
+    (0..len).map(|_| rng.gen::<i32>()).collect()
+}
diff --git a/library/alloc/tests/sort/tests.rs b/library/alloc/tests/sort/tests.rs
new file mode 100644
index 00000000000..14e6013f965
--- /dev/null
+++ b/library/alloc/tests/sort/tests.rs
@@ -0,0 +1,1233 @@
+use std::cell::Cell;
+use std::cmp::Ordering;
+use std::fmt::Debug;
+use std::panic::{self, AssertUnwindSafe};
+use std::rc::Rc;
+use std::{env, fs};
+
+use crate::sort::ffi_types::{F128, FFIOneKibiByte};
+use crate::sort::{Sort, known_good_stable_sort, patterns};
+
+#[cfg(miri)]
+const TEST_LENGTHS: &[usize] = &[2, 3, 4, 7, 10, 15, 20, 24, 33, 50, 100, 171, 300];
+
+#[cfg(not(miri))]
+const TEST_LENGTHS: &[usize] = &[
+    2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 16, 17, 20, 24, 30, 32, 33, 35, 50, 100, 200, 500, 1_000,
+    2_048, 5_000, 10_000, 100_000, 1_100_000,
+];
+
+fn check_is_sorted<T: Ord + Clone + Debug, S: Sort>(v: &mut [T]) {
+    let seed = patterns::get_or_init_rand_seed();
+
+    let is_small_test = v.len() <= 100;
+    let v_orig = v.to_vec();
+
+    <S as Sort>::sort(v);
+
+    assert_eq!(v.len(), v_orig.len());
+
+    for window in v.windows(2) {
+        if window[0] > window[1] {
+            let mut known_good_sorted_vec = v_orig.clone();
+            known_good_stable_sort::sort(known_good_sorted_vec.as_mut_slice());
+
+            if is_small_test {
+                eprintln!("Orginal:  {:?}", v_orig);
+                eprintln!("Expected: {:?}", known_good_sorted_vec);
+                eprintln!("Got:      {:?}", v);
+            } else {
+                if env::var("WRITE_LARGE_FAILURE").is_ok() {
+                    // Large arrays output them as files.
+                    let original_name = format!("original_{}.txt", seed);
+                    let std_name = format!("known_good_sorted_{}.txt", seed);
+                    let testsort_name = format!("{}_sorted_{}.txt", S::name(), seed);
+
+                    fs::write(&original_name, format!("{:?}", v_orig)).unwrap();
+                    fs::write(&std_name, format!("{:?}", known_good_sorted_vec)).unwrap();
+                    fs::write(&testsort_name, format!("{:?}", v)).unwrap();
+
+                    eprintln!(
+                        "Failed comparison, see files {original_name}, {std_name}, and {testsort_name}"
+                    );
+                } else {
+                    eprintln!(
+                        "Failed comparison, re-run with WRITE_LARGE_FAILURE env var set, to get output."
+                    );
+                }
+            }
+
+            panic!("Test assertion failed!")
+        }
+    }
+}
+
+fn test_is_sorted<T: Ord + Clone + Debug, S: Sort>(
+    test_len: usize,
+    map_fn: impl Fn(i32) -> T,
+    pattern_fn: impl Fn(usize) -> Vec<i32>,
+) {
+    let mut test_data: Vec<T> = pattern_fn(test_len).into_iter().map(map_fn).collect();
+    check_is_sorted::<T, S>(test_data.as_mut_slice());
+}
+
+trait DynTrait: Debug {
+    fn get_val(&self) -> i32;
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
+struct DynValA {
+    value: i32,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
+struct DynValB {
+    value: u64,
+}
+
+impl DynTrait for DynValA {
+    fn get_val(&self) -> i32 {
+        self.value
+    }
+}
+impl DynTrait for DynValB {
+    fn get_val(&self) -> i32 {
+        let bytes = self.value.to_ne_bytes();
+        i32::from_ne_bytes([bytes[0], bytes[1], bytes[6], bytes[7]])
+    }
+}
+
+impl PartialOrd for dyn DynTrait {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for dyn DynTrait {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.get_val().cmp(&other.get_val())
+    }
+}
+
+impl PartialEq for dyn DynTrait {
+    fn eq(&self, other: &Self) -> bool {
+        self.get_val() == other.get_val()
+    }
+}
+
+impl Eq for dyn DynTrait {}
+
+fn shift_i32_to_u32(val: i32) -> u32 {
+    (val as i64 + (i32::MAX as i64 + 1)) as u32
+}
+
+fn reverse_shift_i32_to_u32(val: u32) -> i32 {
+    (val as i64 - (i32::MAX as i64 + 1)) as i32
+}
+
+fn extend_i32_to_u64(val: i32) -> u64 {
+    // Extends the value into the 64 bit range,
+    // while preserving input order.
+    (shift_i32_to_u32(val) as u64) * i32::MAX as u64
+}
+
+fn extend_i32_to_u128(val: i32) -> u128 {
+    // Extends the value into the 64 bit range,
+    // while preserving input order.
+    (shift_i32_to_u32(val) as u128) * i64::MAX as u128
+}
+
+fn dyn_trait_from_i32(val: i32) -> Rc<dyn DynTrait> {
+    if val % 2 == 0 {
+        Rc::new(DynValA { value: val })
+    } else {
+        Rc::new(DynValB { value: extend_i32_to_u64(val) })
+    }
+}
+
+fn i32_from_i32(val: i32) -> i32 {
+    val
+}
+
+fn i32_from_i32_ref(val: &i32) -> i32 {
+    *val
+}
+
+fn string_from_i32(val: i32) -> String {
+    format!("{:010}", shift_i32_to_u32(val))
+}
+
+fn i32_from_string(val: &String) -> i32 {
+    reverse_shift_i32_to_u32(val.parse::<u32>().unwrap())
+}
+
+fn cell_i32_from_i32(val: i32) -> Cell<i32> {
+    Cell::new(val)
+}
+
+fn i32_from_cell_i32(val: &Cell<i32>) -> i32 {
+    val.get()
+}
+
+fn calc_comps_required<T, S: Sort>(v: &mut [T], mut cmp_fn: impl FnMut(&T, &T) -> Ordering) -> u32 {
+    let mut comp_counter = 0u32;
+
+    <S as Sort>::sort_by(v, |a, b| {
+        comp_counter += 1;
+
+        cmp_fn(a, b)
+    });
+
+    comp_counter
+}
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+#[repr(C)]
+struct CompCount {
+    val: i32,
+    comp_count: Cell<u32>,
+}
+
+impl CompCount {
+    fn new(val: i32) -> Self {
+        Self { val, comp_count: Cell::new(0) }
+    }
+}
+
+/// Generates $base_name_pattern_name_impl functions calling the test_fns for all test_len.
+macro_rules! gen_sort_test_fns {
+    (
+        $base_name:ident,
+        $test_fn:expr,
+        $test_lengths:expr,
+        [$(($pattern_name:ident, $pattern_fn:expr)),* $(,)?] $(,)?
+    ) => {
+        $(fn ${concat($base_name, _, $pattern_name, _impl)}<S: Sort>() {
+            for test_len in $test_lengths {
+                $test_fn(*test_len, $pattern_fn);
+            }
+        })*
+    };
+}
+
+/// Generates $base_name_pattern_name_impl functions calling the test_fns for all test_len,
+/// with a default set of patterns that can be extended by the caller.
+macro_rules! gen_sort_test_fns_with_default_patterns {
+    (
+        $base_name:ident,
+        $test_fn:expr,
+        $test_lengths:expr,
+        [$(($pattern_name:ident, $pattern_fn:expr)),* $(,)?] $(,)?
+    ) => {
+        gen_sort_test_fns!(
+            $base_name,
+            $test_fn,
+            $test_lengths,
+            [
+                (random, patterns::random),
+                (random_z1, |len| patterns::random_zipf(len, 1.0)),
+                (random_d2, |len| patterns::random_uniform(len, 0..2)),
+                (random_d20, |len| patterns::random_uniform(len, 0..16)),
+                (random_s95, |len| patterns::random_sorted(len, 95.0)),
+                (ascending, patterns::ascending),
+                (descending, patterns::descending),
+                (saw_mixed, |len| patterns::saw_mixed(
+                    len,
+                    ((len as f64).log2().round()) as usize
+                )),
+                $(($pattern_name, $pattern_fn),)*
+            ]
+        );
+    };
+}
+
+/// Generates $base_name_type_pattern_name_impl functions calling the test_fns for all test_len for
+/// three types that cover the core specialization differences in the sort implementations, with a
+/// default set of patterns that can be extended by the caller.
+macro_rules! gen_sort_test_fns_with_default_patterns_3_ty {
+    (
+        $base_name:ident,
+        $test_fn:ident,
+        [$(($pattern_name:ident, $pattern_fn:expr)),* $(,)?] $(,)?
+    ) => {
+        gen_sort_test_fns_with_default_patterns!(
+            ${concat($base_name, _i32)},
+            |len, pattern_fn| $test_fn::<i32, S>(len, i32_from_i32, i32_from_i32_ref, pattern_fn),
+            &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+            [$(($pattern_name, $pattern_fn),)*],
+        );
+
+        gen_sort_test_fns_with_default_patterns!(
+            ${concat($base_name, _cell_i32)},
+            |len, pattern_fn| $test_fn::<Cell<i32>, S>(len, cell_i32_from_i32, i32_from_cell_i32, pattern_fn),
+            &TEST_LENGTHS[..TEST_LENGTHS.len() - 3],
+            [$(($pattern_name, $pattern_fn),)*],
+        );
+
+        gen_sort_test_fns_with_default_patterns!(
+            ${concat($base_name, _string)},
+            |len, pattern_fn| $test_fn::<String, S>(len, string_from_i32, i32_from_string, pattern_fn),
+            &TEST_LENGTHS[..TEST_LENGTHS.len() - 3],
+            [$(($pattern_name, $pattern_fn),)*],
+        );
+    };
+}
+
+// --- TESTS ---
+
+pub fn basic_impl<S: Sort>() {
+    check_is_sorted::<i32, S>(&mut []);
+    check_is_sorted::<(), S>(&mut []);
+    check_is_sorted::<(), S>(&mut [()]);
+    check_is_sorted::<(), S>(&mut [(), ()]);
+    check_is_sorted::<(), S>(&mut [(), (), ()]);
+    check_is_sorted::<i32, S>(&mut []);
+    check_is_sorted::<i32, S>(&mut [77]);
+    check_is_sorted::<i32, S>(&mut [2, 3]);
+    check_is_sorted::<i32, S>(&mut [2, 3, 6]);
+    check_is_sorted::<i32, S>(&mut [2, 3, 99, 6]);
+    check_is_sorted::<i32, S>(&mut [2, 7709, 400, 90932]);
+    check_is_sorted::<i32, S>(&mut [15, -1, 3, -1, -3, -1, 7]);
+}
+
+fn fixed_seed_impl<S: Sort>() {
+    let fixed_seed_a = patterns::get_or_init_rand_seed();
+    let fixed_seed_b = patterns::get_or_init_rand_seed();
+
+    assert_eq!(fixed_seed_a, fixed_seed_b);
+}
+
+fn fixed_seed_rand_vec_prefix_impl<S: Sort>() {
+    let vec_rand_len_5 = patterns::random(5);
+    let vec_rand_len_7 = patterns::random(7);
+
+    assert_eq!(vec_rand_len_5, vec_rand_len_7[..5]);
+}
+
+fn int_edge_impl<S: Sort>() {
+    // Ensure that the sort can handle integer edge cases.
+    check_is_sorted::<i32, S>(&mut [i32::MIN, i32::MAX]);
+    check_is_sorted::<i32, S>(&mut [i32::MAX, i32::MIN]);
+    check_is_sorted::<i32, S>(&mut [i32::MIN, 3]);
+    check_is_sorted::<i32, S>(&mut [i32::MIN, -3]);
+    check_is_sorted::<i32, S>(&mut [i32::MIN, -3, i32::MAX]);
+    check_is_sorted::<i32, S>(&mut [i32::MIN, -3, i32::MAX, i32::MIN, 5]);
+    check_is_sorted::<i32, S>(&mut [i32::MAX, 3, i32::MIN, 5, i32::MIN, -3, 60, 200, 50, 7, 10]);
+
+    check_is_sorted::<u64, S>(&mut [u64::MIN, u64::MAX]);
+    check_is_sorted::<u64, S>(&mut [u64::MAX, u64::MIN]);
+    check_is_sorted::<u64, S>(&mut [u64::MIN, 3]);
+    check_is_sorted::<u64, S>(&mut [u64::MIN, u64::MAX - 3]);
+    check_is_sorted::<u64, S>(&mut [u64::MIN, u64::MAX - 3, u64::MAX]);
+    check_is_sorted::<u64, S>(&mut [u64::MIN, u64::MAX - 3, u64::MAX, u64::MIN, 5]);
+    check_is_sorted::<u64, S>(&mut [
+        u64::MAX,
+        3,
+        u64::MIN,
+        5,
+        u64::MIN,
+        u64::MAX - 3,
+        60,
+        200,
+        50,
+        7,
+        10,
+    ]);
+
+    let mut large = patterns::random(TEST_LENGTHS[TEST_LENGTHS.len() - 2]);
+    large.push(i32::MAX);
+    large.push(i32::MIN);
+    large.push(i32::MAX);
+    check_is_sorted::<i32, S>(&mut large);
+}
+
+fn sort_vs_sort_by_impl<S: Sort>() {
+    // Ensure that sort and sort_by produce the same result.
+    let mut input_normal = [800, 3, -801, 5, -801, -3, 60, 200, 50, 7, 10];
+    let expected = [-801, -801, -3, 3, 5, 7, 10, 50, 60, 200, 800];
+
+    let mut input_sort_by = input_normal.to_vec();
+
+    <S as Sort>::sort(&mut input_normal);
+    <S as Sort>::sort_by(&mut input_sort_by, |a, b| a.cmp(b));
+
+    assert_eq!(input_normal, expected);
+    assert_eq!(input_sort_by, expected);
+}
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_i32,
+    |len, pattern_fn| test_is_sorted::<i32, S>(len, |val| val, pattern_fn),
+    TEST_LENGTHS,
+    [
+        (random_d4, |len| patterns::random_uniform(len, 0..4)),
+        (random_d8, |len| patterns::random_uniform(len, 0..8)),
+        (random_d311, |len| patterns::random_uniform(len, 0..311)),
+        (random_d1024, |len| patterns::random_uniform(len, 0..1024)),
+        (random_z1_03, |len| patterns::random_zipf(len, 1.03)),
+        (random_z2, |len| patterns::random_zipf(len, 2.0)),
+        (random_s50, |len| patterns::random_sorted(len, 50.0)),
+        (narrow, |len| patterns::random_uniform(
+            len,
+            0..=(((len as f64).log2().round()) as i32) * 100
+        )),
+        (all_equal, patterns::all_equal),
+        (saw_mixed_range, |len| patterns::saw_mixed_range(len, 20..50)),
+        (pipe_organ, patterns::pipe_organ),
+    ]
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_u64,
+    |len, pattern_fn| test_is_sorted::<u64, S>(len, extend_i32_to_u64, pattern_fn),
+    TEST_LENGTHS,
+    []
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_u128,
+    |len, pattern_fn| test_is_sorted::<u128, S>(len, extend_i32_to_u128, pattern_fn),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_cell_i32,
+    |len, pattern_fn| test_is_sorted::<Cell<i32>, S>(len, Cell::new, pattern_fn),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_string,
+    |len, pattern_fn| test_is_sorted::<String, S>(
+        len,
+        |val| format!("{:010}", shift_i32_to_u32(val)),
+        pattern_fn
+    ),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_f128,
+    |len, pattern_fn| test_is_sorted::<F128, S>(len, F128::new, pattern_fn),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+gen_sort_test_fns_with_default_patterns!(
+    correct_1k,
+    |len, pattern_fn| test_is_sorted::<FFIOneKibiByte, S>(len, FFIOneKibiByte::new, pattern_fn),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+// Dyn values are fat pointers, something the implementation might have overlooked.
+gen_sort_test_fns_with_default_patterns!(
+    correct_dyn_val,
+    |len, pattern_fn| test_is_sorted::<Rc<dyn DynTrait>, S>(len, dyn_trait_from_i32, pattern_fn),
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+fn stability_legacy_impl<S: Sort>() {
+    // This non pattern variant has proven to catch some bugs the pattern version of this function
+    // doesn't catch, so it remains in conjunction with the other one.
+
+    if <S as Sort>::name().contains("unstable") {
+        // It would be great to mark the test as skipped, but that isn't possible as of now.
+        return;
+    }
+
+    let large_range = if cfg!(miri) { 100..110 } else { 3000..3010 };
+    let rounds = if cfg!(miri) { 1 } else { 10 };
+
+    let rand_vals = patterns::random_uniform(5_000, 0..=9);
+    let mut rand_idx = 0;
+
+    for len in (2..55).chain(large_range) {
+        for _ in 0..rounds {
+            let mut counts = [0; 10];
+
+            // create a vector like [(6, 1), (5, 1), (6, 2), ...],
+            // where the first item of each tuple is random, but
+            // the second item represents which occurrence of that
+            // number this element is, i.e., the second elements
+            // will occur in sorted order.
+            let orig: Vec<_> = (0..len)
+                .map(|_| {
+                    let n = rand_vals[rand_idx];
+                    rand_idx += 1;
+                    if rand_idx >= rand_vals.len() {
+                        rand_idx = 0;
+                    }
+
+                    counts[n as usize] += 1;
+                    i32_tup_as_u64((n, counts[n as usize]))
+                })
+                .collect();
+
+            let mut v = orig.clone();
+            // Only sort on the first element, so an unstable sort
+            // may mix up the counts.
+            <S as Sort>::sort_by(&mut v, |a_packed, b_packed| {
+                let a = i32_tup_from_u64(*a_packed).0;
+                let b = i32_tup_from_u64(*b_packed).0;
+
+                a.cmp(&b)
+            });
+
+            // This comparison includes the count (the second item
+            // of the tuple), so elements with equal first items
+            // will need to be ordered with increasing
+            // counts... i.e., exactly asserting that this sort is
+            // stable.
+            assert!(v.windows(2).all(|w| i32_tup_from_u64(w[0]) <= i32_tup_from_u64(w[1])));
+        }
+    }
+
+    // For cpp_sorts that only support u64 we can pack the two i32 inside a u64.
+    fn i32_tup_as_u64(val: (i32, i32)) -> u64 {
+        let a_bytes = val.0.to_le_bytes();
+        let b_bytes = val.1.to_le_bytes();
+
+        u64::from_le_bytes([a_bytes, b_bytes].concat().try_into().unwrap())
+    }
+
+    fn i32_tup_from_u64(val: u64) -> (i32, i32) {
+        let bytes = val.to_le_bytes();
+
+        let a = i32::from_le_bytes(bytes[0..4].try_into().unwrap());
+        let b = i32::from_le_bytes(bytes[4..8].try_into().unwrap());
+
+        (a, b)
+    }
+}
+
+fn stability_with_patterns<T: Ord + Clone, S: Sort>(
+    len: usize,
+    type_into_fn: impl Fn(i32) -> T,
+    _type_from_fn: impl Fn(&T) -> i32,
+    pattern_fn: fn(usize) -> Vec<i32>,
+) {
+    if <S as Sort>::name().contains("unstable") {
+        // It would be great to mark the test as skipped, but that isn't possible as of now.
+        return;
+    }
+
+    let pattern = pattern_fn(len);
+
+    let mut counts = [0i32; 128];
+
+    // create a vector like [(6, 1), (5, 1), (6, 2), ...],
+    // where the first item of each tuple is random, but
+    // the second item represents which occurrence of that
+    // number this element is, i.e., the second elements
+    // will occur in sorted order.
+    let orig: Vec<_> = pattern
+        .iter()
+        .map(|val| {
+            let n = val.saturating_abs() % counts.len() as i32;
+            counts[n as usize] += 1;
+            (type_into_fn(n), counts[n as usize])
+        })
+        .collect();
+
+    let mut v = orig.clone();
+    // Only sort on the first element, so an unstable sort
+    // may mix up the counts.
+    <S as Sort>::sort(&mut v);
+
+    // This comparison includes the count (the second item
+    // of the tuple), so elements with equal first items
+    // will need to be ordered with increasing
+    // counts... i.e., exactly asserting that this sort is
+    // stable.
+    assert!(v.windows(2).all(|w| w[0] <= w[1]));
+}
+
+gen_sort_test_fns_with_default_patterns_3_ty!(stability, stability_with_patterns, []);
+
+fn observable_is_less<S: Sort>(len: usize, pattern_fn: fn(usize) -> Vec<i32>) {
+    // This test, tests that every is_less is actually observable. Ie. this can go wrong if a hole
+    // is created using temporary memory and, the whole is used as comparison but not copied back.
+    //
+    // If this is not upheld a custom type + comparison function could yield UB in otherwise safe
+    // code. Eg T == Mutex<Option<Box<str>>> which replaces the pointer with none in the comparison
+    // function, which would not be observed in the original slice and would lead to a double free.
+
+    let pattern = pattern_fn(len);
+    let mut test_input = pattern.into_iter().map(|val| CompCount::new(val)).collect::<Vec<_>>();
+
+    let mut comp_count_global = 0;
+
+    <S as Sort>::sort_by(&mut test_input, |a, b| {
+        a.comp_count.replace(a.comp_count.get() + 1);
+        b.comp_count.replace(b.comp_count.get() + 1);
+        comp_count_global += 1;
+
+        a.val.cmp(&b.val)
+    });
+
+    let total_inner: u64 = test_input.iter().map(|c| c.comp_count.get() as u64).sum();
+
+    assert_eq!(total_inner, comp_count_global * 2);
+}
+
+gen_sort_test_fns_with_default_patterns!(
+    observable_is_less,
+    observable_is_less::<S>,
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+fn panic_retain_orig_set<T: Ord + Clone, S: Sort>(
+    len: usize,
+    type_into_fn: impl Fn(i32) -> T + Copy,
+    type_from_fn: impl Fn(&T) -> i32,
+    pattern_fn: fn(usize) -> Vec<i32>,
+) {
+    let mut test_data: Vec<T> = pattern_fn(len).into_iter().map(type_into_fn).collect();
+
+    let sum_before: i64 = test_data.iter().map(|x| type_from_fn(x) as i64).sum();
+
+    // Calculate a specific comparison that should panic.
+    // Ensure that it can be any of the possible comparisons and that it always panics.
+    let required_comps = calc_comps_required::<T, S>(&mut test_data.clone(), |a, b| a.cmp(b));
+    let panic_threshold = patterns::random_uniform(1, 1..=required_comps as i32)[0] as usize - 1;
+
+    let mut comp_counter = 0;
+
+    let res = panic::catch_unwind(AssertUnwindSafe(|| {
+        <S as Sort>::sort_by(&mut test_data, |a, b| {
+            if comp_counter == panic_threshold {
+                // Make the panic dependent on the test len and some random factor. We want to
+                // make sure that panicking may also happen when comparing elements a second
+                // time.
+                panic!();
+            }
+            comp_counter += 1;
+
+            a.cmp(b)
+        });
+    }));
+
+    assert!(res.is_err());
+
+    // If the sum before and after don't match, it means the set of elements hasn't remained the
+    // same.
+    let sum_after: i64 = test_data.iter().map(|x| type_from_fn(x) as i64).sum();
+    assert_eq!(sum_before, sum_after);
+}
+
+gen_sort_test_fns_with_default_patterns_3_ty!(panic_retain_orig_set, panic_retain_orig_set, []);
+
+fn panic_observable_is_less<S: Sort>(len: usize, pattern_fn: fn(usize) -> Vec<i32>) {
+    // This test, tests that every is_less is actually observable. Ie. this can go wrong if a hole
+    // is created using temporary memory and, the whole is used as comparison but not copied back.
+    // This property must also hold if the user provided comparison panics.
+    //
+    // If this is not upheld a custom type + comparison function could yield UB in otherwise safe
+    // code. Eg T == Mutex<Option<Box<str>>> which replaces the pointer with none in the comparison
+    // function, which would not be observed in the original slice and would lead to a double free.
+
+    let mut test_input =
+        pattern_fn(len).into_iter().map(|val| CompCount::new(val)).collect::<Vec<_>>();
+
+    let sum_before: i64 = test_input.iter().map(|x| x.val as i64).sum();
+
+    // Calculate a specific comparison that should panic.
+    // Ensure that it can be any of the possible comparisons and that it always panics.
+    let required_comps =
+        calc_comps_required::<CompCount, S>(&mut test_input.clone(), |a, b| a.val.cmp(&b.val));
+
+    let panic_threshold = patterns::random_uniform(1, 1..=required_comps as i32)[0] as u64 - 1;
+
+    let mut comp_count_global = 0;
+
+    let res = panic::catch_unwind(AssertUnwindSafe(|| {
+        <S as Sort>::sort_by(&mut test_input, |a, b| {
+            if comp_count_global == panic_threshold {
+                // Make the panic dependent on the test len and some random factor. We want to
+                // make sure that panicking may also happen when comparing elements a second
+                // time.
+                panic!();
+            }
+
+            a.comp_count.replace(a.comp_count.get() + 1);
+            b.comp_count.replace(b.comp_count.get() + 1);
+            comp_count_global += 1;
+
+            a.val.cmp(&b.val)
+        });
+    }));
+
+    assert!(res.is_err());
+
+    let total_inner: u64 = test_input.iter().map(|c| c.comp_count.get() as u64).sum();
+
+    assert_eq!(total_inner, comp_count_global * 2);
+
+    // If the sum before and after don't match, it means the set of elements hasn't remained the
+    // same.
+    let sum_after: i64 = test_input.iter().map(|x| x.val as i64).sum();
+    assert_eq!(sum_before, sum_after);
+}
+
+gen_sort_test_fns_with_default_patterns!(
+    panic_observable_is_less,
+    panic_observable_is_less::<S>,
+    &TEST_LENGTHS[..TEST_LENGTHS.len() - 2],
+    []
+);
+
+fn deterministic<T: Ord + Clone + Debug, S: Sort>(
+    len: usize,
+    type_into_fn: impl Fn(i32) -> T + Copy,
+    type_from_fn: impl Fn(&T) -> i32,
+    pattern_fn: fn(usize) -> Vec<i32>,
+) {
+    // A property similar to stability is deterministic output order. If the entire value is used as
+    // the comparison key a lack of determinism has no effect. But if only a part of the value is
+    // used as comparison key, a lack of determinism can manifest itself in the order of values
+    // considered equal by the comparison predicate.
+    //
+    // This test only tests that results are deterministic across runs, it does not test determinism
+    // on different platforms and with different toolchains.
+
+    let mut test_input =
+        pattern_fn(len).into_iter().map(|val| type_into_fn(val)).collect::<Vec<_>>();
+
+    let mut test_input_clone = test_input.clone();
+
+    let comparison_fn = |a: &T, b: &T| {
+        let a_i32 = type_from_fn(a);
+        let b_i32 = type_from_fn(b);
+
+        let a_i32_key_space_reduced = a_i32 % 10_000;
+        let b_i32_key_space_reduced = b_i32 % 10_000;
+
+        a_i32_key_space_reduced.cmp(&b_i32_key_space_reduced)
+    };
+
+    <S as Sort>::sort_by(&mut test_input, comparison_fn);
+    <S as Sort>::sort_by(&mut test_input_clone, comparison_fn);
+
+    assert_eq!(test_input, test_input_clone);
+}
+
+gen_sort_test_fns_with_default_patterns_3_ty!(deterministic, deterministic, []);
+
+fn self_cmp<T: Ord + Clone + Debug, S: Sort>(
+    len: usize,
+    type_into_fn: impl Fn(i32) -> T + Copy,
+    _type_from_fn: impl Fn(&T) -> i32,
+    pattern_fn: fn(usize) -> Vec<i32>,
+) {
+    // It's possible for comparisons to run into problems if the values of `a` and `b` passed into
+    // the comparison function are the same reference. So this tests that they never are.
+
+    let mut test_input =
+        pattern_fn(len).into_iter().map(|val| type_into_fn(val)).collect::<Vec<_>>();
+
+    let comparison_fn = |a: &T, b: &T| {
+        assert_ne!(a as *const T as usize, b as *const T as usize);
+        a.cmp(b)
+    };
+
+    <S as Sort>::sort_by(&mut test_input, comparison_fn);
+
+    // Check that the output is actually sorted and wasn't stopped by the assert.
+    for window in test_input.windows(2) {
+        assert!(window[0] <= window[1]);
+    }
+}
+
+gen_sort_test_fns_with_default_patterns_3_ty!(self_cmp, self_cmp, []);
+
+fn violate_ord_retain_orig_set<T: Ord, S: Sort>(
+    len: usize,
+    type_into_fn: impl Fn(i32) -> T + Copy,
+    type_from_fn: impl Fn(&T) -> i32,
+    pattern_fn: fn(usize) -> Vec<i32>,
+) {
+    // A user may implement Ord incorrectly for a type or violate it by calling sort_by with a
+    // comparison function that violates Ord with the orderings it returns. Even under such
+    // circumstances the input must retain its original set of elements.
+
+    // Ord implies a strict total order see https://en.wikipedia.org/wiki/Total_order.
+
+    // Generating random numbers with miri is quite expensive.
+    let random_orderings_len = if cfg!(miri) { 200 } else { 10_000 };
+
+    // Make sure we get a good distribution of random orderings, that are repeatable with the seed.
+    // Just using random_uniform with the same len and range will always yield the same value.
+    let random_orderings = patterns::random_uniform(random_orderings_len, 0..2);
+
+    let get_random_0_1_or_2 = |random_idx: &mut usize| {
+        let ridx = *random_idx;
+        *random_idx += 1;
+        if ridx + 1 == random_orderings.len() {
+            *random_idx = 0;
+        }
+
+        random_orderings[ridx] as usize
+    };
+
+    let mut random_idx_a = 0;
+    let mut random_idx_b = 0;
+    let mut random_idx_c = 0;
+
+    let mut last_element_a = -1;
+    let mut last_element_b = -1;
+
+    let mut rand_counter_b = 0;
+    let mut rand_counter_c = 0;
+
+    let mut streak_counter_a = 0;
+    let mut streak_counter_b = 0;
+
+    // Examples, a = 3, b = 5, c = 9.
+    // Correct Ord -> 10010 | is_less(a, b) is_less(a, a) is_less(b, a) is_less(a, c) is_less(c, a)
+    let mut invalid_ord_comp_functions: Vec<Box<dyn FnMut(&T, &T) -> Ordering>> = vec![
+        Box::new(|_a, _b| -> Ordering {
+            // random
+            // Eg. is_less(3, 5) == true, is_less(3, 5) == false
+
+            let idx = get_random_0_1_or_2(&mut random_idx_a);
+            [Ordering::Less, Ordering::Equal, Ordering::Greater][idx]
+        }),
+        Box::new(|_a, _b| -> Ordering {
+            // everything is less -> 11111
+            Ordering::Less
+        }),
+        Box::new(|_a, _b| -> Ordering {
+            // everything is equal -> 00000
+            Ordering::Equal
+        }),
+        Box::new(|_a, _b| -> Ordering {
+            // everything is greater -> 00000
+            // Eg. is_less(3, 5) == false, is_less(5, 3) == false, is_less(3, 3) == false
+            Ordering::Greater
+        }),
+        Box::new(|a, b| -> Ordering {
+            // equal means less else greater -> 01000
+            if a == b { Ordering::Less } else { Ordering::Greater }
+        }),
+        Box::new(|a, b| -> Ordering {
+            // Transitive breaker. remember last element -> 10001
+            let lea = last_element_a;
+            let leb = last_element_b;
+
+            let a_as_i32 = type_from_fn(a);
+            let b_as_i32 = type_from_fn(b);
+
+            last_element_a = a_as_i32;
+            last_element_b = b_as_i32;
+
+            if a_as_i32 == lea && b_as_i32 != leb { b.cmp(a) } else { a.cmp(b) }
+        }),
+        Box::new(|a, b| -> Ordering {
+            // Sampled random 1% of comparisons are reversed.
+            rand_counter_b += get_random_0_1_or_2(&mut random_idx_b);
+            if rand_counter_b >= 100 {
+                rand_counter_b = 0;
+                b.cmp(a)
+            } else {
+                a.cmp(b)
+            }
+        }),
+        Box::new(|a, b| -> Ordering {
+            // Sampled random 33% of comparisons are reversed.
+            rand_counter_c += get_random_0_1_or_2(&mut random_idx_c);
+            if rand_counter_c >= 3 {
+                rand_counter_c = 0;
+                b.cmp(a)
+            } else {
+                a.cmp(b)
+            }
+        }),
+        Box::new(|a, b| -> Ordering {
+            // STREAK_LEN comparisons yield a.cmp(b) then STREAK_LEN comparisons less. This can
+            // discover bugs that neither, random Ord, or just Less or Greater can find. Because it
+            // can push a pointer further than expected. Random Ord will average out how far a
+            // comparison based pointer travels. Just Less or Greater will be caught by pattern
+            // analysis and never enter interesting code.
+            const STREAK_LEN: usize = 50;
+
+            streak_counter_a += 1;
+            if streak_counter_a <= STREAK_LEN {
+                a.cmp(b)
+            } else {
+                if streak_counter_a == STREAK_LEN * 2 {
+                    streak_counter_a = 0;
+                }
+                Ordering::Less
+            }
+        }),
+        Box::new(|a, b| -> Ordering {
+            // See above.
+            const STREAK_LEN: usize = 50;
+
+            streak_counter_b += 1;
+            if streak_counter_b <= STREAK_LEN {
+                a.cmp(b)
+            } else {
+                if streak_counter_b == STREAK_LEN * 2 {
+                    streak_counter_b = 0;
+                }
+                Ordering::Greater
+            }
+        }),
+    ];
+
+    for comp_func in &mut invalid_ord_comp_functions {
+        let mut test_data: Vec<T> = pattern_fn(len).into_iter().map(type_into_fn).collect();
+        let sum_before: i64 = test_data.iter().map(|x| type_from_fn(x) as i64).sum();
+
+        // It's ok to panic on Ord violation or to complete.
+        // In both cases the original elements must still be present.
+        let _ = panic::catch_unwind(AssertUnwindSafe(|| {
+            <S as Sort>::sort_by(&mut test_data, &mut *comp_func);
+        }));
+
+        // If the sum before and after don't match, it means the set of elements hasn't remained the
+        // same.
+        let sum_after: i64 = test_data.iter().map(|x| type_from_fn(x) as i64).sum();
+        assert_eq!(sum_before, sum_after);
+
+        if cfg!(miri) {
+            // This test is prohibitively expensive in miri, so only run one of the comparison
+            // functions. This test is not expected to yield direct UB, but rather surface potential
+            // UB by showing that the sum is different now.
+            break;
+        }
+    }
+}
+
+gen_sort_test_fns_with_default_patterns_3_ty!(
+    violate_ord_retain_orig_set,
+    violate_ord_retain_orig_set,
+    []
+);
+
+macro_rules! instantiate_sort_test_inner {
+    ($sort_impl:ty, miri_yes, $test_fn_name:ident) => {
+        #[test]
+        fn $test_fn_name() {
+            $crate::sort::tests::$test_fn_name::<$sort_impl>();
+        }
+    };
+    ($sort_impl:ty, miri_no, $test_fn_name:ident) => {
+        #[test]
+        #[cfg_attr(miri, ignore)]
+        fn $test_fn_name() {
+            $crate::sort::tests::$test_fn_name::<$sort_impl>();
+        }
+    };
+}
+
+// Using this construct allows us to get warnings for unused test functions.
+macro_rules! define_instantiate_sort_tests {
+    ($([$miri_use:ident, $test_fn_name:ident]),*,) => {
+        $(pub fn $test_fn_name<S: Sort>() {
+            ${concat($test_fn_name, _impl)}::<S>();
+        })*
+
+
+        macro_rules! instantiate_sort_tests_gen {
+            ($sort_impl:ty) => {
+                $(
+                    instantiate_sort_test_inner!(
+                        $sort_impl,
+                        $miri_use,
+                        $test_fn_name
+                    );
+                )*
+            }
+        }
+    };
+}
+
+// Some tests are not tested with miri to avoid prohibitively long test times. This leaves coverage
+// holes, but the way they are selected should make for relatively small holes. Many properties that
+// can lead to UB are tested directly, for example that the original set of elements is retained
+// even when a panic occurs or Ord is implemented incorrectly.
+define_instantiate_sort_tests!(
+    [miri_yes, basic],
+    [miri_yes, fixed_seed],
+    [miri_yes, fixed_seed_rand_vec_prefix],
+    [miri_yes, int_edge],
+    [miri_yes, sort_vs_sort_by],
+    [miri_yes, correct_i32_random],
+    [miri_yes, correct_i32_random_z1],
+    [miri_yes, correct_i32_random_d2],
+    [miri_yes, correct_i32_random_d20],
+    [miri_yes, correct_i32_random_s95],
+    [miri_yes, correct_i32_ascending],
+    [miri_yes, correct_i32_descending],
+    [miri_yes, correct_i32_saw_mixed],
+    [miri_no, correct_i32_random_d4],
+    [miri_no, correct_i32_random_d8],
+    [miri_no, correct_i32_random_d311],
+    [miri_no, correct_i32_random_d1024],
+    [miri_no, correct_i32_random_z1_03],
+    [miri_no, correct_i32_random_z2],
+    [miri_no, correct_i32_random_s50],
+    [miri_no, correct_i32_narrow],
+    [miri_no, correct_i32_all_equal],
+    [miri_no, correct_i32_saw_mixed_range],
+    [miri_yes, correct_i32_pipe_organ],
+    [miri_no, correct_u64_random],
+    [miri_yes, correct_u64_random_z1],
+    [miri_no, correct_u64_random_d2],
+    [miri_no, correct_u64_random_d20],
+    [miri_no, correct_u64_random_s95],
+    [miri_no, correct_u64_ascending],
+    [miri_no, correct_u64_descending],
+    [miri_no, correct_u64_saw_mixed],
+    [miri_no, correct_u128_random],
+    [miri_yes, correct_u128_random_z1],
+    [miri_no, correct_u128_random_d2],
+    [miri_no, correct_u128_random_d20],
+    [miri_no, correct_u128_random_s95],
+    [miri_no, correct_u128_ascending],
+    [miri_no, correct_u128_descending],
+    [miri_no, correct_u128_saw_mixed],
+    [miri_no, correct_cell_i32_random],
+    [miri_yes, correct_cell_i32_random_z1],
+    [miri_no, correct_cell_i32_random_d2],
+    [miri_no, correct_cell_i32_random_d20],
+    [miri_no, correct_cell_i32_random_s95],
+    [miri_no, correct_cell_i32_ascending],
+    [miri_no, correct_cell_i32_descending],
+    [miri_no, correct_cell_i32_saw_mixed],
+    [miri_no, correct_string_random],
+    [miri_yes, correct_string_random_z1],
+    [miri_no, correct_string_random_d2],
+    [miri_no, correct_string_random_d20],
+    [miri_no, correct_string_random_s95],
+    [miri_no, correct_string_ascending],
+    [miri_no, correct_string_descending],
+    [miri_no, correct_string_saw_mixed],
+    [miri_no, correct_f128_random],
+    [miri_yes, correct_f128_random_z1],
+    [miri_no, correct_f128_random_d2],
+    [miri_no, correct_f128_random_d20],
+    [miri_no, correct_f128_random_s95],
+    [miri_no, correct_f128_ascending],
+    [miri_no, correct_f128_descending],
+    [miri_no, correct_f128_saw_mixed],
+    [miri_no, correct_1k_random],
+    [miri_yes, correct_1k_random_z1],
+    [miri_no, correct_1k_random_d2],
+    [miri_no, correct_1k_random_d20],
+    [miri_no, correct_1k_random_s95],
+    [miri_no, correct_1k_ascending],
+    [miri_no, correct_1k_descending],
+    [miri_no, correct_1k_saw_mixed],
+    [miri_no, correct_dyn_val_random],
+    [miri_yes, correct_dyn_val_random_z1],
+    [miri_no, correct_dyn_val_random_d2],
+    [miri_no, correct_dyn_val_random_d20],
+    [miri_no, correct_dyn_val_random_s95],
+    [miri_no, correct_dyn_val_ascending],
+    [miri_no, correct_dyn_val_descending],
+    [miri_no, correct_dyn_val_saw_mixed],
+    [miri_no, stability_legacy],
+    [miri_no, stability_i32_random],
+    [miri_yes, stability_i32_random_z1],
+    [miri_no, stability_i32_random_d2],
+    [miri_no, stability_i32_random_d20],
+    [miri_no, stability_i32_random_s95],
+    [miri_no, stability_i32_ascending],
+    [miri_no, stability_i32_descending],
+    [miri_no, stability_i32_saw_mixed],
+    [miri_no, stability_cell_i32_random],
+    [miri_yes, stability_cell_i32_random_z1],
+    [miri_no, stability_cell_i32_random_d2],
+    [miri_no, stability_cell_i32_random_d20],
+    [miri_no, stability_cell_i32_random_s95],
+    [miri_no, stability_cell_i32_ascending],
+    [miri_no, stability_cell_i32_descending],
+    [miri_no, stability_cell_i32_saw_mixed],
+    [miri_no, stability_string_random],
+    [miri_yes, stability_string_random_z1],
+    [miri_no, stability_string_random_d2],
+    [miri_no, stability_string_random_d20],
+    [miri_no, stability_string_random_s95],
+    [miri_no, stability_string_ascending],
+    [miri_no, stability_string_descending],
+    [miri_no, stability_string_saw_mixed],
+    [miri_no, observable_is_less_random],
+    [miri_yes, observable_is_less_random_z1],
+    [miri_no, observable_is_less_random_d2],
+    [miri_no, observable_is_less_random_d20],
+    [miri_no, observable_is_less_random_s95],
+    [miri_no, observable_is_less_ascending],
+    [miri_no, observable_is_less_descending],
+    [miri_no, observable_is_less_saw_mixed],
+    [miri_no, panic_retain_orig_set_i32_random],
+    [miri_yes, panic_retain_orig_set_i32_random_z1],
+    [miri_no, panic_retain_orig_set_i32_random_d2],
+    [miri_no, panic_retain_orig_set_i32_random_d20],
+    [miri_no, panic_retain_orig_set_i32_random_s95],
+    [miri_no, panic_retain_orig_set_i32_ascending],
+    [miri_no, panic_retain_orig_set_i32_descending],
+    [miri_no, panic_retain_orig_set_i32_saw_mixed],
+    [miri_no, panic_retain_orig_set_cell_i32_random],
+    [miri_yes, panic_retain_orig_set_cell_i32_random_z1],
+    [miri_no, panic_retain_orig_set_cell_i32_random_d2],
+    [miri_no, panic_retain_orig_set_cell_i32_random_d20],
+    [miri_no, panic_retain_orig_set_cell_i32_random_s95],
+    [miri_no, panic_retain_orig_set_cell_i32_ascending],
+    [miri_no, panic_retain_orig_set_cell_i32_descending],
+    [miri_no, panic_retain_orig_set_cell_i32_saw_mixed],
+    [miri_no, panic_retain_orig_set_string_random],
+    [miri_yes, panic_retain_orig_set_string_random_z1],
+    [miri_no, panic_retain_orig_set_string_random_d2],
+    [miri_no, panic_retain_orig_set_string_random_d20],
+    [miri_no, panic_retain_orig_set_string_random_s95],
+    [miri_no, panic_retain_orig_set_string_ascending],
+    [miri_no, panic_retain_orig_set_string_descending],
+    [miri_no, panic_retain_orig_set_string_saw_mixed],
+    [miri_no, panic_observable_is_less_random],
+    [miri_yes, panic_observable_is_less_random_z1],
+    [miri_no, panic_observable_is_less_random_d2],
+    [miri_no, panic_observable_is_less_random_d20],
+    [miri_no, panic_observable_is_less_random_s95],
+    [miri_no, panic_observable_is_less_ascending],
+    [miri_no, panic_observable_is_less_descending],
+    [miri_no, panic_observable_is_less_saw_mixed],
+    [miri_no, deterministic_i32_random],
+    [miri_yes, deterministic_i32_random_z1],
+    [miri_no, deterministic_i32_random_d2],
+    [miri_no, deterministic_i32_random_d20],
+    [miri_no, deterministic_i32_random_s95],
+    [miri_no, deterministic_i32_ascending],
+    [miri_no, deterministic_i32_descending],
+    [miri_no, deterministic_i32_saw_mixed],
+    [miri_no, deterministic_cell_i32_random],
+    [miri_yes, deterministic_cell_i32_random_z1],
+    [miri_no, deterministic_cell_i32_random_d2],
+    [miri_no, deterministic_cell_i32_random_d20],
+    [miri_no, deterministic_cell_i32_random_s95],
+    [miri_no, deterministic_cell_i32_ascending],
+    [miri_no, deterministic_cell_i32_descending],
+    [miri_no, deterministic_cell_i32_saw_mixed],
+    [miri_no, deterministic_string_random],
+    [miri_yes, deterministic_string_random_z1],
+    [miri_no, deterministic_string_random_d2],
+    [miri_no, deterministic_string_random_d20],
+    [miri_no, deterministic_string_random_s95],
+    [miri_no, deterministic_string_ascending],
+    [miri_no, deterministic_string_descending],
+    [miri_no, deterministic_string_saw_mixed],
+    [miri_no, self_cmp_i32_random],
+    [miri_yes, self_cmp_i32_random_z1],
+    [miri_no, self_cmp_i32_random_d2],
+    [miri_no, self_cmp_i32_random_d20],
+    [miri_no, self_cmp_i32_random_s95],
+    [miri_no, self_cmp_i32_ascending],
+    [miri_no, self_cmp_i32_descending],
+    [miri_no, self_cmp_i32_saw_mixed],
+    [miri_no, self_cmp_cell_i32_random],
+    [miri_yes, self_cmp_cell_i32_random_z1],
+    [miri_no, self_cmp_cell_i32_random_d2],
+    [miri_no, self_cmp_cell_i32_random_d20],
+    [miri_no, self_cmp_cell_i32_random_s95],
+    [miri_no, self_cmp_cell_i32_ascending],
+    [miri_no, self_cmp_cell_i32_descending],
+    [miri_no, self_cmp_cell_i32_saw_mixed],
+    [miri_no, self_cmp_string_random],
+    [miri_yes, self_cmp_string_random_z1],
+    [miri_no, self_cmp_string_random_d2],
+    [miri_no, self_cmp_string_random_d20],
+    [miri_no, self_cmp_string_random_s95],
+    [miri_no, self_cmp_string_ascending],
+    [miri_no, self_cmp_string_descending],
+    [miri_no, self_cmp_string_saw_mixed],
+    [miri_no, violate_ord_retain_orig_set_i32_random],
+    [miri_yes, violate_ord_retain_orig_set_i32_random_z1],
+    [miri_no, violate_ord_retain_orig_set_i32_random_d2],
+    [miri_no, violate_ord_retain_orig_set_i32_random_d20],
+    [miri_no, violate_ord_retain_orig_set_i32_random_s95],
+    [miri_no, violate_ord_retain_orig_set_i32_ascending],
+    [miri_no, violate_ord_retain_orig_set_i32_descending],
+    [miri_no, violate_ord_retain_orig_set_i32_saw_mixed],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_random],
+    [miri_yes, violate_ord_retain_orig_set_cell_i32_random_z1],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_random_d2],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_random_d20],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_random_s95],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_ascending],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_descending],
+    [miri_no, violate_ord_retain_orig_set_cell_i32_saw_mixed],
+    [miri_no, violate_ord_retain_orig_set_string_random],
+    [miri_yes, violate_ord_retain_orig_set_string_random_z1],
+    [miri_no, violate_ord_retain_orig_set_string_random_d2],
+    [miri_no, violate_ord_retain_orig_set_string_random_d20],
+    [miri_no, violate_ord_retain_orig_set_string_random_s95],
+    [miri_no, violate_ord_retain_orig_set_string_ascending],
+    [miri_no, violate_ord_retain_orig_set_string_descending],
+    [miri_no, violate_ord_retain_orig_set_string_saw_mixed],
+);
+
+macro_rules! instantiate_sort_tests {
+    ($sort_impl:ty) => {
+        instantiate_sort_tests_gen!($sort_impl);
+    };
+}
+
+mod unstable {
+    struct SortImpl {}
+
+    impl crate::sort::Sort for SortImpl {
+        fn name() -> String {
+            "rust_std_unstable".into()
+        }
+
+        fn sort<T>(v: &mut [T])
+        where
+            T: Ord,
+        {
+            v.sort_unstable();
+        }
+
+        fn sort_by<T, F>(v: &mut [T], mut compare: F)
+        where
+            F: FnMut(&T, &T) -> std::cmp::Ordering,
+        {
+            v.sort_unstable_by(|a, b| compare(a, b));
+        }
+    }
+
+    instantiate_sort_tests!(SortImpl);
+}
+
+mod stable {
+    struct SortImpl {}
+
+    impl crate::sort::Sort for SortImpl {
+        fn name() -> String {
+            "rust_std_stable".into()
+        }
+
+        fn sort<T>(v: &mut [T])
+        where
+            T: Ord,
+        {
+            v.sort();
+        }
+
+        fn sort_by<T, F>(v: &mut [T], mut compare: F)
+        where
+            F: FnMut(&T, &T) -> std::cmp::Ordering,
+        {
+            v.sort_by(|a, b| compare(a, b));
+        }
+    }
+
+    instantiate_sort_tests!(SortImpl);
+}
diff --git a/library/alloc/tests/sort/zipf.rs b/library/alloc/tests/sort/zipf.rs
new file mode 100644
index 00000000000..cc774ee5c43
--- /dev/null
+++ b/library/alloc/tests/sort/zipf.rs
@@ -0,0 +1,208 @@
+// This module implements a Zipfian distribution generator.
+//
+// Based on https://github.com/jonhoo/rust-zipf.
+
+use rand::Rng;
+
+/// Random number generator that generates Zipf-distributed random numbers using rejection
+/// inversion.
+#[derive(Clone, Copy)]
+pub struct ZipfDistribution {
+    /// Number of elements
+    num_elements: f64,
+    /// Exponent parameter of the distribution
+    exponent: f64,
+    /// `hIntegral(1.5) - 1}`
+    h_integral_x1: f64,
+    /// `hIntegral(num_elements + 0.5)}`
+    h_integral_num_elements: f64,
+    /// `2 - hIntegralInverse(hIntegral(2.5) - h(2)}`
+    s: f64,
+}
+
+impl ZipfDistribution {
+    /// Creates a new [Zipf-distributed](https://en.wikipedia.org/wiki/Zipf's_law)
+    /// random number generator.
+    ///
+    /// Note that both the number of elements and the exponent must be greater than 0.
+    pub fn new(num_elements: usize, exponent: f64) -> Result<Self, ()> {
+        if num_elements == 0 {
+            return Err(());
+        }
+        if exponent <= 0f64 {
+            return Err(());
+        }
+
+        let z = ZipfDistribution {
+            num_elements: num_elements as f64,
+            exponent,
+            h_integral_x1: ZipfDistribution::h_integral(1.5, exponent) - 1f64,
+            h_integral_num_elements: ZipfDistribution::h_integral(
+                num_elements as f64 + 0.5,
+                exponent,
+            ),
+            s: 2f64
+                - ZipfDistribution::h_integral_inv(
+                    ZipfDistribution::h_integral(2.5, exponent)
+                        - ZipfDistribution::h(2f64, exponent),
+                    exponent,
+                ),
+        };
+
+        // populate cache
+
+        Ok(z)
+    }
+}
+
+impl ZipfDistribution {
+    fn next<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
+        // The paper describes an algorithm for exponents larger than 1 (Algorithm ZRI).
+        //
+        // The original method uses
+        //   H(x) = (v + x)^(1 - q) / (1 - q)
+        // as the integral of the hat function.
+        //
+        // This function is undefined for q = 1, which is the reason for the limitation of the
+        // exponent.
+        //
+        // If instead the integral function
+        //   H(x) = ((v + x)^(1 - q) - 1) / (1 - q)
+        // is used, for which a meaningful limit exists for q = 1, the method works for all
+        // positive exponents.
+        //
+        // The following implementation uses v = 0 and generates integral number in the range [1,
+        // num_elements]. This is different to the original method where v is defined to
+        // be positive and numbers are taken from [0, i_max]. This explains why the implementation
+        // looks slightly different.
+
+        let hnum = self.h_integral_num_elements;
+
+        loop {
+            use std::cmp;
+            let u: f64 = hnum + rng.gen::<f64>() * (self.h_integral_x1 - hnum);
+            // u is uniformly distributed in (h_integral_x1, h_integral_num_elements]
+
+            let x: f64 = ZipfDistribution::h_integral_inv(u, self.exponent);
+
+            // Limit k to the range [1, num_elements] if it would be outside
+            // due to numerical inaccuracies.
+            let k64 = x.max(1.0).min(self.num_elements);
+            // float -> integer rounds towards zero, so we add 0.5
+            // to prevent bias towards k == 1
+            let k = cmp::max(1, (k64 + 0.5) as usize);
+
+            // Here, the distribution of k is given by:
+            //
+            //   P(k = 1) = C * (hIntegral(1.5) - h_integral_x1) = C
+            //   P(k = m) = C * (hIntegral(m + 1/2) - hIntegral(m - 1/2)) for m >= 2
+            //
+            // where C = 1 / (h_integral_num_elements - h_integral_x1)
+            if k64 - x <= self.s
+                || u >= ZipfDistribution::h_integral(k64 + 0.5, self.exponent)
+                    - ZipfDistribution::h(k64, self.exponent)
+            {
+                // Case k = 1:
+                //
+                //   The right inequality is always true, because replacing k by 1 gives
+                //   u >= hIntegral(1.5) - h(1) = h_integral_x1 and u is taken from
+                //   (h_integral_x1, h_integral_num_elements].
+                //
+                //   Therefore, the acceptance rate for k = 1 is P(accepted | k = 1) = 1
+                //   and the probability that 1 is returned as random value is
+                //   P(k = 1 and accepted) = P(accepted | k = 1) * P(k = 1) = C = C / 1^exponent
+                //
+                // Case k >= 2:
+                //
+                //   The left inequality (k - x <= s) is just a short cut
+                //   to avoid the more expensive evaluation of the right inequality
+                //   (u >= hIntegral(k + 0.5) - h(k)) in many cases.
+                //
+                //   If the left inequality is true, the right inequality is also true:
+                //     Theorem 2 in the paper is valid for all positive exponents, because
+                //     the requirements h'(x) = -exponent/x^(exponent + 1) < 0 and
+                //     (-1/hInverse'(x))'' = (1+1/exponent) * x^(1/exponent-1) >= 0
+                //     are both fulfilled.
+                //     Therefore, f(x) = x - hIntegralInverse(hIntegral(x + 0.5) - h(x))
+                //     is a non-decreasing function. If k - x <= s holds,
+                //     k - x <= s + f(k) - f(2) is obviously also true which is equivalent to
+                //     -x <= -hIntegralInverse(hIntegral(k + 0.5) - h(k)),
+                //     -hIntegralInverse(u) <= -hIntegralInverse(hIntegral(k + 0.5) - h(k)),
+                //     and finally u >= hIntegral(k + 0.5) - h(k).
+                //
+                //   Hence, the right inequality determines the acceptance rate:
+                //   P(accepted | k = m) = h(m) / (hIntegrated(m+1/2) - hIntegrated(m-1/2))
+                //   The probability that m is returned is given by
+                //   P(k = m and accepted) = P(accepted | k = m) * P(k = m)
+                //                         = C * h(m) = C / m^exponent.
+                //
+                // In both cases the probabilities are proportional to the probability mass
+                // function of the Zipf distribution.
+
+                return k;
+            }
+        }
+    }
+}
+
+impl rand::distributions::Distribution<usize> for ZipfDistribution {
+    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
+        self.next(rng)
+    }
+}
+
+use std::fmt;
+impl fmt::Debug for ZipfDistribution {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        f.debug_struct("ZipfDistribution")
+            .field("e", &self.exponent)
+            .field("n", &self.num_elements)
+            .finish()
+    }
+}
+
+impl ZipfDistribution {
+    /// Computes `H(x)`, defined as
+    ///
+    ///  - `(x^(1 - exponent) - 1) / (1 - exponent)`, if `exponent != 1`
+    ///  - `log(x)`, if `exponent == 1`
+    ///
+    /// `H(x)` is an integral function of `h(x)`, the derivative of `H(x)` is `h(x)`.
+    fn h_integral(x: f64, exponent: f64) -> f64 {
+        let log_x = x.ln();
+        helper2((1f64 - exponent) * log_x) * log_x
+    }
+
+    /// Computes `h(x) = 1 / x^exponent`
+    fn h(x: f64, exponent: f64) -> f64 {
+        (-exponent * x.ln()).exp()
+    }
+
+    /// The inverse function of `H(x)`.
+    /// Returns the `y` for which `H(y) = x`.
+    fn h_integral_inv(x: f64, exponent: f64) -> f64 {
+        let mut t: f64 = x * (1f64 - exponent);
+        if t < -1f64 {
+            // Limit value to the range [-1, +inf).
+            // t could be smaller than -1 in some rare cases due to numerical errors.
+            t = -1f64;
+        }
+        (helper1(t) * x).exp()
+    }
+}
+
+/// Helper function that calculates `log(1 + x) / x`.
+/// A Taylor series expansion is used, if x is close to 0.
+fn helper1(x: f64) -> f64 {
+    if x.abs() > 1e-8 { x.ln_1p() / x } else { 1f64 - x * (0.5 - x * (1.0 / 3.0 - 0.25 * x)) }
+}
+
+/// Helper function to calculate `(exp(x) - 1) / x`.
+/// A Taylor series expansion is used, if x is close to 0.
+fn helper2(x: f64) -> f64 {
+    if x.abs() > 1e-8 {
+        x.exp_m1() / x
+    } else {
+        1f64 + x * 0.5 * (1f64 + x * 1.0 / 3.0 * (1f64 + 0.25 * x))
+    }
+}
diff --git a/library/alloc/tests/vec.rs b/library/alloc/tests/vec.rs
index f508a3e4c22..0f27fdff3e1 100644
--- a/library/alloc/tests/vec.rs
+++ b/library/alloc/tests/vec.rs
@@ -1288,7 +1288,7 @@ fn test_from_iter_specialization_panic_during_iteration_drops() {
 #[test]
 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
 // FIXME(static_mut_refs): Do not allow `static_mut_refs` lint
-#[cfg_attr(not(bootstrap), allow(static_mut_refs))]
+#[allow(static_mut_refs)]
 fn test_from_iter_specialization_panic_during_drop_doesnt_leak() {
     static mut DROP_COUNTER_OLD: [usize; 5] = [0; 5];
     static mut DROP_COUNTER_NEW: [usize; 2] = [0; 2];