Fix invalid handling of generics

2 files changed, 97 insertions, 76 deletions

diff --git a/src/librustdoc/html/render/cache.rs b/src/librustdoc/html/render/cache.rs
index 0bbc510f7cb..37b2cf02624 100644
--- a/src/librustdoc/html/render/cache.rs
+++ b/src/librustdoc/html/render/cache.rs
@@ -1,7 +1,7 @@
 use std::collections::hash_map::Entry;
 use std::collections::BTreeMap;
 
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fx::FxHashMap;
 use rustc_middle::ty::TyCtxt;
 use rustc_span::symbol::Symbol;
 use serde::ser::{Serialize, SerializeStruct, Serializer};
@@ -192,32 +192,24 @@ crate fn get_index_search_type<'tcx>(
     item: &clean::Item,
     tcx: TyCtxt<'tcx>,
 ) -> Option<IndexItemFunctionType> {
-    let (all_types, ret_types) = match *item.kind {
+    let (mut inputs, mut output) = match *item.kind {
         clean::FunctionItem(ref f) => get_all_types(&f.generics, &f.decl, tcx),
         clean::MethodItem(ref m, _) => get_all_types(&m.generics, &m.decl, tcx),
         clean::TyMethodItem(ref m) => get_all_types(&m.generics, &m.decl, tcx),
         _ => return None,
     };
 
-    let inputs = all_types
-        .iter()
-        .map(|(ty, kind)| TypeWithKind::from((get_index_type(ty), *kind)))
-        .filter(|a| a.ty.name.is_some())
-        .collect();
-    let output = ret_types
-        .iter()
-        .map(|(ty, kind)| TypeWithKind::from((get_index_type(ty), *kind)))
-        .filter(|a| a.ty.name.is_some())
-        .collect::<Vec<_>>();
+    inputs.retain(|a| a.ty.name.is_some());
+    output.retain(|a| a.ty.name.is_some());
     let output = if output.is_empty() { None } else { Some(output) };
 
     Some(IndexItemFunctionType { inputs, output })
 }
 
-fn get_index_type(clean_type: &clean::Type) -> RenderType {
+fn get_index_type(clean_type: &clean::Type, generics: Vec<TypeWithKind>) -> RenderType {
     RenderType {
         name: get_index_type_name(clean_type, true).map(|s| s.as_str().to_ascii_lowercase()),
-        generics: get_generics(clean_type),
+        generics: if generics.is_empty() { None } else { Some(generics) },
     }
 }
 
@@ -246,23 +238,6 @@ fn get_index_type_name(clean_type: &clean::Type, accept_generic: bool) -> Option
     }
 }
 
-/// Return a list of generic parameters for use in the search index.
-///
-/// This function replaces bounds with types, so that `T where T: Debug` just becomes `Debug`.
-/// It does return duplicates, and that's intentional, since search queries like `Result<usize, usize>`
-/// are supposed to match only results where both parameters are `usize`.
-fn get_generics(clean_type: &clean::Type) -> Option<Vec<String>> {
-    clean_type.generics().and_then(|types| {
-        let r = types
-            .iter()
-            .filter_map(|t| {
-                get_index_type_name(t, false).map(|name| name.as_str().to_ascii_lowercase())
-            })
-            .collect::<Vec<_>>();
-        if r.is_empty() { None } else { Some(r) }
-    })
-}
-
 /// The point of this function is to replace bounds with types.
 ///
 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
@@ -272,27 +247,77 @@ crate fn get_real_types<'tcx>(
     generics: &Generics,
     arg: &Type,
     tcx: TyCtxt<'tcx>,
