Fix #45268 by saving all NodeId's for resolved traits.

9 files changed, 137 insertions, 50 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 7823c377b2a..f8dd4c91773 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -298,6 +298,18 @@ dependencies = [
 
 [[package]]
 name = "cargo_metadata"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "error-chain 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "serde 1.0.82 (registry+https://github.com/rust-lang/crates.io-index)",
+ "serde_derive 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)",
+ "serde_json 1.0.33 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "cargo_metadata"
 version = "0.7.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
@@ -1612,7 +1624,7 @@ name = "miri"
 version = "0.1.0"
 dependencies = [
  "byteorder 1.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
- "cargo_metadata 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "cargo_metadata 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "colored 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "compiletest_rs 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)",
  "directories 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2957,6 +2969,7 @@ dependencies = [
  "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "rustc_metadata 0.0.0",
+ "smallvec 0.6.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
 ]
@@ -4066,6 +4079,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum byteorder 1.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "94f88df23a25417badc922ab0f5716cc1330e87f71ddd9203b3a3ccd9cedf75d"
 "checksum bytes 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)" = "40ade3d27603c2cb345eb0912aec461a6dec7e06a4ae48589904e808335c7afa"
 "checksum bytesize 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "716960a18f978640f25101b5cbf1c6f6b0d3192fab36a2d98ca96f0ecbe41010"
+"checksum cargo_metadata 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)" = "e5d1b4d380e1bab994591a24c2bdd1b054f64b60bef483a8c598c7c345bc3bbe"
 "checksum cargo_metadata 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "585784cac9b05c93a53b17a0b24a5cdd1dfdda5256f030e089b549d2390cc720"
 "checksum cc 1.0.35 (registry+https://github.com/rust-lang/crates.io-index)" = "5e5f3fee5eeb60324c2781f1e41286bdee933850fff9b3c672587fed5ec58c83"
 "checksum cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "082bb9b28e00d3c9d39cc03e64ce4cea0f1bb9b3fde493f0cbc008472d22bdf4"
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index ae7358df9d8..8ef5b24a9f2 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -37,6 +37,7 @@ use rustc_macros::HashStable;
 use serialize::{self, Encoder, Encodable, Decoder, Decodable};
 use std::collections::{BTreeSet, BTreeMap};
 use std::fmt;
+use smallvec::SmallVec;
 
 /// HIR doesn't commit to a concrete storage type and has its own alias for a vector.
 /// It can be `Vec`, `P<[T]>` or potentially `Box<[T]>`, or some other container with similar
@@ -2505,10 +2506,16 @@ pub type FreevarMap = NodeMap<Vec<Freevar<ast::NodeId>>>;
 
 pub type CaptureModeMap = NodeMap<CaptureClause>;
 
+pub type SmallHirIdVec = SmallVec<[HirId;1]>;
+pub type SmallNodeIdVec = SmallVec<[NodeId;1]>;
+
+ // The TraitCandidate's import_ids is empty if the trait is defined in the same module, and
+ // has length > 0 if the trait is found through an chain of imports, starting with the
+ // import/use statement in the scope where the trait is used.
 #[derive(Clone, Debug)]
 pub struct TraitCandidate {
     pub def_id: DefId,
-    pub import_id: Option<NodeId>,
+    pub import_ids: SmallNodeIdVec,
 }
 
 // Trait method resolution
diff --git a/src/librustc/ich/impls_hir.rs b/src/librustc/ich/impls_hir.rs
index 65795d2b136..eb57f08003c 100644
--- a/src/librustc/ich/impls_hir.rs
+++ b/src/librustc/ich/impls_hir.rs
@@ -391,13 +391,14 @@ impl<'a> HashStable<StableHashingContext<'a>> for hir::TraitCandidate {
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
         hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
-            let hir::TraitCandidate {
+            let &hir::TraitCandidate {
                 def_id,
-                import_id,
-            } = *self;
+                import_ids,
+            } = &self;
 
             def_id.hash_stable(hcx, hasher);
-            import_id.hash_stable(hcx, hasher);
+            // We only use the outermost import NodeId as key
+            import_ids.first().hash_stable(hcx, hasher);
         });
     }
 }
