Port sort-research-rs test suite Rust stdlib tests

This commit is a followup to https://github.com/rust-lang/rust/pull/124032. It
replaces the tests that test the various sort functions in the standard library
with a test-suite developed as part of
https://github.com/Voultapher/sort-research-rs. The current tests suffer a
couple of problems:

- They don't cover important real world patterns that the implementations take
  advantage of and execute special code for.
- The input lengths tested miss out on code paths. For example, important safety
  property tests never reach the quicksort part of the implementation.
- The miri side is often limited to `len <= 20` which means it very thoroughly
  tests the insertion sort, which accounts for 19 out of 1.5k LoC.
- They are split into to core and alloc, causing code duplication and uneven
  coverage.
- The randomness is not repeatable, as it
  relies on `std::hash::RandomState::new().build_hasher()`.

Most of these issues existed before
https://github.com/rust-lang/rust/pull/124032, but they are intensified by it.
One thing that is new and requires additional testing, is that the new sort
implementations specialize based on type properties. For example `Freeze` and
non `Freeze` execute different code paths.

Effectively there are three dimensions that matter:

- Input type
- Input length
- Input pattern

The ported test-suite tests various properties along all three dimensions,
greatly improving test coverage. It side-steps the miri issue by preferring
sampled approaches. For example the test that checks if after a panic the set of
elements is still the original one, doesn't do so for every single possible
panic opportunity but rather it picks one at random, and performs this test
across a range of input length, which varies the panic point across them. This
allows regular execution to easily test inputs of length 10k, and miri execution
up to 100 which covers significantly more code. The randomness used is tied to a
fixed - but random per process execution - seed. This allows for fully
repeatable tests and fuzzer like exploration across multiple runs.

Structure wise, the tests are previously found in the core integration tests for
`sort_unstable` and alloc unit tests for `sort`. The new test-suite was
developed to be a purely black-box approach, which makes integration testing the
better place, because it can't accidentally rely on internal access. Because
unwinding support is required the tests can't be in core, even if the
implementation is, so they are now part of the alloc integration tests. Are
there architectures that can only build and test core and not alloc? If so, do
such platforms require sort testing? For what it's worth the current
implementation state passes miri `--target mips64-unknown-linux-gnuabi64` which
is big endian.

The test-suite also contains tests for properties that were and are given by the
current and previous implementations, and likely relied upon by users but
weren't tested. For example `self_cmp` tests that the two parameters `a` and `b`
passed into the comparison function are never references to the same object,
which if the user is sorting for example a `&mut [Mutex<i32>]` could lead to a
deadlock.

Instead of using the hashed caller location as rand seed, it uses seconds since
unix epoch / 10, which given timestamps in the CI should be reasonably easy to
reproduce, but also allows fuzzer like space exploration.

2 files changed, 10 insertions, 383 deletions

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]));
-        }
-    }
-}