Auto merge of #43552 - petrochenkov:instab, r=jseyfried

resolve: Try to fix instability in import suggestions

cc https://github.com/rust-lang/rust/pull/42033

`lookup_import_candidates` walks module graph in DFS order and skips modules that were already visited (which is correct because there can be cycles).
However it means that if we visited `std::prelude::v1::Result::Ok` first, we will never visit `std::result::Result::Ok` because `Result` will be skipped as already visited (note: enums are also modules here), and otherwise, if we visited `std::result::Result::Ok` first, we will never get to `std::prelude::v1::Result::Ok`.
What child module of `std` (`prelude` or `result`) we will visit first, depends on randomized hashing, so we have instability in diagnostics.

With this patch modules' children are visited in stable order in `lookup_import_candidates`, this should fix the issue, but let's see what Travis will say.

r? @oli-obk

5 files changed, 55 insertions, 74 deletions

diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 349a21af895..2317e36a0ab 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -546,7 +546,7 @@ impl<'a> PathSource<'a> {
     }
 }
 
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 pub enum Namespace {
     TypeNS,
     ValueNS,
@@ -898,6 +898,19 @@ impl<'a> ModuleData<'a> {
         }
     }
 
+    fn for_each_child_stable<F: FnMut(Ident, Namespace, &'a NameBinding<'a>)>(&self, mut f: F) {
+        let resolutions = self.resolutions.borrow();
+        let mut resolutions = resolutions.iter().map(|(&(ident, ns), &resolution)| {
+                                                    // Pre-compute keys for sorting
+                                                    (ident.name.as_str(), ns, ident, resolution)
+                                                })
+                                                .collect::<Vec<_>>();
+        resolutions.sort_unstable_by_key(|&(str, ns, ..)| (str, ns));
+        for &(_, ns, ident, resolution) in resolutions.iter() {
+            resolution.borrow().binding.map(|binding| f(ident, ns, binding));
+        }
+    }
+
     fn def(&self) -> Option<Def> {
         match self.kind {
             ModuleKind::Def(def, _) => Some(def),
@@ -3352,8 +3365,9 @@ impl<'a> Resolver<'a> {
                         in_module_is_extern)) = worklist.pop() {
             self.populate_module_if_necessary(in_module);
 
-            in_module.for_each_child(|ident, ns, name_binding| {
-
+            // We have to visit module children in deterministic order to avoid
+            // instabilities in reported imports (#43552).
+            in_module.for_each_child_stable(|ident, ns, name_binding| {
                 // avoid imports entirely
                 if name_binding.is_import() && !name_binding.is_extern_crate() { return; }
                 // avoid non-importable candidates as well
diff --git a/src/libsyntax_pos/symbol.rs b/src/libsyntax_pos/symbol.rs
index debac70545a..e49f1f28e5f 100644
--- a/src/libsyntax_pos/symbol.rs
+++ b/src/libsyntax_pos/symbol.rs
@@ -326,7 +326,7 @@ fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
 /// destroyed. In particular, they must not access string contents. This can
 /// be fixed in the future by just leaking all strings until thread death
 /// somehow.
-#[derive(Clone, Hash, PartialOrd, Eq, Ord)]
+#[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
 pub struct InternedString {
     string: &'static str,
 }
diff --git a/src/test/compile-fail/issue-35675.rs b/src/test/compile-fail/issue-35675.rs
deleted file mode 100644
index c09e56cbc5b..00000000000
--- a/src/test/compile-fail/issue-35675.rs
+++ /dev/null
@@ -1,67 +0,0 @@
-// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// these two HELPs are actually in a new line between this line and the `enum Fruit` line
-enum Fruit { //~ HELP possible candidate is found in another module, you can import it into scope
-    //~^ HELP possible candidate is found in another module, you can import it into scope
-    Apple(i64),
-    Orange(i64),
-}
-
-fn should_return_fruit() -> Apple {
-    //~^ ERROR cannot find type `Apple` in this scope
-    //~| NOTE not found in this scope
-    //~| HELP you can try using the variant's enum
-    Apple(5)
-    //~^ ERROR cannot find function `Apple` in this scope
-    //~| NOTE not found in this scope
-}
-
-fn should_return_fruit_too() -> Fruit::Apple {
-    //~^ ERROR expected type, found variant `Fruit::Apple`
-    //~| HELP you can try using the variant's enum
-    //~| NOTE not a type
-    Apple(5)
-    //~^ ERROR cannot find function `Apple` in this scope
-    //~| NOTE not found in this scope
-}
-
-fn foo() -> Ok {
-    //~^ ERROR expected type, found variant `Ok`
-    //~| NOTE not a type
-    //~| HELP there is an enum variant
-    //~| HELP there is an enum variant
-    Ok(())
-}
-
-fn bar() -> Variant3 {
-    //~^ ERROR cannot find type `Variant3` in this scope
-    //~| HELP you can try using the variant's enum
-    //~| NOTE not found in this scope
-}
-
-fn qux() -> Some {
-    //~^ ERROR expected type, found variant `Some`
-    //~| NOTE not a type
-    //~| HELP there is an enum variant
-    //~| HELP there is an enum variant
-    Some(1)
-}
-
-fn main() {}
-
-mod x {
-    enum Enum {
-        Variant1,
-        Variant2(),
-        Variant3(usize),
-        Variant4 {},
-    }
-}
diff --git a/src/test/ui/issue-35675.rs b/src/test/ui/issue-35675.rs
index 391e1f2db5c..001c1f2eddc 100644
--- a/src/test/ui/issue-35675.rs
+++ b/src/test/ui/issue-35675.rs
@@ -33,11 +33,27 @@ fn should_return_fruit_too() -> Fruit::Apple {
     //~| NOTE not found in this scope
 }
 
+fn foo() -> Ok {
+    //~^ ERROR expected type, found variant `Ok`
+    //~| NOTE not a type
+    //~| HELP there is an enum variant
+    //~| HELP there is an enum variant
+    Ok(())
+}
+
 fn bar() -> Variant3 {
     //~^ ERROR cannot find type `Variant3` in this scope
     //~| NOTE not found in this scope
 }
 
+fn qux() -> Some {
+    //~^ ERROR expected type, found variant `Some`
+    //~| NOTE not a type
+    //~| HELP there is an enum variant
+    //~| HELP there is an enum variant
+    Some(1)
+}
+
 fn main() {}
 
 mod x {
diff --git a/src/test/ui/issue-35675.stderr b/src/test/ui/issue-35675.stderr
index c2c10724646..ed330f47208 100644
--- a/src/test/ui/issue-35675.stderr
+++ b/src/test/ui/issue-35675.stderr
@@ -38,14 +38,32 @@ help: possible candidate is found in another module, you can import it into scop
 12 | use Fruit::Apple;
    |
 
-error[E0412]: cannot find type `Variant3` in this scope
+error[E0573]: expected type, found variant `Ok`
   --> $DIR/issue-35675.rs:36:13
    |
-36 | fn bar() -> Variant3 {
+36 | fn foo() -> Ok {
+   |             ^^ not a type
+   |
+   = help: there is an enum variant `std::prelude::v1::Ok`, try using `std::prelude::v1`?
+   = help: there is an enum variant `std::result::Result::Ok`, try using `std::result::Result`?
+
+error[E0412]: cannot find type `Variant3` in this scope
+  --> $DIR/issue-35675.rs:44:13
+   |
+44 | fn bar() -> Variant3 {
    |             ^^^^^^^^
    |             |
    |             not found in this scope
    |             help: you can try using the variant's enum: `x::Enum`
 
-error: aborting due to 5 previous errors
+error[E0573]: expected type, found variant `Some`
+  --> $DIR/issue-35675.rs:49:13
+   |
+49 | fn qux() -> Some {
+   |             ^^^^ not a type
+   |
+   = help: there is an enum variant `std::prelude::v1::Option::Some`, try using `std::prelude::v1::Option`?
+   = help: there is an enum variant `std::prelude::v1::Some`, try using `std::prelude::v1`?
+
+error: aborting due to 7 previous errors