Rollup merge of #99939 - saethlin:pre-sort-tests, r=thomcc,jackh726

Sort tests at compile time, not at startup

Recently, another Miri user was trying to run `cargo miri test` on the crate `iced-x86` with `--features=code_asm,mvex`. This configuration has a startup time of ~18 minutes. That's ~18 minutes before any tests even start to run. The fact that this crate has over 26,000 tests and Miri is slow makes a lot of code which is otherwise a bit sloppy but fine into a huge runtime issue.

Sorting the tests when the test harness is created instead of at startup time knocks just under 4 minutes out of those ~18 minutes. I have ways to remove most of the rest of the startup time, but this change requires coordinating changes of both the compiler and libtest, so I'm sending it separately.

(except for doctests, because there is no compile-time harness)

10 files changed, 130 insertions, 57 deletions

diff --git a/compiler/rustc_builtin_macros/src/test.rs b/compiler/rustc_builtin_macros/src/test.rs
index 705141614e2..fee5d04cdae 100644
--- a/compiler/rustc_builtin_macros/src/test.rs
+++ b/compiler/rustc_builtin_macros/src/test.rs
@@ -36,13 +36,22 @@ pub fn expand_test_case(
     let sp = ecx.with_def_site_ctxt(attr_sp);
     let mut item = anno_item.expect_item();
     item = item.map(|mut item| {
+        let test_path_symbol = Symbol::intern(&item_path(
+            // skip the name of the root module
+            &ecx.current_expansion.module.mod_path[1..],
+            &item.ident,
+        ));
         item.vis = ast::Visibility {
             span: item.vis.span,
             kind: ast::VisibilityKind::Public,
             tokens: None,
         };
         item.ident.span = item.ident.span.with_ctxt(sp.ctxt());
-        item.attrs.push(ecx.attribute(ecx.meta_word(sp, sym::rustc_test_marker)));
+        item.attrs.push(ecx.attribute(attr::mk_name_value_item_str(
+            Ident::new(sym::rustc_test_marker, sp),
+            test_path_symbol,
+            sp,
+        )));
         item
     });
 
@@ -215,6 +224,12 @@ pub fn expand_test_or_bench(
         )
     };
 
+    let test_path_symbol = Symbol::intern(&item_path(
+        // skip the name of the root module
+        &cx.current_expansion.module.mod_path[1..],
+        &item.ident,
+    ));
+
     let mut test_const = cx.item(
         sp,
         Ident::new(item.ident.name, sp),
@@ -224,9 +239,14 @@ pub fn expand_test_or_bench(
                 Ident::new(sym::cfg, attr_sp),
                 vec![attr::mk_nested_word_item(Ident::new(sym::test, attr_sp))],
             )),
