Perform doc-reachability check for inlined impls

This changes the current rule that impls within `doc(hidden)` modules
aren't inlined, to only inlining impls where the implemented
trait and type are reachable in documentation.

13 files changed, 337 insertions, 26 deletions

diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index d3db0804c24..c1a8f747de1 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -113,6 +113,7 @@ pub enum InlinedItemRef<'a> {
 /// LOCAL_CRATE in their DefId.
 pub const LOCAL_CRATE: ast::CrateNum = 0;
 
+#[derive(Copy, Clone)]
 pub struct ChildItem {
     pub def: DefLike,
     pub name: ast::Name,
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index 6cca602466a..345eb5cdee4 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -28,7 +28,7 @@ use rustc_const_eval::lookup_const_by_id;
 
 use core::DocContext;
 use doctree;
-use clean::{self, Attributes, GetDefId};
+use clean::{self, GetDefId};
 
 use super::{Clean, ToSource};
 
@@ -227,6 +227,15 @@ fn build_type(cx: &DocContext, tcx: &TyCtxt, did: DefId) -> clean::ItemEnum {
     }, false)
 }
 
+fn is_item_doc_reachable(cx: &DocContext, did: DefId) -> bool {
+    use ::visit_lib::LibEmbargoVisitor;
+
+    if cx.analyzed_crates.borrow_mut().insert(did.krate) {
+        LibEmbargoVisitor::new(cx).visit_lib(did.krate);
+    }
+    cx.access_levels.borrow().is_public(did)
+}
+
 pub fn build_impls(cx: &DocContext,
                    tcx: &TyCtxt,
                    did: DefId) -> Vec<clean::Item> {
@@ -260,11 +269,6 @@ pub fn build_impls(cx: &DocContext,
             match def {
                 cstore::DlImpl(did) => build_impl(cx, tcx, did, impls),
                 cstore::DlDef(Def::Mod(did)) => {
-                    // Don't recurse if this is a #[doc(hidden)] module
-                    if load_attrs(cx, tcx, did).list("doc").has_word("hidden") {
-                        return;
-                    }
-
                     for item in tcx.sess.cstore.item_children(did) {
                         populate_impls(cx, tcx, item.def, impls)
                     }
@@ -301,10 +305,11 @@ pub fn build_impl(cx: &DocContext,
 
     let attrs = load_attrs(cx, tcx, did);
     let associated_trait = tcx.impl_trait_ref(did);
-    if let Some(ref t) = associated_trait {
-        // If this is an impl for a #[doc(hidden)] trait, be sure to not inline
-        let trait_attrs = load_attrs(cx, tcx, t.def_id);
-        if trait_attrs.list("doc").has_word("hidden") {
+
+    // Only inline impl if the implemented trait is
+    // reachable in rustdoc generated documentation
+    if let Some(traitref) = associated_trait {
+        if !is_item_doc_reachable(cx, traitref.def_id) {
             return
         }
     }
@@ -330,6 +335,17 @@ pub fn build_impl(cx: &DocContext,
         });
     }
 
+    let ty = tcx.lookup_item_type(did);
+    let for_ = ty.ty.clean(cx);
+
+    // Only inline impl if the implementing type is
+    // reachable in rustdoc generated documentation
+    if let Some(did) = for_.def_id() {
+        if !is_item_doc_reachable(cx, did) {
+            return
+        }
+    }
+
     let predicates = tcx.lookup_predicates(did);
     let trait_items = tcx.sess.cstore.impl_items(did)
             .iter()
@@ -412,7 +428,6 @@ pub fn build_impl(cx: &DocContext,
         }
     }).collect::<Vec<_>>();
     let polarity = tcx.trait_impl_polarity(did);
-    let ty = tcx.lookup_item_type(did);
     let trait_ = associated_trait.clean(cx).map(|bound| {
         match bound {
             clean::TraitBound(polyt, _) => polyt.trait_,
@@ -436,7 +451,7 @@ pub fn build_impl(cx: &DocContext,
             derived: clean::detect_derived(&attrs),
             provided_trait_methods: provided,
             trait_: trait_,
-            for_: ty.ty.clean(cx),
+            for_: for_,
             generics: (&ty.generics, &predicates, subst::TypeSpace).clean(cx),
             items: trait_items,
             polarity: polarity.map(|p| { p.clean(cx) }),
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index bba394bb90d..019f7401b54 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -57,7 +57,7 @@ use doctree;
 use visit_ast;
 use html::item_type::ItemType;
 
-mod inline;
+pub mod inline;
 mod simplify;
 
 // extract the stability index for a node from tcx, if possible
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index c9773ebccb4..3cb76ca2339 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -14,6 +14,7 @@ use rustc_driver::{driver, target_features, abort_on_err};
 use rustc::dep_graph::DepGraph;
 use rustc::session::{self, config};
 use rustc::hir::def_id::DefId;
+use rustc::middle::cstore::LOCAL_CRATE;
 use rustc::middle::privacy::AccessLevels;
 use rustc::ty::{self, TyCtxt};
 use rustc::hir::map as hir_map;
@@ -29,7 +30,7 @@ use syntax::feature_gate::UnstableFeatures;
 use syntax::parse::token;
 
 use std::cell::{RefCell, Cell};
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::rc::Rc;
 
 use visit_ast::RustdocVisitor;
@@ -53,12 +54,17 @@ pub struct DocContext<'a, 'tcx: 'a> {
     pub maybe_typed: MaybeTyped<'a, 'tcx>,
     pub input: Input,
     pub all_crate_impls: RefCell<HashMap<ast::CrateNum, Vec<clean::Item>>>,
-    // Later on moved into `clean::Crate`
+    pub deref_trait_did: Cell<Option<DefId>>,
+    /// Crates which have already been processed for `Self.access_levels`
+    pub analyzed_crates: RefCell<HashSet<ast::CrateNum>>,
+    // Note that external items for which `doc(hidden)` applies to are shown as
+    // non-reachable while local items aren't. This is because we're reusing
+    // the access levels from crateanalysis.
+    /// Later on moved into `clean::Crate`
     pub access_levels: RefCell<AccessLevels<DefId>>,
-    // Later on moved into `html::render::CACHE_KEY`
+    /// Later on moved into `html::render::CACHE_KEY`
     pub renderinfo: RefCell<RenderInfo>,
-    pub deref_trait_did: Cell<Option<DefId>>,
-    // Later on moved through `clean::Crate` into `html::render::CACHE_KEY`
+    /// Later on moved through `clean::Crate` into `html::render::CACHE_KEY`
     pub external_traits: RefCell<HashMap<DefId, clean::Trait>>,
 }
 
@@ -166,6 +172,8 @@ pub fn run_core(search_paths: SearchPaths,
                                   .map(|(k, v)| (tcx.map.local_def_id(k), v))
                                   .collect()
         };
+        let mut analyzed_crates = HashSet::new();
+        analyzed_crates.insert(LOCAL_CRATE);
 
         let ctxt = DocContext {
             map: &tcx.map,
@@ -173,6 +181,7 @@ pub fn run_core(search_paths: SearchPaths,
             input: input,
             all_crate_impls: RefCell::new(HashMap::new()),
             deref_trait_did: Cell::new(None),
+            analyzed_crates: RefCell::new(analyzed_crates),
             access_levels: RefCell::new(access_levels),
             external_traits: RefCell::new(HashMap::new()),
             renderinfo: RefCell::new(Default::default()),
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index 2d59747d00c..c83029107c3 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -253,6 +253,9 @@ pub struct Cache {
     parent_is_trait_impl: bool,
     search_index: Vec<IndexItem>,
     stripped_mod: bool,
+    // Note that external items for which `doc(hidden)` applies to are shown as
+    // non-reachable while local items aren't. This is because we're reusing
+    // the access levels from crateanalysis.
     access_levels: Arc<AccessLevels<DefId>>,
     deref_trait_did: Option<DefId>,
 
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index 0d80e702816..86aad10e02f 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -80,6 +80,7 @@ pub mod markdown;
 pub mod passes;
 pub mod plugins;
 pub mod visit_ast;
+pub mod visit_lib;
 pub mod test;
 mod flock;
 
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index 5a7050fb42f..df3c81e7e3b 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::cell::{RefCell, Cell};
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::env;
 use std::ffi::OsString;
 use std::io::prelude::*;
@@ -111,6 +111,7 @@ pub fn run(input: &str,
         external_traits: RefCell::new(HashMap::new()),
         all_crate_impls: RefCell::new(HashMap::new()),
         deref_trait_did: Cell::new(None),
+        analyzed_crates: RefCell::new(HashSet::new()),
         access_levels: Default::default(),
         renderinfo: Default::default(),
     };
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index a406c843b82..2bce8f4c2a1 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -21,12 +21,14 @@ use syntax::attr::AttrMetaMethods;
 use syntax::codemap::Span;
 
 use rustc::hir::map as hir_map;
+use rustc::hir::def::Def;
 use rustc::middle::stability;
+use rustc::middle::privacy::AccessLevel;
 
 use rustc::hir;
 
 use core;
-use clean::{Clean, Attributes};
+use clean::{self, Clean, Attributes};
 use doctree::*;
 
 // looks to me like the first two of these are actually
@@ -240,16 +242,40 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
             Some(tcx) => tcx,
             None => return false
         };
-        let def = tcx.def_map.borrow()[&id].def_id();
-        let def_node_id = match tcx.map.as_local_node_id(def) {
-            Some(n) => n, None => return false
-        };
+        let def = tcx.def_map.borrow()[&id];
+        let def_did = def.def_id();
 
         let use_attrs = tcx.map.attrs(id).clean(self.cx);
+        let is_no_inline = use_attrs.list("doc").has_word("no_inline");
 
-        let is_private = !self.cx.access_levels.borrow().is_public(def);
+        // For cross-crate impl inlining we need to know whether items are
+        // reachable in documentation - a previously nonreachable item can be
+        // made reachable by cross-crate inlining which we're checking here.
+        // (this is done here because we need to know this upfront)
+        if !def.def_id().is_local() && !is_no_inline {
+            let attrs = clean::inline::load_attrs(self.cx, tcx, def_did);
+            let self_is_hidden = attrs.list("doc").has_word("hidden");
+            match def.base_def {
+                Def::Trait(did) |
+                Def::Struct(did) |
+                Def::Enum(did) |
+                Def::TyAlias(did) if !self_is_hidden => {
+                    self.cx.access_levels.borrow_mut().map.insert(did, AccessLevel::Public);
+                },
+                Def::Mod(did) => if !self_is_hidden {
+                    ::visit_lib::LibEmbargoVisitor::new(self.cx).visit_mod(did);
+                },
+                _ => {},
+            }
+            return false
+        }
+
+        let def_node_id = match tcx.map.as_local_node_id(def_did) {
+            Some(n) => n, None => return false
+        };
+
+        let is_private = !self.cx.access_levels.borrow().is_public(def_did);
         let is_hidden = inherits_doc_hidden(self.cx, def_node_id);
-        let is_no_inline = use_attrs.list("doc").has_word("no_inline");
 
         // Only inline if requested or if the item would otherwise be stripped
         if (!please_inline && !is_private && !is_hidden) || is_no_inline {
diff --git a/src/librustdoc/visit_lib.rs b/src/librustdoc/visit_lib.rs
new file mode 100644
index 00000000000..54eae6e237e
--- /dev/null
+++ b/src/librustdoc/visit_lib.rs
@@ -0,0 +1,104 @@
+// Copyright 2016 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.
+
+use rustc::middle::cstore::{CrateStore, ChildItem, DefLike};
+use rustc::middle::privacy::{AccessLevels, AccessLevel};
+use rustc::hir::def::Def;
+use rustc::hir::def_id::{CRATE_DEF_INDEX, DefId};
+use rustc::ty::Visibility;
+use syntax::ast;
+
+use std::cell::RefMut;
+
+use clean::{Attributes, Clean};
+
+// FIXME: since this is only used for cross-crate impl inlining this only
+//        handles traits and items for which traits can be implemented
+
+/// Similar to `librustc_privacy::EmbargoVisitor`, but also takes
+/// specific rustdoc annotations into account (i.e. `doc(hidden)`)
+pub struct LibEmbargoVisitor<'a, 'b: 'a, 'tcx: 'b> {
+    cx: &'a ::core::DocContext<'b, 'tcx>,
+    cstore: &'a CrateStore<'tcx>,
+    // Accessibility levels for reachable nodes
+    access_levels: RefMut<'a, AccessLevels<DefId>>,
+    // Previous accessibility level, None means unreachable
+    prev_level: Option<AccessLevel>,
+}
+
+impl<'a, 'b, 'tcx> LibEmbargoVisitor<'a, 'b, 'tcx> {
+    pub fn new(cx: &'a ::core::DocContext<'b, 'tcx>) -> LibEmbargoVisitor<'a, 'b, 'tcx> {
+        LibEmbargoVisitor {
+            cx: cx,
+            cstore: &*cx.sess().cstore,
+            access_levels: cx.access_levels.borrow_mut(),
+            prev_level: Some(AccessLevel::Public),
+        }
+    }
+
+    pub fn visit_lib(&mut self, cnum: ast::CrateNum) {
+        let did = DefId { krate: cnum, index: CRATE_DEF_INDEX };
+        self.visit_mod(did);
+    }
+
+    // Updates node level and returns the updated level
+    fn update(&mut self, did: DefId, level: Option<AccessLevel>) -> Option<AccessLevel> {
+        let attrs: Vec<_> = self.cx.tcx().get_attrs(did).iter()
+                                                        .map(|a| a.clean(self.cx))
+                                                        .collect();
+        let is_hidden = attrs.list("doc").has_word("hidden");
+
+        let old_level = self.access_levels.map.get(&did).cloned();
+        // Accessibility levels can only grow
+        if level > old_level && !is_hidden {
+            self.access_levels.map.insert(did, level.unwrap());
+            level
+        } else {
+            old_level
+        }
+    }
+
+    pub fn visit_mod(&mut self, did: DefId) {
+        for item in self.cstore.item_children(did) {
+            if let DefLike::DlDef(def) = item.def {
+                match def {
+                    Def::Trait(did) |
+                    Def::Struct(did) |
+                    Def::Mod(did) |
+                    Def::Enum(did) |
+                    Def::TyAlias(did) => self.visit_item(did, item),
+                    _ => {}
+                }
+            }
+        }
+    }
+
+    fn visit_item(&mut self, did: DefId, item: ChildItem) {
+        let inherited_item_level = match item.def {
+            DefLike::DlImpl(..) | DefLike::DlField => unreachable!(),
+            DefLike::DlDef(def) => {
+                match def {
+                    Def::ForeignMod(..) => self.prev_level,
+                    _ => if item.vis == Visibility::Public { self.prev_level } else { None }
+                }
+            }
+        };
+
+        let item_level = self.update(did, inherited_item_level);
+
+        if let DefLike::DlDef(Def::Mod(did)) = item.def {
+            let orig_level = self.prev_level;
+
+            self.prev_level = item_level;
+            self.visit_mod(did);
+            self.prev_level = orig_level;
+        }
+    }
+}
diff --git a/src/test/auxiliary/rustdoc-nonreachable-impls.rs b/src/test/auxiliary/rustdoc-nonreachable-impls.rs
new file mode 100644
index 00000000000..22a311d5797
--- /dev/null
+++ b/src/test/auxiliary/rustdoc-nonreachable-impls.rs
@@ -0,0 +1,44 @@
+// Copyright 2016 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.
+
+pub struct Foo;
+
+pub trait Woof {}
+pub trait Bark {}
+
+mod private {
+    // should be shown
+    impl ::Woof for ::Foo {}
+
+    pub trait Bar {}
+    pub struct Wibble;
+
+    // these should not be shown
+    impl Bar for ::Foo {}
+    impl Bar for Wibble {}
+    impl ::Bark for Wibble {}
+    impl ::Woof for Wibble {}
+}
+
+#[doc(hidden)]
+pub mod hidden {
+    // should be shown
+    impl ::Bark for ::Foo {}
+
+    pub trait Qux {}
+    pub struct Wobble;
+
+
+    // these should only be shown if they're reexported correctly
+    impl Qux for ::Foo {}
+    impl Qux for Wobble {}
+    impl ::Bark for Wobble {}
+    impl ::Woof for Wobble {}
+}
diff --git a/src/test/rustdoc/inline_cross/issue-31948-1.rs b/src/test/rustdoc/inline_cross/issue-31948-1.rs
new file mode 100644
index 00000000000..e953b66fce1
--- /dev/null
+++ b/src/test/rustdoc/inline_cross/issue-31948-1.rs
@@ -0,0 +1,37 @@
+// Copyright 2016 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.
+
+// aux-build:rustdoc-nonreachable-impls.rs
+// build-aux-docs
+// ignore-cross-compile
+
+extern crate rustdoc_nonreachable_impls;
+
+// @has issue_31948_1/struct.Wobble.html
+// @has - '//*[@class="impl"]//code' 'Bark for'
+// @has - '//*[@class="impl"]//code' 'Woof for'
+// @!has - '//*[@class="impl"]//code' 'Bar for'
+// @!has - '//*[@class="impl"]//code' 'Qux for'
+pub use rustdoc_nonreachable_impls::hidden::Wobble;
+
+// @has issue_31948_1/trait.Bark.html
+// FIXME(33025): has - '//code' 'for Foo'
+// @has - '//code' 'for Wobble'
+// @!has - '//code' 'for Wibble'
+pub use rustdoc_nonreachable_impls::Bark;
+
+// @has issue_31948_1/trait.Woof.html
+// FIXME(33025): has - '//code' 'for Foo'
+// @has - '//code' 'for Wobble'
+// @!has - '//code' 'for Wibble'
+pub use rustdoc_nonreachable_impls::Woof;
+
+// @!has issue_31948_1/trait.Bar.html
+// @!has issue_31948_1/trait.Qux.html
diff --git a/src/test/rustdoc/inline_cross/issue-31948-2.rs b/src/test/rustdoc/inline_cross/issue-31948-2.rs
new file mode 100644
index 00000000000..0423fa1de3b
--- /dev/null
+++ b/src/test/rustdoc/inline_cross/issue-31948-2.rs
@@ -0,0 +1,31 @@
+// Copyright 2016 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.
+
+// aux-build:rustdoc-nonreachable-impls.rs
+// build-aux-docs
+// ignore-cross-compile
+
+extern crate rustdoc_nonreachable_impls;
+
+// @has issue_31948_2/struct.Wobble.html
+// @has - '//*[@class="impl"]//code' 'Qux for'
+// @has - '//*[@class="impl"]//code' 'Bark for'
+// @has - '//*[@class="impl"]//code' 'Woof for'
+// @!has - '//*[@class="impl"]//code' 'Bar for'
+pub use rustdoc_nonreachable_impls::hidden::Wobble;
+
+// @has issue_31948_2/trait.Qux.html
+// FIXME(33025): has - '//code' 'for Foo'
+// @has - '//code' 'for Wobble'
+pub use rustdoc_nonreachable_impls::hidden::Qux;
+
+// @!has issue_31948_2/trait.Bar.html
+// @!has issue_31948_2/trait.Woof.html
+// @!has issue_31948_2/trait.Bark.html
diff --git a/src/test/rustdoc/inline_cross/issue-31948.rs b/src/test/rustdoc/inline_cross/issue-31948.rs
new file mode 100644
index 00000000000..073e8eb50fb
--- /dev/null
+++ b/src/test/rustdoc/inline_cross/issue-31948.rs
@@ -0,0 +1,39 @@
+// Copyright 2016 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.
+
+// aux-build:rustdoc-nonreachable-impls.rs
+// build-aux-docs
+// ignore-cross-compile
+
+extern crate rustdoc_nonreachable_impls;
+
+// @has issue_31948/struct.Foo.html
+// @has - '//*[@class="impl"]//code' 'Bark for'
+// @has - '//*[@class="impl"]//code' 'Woof for'
+// @!has - '//*[@class="impl"]//code' 'Bar for'
+// @!has - '//*[@class="impl"]//code' 'Qux for'
+pub use rustdoc_nonreachable_impls::Foo;
+
+// @has issue_31948/trait.Bark.html
+// @has - '//code' 'for Foo'
+// @!has - '//code' 'for Wibble'
+// @!has - '//code' 'for Wobble'
+pub use rustdoc_nonreachable_impls::Bark;
+
+// @has issue_31948/trait.Woof.html
+// @has - '//code' 'for Foo'
+// @!has - '//code' 'for Wibble'
+// @!has - '//code' 'for Wobble'
+pub use rustdoc_nonreachable_impls::Woof;
+
+// @!has issue_31948/trait.Bar.html
+// @!has issue_31948/trait.Qux.html
+// @!has issue_31948/struct.Wibble.html
+// @!has issue_31948/struct.Wobble.html