@@ -410,13 +411,13 @@ impl<'a> ToStableHashKey<StableHashingContext<'a>> for hir::TraitCandidate {
                           -> Self::KeyType {
         let hir::TraitCandidate {
             def_id,
-            import_id,
-        } = *self;
+            import_ids,
+        } = self;
 
-        let import_id = import_id.map(|node_id| hcx.node_to_hir_id(node_id))
-                                 .map(|hir_id| (hcx.local_def_path_hash(hir_id.owner),
-                                                hir_id.local_id));
-        (hcx.def_path_hash(def_id), import_id)
+        let import_ids = import_ids.first().map(|node_id| hcx.node_to_hir_id(*node_id))
+                                           .map(|hir_id| (hcx.local_def_path_hash(hir_id.owner),
+                                                          hir_id.local_id));
+        (hcx.def_path_hash(*def_id), import_ids)
     }
 }
 
diff --git a/src/librustc_resolve/Cargo.toml b/src/librustc_resolve/Cargo.toml
index 836b4ad38ca..968a45e241e 100644
--- a/src/librustc_resolve/Cargo.toml
+++ b/src/librustc_resolve/Cargo.toml
@@ -20,3 +20,4 @@ errors = { path = "../librustc_errors", package = "rustc_errors" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_data_structures = { path = "../librustc_data_structures" }
 rustc_metadata = { path = "../librustc_metadata" }
+smallvec = { version = "0.6.7", features = ["union", "may_dangle"] }
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index e0892f98d31..71721504d5a 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -17,6 +17,7 @@ pub use rustc::hir::def::{Namespace, PerNS};
 
 use GenericParameters::*;
 use RibKind::*;
+use smallvec::smallvec;
 
 use rustc::hir::map::{Definitions, DefCollector};
 use rustc::hir::{self, PrimTy, Bool, Char, Float, Int, Uint, Str};
@@ -28,7 +29,7 @@ use rustc::hir::def::{
 };
 use rustc::hir::def::Namespace::*;
 use rustc::hir::def_id::{CRATE_DEF_INDEX, LOCAL_CRATE, DefId};
-use rustc::hir::{Freevar, FreevarMap, TraitCandidate, TraitMap, GlobMap};
+use rustc::hir::{Freevar, FreevarMap, TraitCandidate, TraitMap, GlobMap, SmallNodeIdVec};
 use rustc::ty::{self, DefIdTree};
 use rustc::util::nodemap::{NodeMap, NodeSet, FxHashMap, FxHashSet, DefIdMap};
 use rustc::{bug, span_bug};
@@ -4582,7 +4583,7 @@ impl<'a> Resolver<'a> {
                 module.span,
             ).is_ok() {
                 let def_id = module.def_id().unwrap();
-                found_traits.push(TraitCandidate { def_id: def_id, import_id: None });
+                found_traits.push(TraitCandidate { def_id: def_id, import_ids: smallvec![] });
             }
         }
 
@@ -4641,37 +4642,35 @@ impl<'a> Resolver<'a> {
                     false,
                     module.span,
                 ).is_ok() {
-                    let import_id = match binding.kind {
-                        NameBindingKind::Import { directive, .. } => {
-                            self.maybe_unused_trait_imports.insert(directive.id);
-                            self.add_to_glob_map(&directive, trait_name);
-                            Some(directive.id)
-                        }
-                        _ => None,
-                    };
+                    let import_ids = self.find_transitive_imports(&binding.kind, &trait_name);
                     let trait_def_id = module.def_id().unwrap();
-                    found_traits.push(TraitCandidate { def_id: trait_def_id, import_id });
+                    found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
                 }
             } else if let Res::Def(DefKind::TraitAlias, _) = binding.res() {
                 // For now, just treat all trait aliases as possible candidates, since we don't
                 // know if the ident is somewhere in the transitive bounds.
-
-                let import_id = match binding.kind {
-                    NameBindingKind::Import { directive, .. } => {
-                        self.maybe_unused_trait_imports.insert(directive.id);
-                        self.add_to_glob_map(&directive, trait_name);
-                        Some(directive.id)
-                    }
-                    _ => None,
-                };
+                let import_ids = self.find_transitive_imports(&binding.kind, &trait_name);
                 let trait_def_id = binding.res().def_id();
-                found_traits.push(TraitCandidate { def_id: trait_def_id, import_id });
+                found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
             } else {
                 bug!("candidate is not trait or trait alias?")
             }
         }
     }
 