-            // #[rustc_test_marker]
-            cx.attribute(cx.meta_word(attr_sp, sym::rustc_test_marker)),
-        ],
+            // #[rustc_test_marker = "test_case_sort_key"]
+            cx.attribute(attr::mk_name_value_item_str(
+                Ident::new(sym::rustc_test_marker, attr_sp),
+                test_path_symbol,
+                attr_sp,
+            )),
+        ]
+        .into(),
         // const $ident: test::TestDescAndFn =
         ast::ItemKind::Const(
             ast::Defaultness::Final,
@@ -250,14 +270,7 @@ pub fn expand_test_or_bench(
                                         cx.expr_call(
                                             sp,
                                             cx.expr_path(test_path("StaticTestName")),
-                                            vec![cx.expr_str(
-                                                sp,
-                                                Symbol::intern(&item_path(
-                                                    // skip the name of the root module
-                                                    &cx.current_expansion.module.mod_path[1..],
-                                                    &item.ident,
-                                                )),
-                                            )],
+                                            vec![cx.expr_str(sp, test_path_symbol)],
                                         ),
                                     ),
                                     // ignore: true | false
diff --git a/compiler/rustc_builtin_macros/src/test_harness.rs b/compiler/rustc_builtin_macros/src/test_harness.rs
index 561ca00c719..b8b8351a36f 100644
--- a/compiler/rustc_builtin_macros/src/test_harness.rs
+++ b/compiler/rustc_builtin_macros/src/test_harness.rs
@@ -18,9 +18,11 @@ use thin_vec::thin_vec;
 
 use std::{iter, mem};
 
+#[derive(Clone)]
 struct Test {
     span: Span,
     ident: Ident,
+    name: Symbol,
 }
 
 struct TestCtxt<'a> {
@@ -120,10 +122,10 @@ impl<'a> MutVisitor for TestHarnessGenerator<'a> {
 
     fn flat_map_item(&mut self, i: P<ast::Item>) -> SmallVec<[P<ast::Item>; 1]> {
         let mut item = i.into_inner();
-        if is_test_case(&self.cx.ext_cx.sess, &item) {
+        if let Some(name) = get_test_name(&self.cx.ext_cx.sess, &item) {
             debug!("this is a test item");
 
-            let test = Test { span: item.span, ident: item.ident };
+            let test = Test { span: item.span, ident: item.ident, name };
             self.tests.push(test);
         }
 
@@ -357,9 +359,12 @@ fn mk_tests_slice(cx: &TestCtxt<'_>, sp: Span) -> P<ast::Expr> {
     debug!("building test vector from {} tests", cx.test_cases.len());
     let ecx = &cx.ext_cx;
 
+    let mut tests = cx.test_cases.clone();
+    tests.sort_by(|a, b| a.name.as_str().cmp(&b.name.as_str()));
+
     ecx.expr_array_ref(
         sp,
-        cx.test_cases
+        tests
             .iter()
             .map(|test| {
                 ecx.expr_addr_of(test.span, ecx.expr_path(ecx.path(test.span, vec![test.ident])))
@@ -368,8 +373,8 @@ fn mk_tests_slice(cx: &TestCtxt<'_>, sp: Span) -> P<ast::Expr> {
     )
 }
 
-fn is_test_case(sess: &Session, i: &ast::Item) -> bool {
-    sess.contains_name(&i.attrs, sym::rustc_test_marker)
+fn get_test_name(sess: &Session, i: &ast::Item) -> Option<Symbol> {
+    sess.first_attr_value_str_by_name(&i.attrs, sym::rustc_test_marker)
 }
 
 fn get_test_runner(
diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs
index afa0f6fcb80..2ead3c2c8d4 100644
--- a/compiler/rustc_feature/src/builtin_attrs.rs
+++ b/compiler/rustc_feature/src/builtin_attrs.rs
@@ -746,7 +746,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
          for reserving for `for<T> From<!> for T` impl"
     ),
     rustc_attr!(
-        rustc_test_marker, Normal, template!(Word), WarnFollowing,
+        rustc_test_marker, Normal, template!(NameValueStr: "name"), WarnFollowing,
         "the `#[rustc_test_marker]` attribute is used internally to track tests",
     ),
     rustc_attr!(
diff --git a/library/test/src/console.rs b/library/test/src/console.rs
index e9dda98966d..b1270c27271 100644
--- a/library/test/src/console.rs
+++ b/library/test/src/console.rs
@@ -147,7 +147,7 @@ pub fn list_tests_console(opts: &TestOpts, tests: Vec<TestDescAndFn>) -> io::Res
     let mut ntest = 0;
     let mut nbench = 0;
 
-    for test in filter_tests(&opts, tests) {
+    for test in filter_tests(&opts, tests).into_iter() {
         use crate::TestFn::*;
 
         let TestDescAndFn { desc: TestDesc { name, .. }, testfn } = test;
diff --git a/library/test/src/lib.rs b/library/test/src/lib.rs
index b1e0bbfc591..4de69455798 100644
--- a/library/test/src/lib.rs
+++ b/library/test/src/lib.rs
@@ -247,7 +247,7 @@ where
     let event = TestEvent::TeFiltered(filtered_descs, shuffle_seed);
     notify_about_test_event(event)?;
 
-    let (filtered_tests, filtered_benchs): (Vec<_>, _) = filtered_tests
+    let (mut filtered_tests, filtered_benchs): (Vec<_>, _) = filtered_tests
         .into_iter()
         .enumerate()
         .map(|(i, e)| (TestId(i), e))
@@ -255,12 +255,12 @@ where
 
     let concurrency = opts.test_threads.unwrap_or_else(get_concurrency);
 
-    let mut remaining = filtered_tests;
     if let Some(shuffle_seed) = shuffle_seed {
-        shuffle_tests(shuffle_seed, &mut remaining);
-    } else {
-        remaining.reverse();
+        shuffle_tests(shuffle_seed, &mut filtered_tests);
     }
+    // Store the tests in a VecDeque so we can efficiently remove the first element to run the
+    // tests in the order they were passed (unless shuffled).
+    let mut remaining = VecDeque::from(filtered_tests);
     let mut pending = 0;
 
     let (tx, rx) = channel::<CompletedTest>();
@@ -300,7 +300,7 @@ where
 
     if concurrency == 1 {
         while !remaining.is_empty() {
-            let (id, test) = remaining.pop().unwrap();
+            let (id, test) = remaining.pop_front().unwrap();
             let event = TestEvent::TeWait(test.desc.clone());
             notify_about_test_event(event)?;
             let join_handle =
@@ -314,7 +314,7 @@ where
     } else {
         while pending > 0 || !remaining.is_empty() {
             while pending < concurrency && !remaining.is_empty() {
-                let (id, test) = remaining.pop().unwrap();
+                let (id, test) = remaining.pop_front().unwrap();
                 let timeout = time::get_default_test_timeout();
                 let desc = test.desc.clone();
 
@@ -426,9 +426,6 @@ pub fn filter_tests(opts: &TestOpts, tests: Vec<TestDescAndFn>) -> Vec<TestDescA
         RunIgnored::No => {}
     }
 
-    // Sort the tests alphabetically
-    filtered.sort_by(|t1, t2| t1.desc.name.as_slice().cmp(t2.desc.name.as_slice()));
-
     filtered
 }
 
diff --git a/library/test/src/tests.rs b/library/test/src/tests.rs
index 278cfb15bb1..b54be64efcf 100644
--- a/library/test/src/tests.rs
+++ b/library/test/src/tests.rs
@@ -611,33 +611,6 @@ fn sample_tests() -> Vec<TestDescAndFn> {
 }
 
 #[test]
-pub fn sort_tests() {
-    let mut opts = TestOpts::new();
-    opts.run_tests = true;
-
-    let tests = sample_tests();
-    let filtered = filter_tests(&opts, tests);
-
-    let expected = vec![
-        "isize::test_pow".to_string(),
-        "isize::test_to_str".to_string(),
-        "sha1::test".to_string(),
-        "test::do_not_run_ignored_tests".to_string(),
-        "test::filter_for_ignored_option".to_string(),
-        "test::first_free_arg_should_be_a_filter".to_string(),
-        "test::ignored_tests_result_in_ignored".to_string(),
-        "test::parse_ignored_flag".to_string(),
-        "test::parse_include_ignored_flag".to_string(),
-        "test::run_include_ignored_option".to_string(),
-        "test::sort_tests".to_string(),
-    ];
-
-    for (a, b) in expected.iter().zip(filtered) {
-        assert_eq!(*a, b.desc.name.to_string());
-    }
-}
-
-#[test]
 pub fn shuffle_tests() {
     let mut opts = TestOpts::new();
     opts.shuffle = true;
diff --git a/src/librustdoc/doctest.rs b/src/librustdoc/doctest.rs
index cb216970c7c..db70029f6ec 100644
--- a/src/librustdoc/doctest.rs
+++ b/src/librustdoc/doctest.rs
@@ -208,12 +208,13 @@ pub(crate) fn run(options: RustdocOptions) -> Result<(), ErrorGuaranteed> {
 pub(crate) fn run_tests(
     mut test_args: Vec<String>,
     nocapture: bool,
-    tests: Vec<test::TestDescAndFn>,
+    mut tests: Vec<test::TestDescAndFn>,
 ) {
     test_args.insert(0, "rustdoctest".to_string());
     if nocapture {
         test_args.push("--nocapture".to_string());
     }
+    tests.sort_by(|a, b| a.desc.name.as_slice().cmp(&b.desc.name.as_slice()));
     test::test_main(&test_args, tests, None);
 }
 
diff --git a/src/test/pretty/tests-are-sorted.pp b/src/test/pretty/tests-are-sorted.pp
new file mode 100644
index 00000000000..15dcd4ed97d
--- /dev/null
+++ b/src/test/pretty/tests-are-sorted.pp
@@ -0,0 +1,69 @@
+#![feature(prelude_import)]
+#![no_std]
+#[prelude_import]
+use ::std::prelude::rust_2015::*;
+#[macro_use]
+extern crate std;
+// compile-flags: --crate-type=lib --test
+// pretty-compare-only
+// pretty-mode:expanded
+// pp-exact:tests-are-sorted.pp
+
+extern crate test;
+#[cfg(test)]
+#[rustc_test_marker = "m_test"]
+pub const m_test: test::TestDescAndFn =
+    test::TestDescAndFn {
+        desc: test::TestDesc {
+            name: test::StaticTestName("m_test"),
+            ignore: false,
+            ignore_message: ::core::option::Option::None,
+            compile_fail: false,
+            no_run: false,
+            should_panic: test::ShouldPanic::No,
+            test_type: test::TestType::Unknown,
+        },
+        testfn: test::StaticTestFn(|| test::assert_test_result(m_test())),
+    };
+fn m_test() {}
+
+extern crate test;
+#[cfg(test)]
+#[rustc_test_marker = "z_test"]
+pub const z_test: test::TestDescAndFn =
+    test::TestDescAndFn {
+        desc: test::TestDesc {
+            name: test::StaticTestName("z_test"),
+            ignore: false,
+            ignore_message: ::core::option::Option::None,
+            compile_fail: false,
+            no_run: false,
+            should_panic: test::ShouldPanic::No,
+            test_type: test::TestType::Unknown,
+        },
+        testfn: test::StaticTestFn(|| test::assert_test_result(z_test())),
+    };
+fn z_test() {}
+
+extern crate test;
+#[cfg(test)]
+#[rustc_test_marker = "a_test"]
+pub const a_test: test::TestDescAndFn =
+    test::TestDescAndFn {
+        desc: test::TestDesc {
+            name: test::StaticTestName("a_test"),
+            ignore: false,
+            ignore_message: ::core::option::Option::None,
+            compile_fail: false,
+            no_run: false,
+            should_panic: test::ShouldPanic::No,
+            test_type: test::TestType::Unknown,
+        },
+        testfn: test::StaticTestFn(|| test::assert_test_result(a_test())),
+    };
+fn a_test() {}
+#[rustc_main]
+pub fn main() -> () {
+    extern crate test;
+    test::test_main_static(&[&a_test, &m_test, &z_test])
+}
diff --git a/src/test/pretty/tests-are-sorted.rs b/src/test/pretty/tests-are-sorted.rs
new file mode 100644
index 00000000000..1f737d54719
--- /dev/null
+++ b/src/test/pretty/tests-are-sorted.rs
@@ -0,0 +1,13 @@
+// compile-flags: --crate-type=lib --test
+// pretty-compare-only
+// pretty-mode:expanded
+// pp-exact:tests-are-sorted.pp
+
+#[test]
+fn m_test() {}
+
+#[test]
+fn z_test() {}
+
+#[test]
+fn a_test() {}
diff --git a/src/tools/compiletest/src/main.rs b/src/tools/compiletest/src/main.rs
index 417b429161f..a8cf6623f35 100644
--- a/src/tools/compiletest/src/main.rs
+++ b/src/tools/compiletest/src/main.rs
@@ -397,6 +397,8 @@ pub fn run_tests(config: Config) {
         make_tests(c, &mut tests);
     }
 
+    tests.sort_by(|a, b| a.desc.name.as_slice().cmp(&b.desc.name.as_slice()));
+
     let res = test::run_tests_console(&opts, tests);
     match res {
         Ok(true) => {}