diff options
Diffstat (limited to 'library/alloc/src/slice')
| -rw-r--r-- | library/alloc/src/slice/tests.rs | 359 |
1 files changed, 359 insertions, 0 deletions
diff --git a/library/alloc/src/slice/tests.rs b/library/alloc/src/slice/tests.rs new file mode 100644 index 00000000000..f674530aaa5 --- /dev/null +++ b/library/alloc/src/slice/tests.rs @@ -0,0 +1,359 @@ +use crate::borrow::ToOwned; +use crate::rc::Rc; +use crate::string::ToString; +use crate::test_helpers::test_rng; +use crate::vec::Vec; + +use core::cell::Cell; +use core::cmp::Ordering::{self, Equal, Greater, Less}; +use core::convert::identity; +use core::fmt; +use core::mem; +use core::sync::atomic::{AtomicUsize, Ordering::Relaxed}; +use rand::{distributions::Standard, prelude::*, Rng, RngCore}; +use std::panic; + +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 _ = std::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 +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 +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])); + } + } + } + + // Sort using a completely random comparison function. + // This will reorder the elements *somehow*, but won't panic. + let mut v = [0; 500]; + for i in 0..v.len() { + v[i] = i as i32; + } + v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap()); + v.sort(); + for i in 0..v.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])); + } + } +} |