-    recurse: i32,
-    res: &mut FxHashSet<(Type, ItemType)>,
-) -> usize {
-    fn insert(res: &mut FxHashSet<(Type, ItemType)>, tcx: TyCtxt<'_>, ty: Type) -> usize {
-        if let Some(kind) = ty.def_id_no_primitives().map(|did| tcx.def_kind(did).into()) {
-            res.insert((ty, kind));
-            1
+    recurse: usize,
+    res: &mut Vec<TypeWithKind>,
+) {
+    fn insert_ty(
+        res: &mut Vec<TypeWithKind>,
+        tcx: TyCtxt<'_>,
+        ty: Type,
+        mut generics: Vec<TypeWithKind>,
+    ) {
+        let is_full_generic = ty.is_full_generic();
+
+        if is_full_generic && generics.len() == 1 {
+            // In this case, no need to go through an intermediate state if the generics
+            // contains only one element.
+            //
+            // For example:
+            //
+            // fn foo<T: Display>(r: Option<T>) {}
+            //
+            // In this case, it would contain:
+            //
+            // ```
+            // [{
+            //     name: "option",
+            //     generics: [{
+            //         name: "",
+            //         generics: [
+            //             name: "Display",
+            //             generics: []
+            //         }]
+            //     }]
+            // }]
+            // ```
+            //
+            // After removing the intermediate (unnecessary) full generic, it'll become:
+            //
+            // ```
+            // [{
+            //     name: "option",
+            //     generics: [{
+            //         name: "Display",
+            //         generics: []
+            //     }]
+            // }]
+            // ```
+            //
+            // To be noted that it can work if there is ONLY ONE generic, otherwise we still
+            // need to keep it as is!
+            res.push(generics.pop().unwrap());
+            return;
+        }
+        let mut index_ty = get_index_type(&ty, generics);
+        if index_ty.name.as_ref().map(|s| s.is_empty()).unwrap_or(true) {
+            return;
+        }
+        if is_full_generic {
+            // We remove the name of the full generic because we have no use for it.
+            index_ty.name = Some(String::new());
+            res.push(TypeWithKind::from((index_ty, ItemType::Generic)));
+        } else if let Some(kind) = ty.def_id_no_primitives().map(|did| tcx.def_kind(did).into()) {
+            res.push(TypeWithKind::from((index_ty, kind)));
         } else if ty.is_primitive() {
             // This is a primitive, let's store it as such.
-            res.insert((ty, ItemType::Primitive));
-            1
-        } else {
-            0
+            res.push(TypeWithKind::from((index_ty, ItemType::Primitive)));
         }
     }
 
     if recurse >= 10 {
         // FIXME: remove this whole recurse thing when the recursion bug is fixed
-        return 0;
+        return;
     }
-    let mut nb_added = 0;
 
     if let Type::Generic(arg_s) = *arg {
         if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
@@ -301,6 +326,7 @@ crate fn get_real_types<'tcx>(
             }
             _ => false,
         }) {
+            let mut ty_generics = Vec::new();
             let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
             for bound in bounds.iter() {
                 if let GenericBound::TraitBound(poly_trait, _) = bound {
@@ -309,41 +335,32 @@ crate fn get_real_types<'tcx>(
                             continue;
                         }
                         if let Some(ty) = x.get_type() {
-                            let adds = get_real_types(generics, &ty, tcx, recurse + 1, res);
-                            nb_added += adds;
-                            if adds == 0 && !ty.is_full_generic() {
-                                nb_added += insert(res, tcx, ty);
-                            }
+                            get_real_types(generics, &ty, tcx, recurse + 1, &mut ty_generics);
                         }
                     }
                 }
             }
+            insert_ty(res, tcx, arg.clone(), ty_generics);
         }
         if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
+            let mut ty_generics = Vec::new();
             for bound in bound.get_bounds().unwrap_or(&[]) {
                 if let Some(path) = bound.get_trait_path() {
                     let ty = Type::ResolvedPath { did: path.def_id(), path };
-                    let adds = get_real_types(generics, &ty, tcx, recurse + 1, res);
-                    nb_added += adds;
-                    if adds == 0 && !ty.is_full_generic() {
-                        nb_added += insert(res, tcx, ty);
-                    }
+                    get_real_types(generics, &ty, tcx, recurse + 1, &mut ty_generics);
                 }
             }
