diff options
Diffstat (limited to '')
4 files changed, 231 insertions, 0 deletions
diff --git a/library/alloc/src/collections/btree/testing/crash_test.rs b/library/alloc/src/collections/btree/testing/crash_test.rs new file mode 100644 index 000000000..bcf5f5f72 --- /dev/null +++ b/library/alloc/src/collections/btree/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/collections/btree/testing/mod.rs b/library/alloc/src/collections/btree/testing/mod.rs new file mode 100644 index 000000000..7a094f8a5 --- /dev/null +++ b/library/alloc/src/collections/btree/testing/mod.rs @@ -0,0 +1,3 @@ +pub mod crash_test; +pub mod ord_chaos; +pub mod rng; diff --git a/library/alloc/src/collections/btree/testing/ord_chaos.rs b/library/alloc/src/collections/btree/testing/ord_chaos.rs new file mode 100644 index 000000000..96ce7c157 --- /dev/null +++ b/library/alloc/src/collections/btree/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/collections/btree/testing/rng.rs b/library/alloc/src/collections/btree/testing/rng.rs new file mode 100644 index 000000000..ecf543bee --- /dev/null +++ b/library/alloc/src/collections/btree/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 + } +} |