Fully test the alloc crate through alloctests

For the tests that make use of internal implementation details, we
include the module to test using #[path] in alloctests now.

6 files changed, 325 insertions, 3 deletions

diff --git a/library/alloctests/Cargo.toml b/library/alloctests/Cargo.toml
index f1a783b1e22..306375f5f01 100644
--- a/library/alloctests/Cargo.toml
+++ b/library/alloctests/Cargo.toml
@@ -10,8 +10,9 @@ edition = "2021"
 
 [lib]
 path = "lib.rs"
-test = false
-bench = false
+test = true
+bench = true
+doc = false
 
 [dev-dependencies]
 rand = { version = "0.9.0", default-features = false, features = ["alloc"] }
diff --git a/library/alloctests/lib.rs b/library/alloctests/lib.rs
index b49208cd4eb..0b5aa2c575d 100644
--- a/library/alloctests/lib.rs
+++ b/library/alloctests/lib.rs
@@ -1 +1,90 @@
-// Intentionally left empty.
+#![cfg(test)]
+#![allow(unused_attributes)]
+#![unstable(feature = "alloctests", issue = "none")]
+#![no_std]
+// Lints:
+#![deny(unsafe_op_in_unsafe_fn)]
+#![warn(deprecated_in_future)]
+#![warn(missing_debug_implementations)]
+#![allow(explicit_outlives_requirements)]
+#![allow(internal_features)]
+#![allow(rustdoc::redundant_explicit_links)]
+#![warn(rustdoc::unescaped_backticks)]
+#![deny(ffi_unwind_calls)]
+//
+// Library features:
+// tidy-alphabetical-start
+#![feature(alloc_layout_extra)]
+#![feature(allocator_api)]
+#![feature(array_into_iter_constructors)]
+#![feature(assert_matches)]
+#![feature(core_intrinsics)]
+#![feature(exact_size_is_empty)]
+#![feature(extend_one)]
+#![feature(extend_one_unchecked)]
+#![feature(hasher_prefixfree_extras)]
+#![feature(inplace_iteration)]
+#![feature(iter_advance_by)]
+#![feature(iter_next_chunk)]
+#![feature(maybe_uninit_slice)]
+#![feature(maybe_uninit_uninit_array_transpose)]
+#![feature(ptr_internals)]
+#![feature(sized_type_properties)]
+#![feature(slice_iter_mut_as_mut_slice)]
+#![feature(slice_ptr_get)]
+#![feature(slice_range)]
+#![feature(std_internals)]
+#![feature(temporary_niche_types)]
+#![feature(trusted_fused)]
+#![feature(trusted_len)]
+#![feature(trusted_random_access)]
+#![feature(try_reserve_kind)]
+#![feature(try_trait_v2)]
+// tidy-alphabetical-end
+//
+// Language features:
+// tidy-alphabetical-start
+#![feature(cfg_sanitize)]
+#![feature(dropck_eyepatch)]
+#![feature(lang_items)]
+#![feature(min_specialization)]
+#![feature(negative_impls)]
+#![feature(never_type)]
+#![feature(optimize_attribute)]
+#![feature(rustc_allow_const_fn_unstable)]
+#![feature(rustc_attrs)]
+#![feature(staged_api)]
+#![feature(test)]
+#![rustc_preserve_ub_checks]
+// tidy-alphabetical-end
+
+// Allow testing this library
+extern crate alloc as realalloc;
+#[macro_use]
+extern crate std;
+#[cfg(test)]
+extern crate test;
+mod testing;
+use realalloc::*;
+
+#[path = "../alloc/src/collections/mod.rs"]
+mod collections;
+
+#[path = "../alloc/src/raw_vec/mod.rs"]
+mod raw_vec;
+
+#[allow(dead_code)] // Not used in all configurations
+pub(crate) mod test_helpers {
+    /// Copied from `std::test_helpers::test_rng`, since these tests rely on the
+    /// seed not being the same for every RNG invocation too.
+    pub(crate) fn test_rng() -> rand_xorshift::XorShiftRng {
+        use std::hash::{BuildHasher, Hash, Hasher};
+        let mut hasher = std::hash::RandomState::new().build_hasher();
+        std::panic::Location::caller().hash(&mut hasher);
+        let hc64 = hasher.finish();
+        let seed_vec =
+            hc64.to_le_bytes().into_iter().chain(0u8..8).collect::<crate::vec::Vec<u8>>();
+        let seed: [u8; 16] = seed_vec.as_slice().try_into().unwrap();
+        rand::SeedableRng::from_seed(seed)
+    }
+}
diff --git a/library/alloctests/testing/crash_test.rs b/library/alloctests/testing/crash_test.rs
new file mode 100644
index 00000000000..8e00e4f41e5
--- /dev/null
+++ b/library/alloctests/testing/crash_test.rs
@@ -0,0 +1,120 @@
+use std::cmp::Ordering;
+use std::sync::atomic::AtomicUsize;
+use std::sync::atomic::Ordering::SeqCst;
+
+use crate::fmt::Debug; // the `Debug` trait is the only thing we use from `crate::fmt`
+
+/// A blueprint for crash test dummy instances that monitor particular events.
+/// Some instances may be configured to panic at some point.
+/// Events are `clone`, `drop` or some anonymous `query`.
+///
+/// Crash test dummies are identified and ordered by an id, so they can be used
+/// as keys in a BTreeMap.
+#[derive(Debug)]
+pub(crate) struct CrashTestDummy {
+    pub id: usize,
+    cloned: AtomicUsize,
+    dropped: AtomicUsize,
+    queried: AtomicUsize,
+}
+
+impl CrashTestDummy {
+    /// Creates a crash test dummy design. The `id` determines order and equality of instances.
+    pub(crate) fn new(id: usize) -> CrashTestDummy {
+        CrashTestDummy {
+            id,
+            cloned: AtomicUsize::new(0),
+            dropped: AtomicUsize::new(0),
+            queried: AtomicUsize::new(0),
+        }
+    }
+
+    /// Creates an instance of a crash test dummy that records what events it experiences
+    /// and optionally panics.
+    pub(crate) fn spawn(&self, panic: Panic) -> Instance<'_> {
+        Instance { origin: self, panic }
+    }
+
+    /// Returns how many times instances of the dummy have been cloned.
+    pub(crate) fn cloned(&self) -> usize {
+        self.cloned.load(SeqCst)
+    }
+
+    /// Returns how many times instances of the dummy have been dropped.
+    pub(crate) fn dropped(&self) -> usize {
+        self.dropped.load(SeqCst)
+    }
+
+    /// Returns how many times instances of the dummy have had their `query` member invoked.
+    pub(crate) fn queried(&self) -> usize {
+        self.queried.load(SeqCst)
+    }
+}
+
+#[derive(Debug)]
+pub(crate) struct Instance<'a> {
+    origin: &'a CrashTestDummy,
+    panic: Panic,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Panic {
+    Never,
+    InClone,
+    InDrop,
+    InQuery,
+}
+
+impl Instance<'_> {
+    pub(crate) fn id(&self) -> usize {
+        self.origin.id
+    }
+
+    /// Some anonymous query, the result of which is already given.
+    pub(crate) fn query<R>(&self, result: R) -> R {
+        self.origin.queried.fetch_add(1, SeqCst);
+        if self.panic == Panic::InQuery {
+            panic!("panic in `query`");
+        }
+        result
+    }
+}
+
+impl Clone for Instance<'_> {
+    fn clone(&self) -> Self {
+        self.origin.cloned.fetch_add(1, SeqCst);
+        if self.panic == Panic::InClone {
+            panic!("panic in `clone`");
+        }
+        Self { origin: self.origin, panic: Panic::Never }
+    }
+}
+
+impl Drop for Instance<'_> {
+    fn drop(&mut self) {
+        self.origin.dropped.fetch_add(1, SeqCst);
+        if self.panic == Panic::InDrop {
+            panic!("panic in `drop`");
+        }
+    }
+}
+
+impl PartialOrd for Instance<'_> {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.id().partial_cmp(&other.id())
+    }
+}
+
+impl Ord for Instance<'_> {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.id().cmp(&other.id())
+    }
+}
+
+impl PartialEq for Instance<'_> {
+    fn eq(&self, other: &Self) -> bool {
+        self.id().eq(&other.id())
+    }
+}
+
+impl Eq for Instance<'_> {}
diff --git a/library/alloctests/testing/mod.rs b/library/alloctests/testing/mod.rs
new file mode 100644
index 00000000000..c8457daf93e
--- /dev/null
+++ b/library/alloctests/testing/mod.rs
@@ -0,0 +1,3 @@
+pub(crate) mod crash_test;
+pub(crate) mod ord_chaos;
+pub(crate) mod rng;
diff --git a/library/alloctests/testing/ord_chaos.rs b/library/alloctests/testing/ord_chaos.rs
new file mode 100644
index 00000000000..55e1ae5e3de
--- /dev/null
+++ b/library/alloctests/testing/ord_chaos.rs
@@ -0,0 +1,81 @@
+use std::cell::Cell;
+use std::cmp::Ordering::{self, *};
+use std::ptr;
+
+// Minimal type with an `Ord` implementation violating transitivity.
+#[derive(Debug)]
+pub(crate) enum Cyclic3 {
+    A,
+    B,
+    C,
+}
+use Cyclic3::*;
+
+impl PartialOrd for Cyclic3 {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for Cyclic3 {
+    fn cmp(&self, other: &Self) -> Ordering {
+        match (self, other) {
+            (A, A) | (B, B) | (C, C) => Equal,
+            (A, B) | (B, C) | (C, A) => Less,
+            (A, C) | (B, A) | (C, B) => Greater,
+        }
+    }
+}
+
+impl PartialEq for Cyclic3 {
+    fn eq(&self, other: &Self) -> bool {
+        self.cmp(&other) == Equal
+    }
+}
+
+impl Eq for Cyclic3 {}
+
+// Controls the ordering of values wrapped by `Governed`.
+#[derive(Debug)]
+pub(crate) struct Governor {
+    flipped: Cell<bool>,
+}
+
+impl Governor {
+    pub(crate) fn new() -> Self {
+        Governor { flipped: Cell::new(false) }
+    }
+
+    pub(crate) fn flip(&self) {
+        self.flipped.set(!self.flipped.get());
+    }
+}
+
+// Type with an `Ord` implementation that forms a total order at any moment
+// (assuming that `T` respects total order), but can suddenly be made to invert
+// that total order.
+#[derive(Debug)]
+pub(crate) struct Governed<'a, T>(pub T, pub &'a Governor);
+
+impl<T: Ord> PartialOrd for Governed<'_, T> {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl<T: Ord> Ord for Governed<'_, T> {
+    fn cmp(&self, other: &Self) -> Ordering {
+        assert!(ptr::eq(self.1, other.1));
+        let ord = self.0.cmp(&other.0);
+        if self.1.flipped.get() { ord.reverse() } else { ord }
+    }
+}
+
+impl<T: PartialEq> PartialEq for Governed<'_, T> {
+    fn eq(&self, other: &Self) -> bool {
+        assert!(ptr::eq(self.1, other.1));
+        self.0.eq(&other.0)
+    }
+}
+
+impl<T: Eq> Eq for Governed<'_, T> {}
diff --git a/library/alloctests/testing/rng.rs b/library/alloctests/testing/rng.rs
new file mode 100644
index 00000000000..77d3348f38a
--- /dev/null
+++ b/library/alloctests/testing/rng.rs
@@ -0,0 +1,28 @@
+/// XorShiftRng
+pub(crate) struct DeterministicRng {
+    count: usize,
+    x: u32,
+    y: u32,
+    z: u32,
+    w: u32,
+}
+
+impl DeterministicRng {
+    pub(crate) fn new() -> Self {
+        DeterministicRng { count: 0, x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb }
+    }
+
+    /// Guarantees that each returned number is unique.
+    pub(crate) fn next(&mut self) -> u32 {
+        self.count += 1;
+        assert!(self.count <= 70029);
+        let x = self.x;
+        let t = x ^ (x << 11);
+        self.x = self.y;
+        self.y = self.z;
+        self.z = self.w;
+        let w_ = self.w;
+        self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8));
+        self.w
+    }
+}