+            insert_ty(res, tcx, arg.clone(), ty_generics);
         }
     } else {
-        nb_added += insert(res, tcx, arg.clone());
-        if let Some(gens) = arg.generics() {
-            for gen in gens.iter() {
-                if gen.is_full_generic() {
-                    nb_added += get_real_types(generics, gen, tcx, recurse + 1, res);
-                } else {
-                    nb_added += insert(res, tcx, (*gen).clone());
-                }
+        let mut ty_generics = Vec::new();
+        if let Some(arg_generics) = arg.generics() {
+            for gen in arg_generics.iter() {
+                get_real_types(generics, gen, tcx, recurse + 1, &mut ty_generics);
             }
         }
+        insert_ty(res, tcx, arg.clone(), ty_generics);
     }
-    nb_added
 }
 
 /// Return the full list of types when bounds have been resolved.
@@ -354,38 +371,41 @@ crate fn get_all_types<'tcx>(
     generics: &Generics,
     decl: &FnDecl,
     tcx: TyCtxt<'tcx>,
-) -> (Vec<(Type, ItemType)>, Vec<(Type, ItemType)>) {
-    let mut all_types = FxHashSet::default();
+) -> (Vec<TypeWithKind>, Vec<TypeWithKind>) {
+    let mut all_types = Vec::new();
     for arg in decl.inputs.values.iter() {
         if arg.type_.is_self_type() {
             continue;
         }
-        let mut args = FxHashSet::default();
+        // FIXME: performance wise, it'd be much better to move `args` declaration outside of the
+        // loop and replace this line with `args.clear()`.
+        let mut args = Vec::new();
         get_real_types(generics, &arg.type_, tcx, 0, &mut args);
         if !args.is_empty() {
+            // FIXME: once back to performance improvements, replace this line with:
+            // `all_types.extend(args.drain(..));`.
             all_types.extend(args);
         } else {
             if let Some(kind) = arg.type_.def_id_no_primitives().map(|did| tcx.def_kind(did).into())
             {
-                all_types.insert((arg.type_.clone(), kind));
+                all_types.push(TypeWithKind::from((get_index_type(&arg.type_, vec![]), kind)));
             }
         }
     }
 
-    let ret_types = match decl.output {
+    let mut ret_types = Vec::new();
+    match decl.output {
         FnRetTy::Return(ref return_type) => {
-            let mut ret = FxHashSet::default();
-            get_real_types(generics, return_type, tcx, 0, &mut ret);
-            if ret.is_empty() {
+            get_real_types(generics, return_type, tcx, 0, &mut ret_types);
+            if ret_types.is_empty() {
                 if let Some(kind) =
                     return_type.def_id_no_primitives().map(|did| tcx.def_kind(did).into())
                 {
-                    ret.insert((return_type.clone(), kind));
+                    ret_types.push(TypeWithKind::from((get_index_type(return_type, vec![]), kind)));
                 }
             }
-            ret.into_iter().collect()
         }
-        _ => Vec::new(),
+        _ => {}
     };
-    (all_types.into_iter().collect(), ret_types)
+    (all_types, ret_types)
 }
diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index 07dea624d7c..68b2dd1536b 100644
--- a/src/librustdoc/html/render/mod.rs
+++ b/src/librustdoc/html/render/mod.rs
@@ -108,7 +108,7 @@ crate struct IndexItem {
 #[derive(Debug)]
 crate struct RenderType {
     name: Option<String>,
-    generics: Option<Vec<String>>,
+    generics: Option<Vec<TypeWithKind>>,
 }
 
 /// Full type of functions/methods in the search index.
@@ -2387,6 +2387,7 @@ fn item_ty_to_strs(ty: ItemType) -> (&'static str, &'static str) {
         ItemType::ProcAttribute => ("attributes", "Attribute Macros"),
         ItemType::ProcDerive => ("derives", "Derive Macros"),
         ItemType::TraitAlias => ("trait-aliases", "Trait aliases"),
+        ItemType::Generic => unreachable!(),
     }
 }