Auto merge of #60415 - jespersm:pr_unused_import_45268, r=petrochenkov

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

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

I've verifies this against master (but only on MacOS). However, with some recent changes in master, it appears that there are some failures on my machine. They are unrelated to my changes, anyway.

10 files changed, 127 insertions, 48 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 7823c377b2a..ffa33393c30 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2957,6 +2957,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",
 ]
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index ae7358df9d8..9ce300ce048 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,13 @@ pub type FreevarMap = NodeMap<Vec<Freevar<ast::NodeId>>>;
 
 pub type CaptureModeMap = NodeMap<CaptureClause>;
 
+ // 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: SmallVec<[NodeId; 1]>,
 }
 
 // Trait method resolution
diff --git a/src/librustc/ich/impls_hir.rs b/src/librustc/ich/impls_hir.rs
index 65795d2b136..5b2a1e783c0 100644
--- a/src/librustc/ich/impls_hir.rs
+++ b/src/librustc/ich/impls_hir.rs
@@ -7,6 +7,7 @@ use crate::hir::def_id::{DefId, LocalDefId, CrateNum, CRATE_DEF_INDEX};
 use crate::ich::{StableHashingContext, NodeIdHashingMode, Fingerprint};
 use rustc_data_structures::stable_hasher::{HashStable, ToStableHashKey,
                                            StableHasher, StableHasherResult};
+use smallvec::SmallVec;
 use std::mem;
 use syntax::ast;
 use syntax::attr;
@@ -393,30 +394,30 @@ impl<'a> HashStable<StableHashingContext<'a>> for hir::TraitCandidate {
         hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
             let hir::TraitCandidate {
                 def_id,
-                import_id,
-            } = *self;
+                import_ids,
+            } = self;
 
             def_id.hash_stable(hcx, hasher);
-            import_id.hash_stable(hcx, hasher);
+            import_ids.hash_stable(hcx, hasher);
         });
     }
 }
 
 impl<'a> ToStableHashKey<StableHashingContext<'a>> for hir::TraitCandidate {
-    type KeyType = (DefPathHash, Option<(DefPathHash, hir::ItemLocalId)>);
+    type KeyType = (DefPathHash, SmallVec<[(DefPathHash, hir::ItemLocalId); 1]>);
 
     fn to_stable_hash_key(&self,
                           hcx: &StableHashingContext<'a>)
                           -> 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_keys = import_ids.iter().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)).collect();
+        (hcx.def_path_hash(*def_id), import_keys)
     }
 }
 
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 19343a9250d..fa573907d4c 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -1,6 +1,7 @@
 use std::hash::{Hash, Hasher, BuildHasher};
 use std::marker::PhantomData;
 use std::mem;
+use smallvec::SmallVec;
 use crate::sip128::SipHasher128;
 use crate::indexed_vec;
 use crate::bit_set;
@@ -318,6 +319,15 @@ impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
     }
 }
 
+impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (&self[..]).hash_stable(ctx, hasher);
+    }
+}
+
 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
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..c439ad9c315 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};
@@ -66,6 +67,7 @@ use std::collections::BTreeSet;
 use std::mem::replace;
 use rustc_data_structures::ptr_key::PtrKey;
 use rustc_data_structures::sync::Lrc;
+use smallvec::SmallVec;
 
 use diagnostics::{find_span_of_binding_until_next_binding, extend_span_to_previous_binding};
 use resolve_imports::{ImportDirective, ImportDirectiveSubclass, NameResolution, ImportResolver};
@@ -4582,7 +4584,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 +4643,34 @@ 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, mut kind: &NameBindingKind<'_>,
+                               trait_name: Ident) -> SmallVec<[NodeId; 1]> {
+        let mut import_ids = smallvec![];
+        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..314f7e97cd2 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -35,6 +35,8 @@ use std::mem;
 use std::ops::Deref;
 use std::cmp::max;
 
+use smallvec::{smallvec, SmallVec};
+
 use self::CandidateKind::*;
 pub use self::PickKind::*;
 
@@ -121,7 +123,7 @@ struct Candidate<'tcx> {
     xform_ret_ty: Option<Ty<'tcx>>,
     item: ty::AssociatedItem,
     kind: CandidateKind<'tcx>,
-    import_id: Option<hir::HirId>,
+    import_ids: SmallVec<[hir::HirId; 1]>,
 }
 
 #[derive(Debug)]
@@ -146,7 +148,7 @@ enum ProbeResult {
 pub struct Pick<'tcx> {
     pub item: ty::AssociatedItem,
     pub kind: PickKind<'tcx>,
-    pub import_id: Option<hir::HirId>,
+    pub import_ids: SmallVec<[hir::HirId; 1]>,
 
     // Indicates that the source expression should be autoderef'd N times
     //
@@ -716,7 +718,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 +752,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 +801,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 +840,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 +855,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 +893,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
     }
 
     fn assemble_extension_candidates_for_trait(&mut self,
-                                               import_id: Option<hir::HirId>,
+                                               import_ids: SmallVec<[hir::HirId; 1]>,
                                                trait_def_id: DefId)
                                                -> Result<(), MethodError<'tcx>> {
         debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
@@ -907,7 +910,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 +927,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 +1416,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 +1655,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..0bd77511135
--- /dev/null
+++ b/src/test/ui/lint/unused_import_warning_issue_45268.rs
@@ -0,0 +1,48 @@
+// 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
+   |         ^^^^^^^^^^^^^^
+