rustdoc-search: add impl disambiguator to duplicate assoc items

Helps with #90929

This changes the search results, specifically, when there's more than
one impl with an associated item with the same name. For example,
the search queries `simd<i8> -> simd<i8>` and `simd<i64> -> simd<i64>`
don't link to the same function, but most of the functions have the
same names.

This change should probably be FCP-ed, especially since it adds a new
anchor link format for `main.js` to handle, so that URLs like
`struct.Vec.html#impl-AsMut<[T]>-for-Vec<T,+A>/method.as_mut` redirect
to `struct.Vec.html#method.as_mut-2`. It's a strange design, but there
are a few reasons for it:

* I'd like to avoid making the HTML bigger. Obviously, fixing this bug
  is going to add at least a little more data to the search index, but
  adding more HTML penalises viewers for the benefit of searchers.

* Breaking `struct.Vec.html#method.len` would also be a disappointment.

On the other hand:

* The path-style anchors might be less prone to link rot than the numbered
  anchors. It's definitely less likely to have URLs that appear to "work",
  but silently point at the wrong thing.

* This commit arranges the path-style anchor to redirect to the numbered
  anchor. Nothing stops rustdoc from doing the opposite, making path-style
  anchors the default and redirecting the "legacy" numbered ones.

3 files changed, 60 insertions, 17 deletions

diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index 3e671a64b54..b0ce475850c 100644
--- a/src/librustdoc/html/render/mod.rs
+++ b/src/librustdoc/html/render/mod.rs
@@ -54,7 +54,7 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_hir::def_id::{DefId, DefIdSet};
 use rustc_hir::Mutability;
 use rustc_middle::middle::stability;
