Generate documentation for auto-trait impls

A new section is added to both both struct and trait doc pages.

On struct/enum pages, a new 'Auto Trait Implementations' section displays any
synthetic implementations for auto traits. Currently, this is only done
for Send and Sync.

On trait pages, a new 'Auto Implementors' section displays all types
which automatically implement the trait. Effectively, this is a list of
all public types in the standard library.

Synthesized impls for a particular auto trait ('synthetic impls') take
into account generic bounds. For example, a type 'struct Foo<T>(T)' will
have 'impl<T> Send for Foo<T> where T: Send' generated for it.

Manual implementations of auto traits are also taken into account. If we have
the following types:

'struct Foo<T>(T)'
'struct Wrapper<T>(Foo<T>)'
'unsafe impl<T> Send for Wrapper<T>' // pretend that Wrapper<T> makes
this sound somehow

Then Wrapper will have the following impl generated:
'impl<T> Send for Wrapper<T>'
reflecting the fact that 'T: Send' need not hold for 'Wrapper<T>: Send'
to hold

Lifetimes, HRTBS, and projections (e.g. '<T as Iterator>::Item') are
taken into account by synthetic impls

However, if a type can *never* implement a particular auto trait
(e.g. 'struct MyStruct<T>(*const T)'), then a negative impl will be
generated (in this case, 'impl<T> !Send for MyStruct<T>')

All of this means that a user should be able to copy-paste a synthetic
impl into their code, without any observable changes in behavior
(assuming the rest of the program remains unchanged).

8 files changed, 242 insertions, 0 deletions

