Auto merge of #29620 - petrochenkov:reachable2, r=alexcrichton

Handle them in `middle::reachable` instead (no optimizations so far, just drop all trait impl items into the reachable set, as before). Addresses the concerns from https://github.com/rust-lang/rust/pull/29291#discussion_r43672413
\+ In `middle::reachable` don't treat impls of `Drop` specially, they are subsumed by the general impl treatment.
\+ Add some tests checking reachability of trait methods written in UFCS form
\+ Minor refactoring in the second commit

r? @alexcrichton

8 files changed, 85 insertions, 55 deletions

diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 97ab9c2dfb7..7175fbe0e57 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -125,6 +125,9 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ReachableContext<'a, 'tcx> {
             hir::ExprMethodCall(..) => {
                 let method_call = ty::MethodCall::expr(expr.id);
                 let def_id = self.tcx.tables.borrow().method_map[&method_call].def_id;
+
+                // Mark the trait item (and, possibly, its default impl) as reachable
+                // Or mark inherent impl item as reachable
                 if let Some(node_id) = self.tcx.map.as_local_node_id(def_id) {
                     if self.def_id_represents_local_inlined_item(def_id) {
                         self.worklist.push(node_id)
@@ -322,57 +325,69 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
             }
         }
     }
+}
 
-    // Step 3: Mark all destructors as reachable.
-    //
-    // FIXME #10732: This is a conservative overapproximation, but fixing
-    // this properly would result in the necessity of computing *type*
-    // reachability, which might result in a compile time loss.
-    fn mark_destructors_reachable(&mut self) {
-        let drop_trait = match self.tcx.lang_items.drop_trait() {
-            Some(id) => self.tcx.lookup_trait_def(id), None => { return }
-        };
-        drop_trait.for_each_impl(self.tcx, |drop_impl| {
-            for destructor in &self.tcx.impl_items.borrow()[&drop_impl] {
-                let destructor_did = destructor.def_id();
-                if let Some(destructor_node_id) = self.tcx.map.as_local_node_id(destructor_did) {
-                    self.reachable_symbols.insert(destructor_node_id);
+// Some methods from non-exported (completely private) trait impls still have to be
+// reachable if they are called from inlinable code. Generally, it's not known until
+// monomorphization if a specific trait impl item can be reachable or not. So, we
+// conservatively mark all of them as reachable.
+// FIXME: One possible strategy for pruning the reachable set is to avoid marking impl
+// items of non-exported traits (or maybe all local traits?) unless their respective
+// trait items are used from inlinable code through method call syntax or UFCS, or their
+// trait is a lang item.
+struct CollectPrivateImplItemsVisitor<'a> {
+    exported_items: &'a privacy::ExportedItems,
+    worklist: &'a mut Vec<ast::NodeId>,
+}
+
+impl<'a, 'v> Visitor<'v> for CollectPrivateImplItemsVisitor<'a> {
+    fn visit_item(&mut self, item: &hir::Item) {
+        // We need only trait impls here, not inherent impls, and only non-exported ones
+        if let hir::ItemImpl(_, _, _, Some(_), _, ref impl_items) = item.node {
+            if !self.exported_items.contains(&item.id) {
+                for impl_item in impl_items {
+                    self.worklist.push(impl_item.id);
                 }
             }
-        })
+        }
+
+        visit::walk_item(self, item);
     }
 }
 
 pub fn find_reachable(tcx: &ty::ctxt,
                       exported_items: &privacy::ExportedItems)
                       -> NodeSet {
+
     let mut reachable_context = ReachableContext::new(tcx);
 
     // Step 1: Seed the worklist with all nodes which were found to be public as
-    //         a result of the privacy pass along with all local lang items. If
-    //         other crates link to us, they're going to expect to be able to
+    //         a result of the privacy pass along with all local lang items and impl items.
+    //         If other crates link to us, they're going to expect to be able to
     //         use the lang items, so we need to be sure to mark them as
     //         exported.
     for id in exported_items {
         reachable_context.worklist.push(*id);
     }
     for (_, item) in tcx.lang_items.items() {
-        match *item {
-            Some(did) => {
-                if let Some(node_id) = tcx.map.as_local_node_id(did) {
-                    reachable_context.worklist.push(node_id);
-                }
+        if let Some(did) = *item {
+            if let Some(node_id) = tcx.map.as_local_node_id(did) {
+                reachable_context.worklist.push(node_id);
             }
-            _ => {}
         }
     }
+    {
+        let mut collect_private_impl_items = CollectPrivateImplItemsVisitor {
+            exported_items: exported_items,
+            worklist: &mut reachable_context.worklist,
+        };
+
+        visit::walk_crate(&mut collect_private_impl_items, tcx.map.krate());
+    }
 
     // Step 2: Mark all symbols that the symbols on the worklist touch.
     reachable_context.propagate();
 
-    // Step 3: Mark all destructors as reachable.
-    reachable_context.mark_destructors_reachable();
-
     // Return the set of reachable symbols.
     reachable_context.reachable_symbols
 }
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 4fbe3a68335..491c8a2c452 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -165,13 +165,6 @@ struct EmbargoVisitor<'a, 'tcx: 'a> {
     // may jump across private boundaries through reexport statements or type aliases.
     exported_items: ExportedItems,
 
-    // This sets contains all the destination nodes which are publicly
-    // re-exported. This is *not* a set of all reexported nodes, only a set of
-    // all nodes which are reexported *and* reachable from external crates. This
-    // means that the destination of the reexport is exported, and hence the
-    // destination must also be exported.
-    reexports: NodeSet,
-
     // Items that are directly public without help of reexports or type aliases.
     // These two fields are closely related to one another in that they are only
     // used for generation of the `public_items` set, not for privacy checking at
@@ -185,7 +178,9 @@ impl<'a, 'tcx> EmbargoVisitor<'a, 'tcx> {
     fn is_public_exported_ty(&self, ty: &hir::Ty) -> (bool, bool) {
         if let hir::TyPath(..) = ty.node {
             match self.tcx.def_map.borrow().get(&ty.id).unwrap().full_def() {
-                def::DefPrimTy(..) | def::DefSelfTy(..) => (true, true),
+                def::DefPrimTy(..) | def::DefSelfTy(..) | def::DefTyParam(..) => {
+                    (true, true)
+                }
                 def => {
                     if let Some(node_id) = self.tcx.map.as_local_node_id(def.def_id()) {
                         (self.public_items.contains(&node_id),
@@ -235,7 +230,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
             _ => {
                 self.prev_public = self.prev_public && item.vis == hir::Public;
                 self.prev_exported = (self.prev_exported && item.vis == hir::Public) ||
-                                     self.reexports.contains(&item.id);
+                                     self.exported_items.contains(&item.id);
 
                 self.maybe_insert_id(item.id);
             }
@@ -272,25 +267,26 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
                 }
             }
 
-            // It's not known until monomorphization if a trait impl item should be reachable
-            // from external crates or not. So, we conservatively mark all of them exported and
-            // the reachability pass (middle::reachable) marks all exported items as reachable.
-            // For example of private trait impl for private type that should be reachable see
-            // src/test/auxiliary/issue-11225-3.rs
+            // Trait impl and its items are public/exported if both the self type and the trait
+            // of this impl are public/exported
             hir::ItemImpl(_, _, _, Some(ref trait_ref), ref ty, ref impl_items) => {
-                let (public_ty, _exported_ty) = self.is_public_exported_ty(&ty);
-                let (public_trait, _exported_trait) = self.is_public_exported_trait(trait_ref);
+                let (public_ty, exported_ty) = self.is_public_exported_ty(&ty);
+                let (public_trait, exported_trait) = self.is_public_exported_trait(trait_ref);
 
                 if public_ty && public_trait {
                     self.public_items.insert(item.id);
                 }
-                self.exported_items.insert(item.id);
+                if exported_ty && exported_trait {
+                    self.exported_items.insert(item.id);
+                }
 
                 for impl_item in impl_items {
                     if public_ty && public_trait {
                         self.public_items.insert(impl_item.id);
                     }
-                    self.exported_items.insert(impl_item.id);
+                    if exported_ty && exported_trait {
+                        self.exported_items.insert(impl_item.id);
+                    }
                 }
             }
 
@@ -332,8 +328,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
                     match self.tcx.def_map.borrow().get(&ty.id).unwrap().full_def() {
                         def::DefPrimTy(..) | def::DefSelfTy(..) | def::DefTyParam(..) => {},
                         def => {
-                            let did = def.def_id();
-                            if let Some(node_id) = self.tcx.map.as_local_node_id(did) {
+                            if let Some(node_id) = self.tcx.map.as_local_node_id(def.def_id()) {
                                 self.exported_items.insert(node_id);
                             }
                         }
@@ -345,7 +340,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
                 for foreign_item in &foreign_mod.items {
                     let public = self.prev_public && foreign_item.vis == hir::Public;
                     let exported = (self.prev_exported && foreign_item.vis == hir::Public) ||
-                                   self.reexports.contains(&foreign_item.id);
+                                   self.exported_items.contains(&foreign_item.id);
 
                     if public {
                         self.public_items.insert(foreign_item.id);
@@ -385,7 +380,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
             assert!(self.export_map.contains_key(&id), "wut {}", id);
             for export in self.export_map.get(&id).unwrap() {
                 if let Some(node_id) = self.tcx.map.as_local_node_id(export.def_id) {
-                    self.reexports.insert(node_id);
+                    self.exported_items.insert(node_id);
                 }
             }
         }
@@ -1530,17 +1525,14 @@ pub fn check_crate(tcx: &ty::ctxt,
         tcx: tcx,
         exported_items: NodeSet(),
         public_items: NodeSet(),
-        reexports: NodeSet(),
         export_map: export_map,
         prev_exported: true,
         prev_public: true,
     };
     loop {
-        let before = (visitor.exported_items.len(), visitor.public_items.len(),
-                      visitor.reexports.len());
+        let before = (visitor.exported_items.len(), visitor.public_items.len());
         visit::walk_crate(&mut visitor, krate);
-        let after = (visitor.exported_items.len(), visitor.public_items.len(),
-                     visitor.reexports.len());
+        let after = (visitor.exported_items.len(), visitor.public_items.len());
         if after == before {
             break
         }
diff --git a/src/test/auxiliary/issue-11225-1.rs b/src/test/auxiliary/issue-11225-1.rs
index 37543ea1d3c..e1ec15be927 100644
--- a/src/test/auxiliary/issue-11225-1.rs
+++ b/src/test/auxiliary/issue-11225-1.rs
@@ -11,13 +11,18 @@
 mod inner {
     pub trait Trait {
         fn f(&self) { f(); }
+        fn f_ufcs(&self) { f_ufcs(); }
     }
 
     impl Trait for isize {}
 
     fn f() {}
+    fn f_ufcs() {}
 }
 
 pub fn foo<T: inner::Trait>(t: T) {
     t.f();
 }
+pub fn foo_ufcs<T: inner::Trait>(t: T) {
+    T::f_ufcs(&t);
+}
diff --git a/src/test/auxiliary/issue-11225-2.rs b/src/test/auxiliary/issue-11225-2.rs
index f12e4c9b6e7..25110edda27 100644
--- a/src/test/auxiliary/issue-11225-2.rs
+++ b/src/test/auxiliary/issue-11225-2.rs
@@ -14,15 +14,18 @@ mod inner {
     pub struct Foo;
     pub trait Trait {
         fn f(&self);
+        fn f_ufcs(&self);
     }
 
     impl Trait for Foo {
         fn f(&self) { }
+        fn f_ufcs(&self) { }
     }
 }
 
 pub trait Outer {
     fn foo<T: Trait>(&self, t: T) { t.f(); }
+    fn foo_ufcs<T: Trait>(&self, t: T) { T::f(&t); }
 }
 
 impl Outer for isize {}
@@ -30,3 +33,6 @@ impl Outer for isize {}
 pub fn foo<T: Outer>(t: T) {
     t.foo(inner::Foo);
 }
+pub fn foo_ufcs<T: Outer>(t: T) {
+    T::foo_ufcs(&t, inner::Foo)
+}
diff --git a/src/test/auxiliary/issue-11225-3.rs b/src/test/auxiliary/issue-11225-3.rs
index 51d73925dff..d48fb68ba0f 100644
--- a/src/test/auxiliary/issue-11225-3.rs
+++ b/src/test/auxiliary/issue-11225-3.rs
@@ -10,20 +10,29 @@
 
 trait PrivateTrait {
     fn private_trait_method(&self);
+    fn private_trait_method_ufcs(&self);
 }
 
 struct PrivateStruct;
 
 impl PrivateStruct {
     fn private_inherent_method(&self) { }
+    fn private_inherent_method_ufcs(&self) { }
 }
 
 impl PrivateTrait for PrivateStruct {
     fn private_trait_method(&self) { }
+    fn private_trait_method_ufcs(&self) { }
 }
 
 #[inline]
-pub fn public_generic_function() {
+pub fn public_inlinable_function() {
     PrivateStruct.private_trait_method();
     PrivateStruct.private_inherent_method();
 }
+
+#[inline]
+pub fn public_inlinable_function_ufcs() {
+    PrivateStruct::private_trait_method(&PrivateStruct);
+    PrivateStruct::private_inherent_method(&PrivateStruct);
+}
diff --git a/src/test/run-pass/issue-11225-1.rs b/src/test/run-pass/issue-11225-1.rs
index a74fdbe3de4..60789be62b3 100644
--- a/src/test/run-pass/issue-11225-1.rs
+++ b/src/test/run-pass/issue-11225-1.rs
@@ -16,4 +16,5 @@ extern crate issue_11225_1 as foo;
 
 pub fn main() {
     foo::foo(1);
+    foo::foo_ufcs(1);
 }
diff --git a/src/test/run-pass/issue-11225-2.rs b/src/test/run-pass/issue-11225-2.rs
index c6fc5e8b484..540183b7ef4 100644
--- a/src/test/run-pass/issue-11225-2.rs
+++ b/src/test/run-pass/issue-11225-2.rs
@@ -16,4 +16,5 @@ extern crate issue_11225_2 as foo;
 
 pub fn main() {
     foo::foo(1);
+    foo::foo_ufcs(1);
 }
diff --git a/src/test/run-pass/issue-11225-3.rs b/src/test/run-pass/issue-11225-3.rs
index 046c145e70e..317c3d3222d 100644
--- a/src/test/run-pass/issue-11225-3.rs
+++ b/src/test/run-pass/issue-11225-3.rs
@@ -15,5 +15,6 @@
 extern crate issue_11225_3;
 
 pub fn main() {
-    issue_11225_3::public_generic_function();
+    issue_11225_3::public_inlinable_function();
+    issue_11225_3::public_inlinable_function_ufcs();
 }