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.

10 files changed, 480 insertions, 174 deletions

diff --git a/src/librustc_resolve/late.rs b/src/librustc_resolve/late.rs
index 0dbb6269d2e..d113eb22aba 100644
--- a/src/librustc_resolve/late.rs
+++ b/src/librustc_resolve/late.rs
@@ -8,7 +8,7 @@
 use RibKind::*;
 
 use crate::{path_names_to_string, BindingError, CrateLint, LexicalScopeBinding};
-use crate::{Module, ModuleOrUniformRoot, NameBindingKind, ParentScope, PathResult};
+use crate::{Module, ModuleOrUniformRoot, ParentScope, PathResult};
 use crate::{ResolutionError, Resolver, Segment, UseError};
 
 use rustc_ast::ptr::P;
@@ -24,7 +24,6 @@ use rustc_hir::def_id::{DefId, CRATE_DEF_INDEX};
 use rustc_hir::TraitCandidate;
 use rustc_middle::{bug, span_bug};
 use rustc_session::lint;
-use rustc_span::def_id::LocalDefId;
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::Span;
 use smallvec::{smallvec, SmallVec};
@@ -2342,95 +2341,31 @@ impl<'a, 'b, 'ast> LateResolutionVisitor<'a, 'b, 'ast> {
         ident.span = ident.span.normalize_to_macros_2_0();
         let mut search_module = self.parent_scope.module;
         loop {
-            self.get_traits_in_module_containing_item(ident, ns, search_module, &mut found_traits);
+            self.r.get_traits_in_module_containing_item(
+                ident,
+                ns,
+                search_module,
+                &mut found_traits,
+                &self.parent_scope,
+            );
             search_module =
                 unwrap_or!(self.r.hygienic_lexical_parent(search_module, &mut ident.span), break);
         }
 
         if let Some(prelude) = self.r.prelude {
             if !search_module.no_implicit_prelude {
-                self.get_traits_in_module_containing_item(ident, ns, prelude, &mut found_traits);
+                self.r.get_traits_in_module_containing_item(
+                    ident,
+                    ns,
+                    prelude,
+                    &mut found_traits,
+                    &self.parent_scope,
+                );
             }
         }
 
         found_traits
     }
-
-    fn get_traits_in_module_containing_item(
-        &mut self,
-        ident: Ident,
-        ns: Namespace,
-        module: Module<'a>,
-        found_traits: &mut Vec<TraitCandidate>,
-    ) {
-        assert!(ns == TypeNS || ns == ValueNS);
-        let mut traits = module.traits.borrow_mut();
-        if traits.is_none() {
-            let mut collected_traits = Vec::new();
-            module.for_each_child(self.r, |_, name, ns, binding| {
-                if ns != TypeNS {
-                    return;
-                }
-                match binding.res() {
-                    Res::Def(DefKind::Trait | DefKind::TraitAlias, _) => {
-                        collected_traits.push((name, binding))
-                    }
-                    _ => (),
-                }
-            });
-            *traits = Some(collected_traits.into_boxed_slice());
-        }
-
-        for &(trait_name, binding) in traits.as_ref().unwrap().iter() {
-            // Traits have pseudo-modules that can be used to search for the given ident.
-            if let Some(module) = binding.module() {
-                let mut ident = ident;
-                if ident.span.glob_adjust(module.expansion, binding.span).is_none() {
-                    continue;
-                }
-                if self
-                    .r
-                    .resolve_ident_in_module_unadjusted(
-                        ModuleOrUniformRoot::Module(module),
-                        ident,
-                        ns,
-                        &self.parent_scope,
-                        false,
-                        module.span,
-                    )
-                    .is_ok()
-                {
-                    let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
-                    let trait_def_id = module.def_id().unwrap();
-                    found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
-                }
-            } else if let Res::Def(DefKind::TraitAlias, _) = binding.res() {
-                // For now, just treat all trait aliases as possible candidates, since we don't
-                // know if the ident is somewhere in the transitive bounds.
-                let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
-                let trait_def_id = binding.res().def_id();
-                found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
-            } else {
-                bug!("candidate is not trait or trait alias?")
-            }
-        }
-    }
-
-    fn find_transitive_imports(
-        &mut self,
-        mut kind: &NameBindingKind<'_>,
-        trait_name: Ident,
-    ) -> SmallVec<[LocalDefId; 1]> {
-        let mut import_ids = smallvec![];
-        while let NameBindingKind::Import { import, binding, .. } = kind {
-            let id = self.r.local_def_id(import.id);
-            self.r.maybe_unused_trait_imports.insert(id);
-            self.r.add_to_glob_map(&import, trait_name);
-            import_ids.push(id);
-            kind = &binding.kind;
-        }
-        import_ids
-    }
 }
 
 impl<'a> Resolver<'a> {
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 36b7a430f78..f2319bfe64d 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -43,9 +43,9 @@ use rustc_index::vec::IndexVec;
 use rustc_metadata::creader::{CStore, CrateLoader};
 use rustc_middle::hir::exports::ExportMap;
 use rustc_middle::middle::cstore::{CrateStore, MetadataLoaderDyn};
-use rustc_middle::span_bug;
 use rustc_middle::ty::query::Providers;
 use rustc_middle::ty::{self, DefIdTree, ResolverOutputs};
+use rustc_middle::{bug, span_bug};
 use rustc_session::lint;
 use rustc_session::lint::{BuiltinLintDiagnostics, LintBuffer};
 use rustc_session::Session;
@@ -54,6 +54,7 @@ use rustc_span::source_map::Spanned;
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
 
+use smallvec::{smallvec, SmallVec};
 use std::cell::{Cell, RefCell};
 use std::collections::BTreeSet;
 use std::{cmp, fmt, iter, ptr};
@@ -521,6 +522,29 @@ impl<'a> ModuleData<'a> {
         }
     }
 
