Auto merge of #74489 - jyn514:assoc-items, r=manishearth,petrochenkov

Fix intra-doc links for associated items

@Manishearth and I found that links of the following sort are broken:
```rust
$ cat str_from.rs
/// [`String::from`]
pub fn foo() {}
$ rustdoc str_from.rs
warning: `[String::from]` cannot be resolved, ignoring it.
 --> str_from.rs:4:6
  |
4 | /// [`String::from`]
  |      ^^^^^^^^^^^^^^ cannot be resolved, ignoring
```
It turns out this is because the current implementation only looks at inherent impls (`impl Bar {}`) and traits _for the item being documented_. Note that this is not the same as the item being _linked_ to. So this code would work:

```rust
pub trait T1 {
    fn method();
}

pub struct S;
impl T1 for S {
    /// [S::method] on method
    fn method() {}
}
```

but putting the documentation on `trait T1` would not.

~~I realized that writing it up that my fix is only partially correct: It removes the inherent impls code when it should instead remove the `trait_item` code.~~ Fixed.

Additionally, I discovered while writing this there is some ambiguity: you could have multiple methods with the same name, but for different traits:

```rust
pub trait T1 {
    fn method();
}

pub trait T2 {
    fn method();
}

/// See [S::method]
pub struct S;
```

Rustdoc should give an ambiguity error here, but since there is currently no way to disambiguate the traits (https://github.com/rust-lang/rust/issues/74563) it does not (https://github.com/rust-lang/rust/pull/74489#issuecomment-673878404).

There is a _third_ ambiguity that pops up: What if the trait is generic and is implemented multiple times with different generic parameters? In this case, my fix does not do very well: it thinks there is only one trait instantiated and links to that trait:

```
/// [`String::from`] -- this resolves to https://doc.rust-lang.org/nightly/alloc/string/struct.String.html#method.from
pub fn foo() {}
```

However, every `From` implementation has a method called `from`! So the browser picks a random one. This is not the desired behavior, but it's not clear how to avoid it.

To be consistent with the rest of intra-doc links, this only resolves associated items from traits that are in scope. This required changes to rustc_resolve to work cross-crate; the relevant commits are prefixed with `resolve: `. As a bonus, considering only traits in scope is slightly faster. To avoid re-calculating the traits over and over, rustdoc uses a cache to store the traits in scope for a given module.

4 files changed, 123 insertions, 0 deletions

diff --git a/src/test/rustdoc-ui/assoc-item-not-in-scope.rs b/src/test/rustdoc-ui/assoc-item-not-in-scope.rs
new file mode 100644
index 00000000000..c5bb4305db7
--- /dev/null
+++ b/src/test/rustdoc-ui/assoc-item-not-in-scope.rs
@@ -0,0 +1,22 @@
+#![deny(broken_intra_doc_links)]
+
+#[derive(Debug)]
+/// Link to [`S::fmt`]
+//~^ ERROR unresolved link
+pub struct S;
+
+pub mod inner {
+    use std::fmt::Debug;
+    use super::S;
+
+    /// Link to [`S::fmt`]
+    pub fn f() {}
+}
+
+pub mod ambiguous {
+    use std::fmt::{Display, Debug};
+    use super::S;
+
+    /// Link to [`S::fmt`]
+    pub fn f() {}
+}
diff --git a/src/test/rustdoc-ui/assoc-item-not-in-scope.stderr b/src/test/rustdoc-ui/assoc-item-not-in-scope.stderr
new file mode 100644
index 00000000000..8827c9351a6
--- /dev/null
+++ b/src/test/rustdoc-ui/assoc-item-not-in-scope.stderr
@@ -0,0 +1,15 @@
+error: unresolved link to `S::fmt`
+  --> $DIR/assoc-item-not-in-scope.rs:4:14
+   |
+LL | /// Link to [`S::fmt`]
+   |              ^^^^^^^^ unresolved link
+   |
+note: the lint level is defined here
+  --> $DIR/assoc-item-not-in-scope.rs:1:9
+   |
+LL | #![deny(broken_intra_doc_links)]
+   |         ^^^^^^^^^^^^^^^^^^^^^^
+   = help: to escape `[` and `]` characters, add '\' before them like `\[` or `\]`
+
+error: aborting due to previous error
+
diff --git a/src/test/rustdoc/intra-link-associated-defaults.rs b/src/test/rustdoc/intra-link-associated-defaults.rs
new file mode 100644
index 00000000000..2051129b948
--- /dev/null
+++ b/src/test/rustdoc/intra-link-associated-defaults.rs
@@ -0,0 +1,27 @@
+// ignore-tidy-linelength
+#![deny(intra_doc_link_resolution_failure)]
+#![feature(associated_type_defaults)]
+
+pub trait TraitWithDefault {
+    type T = usize;
+    fn f() -> Self::T {
+        0
+    }
+}
+
+/// Link to [UsesDefaults::T] and [UsesDefaults::f]
+// @has 'intra_link_associated_defaults/struct.UsesDefaults.html' '//a[@href="../intra_link_associated_defaults/struct.UsesDefaults.html#associatedtype.T"]' 'UsesDefaults::T'
+// @has 'intra_link_associated_defaults/struct.UsesDefaults.html' '//a[@href="../intra_link_associated_defaults/struct.UsesDefaults.html#method.f"]' 'UsesDefaults::f'
+pub struct UsesDefaults;
+impl TraitWithDefault for UsesDefaults {}
+
+/// Link to [OverridesDefaults::T] and [OverridesDefaults::f]
+// @has 'intra_link_associated_defaults/struct.OverridesDefaults.html' '//a[@href="../intra_link_associated_defaults/struct.OverridesDefaults.html#associatedtype.T"]' 'OverridesDefaults::T'
+// @has 'intra_link_associated_defaults/struct.OverridesDefaults.html' '//a[@href="../intra_link_associated_defaults/struct.OverridesDefaults.html#method.f"]' 'OverridesDefaults::f'
+pub struct OverridesDefaults;
+impl TraitWithDefault for OverridesDefaults {
+    type T = bool;
+    fn f() -> bool {
+        true
+    }
+}
diff --git a/src/test/rustdoc/intra-link-associated-items.rs b/src/test/rustdoc/intra-link-associated-items.rs
new file mode 100644
index 00000000000..16a21e33748
--- /dev/null
+++ b/src/test/rustdoc/intra-link-associated-items.rs
@@ -0,0 +1,59 @@
+// ignore-tidy-linelength
+#![deny(intra_doc_link_resolution_failure)]
+
+/// [`std::collections::BTreeMap::into_iter`]
+/// [`String::from`] is ambiguous as to which `From` impl
+// @has 'intra_link_associated_items/fn.foo.html' '//a[@href="https://doc.rust-lang.org/nightly/alloc/collections/btree/map/struct.BTreeMap.html#method.into_iter"]' 'std::collections::BTreeMap::into_iter'
+// @has 'intra_link_associated_items/fn.foo.html' '//a[@href="https://doc.rust-lang.org/nightly/alloc/string/struct.String.html#method.from"]' 'String::from'
+pub fn foo() {}
+
+/// Link to [MyStruct], [link from struct][MyStruct::method], [MyStruct::clone], [MyStruct::Input]
+// @has 'intra_link_associated_items/struct.MyStruct.html' '//a[@href="../intra_link_associated_items/struct.MyStruct.html"]' 'MyStruct'
+// @has 'intra_link_associated_items/struct.MyStruct.html' '//a[@href="../intra_link_associated_items/struct.MyStruct.html#method.method"]' 'link from struct'
+// @has 'intra_link_associated_items/struct.MyStruct.html' '//a[@href="../intra_link_associated_items/struct.MyStruct.html#method.clone"]' 'MyStruct::clone'
+// @has 'intra_link_associated_items/struct.MyStruct.html' '//a[@href="../intra_link_associated_items/struct.MyStruct.html#associatedtype.Input"]' 'MyStruct::Input'
+pub struct MyStruct { foo: () }
+
+impl Clone for MyStruct {
+    fn clone(&self) -> Self {
+        MyStruct
+    }
+}
+
+pub trait T {
+    type Input;
+    fn method(i: Self::Input);
+}
+
+impl T for MyStruct {
+    type Input = usize;
+
+    /// [link from method][MyStruct::method] on method
+    // @has 'intra_link_associated_items/struct.MyStruct.html' '//a[@href="../intra_link_associated_items/struct.MyStruct.html#method.method"]' 'link from method'
+    fn method(i: usize) {
+    }
+}
+
+/// Ambiguity between which trait to use
+pub trait T1 {
+    fn ambiguous_method();
+}
+
+pub trait T2 {
+    fn ambiguous_method();
+}
+
+/// Link to [S::ambiguous_method]
+// FIXME: there is no way to disambiguate these.
+// Since we have `#[deny(intra_doc_failure)]`, we still know it was one or the other.
+pub struct S;
+
+impl T1 for S {
+    fn ambiguous_method() {}
+}
+
+impl T2 for S {
+    fn ambiguous_method() {}
+}
+
+fn main() {}