Implement #85440

13 files changed, 186 insertions, 14 deletions

diff --git a/library/test/src/cli.rs b/library/test/src/cli.rs
index 84874a2d225..e26b9101011 100644
--- a/library/test/src/cli.rs
+++ b/library/test/src/cli.rs
@@ -21,6 +21,8 @@ pub struct TestOpts {
     pub nocapture: bool,
     pub color: ColorConfig,
     pub format: OutputFormat,
+    pub shuffle: bool,
+    pub shuffle_seed: Option<u64>,
     pub test_threads: Option<usize>,
     pub skip: Vec<String>,
     pub time_options: Option<TestTimeOptions>,
@@ -138,6 +140,13 @@ fn optgroups() -> getopts::Options {
 
             `CRITICAL_TIME` here means the limit that should not be exceeded by test.
             ",
+        )
+        .optflag("", "shuffle", "Run tests in random order")
+        .optopt(
+            "",
+            "shuffle-seed",
+            "Run tests in random order; seed the random number generator with SEED",
+            "SEED",
         );
     opts
 }
@@ -155,6 +164,12 @@ By default, all tests are run in parallel. This can be altered with the
 --test-threads flag or the RUST_TEST_THREADS environment variable when running
 tests (set it to 1).
 
+By default, the tests are run in alphabetical order. Use --shuffle or set
+RUST_TEST_SHUFFLE to run the tests in random order. Pass the generated
+"shuffle seed" to --shuffle-seed (or set RUST_TEST_SHUFFLE_SEED) to run the
+tests in the same order again. Note that --shuffle and --shuffle-seed do not
+affect whether the tests are run in parallel.
+
 All tests have their standard output and standard error captured by default.
 This can be overridden with the --nocapture flag or setting RUST_TEST_NOCAPTURE
 environment variable to a value other than "0". Logging is not captured by default.
@@ -218,6 +233,21 @@ macro_rules! unstable_optflag {
     }};
 }
 
