rustdoc: fix quadratic time in intra-doc link pass

In the collect_intra_doc_links pass, links to a given item that occurred
repeatedly were getting inserted into a Vec<clean::ItemLink> repeatedly.
This led to n^2 behavior (where n = the number of pages generated), particularly
for the intra-doc link on the `Into<U> for T where U: From<T>` blanket
implementation, since that link appears on every single struct page.

3 files changed, 14 insertions, 10 deletions

diff --git a/src/librustdoc/clean/types.rs b/src/librustdoc/clean/types.rs
index 7dbb3f76a0a..a21a91a0ce8 100644
--- a/src/librustdoc/clean/types.rs
+++ b/src/librustdoc/clean/types.rs
@@ -482,10 +482,12 @@ impl Item {
     pub(crate) fn links(&self, cx: &Context<'_>) -> Vec<RenderedLink> {
         use crate::html::format::{href, link_tooltip};
 
-        cx.cache()
+        let Some(links) = cx.cache()
             .intra_doc_links
-            .get(&self.item_id)
-            .map_or(&[][..], |v| v.as_slice())
+            .get(&self.item_id) else {
+                return vec![]
+            };
+        links
             .iter()
             .filter_map(|ItemLink { link: s, link_text, page_id: id, ref fragment }| {
                 debug!(?id);
@@ -513,10 +515,12 @@ impl Item {
     /// the link text, but does need to know which `[]`-bracketed names
     /// are actually links.
     pub(crate) fn link_names(&self, cache: &Cache) -> Vec<RenderedLink> {
-        cache
+        let Some(links) = cache
             .intra_doc_links
-            .get(&self.item_id)
-            .map_or(&[][..], |v| v.as_slice())
+            .get(&self.item_id) else {
+                return vec![];
+            };
+        links
             .iter()
             .map(|ItemLink { link: s, link_text, .. }| RenderedLink {
                 original_text: s.clone(),
@@ -1014,7 +1018,7 @@ pub(crate) fn collapse_doc_fragments(doc_strings: &[DocFragment]) -> String {
 /// A link that has not yet been rendered.
 ///
 /// This link will be turned into a rendered link by [`Item::links`].
-#[derive(Clone, Debug, PartialEq, Eq)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub(crate) struct ItemLink {
     /// The original link written in the markdown
     pub(crate) link: Box<str>,
diff --git a/src/librustdoc/formats/cache.rs b/src/librustdoc/formats/cache.rs
index 0295de8437e..c0329182032 100644
--- a/src/librustdoc/formats/cache.rs
+++ b/src/librustdoc/formats/cache.rs
@@ -1,6 +1,6 @@
 use std::mem;
 
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet};
 use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIdSet};
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_span::Symbol;
@@ -118,7 +118,7 @@ pub(crate) struct Cache {
     /// All intra-doc links resolved so far.
     ///
     /// Links are indexed by the DefId of the item they document.
-    pub(crate) intra_doc_links: FxHashMap<ItemId, Vec<clean::ItemLink>>,
+    pub(crate) intra_doc_links: FxHashMap<ItemId, FxIndexSet<clean::ItemLink>>,
     /// Cfg that have been hidden via #![doc(cfg_hide(...))]
     pub(crate) hidden_cfg: FxHashSet<clean::cfg::Cfg>,
 }
diff --git a/src/librustdoc/passes/collect_intra_doc_links.rs b/src/librustdoc/passes/collect_intra_doc_links.rs
index 789523c561e..f907dcd0916 100644
--- a/src/librustdoc/passes/collect_intra_doc_links.rs
+++ b/src/librustdoc/passes/collect_intra_doc_links.rs
@@ -918,7 +918,7 @@ impl LinkCollector<'_, '_> {
             for md_link in preprocessed_markdown_links(&doc) {
                 let link = self.resolve_link(item, item_id, module_id, &doc, &md_link);
                 if let Some(link) = link {
-                    self.cx.cache.intra_doc_links.entry(item.item_id).or_default().push(link);
+                    self.cx.cache.intra_doc_links.entry(item.item_id).or_default().insert(link);
                 }
             }
         }