+    /// This modifies `self` in place. The traits will be stored in `self.traits`.
+    fn ensure_traits<R>(&'a self, resolver: &mut R)
+    where
+        R: AsMut<Resolver<'a>>,
+    {
+        let mut traits = self.traits.borrow_mut();
+        if traits.is_none() {
+            let mut collected_traits = Vec::new();
+            self.for_each_child(resolver, |_, name, ns, binding| {
+                if ns != TypeNS {
+                    return;
+                }
+                match binding.res() {
+                    Res::Def(DefKind::Trait | DefKind::TraitAlias, _) => {
+                        collected_traits.push((name, binding))
+                    }
+                    _ => (),
+                }
+            });
+            *traits = Some(collected_traits.into_boxed_slice());
+        }
+    }
+
     fn res(&self) -> Option<Res> {
         match self.kind {
             ModuleKind::Def(kind, def_id, _) => Some(Res::Def(kind, def_id)),
@@ -1430,6 +1454,68 @@ impl<'a> Resolver<'a> {
         self.crate_loader.postprocess(krate);
     }
 
+    fn get_traits_in_module_containing_item(
+        &mut self,
+        ident: Ident,
+        ns: Namespace,
+        module: Module<'a>,
+        found_traits: &mut Vec<TraitCandidate>,
+        parent_scope: &ParentScope<'a>,
+    ) {
+        assert!(ns == TypeNS || ns == ValueNS);
+        module.ensure_traits(self);
+        let traits = module.traits.borrow();
+
+        for &(trait_name, binding) in traits.as_ref().unwrap().iter() {
+            // Traits have pseudo-modules that can be used to search for the given ident.
+            if let Some(module) = binding.module() {
+                let mut ident = ident;
+                if ident.span.glob_adjust(module.expansion, binding.span).is_none() {
+                    continue;
+                }
+                if self
+                    .resolve_ident_in_module_unadjusted(
+                        ModuleOrUniformRoot::Module(module),
+                        ident,
+                        ns,
+                        parent_scope,
+                        false,
+                        module.span,
+                    )
+                    .is_ok()
+                {
+                    let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
+                    let trait_def_id = module.def_id().unwrap();
+                    found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
+                }
+            } else if let Res::Def(DefKind::TraitAlias, _) = binding.res() {
+                // For now, just treat all trait aliases as possible candidates, since we don't
+                // know if the ident is somewhere in the transitive bounds.
+                let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
+                let trait_def_id = binding.res().def_id();
+                found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
+            } else {
+                bug!("candidate is not trait or trait alias?")
+            }
+        }
+    }
+
+    fn find_transitive_imports(
+        &mut self,
+        mut kind: &NameBindingKind<'_>,
+        trait_name: Ident,
+    ) -> SmallVec<[LocalDefId; 1]> {
+        let mut import_ids = smallvec![];
+        while let NameBindingKind::Import { import, binding, .. } = kind {
+            let id = self.local_def_id(import.id);
+            self.maybe_unused_trait_imports.insert(id);
+            self.add_to_glob_map(&import, trait_name);
+            import_ids.push(id);
+            kind = &binding.kind;
+        }
+        import_ids
+    }
+
     fn new_module(
         &self,
         parent: Module<'a>,
@@ -3039,6 +3125,34 @@ impl<'a> Resolver<'a> {
         })
     }
 
+    /// This is equivalent to `get_traits_in_module_containing_item`, but without filtering by the associated item.
+    ///
+    /// This is used by rustdoc for intra-doc links.
+    pub fn traits_in_scope(&mut self, module_id: DefId) -> Vec<TraitCandidate> {
+        let module = self.get_module(module_id);
+        module.ensure_traits(self);
+        let traits = module.traits.borrow();
+        let to_candidate =
+            |this: &mut Self, &(trait_name, binding): &(Ident, &NameBinding<'_>)| TraitCandidate {
+                def_id: binding.res().def_id(),
+                import_ids: this.find_transitive_imports(&binding.kind, trait_name),
+            };
+
+        let mut candidates: Vec<_> =
+            traits.as_ref().unwrap().iter().map(|x| to_candidate(self, x)).collect();
+
+        if let Some(prelude) = self.prelude {
+            if !module.no_implicit_prelude {
+                prelude.ensure_traits(self);
+                candidates.extend(
+                    prelude.traits.borrow().as_ref().unwrap().iter().map(|x| to_candidate(self, x)),
+                );
+            }
+        }
+
+        candidates
+    }
+
     /// Rustdoc uses this to resolve things in a recoverable way. `ResolutionError<'a>`
     /// isn't something that can be returned because it can't be made to live that long,
     /// and also it's a private type. Fortunately rustdoc doesn't need to know the error,
diff --git a/src/librustdoc/clean/types.rs b/src/librustdoc/clean/types.rs
index 3eac5bbda00..932585918df 100644
--- a/src/librustdoc/clean/types.rs
+++ b/src/librustdoc/clean/types.rs
@@ -20,7 +20,7 @@ use rustc_hir::lang_items;
 use rustc_hir::Mutability;
 use rustc_index::vec::IndexVec;
 use rustc_middle::middle::stability;
-use rustc_middle::ty::TyCtxt;
+use rustc_middle::ty::{AssocKind, TyCtxt};
 use rustc_span::hygiene::MacroKind;
 use rustc_span::source_map::DUMMY_SP;
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
@@ -282,12 +282,21 @@ pub enum ItemEnum {
 }
 
 impl ItemEnum {
-    pub fn is_associated(&self) -> bool {
+    pub fn is_type_alias(&self) -> bool {
         match *self {
             ItemEnum::TypedefItem(_, _) | ItemEnum::AssocTypeItem(_, _) => true,
             _ => false,
         }
     }
+
+    pub fn as_assoc_kind(&self) -> Option<AssocKind> {
+        match *self {
+            ItemEnum::AssocConstItem(..) => Some(AssocKind::Const),
+            ItemEnum::AssocTypeItem(..) => Some(AssocKind::Type),
+            ItemEnum::TyMethodItem(..) | ItemEnum::MethodItem(..) => Some(AssocKind::Fn),
+            _ => None,
+        }
+    }
 }
 
 #[derive(Clone, Debug)]
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index c942a6cee70..a2f6d33a27a 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -69,6 +69,11 @@ pub struct DocContext<'tcx> {
     pub auto_traits: Vec<DefId>,
     /// The options given to rustdoc that could be relevant to a pass.
     pub render_options: RenderOptions,
+    /// The traits in scope for a given module.
+    ///
+    /// See `collect_intra_doc_links::traits_implemented_by` for more details.
+    /// `map<module, set<trait>>`
+    pub module_trait_cache: RefCell<FxHashMap<DefId, FxHashSet<DefId>>>,
 }
 
 impl<'tcx> DocContext<'tcx> {
@@ -510,6 +515,7 @@ pub fn run_core(options: RustdocOptions) -> (clean::Crate, RenderInfo, RenderOpt
                         .filter(|trait_def_id| tcx.trait_is_auto(*trait_def_id))
                         .collect(),
                     render_options,
+                    module_trait_cache: RefCell::new(FxHashMap::default()),
                 };
                 debug!("crate: {:?}", tcx.hir().krate());
 
diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index bd919205dd1..d17961521c8 100644
--- a/src/librustdoc/html/render/mod.rs
+++ b/src/librustdoc/html/render/mod.rs
@@ -3612,7 +3612,7 @@ fn render_impl(
         };
 
         let (is_hidden, extra_class) =
-            if (trait_.is_none() || item.doc_value().is_some() || item.inner.is_associated())
+            if (trait_.is_none() || item.doc_value().is_some() || item.inner.is_type_alias())
                 && !is_default_item
             {
                 (false, "")
diff --git a/src/librustdoc/passes/collect_intra_doc_links.rs b/src/librustdoc/passes/collect_intra_doc_links.rs
index 9c57435a8c0..2ed3d07974f 100644
--- a/src/librustdoc/passes/collect_intra_doc_links.rs
+++ b/src/librustdoc/passes/collect_intra_doc_links.rs
@@ -1,4 +1,5 @@
 use rustc_ast as ast;
+use rustc_data_structures::stable_set::FxHashSet;
 use rustc_errors::{Applicability, DiagnosticBuilder};
 use rustc_expand::base::SyntaxExtensionKind;
 use rustc_feature::UnstableFeatures;
@@ -185,7 +186,6 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
         current_item: &Option<String>,
         parent_id: Option<DefId>,
         extra_fragment: &Option<String>,
-        item_opt: Option<&Item>,
     ) -> Result<(Res, Option<String>), ErrorKind> {
         let cx = self.cx;
 
@@ -245,13 +245,6 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                     return Err(ErrorKind::AnchorFailure(AnchorFailure::Primitive));
                 }
                 return Ok((prim, Some(path.to_owned())));
-            } else {
-                // If resolution failed, it may still be a method
-                // because methods are not handled by the resolver
-                // If so, bail when we're not looking for a value.
-                if ns != ValueNS {
-                    return Err(ErrorKind::ResolutionFailure);
-                }
             }
 
             // Try looking for methods and associated items.
@@ -299,65 +292,56 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                 })
                 .map_err(|_| ErrorKind::ResolutionFailure)?;
             if let Res::Err = ty_res {
-                return self.variant_field(path_str, current_item, module_id);
+                return if ns == Namespace::ValueNS {
+                    self.variant_field(path_str, current_item, module_id)
+                } else {
+                    Err(ErrorKind::ResolutionFailure)
+                };
             }
             let ty_res = ty_res.map_id(|_| panic!("unexpected node_id"));