+// Gets the option value and checks if unstable features are enabled.
+macro_rules! unstable_optopt {
+    ($matches:ident, $allow_unstable:ident, $option_name:literal) => {{
+        let opt = $matches.opt_str($option_name);
+        if !$allow_unstable && opt.is_some() {
+            return Err(format!(
+                "The \"{}\" option is only accepted on the nightly compiler with -Z unstable-options",
+                $option_name
+            ));
+        }
+
+        opt
+    }};
+}
+
 // Implementation of `parse_opts` that doesn't care about help message
 // and returns a `Result`.
 fn parse_opts_impl(matches: getopts::Matches) -> OptRes {
@@ -227,6 +257,8 @@ fn parse_opts_impl(matches: getopts::Matches) -> OptRes {
     let force_run_in_process = unstable_optflag!(matches, allow_unstable, "force-run-in-process");
     let exclude_should_panic = unstable_optflag!(matches, allow_unstable, "exclude-should-panic");
     let time_options = get_time_options(&matches, allow_unstable)?;
+    let shuffle = get_shuffle(&matches, allow_unstable)?;
+    let shuffle_seed = get_shuffle_seed(&matches, allow_unstable)?;
 
     let include_ignored = matches.opt_present("include-ignored");
     let quiet = matches.opt_present("quiet");
@@ -260,6 +292,8 @@ fn parse_opts_impl(matches: getopts::Matches) -> OptRes {
         nocapture,
         color,
         format,
+        shuffle,
+        shuffle_seed,
         test_threads,
         skip,
         time_options,
@@ -303,6 +337,46 @@ fn get_time_options(
     Ok(options)
 }
 
+fn get_shuffle(matches: &getopts::Matches, allow_unstable: bool) -> OptPartRes<bool> {
+    let mut shuffle = unstable_optflag!(matches, allow_unstable, "shuffle");
+    if !shuffle {
+        shuffle = match env::var("RUST_TEST_SHUFFLE") {
+            Ok(val) => &val != "0",
+            Err(_) => false,
+        };
+    }
+
+    Ok(shuffle)
+}
+
+fn get_shuffle_seed(matches: &getopts::Matches, allow_unstable: bool) -> OptPartRes<Option<u64>> {
+    let mut shuffle_seed = match unstable_optopt!(matches, allow_unstable, "shuffle-seed") {
+        Some(n_str) => match n_str.parse::<u64>() {
+            Ok(n) => Some(n),
+            Err(e) => {
+                return Err(format!(
+                    "argument for --shuffle-seed must be a number \
+                     (error: {})",
+                    e
+                ));
+            }
+        },
+        None => None,
+    };
+
+    if shuffle_seed.is_none() {
+        shuffle_seed = match env::var("RUST_TEST_SHUFFLE_SEED") {
+            Ok(val) => match val.parse::<u64>() {
+                Ok(n) => Some(n),
+                Err(_) => panic!("RUST_TEST_SHUFFLE_SEED is `{}`, should be a number.", val),
+            },
+            Err(_) => None,
+        };
+    }
+
+    Ok(shuffle_seed)
+}
+
 fn get_test_threads(matches: &getopts::Matches) -> OptPartRes<Option<usize>> {
     let test_threads = match matches.opt_str("test-threads") {
         Some(n_str) => match n_str.parse::<usize>() {
diff --git a/library/test/src/console.rs b/library/test/src/console.rs
index 54e30a1fcd0..11c5ab48ed3 100644
--- a/library/test/src/console.rs
+++ b/library/test/src/console.rs
@@ -225,9 +225,9 @@ fn on_test_event(
     out: &mut dyn OutputFormatter,
 ) -> io::Result<()> {
     match (*event).clone() {
-        TestEvent::TeFiltered(ref filtered_tests) => {
+        TestEvent::TeFiltered(ref filtered_tests, shuffle_seed) => {
             st.total = filtered_tests.len();
-            out.write_run_start(filtered_tests.len())?;
+            out.write_run_start(filtered_tests.len(), shuffle_seed)?;
         }
         TestEvent::TeFilteredOut(filtered_out) => {
             st.filtered_out = filtered_out;
diff --git a/library/test/src/event.rs b/library/test/src/event.rs
index 206f3e10e84..6ff1a615eb4 100644
--- a/library/test/src/event.rs
+++ b/library/test/src/event.rs
@@ -28,7 +28,7 @@ impl CompletedTest {
 
 #[derive(Debug, Clone)]
 pub enum TestEvent {
-    TeFiltered(Vec<TestDesc>),
+    TeFiltered(Vec<TestDesc>, Option<u64>),
     TeWait(TestDesc),
     TeResult(CompletedTest),
     TeTimeout(TestDesc),
diff --git a/library/test/src/formatters/json.rs b/library/test/src/formatters/json.rs
index 57b6d1a0202..424d3ef7b41 100644
--- a/library/test/src/formatters/json.rs
+++ b/library/test/src/formatters/json.rs
@@ -60,10 +60,15 @@ impl<T: Write> JsonFormatter<T> {
 }
 
 impl<T: Write> OutputFormatter for JsonFormatter<T> {
-    fn write_run_start(&mut self, test_count: usize) -> io::Result<()> {
+    fn write_run_start(&mut self, test_count: usize, shuffle_seed: Option<u64>) -> io::Result<()> {
+        let shuffle_seed_json = if let Some(shuffle_seed) = shuffle_seed {
+            format!(r#", "shuffle_seed": {}"#, shuffle_seed)
+        } else {
+            String::new()
+        };
         self.writeln_message(&*format!(
-            r#"{{ "type": "suite", "event": "started", "test_count": {} }}"#,
-            test_count
+            r#"{{ "type": "suite", "event": "started", "test_count": {}{} }}"#,
+            test_count, shuffle_seed_json
         ))
     }
 
diff --git a/library/test/src/formatters/junit.rs b/library/test/src/formatters/junit.rs
index aa244807514..f3ae5494906 100644
--- a/library/test/src/formatters/junit.rs
+++ b/library/test/src/formatters/junit.rs
@@ -27,7 +27,11 @@ impl<T: Write> JunitFormatter<T> {
 }
 
 impl<T: Write> OutputFormatter for JunitFormatter<T> {
-    fn write_run_start(&mut self, _test_count: usize) -> io::Result<()> {
+    fn write_run_start(
+        &mut self,
+        _test_count: usize,
+        _shuffle_seed: Option<u64>,
+    ) -> io::Result<()> {
         // We write xml header on run start
         self.write_message(&"<?xml version=\"1.0\" encoding=\"UTF-8\"?>")
     }
diff --git a/library/test/src/formatters/mod.rs b/library/test/src/formatters/mod.rs
index 2e03581b3af..cb80859759f 100644
--- a/library/test/src/formatters/mod.rs
+++ b/library/test/src/formatters/mod.rs
@@ -18,7 +18,7 @@ pub(crate) use self::pretty::PrettyFormatter;
 pub(crate) use self::terse::TerseFormatter;
 
 pub(crate) trait OutputFormatter {
-    fn write_run_start(&mut self, test_count: usize) -> io::Result<()>;
+    fn write_run_start(&mut self, test_count: usize, shuffle_seed: Option<u64>) -> io::Result<()>;
     fn write_test_start(&mut self, desc: &TestDesc) -> io::Result<()>;
     fn write_timeout(&mut self, desc: &TestDesc) -> io::Result<()>;
     fn write_result(
diff --git a/library/test/src/formatters/pretty.rs b/library/test/src/formatters/pretty.rs
index 9cad71e30bd..4a03b4b9147 100644
--- a/library/test/src/formatters/pretty.rs
+++ b/library/test/src/formatters/pretty.rs
@@ -181,9 +181,14 @@ impl<T: Write> PrettyFormatter<T> {
 }
 
 impl<T: Write> OutputFormatter for PrettyFormatter<T> {
-    fn write_run_start(&mut self, test_count: usize) -> io::Result<()> {
+    fn write_run_start(&mut self, test_count: usize, shuffle_seed: Option<u64>) -> io::Result<()> {
         let noun = if test_count != 1 { "tests" } else { "test" };
-        self.write_plain(&format!("\nrunning {} {}\n", test_count, noun))
+        let shuffle_seed_msg = if let Some(shuffle_seed) = shuffle_seed {
+            format!(" (shuffle seed: {})", shuffle_seed)
+        } else {
+            String::new()
+        };
+        self.write_plain(&format!("\nrunning {} {}{}\n", test_count, noun, shuffle_seed_msg))
     }
 
     fn write_test_start(&mut self, desc: &TestDesc) -> io::Result<()> {
diff --git a/library/test/src/formatters/terse.rs b/library/test/src/formatters/terse.rs
index 0c8215c5dac..1f2c410cd96 100644
--- a/library/test/src/formatters/terse.rs
+++ b/library/test/src/formatters/terse.rs
@@ -170,10 +170,15 @@ impl<T: Write> TerseFormatter<T> {
 }
 
 impl<T: Write> OutputFormatter for TerseFormatter<T> {
-    fn write_run_start(&mut self, test_count: usize) -> io::Result<()> {
+    fn write_run_start(&mut self, test_count: usize, shuffle_seed: Option<u64>) -> io::Result<()> {
         self.total_test_count = test_count;
         let noun = if test_count != 1 { "tests" } else { "test" };
-        self.write_plain(&format!("\nrunning {} {}\n", test_count, noun))
+        let shuffle_seed_msg = if let Some(shuffle_seed) = shuffle_seed {
+            format!(" (shuffle seed: {})", shuffle_seed)
+        } else {
+            String::new()
+        };
+        self.write_plain(&format!("\nrunning {} {}{}\n", test_count, noun, shuffle_seed_msg))
     }
 
     fn write_test_start(&mut self, desc: &TestDesc) -> io::Result<()> {
diff --git a/library/test/src/helpers/mod.rs b/library/test/src/helpers/mod.rs
index b7f00c4c86c..049cadf86a6 100644
--- a/library/test/src/helpers/mod.rs
+++ b/library/test/src/helpers/mod.rs
@@ -5,3 +5,4 @@ pub mod concurrency;
 pub mod exit_code;
 pub mod isatty;
 pub mod metrics;
+pub mod shuffle;
diff --git a/library/test/src/helpers/shuffle.rs b/library/test/src/helpers/shuffle.rs
new file mode 100644
index 00000000000..ca503106c55
--- /dev/null
+++ b/library/test/src/helpers/shuffle.rs
@@ -0,0 +1,67 @@
+use crate::cli::TestOpts;
+use crate::types::{TestDescAndFn, TestId, TestName};
+use std::collections::hash_map::DefaultHasher;
+use std::hash::Hasher;
+use std::time::{SystemTime, UNIX_EPOCH};
+
+pub fn get_shuffle_seed(opts: &TestOpts) -> Option<u64> {
+    opts.shuffle_seed.or_else(|| {
+        if opts.shuffle {
+            Some(
+                SystemTime::now()
+                    .duration_since(UNIX_EPOCH)
+                    .expect("Failed to get system time")
+                    .as_nanos() as u64,
+            )
+        } else {
+            None
+        }
+    })
+}
+
+pub fn shuffle_tests(shuffle_seed: u64, tests: &mut [(TestId, TestDescAndFn)]) {
+    let test_names: Vec<&TestName> = tests.iter().map(|test| &test.1.desc.name).collect();
+    let test_names_hash = calculate_hash(&test_names);
+    let mut rng = Rng::new(shuffle_seed, test_names_hash);
+    shuffle(&mut rng, tests);
+}
+
+// `shuffle` is from `rust-analyzer/src/cli/analysis_stats.rs`.
+fn shuffle<T>(rng: &mut Rng, slice: &mut [T]) {
+    for i in 0..slice.len() {
+        randomize_first(rng, &mut slice[i..]);
+    }
+
+    fn randomize_first<T>(rng: &mut Rng, slice: &mut [T]) {
+        assert!(!slice.is_empty());
+        let idx = rng.rand_range(0..slice.len() as u64) as usize;
+        slice.swap(0, idx);
+    }
+}
+
+struct Rng {
+    state: u64,
+    extra: u64,
+}
+
+impl Rng {
+    fn new(seed: u64, extra: u64) -> Self {
+        Self { state: seed, extra }
+    }
+
+    fn rand_range(&mut self, range: core::ops::Range<u64>) -> u64 {
+        self.rand_u64() % (range.end - range.start) + range.start
+    }
+
+    fn rand_u64(&mut self) -> u64 {
+        self.state = calculate_hash(&(self.state, self.extra));
+        self.state
+    }
+}
+
+// `calculate_hash` is from `core/src/hash/mod.rs`.
+fn calculate_hash<T: core::hash::Hash>(t: &T) -> u64 {
+    let mut s = DefaultHasher::new();
+    t.hash(&mut s);
+    s.finish()
+}
diff --git a/library/test/src/lib.rs b/library/test/src/lib.rs
index 251f099f28a..67548819f65 100644
--- a/library/test/src/lib.rs
+++ b/library/test/src/lib.rs
@@ -91,6 +91,7 @@ mod tests;
 use event::{CompletedTest, TestEvent};
 use helpers::concurrency::get_concurrency;
 use helpers::exit_code::get_exit_code;
+use helpers::shuffle::{get_shuffle_seed, shuffle_tests};
 use options::{Concurrent, RunStrategy};
 use test_result::*;
 use time::TestExecTime;
@@ -247,7 +248,9 @@ where
 
     let filtered_descs = filtered_tests.iter().map(|t| t.desc.clone()).collect();
 
-    let event = TestEvent::TeFiltered(filtered_descs);
+    let shuffle_seed = get_shuffle_seed(opts);
+
+    let event = TestEvent::TeFiltered(filtered_descs, shuffle_seed);
     notify_about_test_event(event)?;
 
     let (filtered_tests, filtered_benchs): (Vec<_>, _) = filtered_tests
@@ -259,7 +262,11 @@ where
     let concurrency = opts.test_threads.unwrap_or_else(get_concurrency);
 
     let mut remaining = filtered_tests;
-    remaining.reverse();
+    if let Some(shuffle_seed) = shuffle_seed {
+        shuffle_tests(shuffle_seed, &mut remaining);
+    } else {
+        remaining.reverse();
+    }
     let mut pending = 0;
 
     let (tx, rx) = channel::<CompletedTest>();
diff --git a/library/test/src/tests.rs b/library/test/src/tests.rs
index 794f7277004..7b68b8fbaf8 100644
--- a/library/test/src/tests.rs
+++ b/library/test/src/tests.rs
@@ -45,6 +45,8 @@ impl TestOpts {
             nocapture: false,
             color: AutoColor,
             format: OutputFormat::Pretty,
+            shuffle: false,
+            shuffle_seed: None,
             test_threads: None,
             skip: vec![],
             time_options: None,
diff --git a/src/tools/compiletest/src/main.rs b/src/tools/compiletest/src/main.rs
index 9e655557fd2..d72ed61d134 100644
--- a/src/tools/compiletest/src/main.rs
+++ b/src/tools/compiletest/src/main.rs
@@ -505,6 +505,8 @@ pub fn test_opts(config: &Config) -> test::TestOpts {
             Err(_) => false,
         },
         color: config.color,
+        shuffle: false,
+        shuffle_seed: None,
         test_threads: None,
         skip: vec![],
         list: false,