Rollup merge of #47833 - Aaron1011:final_auto_trait, r=GuillaumeGomez

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.

![Auto trait implementations for Cloned](https://i.imgur.com/XtTV6IJ.png)

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.

![Auto trait implementors for Send](https://i.imgur.com/3GRBpTy.png)

Synthesized impls for a particular auto trait ('synthetic impls') take generic bounds into account. For example, a type
```rust
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:

```rust
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:
```rust
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:

![A ridiculous demonstration type](https://i.imgur.com/TkZMWuN.png)

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 syntheticimpl into their code, without any observable changes in behavior (assuming the rest of the program remains unchanged).

11 files changed, 247 insertions, 4 deletions

diff --git a/src/test/rustdoc/duplicate_impls/issue-33054.rs b/src/test/rustdoc/duplicate_impls/issue-33054.rs
index df6ebcae107..43a425d4c5e 100644
--- a/src/test/rustdoc/duplicate_impls/issue-33054.rs
+++ b/src/test/rustdoc/duplicate_impls/issue-33054.rs
@@ -11,7 +11,8 @@
 // @has issue_33054/impls/struct.Foo.html
 // @has - '//code' 'impl Foo'
 // @has - '//code' 'impl Bar for Foo'
-// @count - '//*[@class="impl"]' 2
+// @count - '//*[@id="implementations-list"]/*[@class="impl"]' 1
+// @count - '//*[@id="main"]/*[@class="impl"]' 1
 // @has issue_33054/impls/bar/trait.Bar.html
 // @has - '//code' 'impl Bar for Foo'
 // @count - '//*[@class="struct"]' 1
diff --git a/src/test/rustdoc/issue-21474.rs b/src/test/rustdoc/issue-21474.rs
index 36f160acf1c..553bbeb0cff 100644
--- a/src/test/rustdoc/issue-21474.rs
+++ b/src/test/rustdoc/issue-21474.rs
@@ -17,5 +17,5 @@ mod inner {
 pub trait Blah { }
 
 // @count issue_21474/struct.What.html \
-//        '//*[@class="impl"]' 1
+//        '//*[@id="implementations-list"]/*[@class="impl"]' 1
 pub struct What;
diff --git a/src/test/rustdoc/issue-45584.rs b/src/test/rustdoc/issue-45584.rs
index 6d6ae3dc94a..b0e64557be2 100644
--- a/src/test/rustdoc/issue-45584.rs
+++ b/src/test/rustdoc/issue-45584.rs
@@ -14,12 +14,12 @@ pub trait Bar<T, U> {}
 
 // @has 'foo/struct.Foo1.html'
 pub struct Foo1;
-// @count - '//*[@class="impl"]' 1
+// @count - '//*[@id="implementations-list"]/*[@class="impl"]' 1
 // @has - '//*[@class="impl"]' "impl Bar<Foo1, &'static Foo1> for Foo1"
 impl Bar<Foo1, &'static Foo1> for Foo1 {}
 
 // @has 'foo/struct.Foo2.html'
 pub struct Foo2;
-// @count - '//*[@class="impl"]' 1
+// @count - '//*[@id="implementations-list"]/*[@class="impl"]' 1
 // @has - '//*[@class="impl"]' "impl Bar<&'static Foo2, Foo2> for u8"
 impl Bar<&'static Foo2, Foo2> for u8 {}
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..531798c30c6
--- /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 K: for<'b> Fn((&'b bool, &'a u8)) \
+// -> &'b i8, T: MyTrait<'a>, <T as MyTrait<'a>>::MyItem: Copy, 'a: 'static"
+
+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,
+    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..272925e5db5
--- /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 K: for<'b> Fn(&'b bool) -> &'c u8, 'c: 'static"
+//
+// @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..977607fb148
--- /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 K: MyTrait<MyItem = bool>, 'c: 'static"
+//
+// @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<'c, K> Sync \
+// for Foo<'c, K> where K: MyTrait, <K as MyTrait>::MyItem: OtherTrait, 'c: 'static,"
+pub struct Foo<'c, K: 'c> {
+    inner_field: Inner<'c, K>,
+}