Auto merge of #27439 - vberger:more_perseverant_resolve, r=nrc

(This is a second try at #26242. This time I think things should be ok.)

The current algorithm handling import resolutions works sequentially, handling imports in the order they appear in the source file, and blocking/bailing on the first one generating an error/being unresolved.

This can lead to situations where the order of the `use` statements can make the difference between "this code compiles" and "this code fails on an unresolved import" (see #18083 for example). This is especially true when considering glob imports.

This PR changes the behaviour of the algorithm to instead try to resolve all imports in a module. If one fails, it is recorded and the next one is tried (instead of directly giving up). Also, all errors generated are stored (and not reported directly).

The main loop of the algorithms guaranties that the algorithm will always finish: if a round of resolution does not resolve anything new, we are stuck and give up. At this point, the new version of the algorithm will display all errors generated by the last round of resolve. This way we are sure to not silence relevant errors or help messages, but also to not give up too early.

**As a consequence, the import resolution becomes independent of the order in which the `use` statements are written in the source files.** I personally don't see any situations where this could be a problem, but this might need some thought.

I passed `rpass` and `cfail` tests on my computer, and now am compiling a full stage2 compiler to ensure the crates reporting errors in my previous attempts still build correctly. I guess once I have checked it, this will need a crater run?

Fixes #18083.

r? @alexcrichton , cc @nrc @brson 

5 files changed, 114 insertions, 7 deletions

diff --git a/src/test/compile-fail/import-shadow-6.rs b/src/test/compile-fail/import-shadow-6.rs
index fa3b75c70f0..0f3d54d5fe3 100644
--- a/src/test/compile-fail/import-shadow-6.rs
+++ b/src/test/compile-fail/import-shadow-6.rs
@@ -12,8 +12,8 @@
 
 #![no_implicit_prelude]
 
-use qux::*;
-use foo::*; //~ERROR a type named `Baz` has already been imported in this module
+use qux::*; //~ERROR a type named `Baz` has already been imported in this module
+use foo::*;
 
 mod foo {
     pub type Baz = isize;
diff --git a/src/test/compile-fail/issue-25396.rs b/src/test/compile-fail/issue-25396.rs
index 3ada57c9993..bf26a591b4b 100644
--- a/src/test/compile-fail/issue-25396.rs
+++ b/src/test/compile-fail/issue-25396.rs
@@ -11,14 +11,14 @@
 use foo::baz;
 use bar::baz; //~ ERROR a module named `baz` has already been imported
 
-use foo::Quux;
 use bar::Quux; //~ ERROR a trait named `Quux` has already been imported
+use foo::Quux;
 
-use foo::blah;
-use bar::blah; //~ ERROR a type named `blah` has already been imported
+use foo::blah; //~ ERROR a type named `blah` has already been imported
+use bar::blah;
 
-use foo::WOMP;
-use bar::WOMP; //~ ERROR a value named `WOMP` has already been imported
+use foo::WOMP; //~ ERROR a value named `WOMP` has already been imported
+use bar::WOMP;
 
 fn main() {}
 
diff --git a/src/test/run-pass/import-glob-1.rs b/src/test/run-pass/import-glob-1.rs
new file mode 100644
index 00000000000..a7949e7d6e3
--- /dev/null
+++ b/src/test/run-pass/import-glob-1.rs
@@ -0,0 +1,34 @@
+// Copyright 2015 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.
+
+// This should resolve fine. Prior to fix, the last import
+// was being tried too early, and marked as unrsolved before
+// the glob import had a chance to be resolved.
+
+mod bar {
+    pub use self::middle::*;
+
+    mod middle {
+        pub use self::baz::Baz;
+
+        mod baz {
+            pub enum Baz {
+                Baz1,
+                Baz2
+            }
+        }
+    }
+}
+
+mod foo {
+    use bar::Baz::{Baz1, Baz2};
+}
+
+fn main() {}
diff --git a/src/test/run-pass/issue-18083.rs b/src/test/run-pass/issue-18083.rs
new file mode 100644
index 00000000000..ff26e186db3
--- /dev/null
+++ b/src/test/run-pass/issue-18083.rs
@@ -0,0 +1,32 @@
+// Copyright 2015 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 crossed imports should resolve fine, and not block on
+// each other and be reported as unresolved.
+
+mod a {
+    use b::{B};
+    pub use self::inner::A;
+
+    mod inner {
+        pub struct A;
+    }
+}
+
+mod b {
+    use a::{A};
+    pub use self::inner::B;
+
+    mod inner {
+        pub struct B;
+    }
+}
+
+fn main() {}
diff --git a/src/test/run-pass/issue-4865-1.rs b/src/test/run-pass/issue-4865-1.rs
new file mode 100644
index 00000000000..3c477795130
--- /dev/null
+++ b/src/test/run-pass/issue-4865-1.rs
@@ -0,0 +1,41 @@
+// Copyright 2015 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.
+
+// This should resolve fine.
+// Prior to fix, the crossed imports between a and b
+// would block on the glob import, itself never being resolved
+// because these previous imports were not resolved.
+
+pub mod a {
+    use b::fn_b;
+    use c::*;
+
+    pub fn fn_a(){
+    }
+}
+
+pub mod b {
+    use a::fn_a;
+    use c::*;
+
+    pub fn fn_b(){
+    }
+}
+
+pub mod c{
+    pub fn fn_c(){
+    }
+}
+
+use a::fn_a;
+use b::fn_b;
+
+fn main() {
+}