4 files changed, 231 insertions, 0 deletions
diff --git a/library/alloc/src/testing/crash_test.rs b/library/alloc/src/testing/crash_test.rs
new file mode 100644
index 000000000..bcf5f5f72
--- /dev/null
+++ b/library/alloc/src/testing/crash_test.rs
@@ -0,0 +1,119 @@
+// We avoid relying on anything else in the crate, apart from the `Debug` trait.
+use crate::fmt::Debug;
+use std::cmp::Ordering;
+use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
+
+/// 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 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 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 fn spawn(&self, panic: Panic) -> Instance<'_> {
+        Instance { origin: self, panic }
+    }
+
+    /// Returns how many times instances of the dummy have been cloned.
+    pub fn cloned(&self) -> usize {
+        self.cloned.load(SeqCst)
+    }
+
+    /// Returns how many times instances of the dummy have been dropped.
+    pub fn dropped(&self) -> usize {
+        self.dropped.load(SeqCst)
+    }
+
+    /// Returns how many times instances of the dummy have had their `query` member invoked.
+    pub fn queried(&self) -> usize {
+        self.queried.load(SeqCst)
+    }
+}
+
+#[derive(Debug)]
+pub struct Instance<'a> {
+    origin: &'a CrashTestDummy,
+    panic: Panic,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum Panic {
+    Never,
+    InClone,
+    InDrop,
+    InQuery,
+}
+
+impl Instance<'_> {
+    pub fn id(&self) -> usize {
+        self.origin.id
+    }
+
+    /// Some anonymous query, the result of which is already given.
+    pub 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/alloc/src/testing/mod.rs b/library/alloc/src/testing/mod.rs
new file mode 100644
index 000000000..7a094f8a5
--- /dev/null
+++ b/library/alloc/src/testing/mod.rs
@@ -0,0 +1,3 @@
+pub mod crash_test;
+pub mod ord_chaos;
+pub mod rng;
diff --git a/library/alloc/src/testing/ord_chaos.rs b/library/alloc/src/testing/ord_chaos.rs
new file mode 100644
index 000000000..96ce7c157
--- /dev/null
+++ b/library/alloc/src/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 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 struct Governor {
+    flipped: Cell<bool>,
+}
+
+impl Governor {
+    pub fn new() -> Self {
+        Governor { flipped: Cell::new(false) }
+    }
+
+    pub 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 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/alloc/src/testing/rng.rs b/library/alloc/src/testing/rng.rs
new file mode 100644
index 000000000..ecf543bee
--- /dev/null
+++ b/library/alloc/src/testing/rng.rs
@@ -0,0 +1,28 @@
+/// XorShiftRng
+pub struct DeterministicRng {
+    count: usize,
+    x: u32,
+    y: u32,
+    z: u32,
+    w: u32,
+}
+
+impl DeterministicRng {
+    pub fn new() -> Self {
+        DeterministicRng { count: 0, x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb }
+    }
+
+    /// Guarantees that each returned number is unique.
+    pub 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
+    }
+}