1 files changed, 170 insertions, 0 deletions
diff --git a/third_party/rust/rayon/src/slice/test.rs b/third_party/rust/rayon/src/slice/test.rs
new file mode 100644
index 0000000000..f74ca0f743
--- /dev/null
+++ b/third_party/rust/rayon/src/slice/test.rs
@@ -0,0 +1,170 @@
+#![cfg(test)]
+
+use crate::prelude::*;
+use rand::distributions::Uniform;
+use rand::seq::SliceRandom;
+use rand::{thread_rng, Rng};
+use std::cmp::Ordering::{Equal, Greater, Less};
+
+macro_rules! sort {
+    ($f:ident, $name:ident) => {
+        #[test]
+        fn $name() {
+            let rng = &mut thread_rng();
+
+            for len in (0..25).chain(500..501) {
+                for &modulus in &[5, 10, 100] {
+                    let dist = Uniform::new(0, modulus);
+                    for _ in 0..100 {
+                        let v: Vec<i32> = rng.sample_iter(&dist).take(len).collect();
+
+                        // Test sort using `<` operator.
+                        let mut tmp = v.clone();
+                        tmp.$f(|a, b| a.cmp(b));
+                        assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
+
+                        // Test sort using `>` operator.
+                        let mut tmp = v.clone();
+                        tmp.$f(|a, b| b.cmp(a));
+                        assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
+                    }
+                }
+            }
+
+            // Test sort with many duplicates.
+            for &len in &[1_000, 10_000, 100_000] {
+                for &modulus in &[5, 10, 100, 10_000] {
+                    let dist = Uniform::new(0, modulus);
+                    let mut v: Vec<i32> = rng.sample_iter(&dist).take(len).collect();
+
+                    v.$f(|a, b| a.cmp(b));
+                    assert!(v.windows(2).all(|w| w[0] <= w[1]));
+                }
+            }
+
+            // Test sort with many pre-sorted runs.
+            for &len in &[1_000, 10_000, 100_000] {
+                let len_dist = Uniform::new(0, len);
+                for &modulus in &[5, 10, 1000, 50_000] {
+                    let dist = Uniform::new(0, modulus);
+                    let mut v: Vec<i32> = rng.sample_iter(&dist).take(len).collect();
+
+                    v.sort();
+                    v.reverse();
+
+                    for _ in 0..5 {
+                        let a = rng.sample(&len_dist);
+                        let b = rng.sample(&len_dist);
+                        if a < b {
+                            v[a..b].reverse();
+                        } else {
+                            v.swap(a, b);
+                        }
+                    }
+
+                    v.$f(|a, b| a.cmp(b));
+                    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: Vec<_> = (0..100).collect();
+            v.$f(|_, _| *[Less, Equal, Greater].choose(&mut thread_rng()).unwrap());
+            v.$f(|a, b| a.cmp(b));
+            for i in 0..v.len() {
+                assert_eq!(v[i], i);
+            }
+
+            // Should not panic.
+            [0i32; 0].$f(|a, b| a.cmp(b));
+            [(); 10].$f(|a, b| a.cmp(b));
+            [(); 100].$f(|a, b| a.cmp(b));
+
+            let mut v = [0xDEAD_BEEFu64];
+            v.$f(|a, b| a.cmp(b));
+            assert!(v == [0xDEAD_BEEF]);
+        }
+    };
+}
+
+sort!(par_sort_by, test_par_sort);
+sort!(par_sort_unstable_by, test_par_sort_unstable);
+
+#[test]
+fn test_par_sort_stability() {
+    for len in (2..25).chain(500..510).chain(50_000..50_010) {
+        for _ in 0..10 {
+            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 mut rng = thread_rng();
+            let mut v: Vec<_> = (0..len)
+                .map(|_| {
+                    let n: usize = rng.gen_range(0..10);
+                    counts[n] += 1;
+                    (n, counts[n])
+                })
+                .collect();
+
+            // Only sort on the first element, so an unstable sort
+            // may mix up the counts.
+            v.par_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]));
+        }
+    }
+}
+
+#[test]
+fn test_par_chunks_exact_remainder() {
+    let v: &[i32] = &[0, 1, 2, 3, 4];
+    let c = v.par_chunks_exact(2);
+    assert_eq!(c.remainder(), &[4]);
+    assert_eq!(c.len(), 2);
+}
+
+#[test]
+fn test_par_chunks_exact_mut_remainder() {
+    let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
+    let mut c = v.par_chunks_exact_mut(2);
+    assert_eq!(c.remainder(), &[4]);
+    assert_eq!(c.len(), 2);
+    assert_eq!(c.into_remainder(), &[4]);
+
+    let mut c = v.par_chunks_exact_mut(2);
+    assert_eq!(c.take_remainder(), &[4]);
+    assert_eq!(c.take_remainder(), &[]);
+    assert_eq!(c.len(), 2);
+}
+
+#[test]
+fn test_par_rchunks_exact_remainder() {
+    let v: &[i32] = &[0, 1, 2, 3, 4];
+    let c = v.par_rchunks_exact(2);
+    assert_eq!(c.remainder(), &[0]);
+    assert_eq!(c.len(), 2);
+}
+
+#[test]
+fn test_par_rchunks_exact_mut_remainder() {
+    let v: &mut [i32] = &mut [0, 1, 2, 3, 4];
+    let mut c = v.par_rchunks_exact_mut(2);
+    assert_eq!(c.remainder(), &[0]);
+    assert_eq!(c.len(), 2);
+    assert_eq!(c.into_remainder(), &[0]);
+
+    let mut c = v.par_rchunks_exact_mut(2);
+    assert_eq!(c.take_remainder(), &[0]);
+    assert_eq!(c.take_remainder(), &[]);
+    assert_eq!(c.len(), 2);
+}