-use rustc_middle::ty::TyCtxt;
+use rustc_middle::ty::{self, TyCtxt};
 use rustc_span::{
     symbol::{sym, Symbol},
     BytePos, FileName, RealFileName,
@@ -102,6 +102,7 @@ pub(crate) struct IndexItem {
     pub(crate) desc: String,
     pub(crate) parent: Option<DefId>,
     pub(crate) parent_idx: Option<isize>,
+    pub(crate) impl_id: Option<DefId>,
     pub(crate) search_type: Option<IndexItemFunctionType>,
     pub(crate) aliases: Box<[Symbol]>,
     pub(crate) deprecation: Option<Deprecation>,
@@ -1877,7 +1878,7 @@ pub(crate) fn render_impl_summary(
     aliases: &[String],
 ) {
     let inner_impl = i.inner_impl();
-    let id = cx.derive_id(get_id_for_impl(&inner_impl.for_, inner_impl.trait_.as_ref(), cx));
+    let id = cx.derive_id(get_id_for_impl(cx.tcx(), i.impl_item.item_id));
     let aliases = if aliases.is_empty() {
         String::new()
     } else {
@@ -1994,21 +1995,35 @@ pub(crate) fn small_url_encode(s: String) -> String {
     }
 }
 
-fn get_id_for_impl(for_: &clean::Type, trait_: Option<&clean::Path>, cx: &Context<'_>) -> String {
-    match trait_ {
-        Some(t) => small_url_encode(format!("impl-{:#}-for-{:#}", t.print(cx), for_.print(cx))),
-        None => small_url_encode(format!("impl-{:#}", for_.print(cx))),
-    }
+fn get_id_for_impl<'tcx>(tcx: TyCtxt<'tcx>, impl_id: ItemId) -> String {
+    use rustc_middle::ty::print::with_forced_trimmed_paths;
+    let (type_, trait_) = match impl_id {
+        ItemId::Auto { trait_, for_ } => {
+            let ty = tcx.type_of(for_).skip_binder();
+            (ty, Some(ty::TraitRef::new(tcx, trait_, [ty])))
+        }
+        ItemId::Blanket { impl_id, .. } | ItemId::DefId(impl_id) => {
+            match tcx.impl_subject(impl_id).skip_binder() {
+                ty::ImplSubject::Trait(trait_ref) => {
+                    (trait_ref.args[0].expect_ty(), Some(trait_ref))
+                }
+                ty::ImplSubject::Inherent(ty) => (ty, None),
+            }
+        }
+    };
+    with_forced_trimmed_paths!(small_url_encode(if let Some(trait_) = trait_ {
+        format!("impl-{trait_}-for-{type_}", trait_ = trait_.print_only_trait_path())
+    } else {
+        format!("impl-{type_}")
+    }))
 }
 
 fn extract_for_impl_name(item: &clean::Item, cx: &Context<'_>) -> Option<(String, String)> {
     match *item.kind {
-        clean::ItemKind::ImplItem(ref i) => {
-            i.trait_.as_ref().map(|trait_| {
-                // Alternative format produces no URLs,
-                // so this parameter does nothing.
-                (format!("{:#}", i.for_.print(cx)), get_id_for_impl(&i.for_, Some(trait_), cx))
-            })
+        clean::ItemKind::ImplItem(ref i) if i.trait_.is_some() => {
+            // Alternative format produces no URLs,
+            // so this parameter does nothing.
+            Some((format!("{:#}", i.for_.print(cx)), get_id_for_impl(cx.tcx(), item.item_id)))
         }
         _ => None,
     }
diff --git a/src/librustdoc/html/render/search_index.rs b/src/librustdoc/html/render/search_index.rs
index 78c443b2257..af1dab59496 100644
--- a/src/librustdoc/html/render/search_index.rs
+++ b/src/librustdoc/html/render/search_index.rs
@@ -12,7 +12,7 @@ use crate::formats::cache::{Cache, OrphanImplItem};
 use crate::formats::item_type::ItemType;
 use crate::html::format::join_with_double_colon;
 use crate::html::markdown::short_markdown_summary;
-use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
+use crate::html::render::{self, IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
 
 /// Builds the search index from the collected metadata
 pub(crate) fn build_index<'tcx>(
@@ -26,7 +26,8 @@ pub(crate) fn build_index<'tcx>(
 
     // Attach all orphan items to the type's definition if the type
     // has since been learned.
-    for &OrphanImplItem { parent, ref item, ref impl_generics } in &cache.orphan_impl_items {
+    for &OrphanImplItem { impl_id, parent, ref item, ref impl_generics } in &cache.orphan_impl_items
+    {
         if let Some((fqp, _)) = cache.paths.get(&parent) {
             let desc = short_markdown_summary(&item.doc_value(), &item.link_names(cache));
             cache.search_index.push(IndexItem {
@@ -36,6 +37,7 @@ pub(crate) fn build_index<'tcx>(
                 desc,
                 parent: Some(parent),
                 parent_idx: None,
+                impl_id,
                 search_type: get_function_type_for_search(item, tcx, impl_generics.as_ref(), cache),
                 aliases: item.attrs.get_doc_aliases(),
                 deprecation: item.deprecation(tcx),
@@ -222,6 +224,29 @@ pub(crate) fn build_index<'tcx>(
         })
         .collect();
 
+    // Find associated items that need disambiguators
+    let mut associated_item_duplicates = FxHashMap::<(isize, ItemType, Symbol), usize>::default();
+
+    for &item in &crate_items {
+        if item.impl_id.is_some() && let Some(parent_idx) = item.parent_idx {
+            let count = associated_item_duplicates
+                .entry((parent_idx, item.ty, item.name))
+                .or_insert(0);
+            *count += 1;
+        }
+    }
+
+    let associated_item_disambiguators = crate_items
+        .iter()
+        .enumerate()
+        .filter_map(|(index, item)| {
+            let impl_id = ItemId::DefId(item.impl_id?);
+            let parent_idx = item.parent_idx?;
+            let count = *associated_item_duplicates.get(&(parent_idx, item.ty, item.name))?;
+            if count > 1 { Some((index, render::get_id_for_impl(tcx, impl_id))) } else { None }
+        })
+        .collect::<Vec<_>>();
+
     struct CrateData<'a> {
         doc: String,
         items: Vec<&'a IndexItem>,
@@ -230,6 +255,8 @@ pub(crate) fn build_index<'tcx>(
         //
         // To be noted: the `usize` elements are indexes to `items`.
         aliases: &'a BTreeMap<String, Vec<usize>>,
+        // Used when a type has more than one impl with an associated item with the same name.
+        associated_item_disambiguators: &'a Vec<(usize, String)>,
     }
 
     struct Paths {
@@ -382,6 +409,7 @@ pub(crate) fn build_index<'tcx>(
             crate_data.serialize_field("f", &functions)?;
             crate_data.serialize_field("c", &deprecated)?;
             crate_data.serialize_field("p", &paths)?;
+            crate_data.serialize_field("b", &self.associated_item_disambiguators)?;
             if has_aliases {
                 crate_data.serialize_field("a", &self.aliases)?;
             }
@@ -398,6 +426,7 @@ pub(crate) fn build_index<'tcx>(
             items: crate_items,
             paths: crate_paths,
             aliases: &aliases,
+            associated_item_disambiguators: &associated_item_disambiguators,
         })
         .expect("failed serde conversion")
         // All these `replace` calls are because we have to go through JS string for JSON content.
diff --git a/src/librustdoc/html/render/sidebar.rs b/src/librustdoc/html/render/sidebar.rs
index 76f63c6f63e..3f8b22050c8 100644
--- a/src/librustdoc/html/render/sidebar.rs
+++ b/src/librustdoc/html/render/sidebar.rs
@@ -503,8 +503,7 @@ fn sidebar_render_assoc_items(
             .iter()
             .filter_map(|it| {
                 let trait_ = it.inner_impl().trait_.as_ref()?;
-                let encoded =
-                    id_map.derive(super::get_id_for_impl(&it.inner_impl().for_, Some(trait_), cx));
+                let encoded = id_map.derive(super::get_id_for_impl(cx.tcx(), it.impl_item.item_id));
 
                 let prefix = match it.inner_impl().polarity {
                     ty::ImplPolarity::Positive | ty::ImplPolarity::Reservation => "",