+    fn find_transitive_imports(&mut self, kind: &NameBindingKind<'_>,
+                               trait_name: &Ident) -> SmallNodeIdVec {
+        let mut import_ids = smallvec![];
+        let mut kind = kind;
+        while let NameBindingKind::Import { directive, binding, .. } = *kind {
+            self.maybe_unused_trait_imports.insert(directive.id);
+            self.add_to_glob_map(&directive, *trait_name);
+            import_ids.push(directive.id);
+            kind = &binding.kind;
+        };
+        import_ids
+    }
+
     fn lookup_import_candidates_from_module<FilterFn>(&mut self,
                                           lookup_ident: Ident,
                                           namespace: Namespace,
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index bbdc7df4441..a4b1687ea53 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -195,8 +195,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             ProbeScope::TraitsInScope
         )?;
 
-        if let Some(import_id) = pick.import_id {
-            let import_def_id = self.tcx.hir().local_def_id_from_hir_id(import_id);
+        for import_id in &pick.import_ids {
+            let import_def_id = self.tcx.hir().local_def_id_from_hir_id(*import_id);
             debug!("used_trait_import: {:?}", import_def_id);
             Lrc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
                 .unwrap().insert(import_def_id);
@@ -434,7 +434,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         let pick = self.probe_for_name(span, probe::Mode::Path, method_name, IsSuggestion(false),
                                        self_ty, expr_id, ProbeScope::TraitsInScope)?;
         debug!("resolve_ufcs: pick={:?}", pick);
-        if let Some(import_id) = pick.import_id {
+        for import_id in pick.import_ids {
             let import_def_id = tcx.hir().local_def_id_from_hir_id(import_id);
             debug!("resolve_ufcs: used_trait_import: {:?}", import_def_id);
             Lrc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 8c61a127d10..148b7d5edb5 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -7,6 +7,7 @@ use crate::check::autoderef::{self, Autoderef};
 use crate::check::FnCtxt;
 use crate::hir::def_id::DefId;
 use crate::hir::def::DefKind;
+use crate::hir::SmallHirIdVec;
 use crate::namespace::Namespace;
 
 use rustc_data_structures::sync::Lrc;
@@ -35,6 +36,8 @@ use std::mem;
 use std::ops::Deref;
 use std::cmp::max;
 
+use smallvec::smallvec;
+
 use self::CandidateKind::*;
 pub use self::PickKind::*;
 
@@ -121,7 +124,7 @@ struct Candidate<'tcx> {
     xform_ret_ty: Option<Ty<'tcx>>,
     item: ty::AssociatedItem,
     kind: CandidateKind<'tcx>,
-    import_id: Option<hir::HirId>,
+    import_ids: SmallHirIdVec,
 }
 
 #[derive(Debug)]
@@ -146,7 +149,7 @@ enum ProbeResult {
 pub struct Pick<'tcx> {
     pub item: ty::AssociatedItem,
     pub kind: PickKind<'tcx>,
-    pub import_id: Option<hir::HirId>,
+    pub import_ids: hir::SmallHirIdVec,
 
     // Indicates that the source expression should be autoderef'd N times
     //
@@ -716,7 +719,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             self.push_candidate(Candidate {
                 xform_self_ty, xform_ret_ty, item,
                 kind: InherentImplCandidate(impl_substs, obligations),
-                import_id: None
+                import_ids: smallvec![]
             }, true);
         }
     }
@@ -750,7 +753,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             this.push_candidate(Candidate {
                 xform_self_ty, xform_ret_ty, item,
                 kind: ObjectCandidate,
-                import_id: None
+                import_ids: smallvec![]
             }, true);
         });
     }
@@ -799,7 +802,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             this.push_candidate(Candidate {
                 xform_self_ty, xform_ret_ty, item,
                 kind: WhereClauseCandidate(poly_trait_ref),
-                import_id: None
+                import_ids: smallvec![]
             }, true);
         });
     }
@@ -838,9 +841,10 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             for trait_candidate in applicable_traits.iter() {
                 let trait_did = trait_candidate.def_id;
                 if duplicates.insert(trait_did) {
-                    let import_id = trait_candidate.import_id.map(|node_id|
-                        self.fcx.tcx.hir().node_to_hir_id(node_id));
-                    let result = self.assemble_extension_candidates_for_trait(import_id, trait_did);
+                    let import_ids = trait_candidate.import_ids.iter().map(|node_id|
+                        self.fcx.tcx.hir().node_to_hir_id(*node_id)).collect();
+                    let result = self.assemble_extension_candidates_for_trait(import_ids,
+                                                                              trait_did);
                     result?;
                 }
             }