diff --git a/src/test/rustdoc/synthetic_auto/basic.rs b/src/test/rustdoc/synthetic_auto/basic.rs
new file mode 100644
index 00000000000..8ff84d11a50
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/basic.rs
@@ -0,0 +1,18 @@
+// Copyright 2018 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.
+
+// @has basic/struct.Foo.html
+// @has - '//code' 'impl<T> Send for Foo<T> where T: Send'
+// @has - '//code' 'impl<T> Sync for Foo<T> where T: Sync'
+// @count - '//*[@id="implementations-list"]/*[@class="impl"]' 0
+// @count - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]' 2
+pub struct Foo<T> {
+    field: T,
+}
diff --git a/src/test/rustdoc/synthetic_auto/complex.rs b/src/test/rustdoc/synthetic_auto/complex.rs
new file mode 100644
index 00000000000..896d49ca79a
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/complex.rs
@@ -0,0 +1,52 @@
+// Copyright 2018 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.
+
+mod foo {
+    pub trait MyTrait<'a> {
+        type MyItem: ?Sized;
+    }
+
+    pub struct Inner<'a, Q, R: ?Sized> {
+        field: Q,
+        field3: &'a u8,
+        my_foo: Foo<Q>,
+        field2: R,
+    }
+
+    pub struct Outer<'a, T, K: ?Sized> {
+        my_inner: Inner<'a, T, K>,
+    }
+
+    pub struct Foo<T> {
+        myfield: T,
+    }
+}
+
+// @has complex/struct.NotOuter.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'a, T, K: \
+// ?Sized> Send for NotOuter<'a, T, K> where 'a: 'static, K: for<'b> Fn((&'b bool, &'a u8)) \
+// -> &'b i8, <T as MyTrait<'a>>::MyItem: Copy,  T: MyTrait<'a>"
+
+pub use foo::{Foo, Inner as NotInner, MyTrait as NotMyTrait, Outer as NotOuter};
+
+unsafe impl<T> Send for Foo<T>
+where
+    T: NotMyTrait<'static>,
+{
+}
+
+unsafe impl<'a, Q, R: ?Sized> Send for NotInner<'a, Q, R>
+where
+    Q: NotMyTrait<'a>,
+    <Q as NotMyTrait<'a>>::MyItem: Copy,
+    /* for<'b> */ R: for<'b> Fn((&'b bool, &'a u8)) -> &'b i8,
+    Foo<Q>: Send,
+{
+}
diff --git a/src/test/rustdoc/synthetic_auto/lifetimes.rs b/src/test/rustdoc/synthetic_auto/lifetimes.rs
new file mode 100644
index 00000000000..2f92627f954
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/lifetimes.rs
@@ -0,0 +1,28 @@
+// Copyright 2018 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 Inner<'a, T: 'a> {
+    field: &'a T,
+}
+
+unsafe impl<'a, T> Send for Inner<'a, T>
+where
+    'a: 'static,
+    T: for<'b> Fn(&'b bool) -> &'a u8,
+{}
+
+// @has lifetimes/struct.Foo.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'c, K> Send \
+// for Foo<'c, K> where 'c: 'static, K: for<'b> Fn(&'b bool) -> &'c u8"
+//
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'c, K> Sync \
+// for Foo<'c, K> where K: Sync"
+pub struct Foo<'c, K: 'c> {
+    inner_field: Inner<'c, K>,
+}
diff --git a/src/test/rustdoc/synthetic_auto/manual.rs b/src/test/rustdoc/synthetic_auto/manual.rs
new file mode 100644
index 00000000000..d81e6309dff
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/manual.rs
@@ -0,0 +1,24 @@
+// Copyright 2018 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.
+
+// @has manual/struct.Foo.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' 'impl<T> Sync for \
+// Foo<T> where T: Sync'
+//
+// @has - '//*[@id="implementations-list"]/*[@class="impl"]/*/code' \
+// 'impl<T> Send for Foo<T>'
+//
+// @count - '//*[@id="implementations-list"]/*[@class="impl"]' 1
+// @count - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]' 1
+pub struct Foo<T> {
+    field: T,
+}
+
+unsafe impl<T> Send for Foo<T> {}
diff --git a/src/test/rustdoc/synthetic_auto/negative.rs b/src/test/rustdoc/synthetic_auto/negative.rs
new file mode 100644
index 00000000000..ec9cb710f1f
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/negative.rs
@@ -0,0 +1,23 @@
+// Copyright 2018 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 Inner<T: Copy> {
+    field: *mut T,
+}
+
+// @has negative/struct.Outer.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<T> !Send for \
+// Outer<T>"
+//
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<T> \
+// !Sync for Outer<T>"
+pub struct Outer<T: Copy> {
+    inner_field: Inner<T>,
+}
diff --git a/src/test/rustdoc/synthetic_auto/nested.rs b/src/test/rustdoc/synthetic_auto/nested.rs
new file mode 100644
index 00000000000..1f33a8b13cb
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/nested.rs
@@ -0,0 +1,28 @@
+// Copyright 2018 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 Inner<T> {
+    field: T,
+}
+
+unsafe impl<T> Send for Inner<T>
+where
+    T: Copy,
+{
+}
+
+// @has nested/struct.Foo.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' 'impl<T> Send for \
+// Foo<T> where T: Copy'
+//
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' \
+// 'impl<T> Sync for Foo<T> where T: Sync'
+pub struct Foo<T> {
+    inner_field: Inner<T>,
+}
diff --git a/src/test/rustdoc/synthetic_auto/no-redundancy.rs b/src/test/rustdoc/synthetic_auto/no-redundancy.rs
new file mode 100644
index 00000000000..0b37f2ed317
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/no-redundancy.rs
@@ -0,0 +1,26 @@
+// Copyright 2018 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 Inner<T> {
+    field: T,
+}
+
+unsafe impl<T> Send for Inner<T>
+where
+    T: Copy + Send,
+{
+}
+
+// @has no_redundancy/struct.Outer.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<T> Send for \
+// Outer<T> where T: Copy + Send"
+pub struct Outer<T> {
+    inner_field: Inner<T>,
+}
diff --git a/src/test/rustdoc/synthetic_auto/project.rs b/src/test/rustdoc/synthetic_auto/project.rs
new file mode 100644
index 00000000000..e1b8621ff6d
--- /dev/null
+++ b/src/test/rustdoc/synthetic_auto/project.rs
@@ -0,0 +1,43 @@
+// Copyright 2018 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 Inner<'a, T: 'a> {
+    field: &'a T,
+}
+
+trait MyTrait {
+    type MyItem;
+}
+
+trait OtherTrait {}
+
+unsafe impl<'a, T> Send for Inner<'a, T>
+where
+    'a: 'static,
+    T: MyTrait<MyItem = bool>,
+{
+}
+unsafe impl<'a, T> Sync for Inner<'a, T>
+where
+    'a: 'static,
+    T: MyTrait,
+    <T as MyTrait>::MyItem: OtherTrait,
+{
+}
+
+// @has project/struct.Foo.html
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'c, K> Send \
+// for Foo<'c, K> where 'c: 'static, K: MyTrait<MyItem = bool>"
+//
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'c, K> Sync \
+// for Foo<'c, K> where 'c: 'static, K: MyTrait, <K as MyTrait>::MyItem: OtherTrait"
+pub struct Foo<'c, K: 'c> {
+    inner_field: Inner<'c, K>,
+}