path: root/library/alloc/src/slice/tests.rs

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