@@ -852,7 +856,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         let mut duplicates = FxHashSet::default();
         for trait_info in suggest::all_traits(self.tcx) {
             if duplicates.insert(trait_info.def_id) {
-                self.assemble_extension_candidates_for_trait(None, trait_info.def_id)?;
+                self.assemble_extension_candidates_for_trait(smallvec![], trait_info.def_id)?;
             }
         }
         Ok(())
@@ -890,7 +894,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
     }
 
     fn assemble_extension_candidates_for_trait(&mut self,
-                                               import_id: Option<hir::HirId>,
+                                               import_ids: SmallHirIdVec,
                                                trait_def_id: DefId)
                                                -> Result<(), MethodError<'tcx>> {
         debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
@@ -907,7 +911,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
                 let (xform_self_ty, xform_ret_ty) =
                     this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs);
                 this.push_candidate(Candidate {
-                    xform_self_ty, xform_ret_ty, item, import_id,
+                    xform_self_ty, xform_ret_ty, item, import_ids: import_ids.clone(),
                     kind: TraitCandidate(new_trait_ref),
                 }, true);
             });
@@ -924,7 +928,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
                 let (xform_self_ty, xform_ret_ty) =
                     self.xform_self_ty(&item, trait_ref.self_ty(), trait_substs);
                 self.push_candidate(Candidate {
-                    xform_self_ty, xform_ret_ty, item, import_id,
+                    xform_self_ty, xform_ret_ty, item, import_ids: import_ids.clone(),
                     kind: TraitCandidate(trait_ref),
                 }, false);
             }
@@ -1413,7 +1417,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         Some(Pick {
             item: probes[0].0.item.clone(),
             kind: TraitPick,
-            import_id: probes[0].0.import_id,
+            import_ids: probes[0].0.import_ids.clone(),
             autoderefs: 0,
             autoref: None,
             unsize: None,
@@ -1652,7 +1656,7 @@ impl<'tcx> Candidate<'tcx> {
                     WhereClausePick(trait_ref.clone())
                 }
             },
-            import_id: self.import_id,
+            import_ids: self.import_ids.clone(),
             autoderefs: 0,
             autoref: None,
             unsize: None,
diff --git a/src/test/ui/lint/unused_import_warning_issue_45268.rs b/src/test/ui/lint/unused_import_warning_issue_45268.rs
new file mode 100644
index 00000000000..9f3f5573a15
--- /dev/null
+++ b/src/test/ui/lint/unused_import_warning_issue_45268.rs
@@ -0,0 +1,49 @@
+// compile-pass
+
+#![warn(unused_imports)] // Warning explanation here, it's OK
+
+mod test {
+    pub trait A {
+        fn a();
+    }
+
+    impl A for () {
+        fn a() { }
+    }
+
+    pub trait B {
+        fn b(self);
+    }
+
+    impl B for () {
+        fn b(self) { }
+    }
+
+    pub trait Unused {
+    }
+}
+
+use test::Unused;   // This is really unused, so warning is OK
+use test::A;        // This is used by the test2::func() through import of super::*
+use test::B;        // This is used by the test2::func() through import of super::*
+
+mod test2 {
+    use super::*;
+    pub fn func() {
+        let _ = <()>::a();
+        let _ = ().b();
+        test3::inner_func();
+    }
+    mod test3 {
+    use super::*;
+    pub fn inner_func() {
+        let _ = <()>::a();
+        let _ = ().b();
+    }
+}
+
+}
+
+fn main() {
+    test2::func();
+}
diff --git a/src/test/ui/lint/unused_import_warning_issue_45268.stderr b/src/test/ui/lint/unused_import_warning_issue_45268.stderr
new file mode 100644
index 00000000000..7392e99f7ae
--- /dev/null
+++ b/src/test/ui/lint/unused_import_warning_issue_45268.stderr
@@ -0,0 +1,12 @@
+warning: unused import: `test::Unused`
+  --> $DIR/unused_import_warning_issue_45268.rs:26:5
+   |
+LL | use test::Unused;   // This is really unused, so warning is OK
+   |     ^^^^^^^^^^^^
+   |
+note: lint level defined here
+  --> $DIR/unused_import_warning_issue_45268.rs:3:9
+   |
+LL | #![warn(unused_imports)] // Warning explanation here, it's OK
+   |         ^^^^^^^^^^^^^^
+