-            match ty_res {
+            let res = match ty_res {
                 Res::Def(
                     DefKind::Struct | DefKind::Union | DefKind::Enum | DefKind::TyAlias,
                     did,
                 ) => {
+                    debug!("looking for associated item named {} for item {:?}", item_name, did);
                     // Checks if item_name belongs to `impl SomeItem`
-                    let impl_item = cx
+                    let kind = cx
                         .tcx
                         .inherent_impls(did)
                         .iter()
-                        .flat_map(|imp| cx.tcx.associated_items(*imp).in_definition_order())
-                        .find(|item| item.ident.name == item_name);
-                    let trait_item = item_opt
-                        .and_then(|item| self.cx.as_local_hir_id(item.def_id))
-                        .and_then(|item_hir| {
-                            // Checks if item_name belongs to `impl SomeTrait for SomeItem`
-                            let parent_hir = self.cx.tcx.hir().get_parent_item(item_hir);
-                            let item_parent = self.cx.tcx.hir().find(parent_hir);
-                            match item_parent {
-                                Some(hir::Node::Item(hir::Item {
-                                    kind: hir::ItemKind::Impl { of_trait: Some(_), self_ty, .. },
-                                    ..
-                                })) => cx
-                                    .tcx
-                                    .associated_item_def_ids(self_ty.hir_id.owner)
-                                    .iter()
-                                    .map(|child| {
-                                        let associated_item = cx.tcx.associated_item(*child);
-                                        associated_item
-                                    })
-                                    .find(|child| child.ident.name == item_name),
-                                _ => None,
-                            }
+                        .flat_map(|&imp| {
+                            cx.tcx.associated_items(imp).find_by_name_and_namespace(
+                                cx.tcx,
+                                Ident::with_dummy_span(item_name),
+                                ns,
+                                imp,
+                            )
+                        })
+                        .map(|item| item.kind)
+                        // There should only ever be one associated item that matches from any inherent impl
+                        .next()
+                        // Check if item_name belongs to `impl SomeTrait for SomeItem`
+                        // This gives precedence to `impl SomeItem`:
+                        // Although having both would be ambiguous, use impl version for compat. sake.
+                        // To handle that properly resolve() would have to support
+                        // something like [`ambi_fn`](<SomeStruct as SomeTrait>::ambi_fn)
+                        .or_else(|| {
+                            let kind = resolve_associated_trait_item(
+                                did, module_id, item_name, ns, &self.cx,
+                            );
+                            debug!("got associated item kind {:?}", kind);
+                            kind
                         });
-                    let item = match (impl_item, trait_item) {
-                        (Some(from_impl), Some(_)) => {
-                            // Although it's ambiguous, return impl version for compat. sake.
-                            // To handle that properly resolve() would have to support
-                            // something like
-                            // [`ambi_fn`](<SomeStruct as SomeTrait>::ambi_fn)
-                            Some(from_impl)
-                        }
-                        (None, Some(from_trait)) => Some(from_trait),
-                        (Some(from_impl), None) => Some(from_impl),
-                        _ => None,
-                    };
-
-                    if let Some(item) = item {
-                        let out = match item.kind {
-                            ty::AssocKind::Fn if ns == ValueNS => "method",
-                            ty::AssocKind::Const if ns == ValueNS => "associatedconstant",
-                            ty::AssocKind::Type if ns == ValueNS => "associatedtype",
-                            _ => return self.variant_field(path_str, current_item, module_id),
+
+                    if let Some(kind) = kind {
+                        let out = match kind {
+                            ty::AssocKind::Fn => "method",
+                            ty::AssocKind::Const => "associatedconstant",
+                            ty::AssocKind::Type => "associatedtype",
                         };
-                        if extra_fragment.is_some() {
-                            Err(ErrorKind::AnchorFailure(if item.kind == ty::AssocKind::Fn {
+                        Some(if extra_fragment.is_some() {
+                            Err(ErrorKind::AnchorFailure(if kind == ty::AssocKind::Fn {
                                 AnchorFailure::Method
                             } else {
                                 AnchorFailure::AssocConstant
@@ -366,20 +350,21 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                             // HACK(jynelson): `clean` expects the type, not the associated item.
                             // but the disambiguator logic expects the associated item.
                             // Store the kind in a side channel so that only the disambiguator logic looks at it.
-                            self.kind_side_channel.replace(Some(item.kind.as_def_kind()));
+                            self.kind_side_channel.set(Some(kind.as_def_kind()));
                             Ok((ty_res, Some(format!("{}.{}", out, item_name))))
-                        }
-                    } else {
+                        })
+                    } else if ns == Namespace::ValueNS {
                         match cx.tcx.type_of(did).kind {
                             ty::Adt(def, _) => {
-                                if let Some(item) = if def.is_enum() {
+                                let field = if def.is_enum() {
                                     def.all_fields().find(|item| item.ident.name == item_name)
                                 } else {
                                     def.non_enum_variant()
                                         .fields
                                         .iter()
                                         .find(|item| item.ident.name == item_name)
-                                } {
+                                };
+                                field.map(|item| {
                                     if extra_fragment.is_some() {
                                         Err(ErrorKind::AnchorFailure(if def.is_enum() {
                                             AnchorFailure::Variant
@@ -400,31 +385,31 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                                             )),
                                         ))
                                     }
-                                } else {
-                                    self.variant_field(path_str, current_item, module_id)
-                                }
+                                })
                             }
-                            _ => self.variant_field(path_str, current_item, module_id),
+                            _ => None,
                         }
+                    } else {
+                        // We already know this isn't in ValueNS, so no need to check variant_field
+                        return Err(ErrorKind::ResolutionFailure);
                     }
                 }
-                Res::Def(DefKind::Trait, did) => {
-                    let item = cx
-                        .tcx
-                        .associated_item_def_ids(did)
-                        .iter()
-                        .map(|item| cx.tcx.associated_item(*item))
-                        .find(|item| item.ident.name == item_name);
-                    if let Some(item) = item {
-                        let kind =
-                            match item.kind {
-                                ty::AssocKind::Const if ns == ValueNS => "associatedconstant",
-                                ty::AssocKind::Type if ns == TypeNS => "associatedtype",
-                                ty::AssocKind::Fn if ns == ValueNS => {
-                                    if item.defaultness.has_value() { "method" } else { "tymethod" }
+                Res::Def(DefKind::Trait, did) => cx
+                    .tcx
+                    .associated_items(did)
+                    .find_by_name_and_namespace(cx.tcx, Ident::with_dummy_span(item_name), ns, did)
+                    .map(|item| {
+                        let kind = match item.kind {
+                            ty::AssocKind::Const => "associatedconstant",
+                            ty::AssocKind::Type => "associatedtype",
+                            ty::AssocKind::Fn => {
+                                if item.defaultness.has_value() {
+                                    "method"
+                                } else {
+                                    "tymethod"
                                 }
-                                _ => return self.variant_field(path_str, current_item, module_id),
-                            };
+                            }
+                        };
 
                         if extra_fragment.is_some() {
                             Err(ErrorKind::AnchorFailure(if item.kind == ty::AssocKind::Const {
@@ -438,12 +423,16 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                             let res = Res::Def(item.kind.as_def_kind(), item.def_id);
                             Ok((res, Some(format!("{}.{}", kind, item_name))))
                         }
-                    } else {
-                        self.variant_field(path_str, current_item, module_id)
-                    }
+                    }),
+                _ => None,
+            };
+            res.unwrap_or_else(|| {
+                if ns == Namespace::ValueNS {
+                    self.variant_field(path_str, current_item, module_id)
+                } else {
+                    Err(ErrorKind::ResolutionFailure)
                 }
-                _ => self.variant_field(path_str, current_item, module_id),
-            }
+            })
         } else {
             debug!("attempting to resolve item without parent module: {}", path_str);
             Err(ErrorKind::ResolutionFailure)
@@ -451,6 +440,134 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
     }
 }
 
+fn resolve_associated_trait_item(
+    did: DefId,
+    module: DefId,
+    item_name: Symbol,
+    ns: Namespace,
+    cx: &DocContext<'_>,
+) -> Option<ty::AssocKind> {
+    let ty = cx.tcx.type_of(did);
+    // First consider automatic impls: `impl From<T> for T`
+    let implicit_impls = crate::clean::get_auto_trait_and_blanket_impls(cx, ty, did);
+    let mut candidates: Vec<_> = implicit_impls
+        .flat_map(|impl_outer| {
+            match impl_outer.inner {
+                ImplItem(impl_) => {
+                    debug!("considering auto or blanket impl for trait {:?}", impl_.trait_);
+                    // Give precedence to methods that were overridden
+                    if !impl_.provided_trait_methods.contains(&*item_name.as_str()) {
+                        let mut items = impl_.items.into_iter().filter_map(|assoc| {
+                            if assoc.name.as_deref() != Some(&*item_name.as_str()) {
+                                return None;
+                            }
+                            let kind = assoc
+                                .inner
+                                .as_assoc_kind()
+                                .expect("inner items for a trait should be associated items");
+                            if kind.namespace() != ns {
+                                return None;
+                            }
+
+                            trace!("considering associated item {:?}", assoc.inner);
+                            // We have a slight issue: normal methods come from `clean` types,
+                            // but provided methods come directly from `tcx`.
+                            // Fortunately, we don't need the whole method, we just need to know
+                            // what kind of associated item it is.
+                            Some((assoc.def_id, kind))
+                        });
+                        let assoc = items.next();
+                        debug_assert_eq!(items.count(), 0);
+                        assoc
+                    } else {
+                        // These are provided methods or default types:
+                        // ```
+                        // trait T {
+                        //   type A = usize;
+                        //   fn has_default() -> A { 0 }
+                        // }
+                        // ```
+                        let trait_ = impl_.trait_.unwrap().def_id().unwrap();
+                        cx.tcx
+                            .associated_items(trait_)
+                            .find_by_name_and_namespace(
+                                cx.tcx,
+                                Ident::with_dummy_span(item_name),
+                                ns,
+                                trait_,
+                            )
+                            .map(|assoc| (assoc.def_id, assoc.kind))
+                    }
+                }
+                _ => panic!("get_impls returned something that wasn't an impl"),
+            }
+        })
+        .collect();
+
+    // Next consider explicit impls: `impl MyTrait for MyType`
+    // Give precedence to inherent impls.
+    if candidates.is_empty() {
+        let traits = traits_implemented_by(cx, did, module);
+        debug!("considering traits {:?}", traits);
+        candidates.extend(traits.iter().filter_map(|&trait_| {
+            cx.tcx
+                .associated_items(trait_)
+                .find_by_name_and_namespace(cx.tcx, Ident::with_dummy_span(item_name), ns, trait_)
+                .map(|assoc| (assoc.def_id, assoc.kind))
+        }));
+    }
+    // FIXME: warn about ambiguity
+    debug!("the candidates were {:?}", candidates);
+    candidates.pop().map(|(_, kind)| kind)
+}
+
+/// Given a type, return all traits in scope in `module` implemented by that type.
+///
+/// NOTE: this cannot be a query because more traits could be available when more crates are compiled!
+/// So it is not stable to serialize cross-crate.
+fn traits_implemented_by(cx: &DocContext<'_>, type_: DefId, module: DefId) -> FxHashSet<DefId> {
+    let mut cache = cx.module_trait_cache.borrow_mut();
+    let in_scope_traits = cache.entry(module).or_insert_with(|| {
+        cx.enter_resolver(|resolver| {
+            resolver.traits_in_scope(module).into_iter().map(|candidate| candidate.def_id).collect()
+        })
+    });
+
+    let ty = cx.tcx.type_of(type_);
+    let iter = in_scope_traits.iter().flat_map(|&trait_| {
+        trace!("considering explicit impl for trait {:?}", trait_);
+        let mut saw_impl = false;
+        // Look at each trait implementation to see if it's an impl for `did`
+        cx.tcx.for_each_relevant_impl(trait_, ty, |impl_| {
+            // FIXME: this is inefficient, find a way to short-circuit for_each_* so this doesn't take as long
+            if saw_impl {
+                return;
+            }
+
+            let trait_ref = cx.tcx.impl_trait_ref(impl_).expect("this is not an inherent impl");
+            // Check if these are the same type.
+            let impl_type = trait_ref.self_ty();
+            debug!(
+                "comparing type {} with kind {:?} against type {:?}",
+                impl_type, impl_type.kind, type_
+            );
+            // Fast path: if this is a primitive simple `==` will work
+            saw_impl = impl_type == ty
+                || match impl_type.kind {
+                    // Check if these are the same def_id
+                    ty::Adt(def, _) => {
+                        debug!("adt def_id: {:?}", def.did);
+                        def.did == type_
+                    }
+                    ty::Foreign(def_id) => def_id == type_,
+                    _ => false,
+                };
+        });
+        if saw_impl { Some(trait_) } else { None }
+    });
+    iter.collect()
+}
+
 /// Check for resolve collisions between a trait and its derive
 ///
 /// These are common and we should just resolve to the trait in that case
@@ -644,7 +761,6 @@ impl<'a, 'tcx> DocFolder for LinkCollector<'a, 'tcx> {
                             &current_item,
                             base_node,
                             &extra_fragment,
-                            Some(&item),
                         ) {
                             Ok(res) => res,
                             Err(ErrorKind::ResolutionFailure) => {
@@ -673,13 +789,16 @@ impl<'a, 'tcx> DocFolder for LinkCollector<'a, 'tcx> {
                                 &current_item,
                                 base_node,
                                 &extra_fragment,
-                                Some(&item),
                             ) {
+                                Ok(res) => {
+                                    debug!("got res in TypeNS: {:?}", res);
+                                    Some(res)
+                                }
                                 Err(ErrorKind::AnchorFailure(msg)) => {
                                     anchor_failure(cx, &item, &ori_link, &dox, link_range, msg);
                                     continue;
                                 }
-                                x => x.ok(),
+                                Err(ErrorKind::ResolutionFailure) => None,
                             },
                             value_ns: match self.resolve(
                                 path_str,
@@ -688,13 +807,13 @@ impl<'a, 'tcx> DocFolder for LinkCollector<'a, 'tcx> {
                                 &current_item,
                                 base_node,
                                 &extra_fragment,
-                                Some(&item),
                             ) {
+                                Ok(res) => Some(res),
                                 Err(ErrorKind::AnchorFailure(msg)) => {
                                     anchor_failure(cx, &item, &ori_link, &dox, link_range, msg);
                                     continue;
                                 }
-                                x => x.ok(),
+                                Err(ErrorKind::ResolutionFailure) => None,
                             }
                             .and_then(|(res, fragment)| {
                                 // Constructors are picked up in the type namespace.
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() {}