Fix invalid handling of generics

7 files changed, 147 insertions, 93 deletions

diff --git a/src/librustdoc/formats/item_type.rs b/src/librustdoc/formats/item_type.rs
index 955de57dc0e..793db16faf3 100644
--- a/src/librustdoc/formats/item_type.rs
+++ b/src/librustdoc/formats/item_type.rs
@@ -48,6 +48,7 @@ crate enum ItemType {
     ProcAttribute = 23,
     ProcDerive = 24,
     TraitAlias = 25,
+    Generic = 26,
 }
 
 impl Serialize for ItemType {
@@ -173,6 +174,7 @@ impl ItemType {
             ItemType::ProcAttribute => "attr",
             ItemType::ProcDerive => "derive",
             ItemType::TraitAlias => "traitalias",
+            ItemType::Generic => "generic",
         }
     }
 }
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!(),
     }
 }
 
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index 5eb545f7582..c2ea54abd2e 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -299,10 +299,10 @@ window.initSearch = function(rawSearchIndex) {
                     var elems = Object.create(null);
                     var elength = obj[GENERICS_DATA].length;
                     for (var x = 0; x < elength; ++x) {
-                        if (!elems[obj[GENERICS_DATA][x]]) {
-                            elems[obj[GENERICS_DATA][x]] = 0;
+                        if (!elems[obj[GENERICS_DATA][x][NAME]]) {
+                            elems[obj[GENERICS_DATA][x][NAME]] = 0;
                         }
-                        elems[obj[GENERICS_DATA][x]] += 1;
+                        elems[obj[GENERICS_DATA][x][NAME]] += 1;
                     }
                     var total = 0;
                     var done = 0;
@@ -345,6 +345,7 @@ window.initSearch = function(rawSearchIndex) {
         // Check for type name and type generics (if any).
         function checkType(obj, val, literalSearch) {
             var lev_distance = MAX_LEV_DISTANCE + 1;
+            var tmp_lev = MAX_LEV_DISTANCE + 1;
             var len, x, firstGeneric;
             if (obj[NAME] === val.name) {
                 if (literalSearch) {
@@ -354,10 +355,10 @@ window.initSearch = function(rawSearchIndex) {
                             var elems = Object.create(null);
                             len = obj[GENERICS_DATA].length;
                             for (x = 0; x < len; ++x) {
-                                if (!elems[obj[GENERICS_DATA][x]]) {
-                                    elems[obj[GENERICS_DATA][x]] = 0;
+                                if (!elems[obj[GENERICS_DATA][x][NAME]]) {
+                                    elems[obj[GENERICS_DATA][x][NAME]] = 0;
                                 }
-                                elems[obj[GENERICS_DATA][x]] += 1;
+                                elems[obj[GENERICS_DATA][x][NAME]] += 1;
                             }
 
                             var allFound = true;
@@ -382,7 +383,7 @@ window.initSearch = function(rawSearchIndex) {
                     // If the type has generics but don't match, then it won't return at this point.
                     // Otherwise, `checkGenerics` will return 0 and it'll return.
                     if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length !== 0) {
-                        var tmp_lev = checkGenerics(obj, val);
+                        tmp_lev = checkGenerics(obj, val);
                         if (tmp_lev <= MAX_LEV_DISTANCE) {
                             return tmp_lev;
                         }
@@ -392,8 +393,8 @@ window.initSearch = function(rawSearchIndex) {
                 if ((!val.generics || val.generics.length === 0) &&
                       obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
                     return obj[GENERICS_DATA].some(
-                        function(name) {
-                            return name === val.name;
+                        function(gen) {
+                            return gen[NAME] === val.name;
                         });
                 }
                 return false;
@@ -404,17 +405,27 @@ window.initSearch = function(rawSearchIndex) {
                 // a levenshtein distance value that isn't *this* good so it goes
                 // into the search results but not too high.
                 lev_distance = Math.ceil((checkGenerics(obj, val) + lev_distance) / 2);
-            } else if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
+            }
+            if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
                 // We can check if the type we're looking for is inside the generics!
                 var olength = obj[GENERICS_DATA].length;
                 for (x = 0; x < olength; ++x) {
-                    lev_distance = Math.min(levenshtein(obj[GENERICS_DATA][x], val.name),
-                                            lev_distance);
+                    tmp_lev = Math.min(levenshtein(obj[GENERICS_DATA][x][NAME], val.name), tmp_lev);
+                }
+                if (tmp_lev !== 0) {
+                    // If we didn't find a good enough result, we go check inside the generics of
+                    // the generics.
+                    for (x = 0; x < olength && tmp_lev !== 0; ++x) {
+                        tmp_lev = Math.min(
+                            checkType(obj[GENERICS_DATA][x], val, literalSearch),
+                            tmp_lev
+                        );
+                    }
                 }
             }
             // Now whatever happens, the returned distance is "less good" so we should mark it
             // as such, and so we add 1 to the distance to make it "less good".
-            return lev_distance + 1;
+            return Math.min(lev_distance, tmp_lev) + 1;
         }
 
         function findArg(obj, val, literalSearch, typeFilter) {
diff --git a/src/librustdoc/json/conversions.rs b/src/librustdoc/json/conversions.rs
index 443ac282134..f740ecdbded 100644
--- a/src/librustdoc/json/conversions.rs
+++ b/src/librustdoc/json/conversions.rs
@@ -697,6 +697,7 @@ impl FromWithTcx<ItemType> for ItemKind {
             TraitAlias => ItemKind::TraitAlias,
             ProcAttribute => ItemKind::ProcAttribute,
             ProcDerive => ItemKind::ProcDerive,
+            Generic => unreachable!(),
         }
     }
 }
diff --git a/src/test/rustdoc-js/generics.js b/src/test/rustdoc-js/generics.js
index 49a80ae2360..63a9ad53812 100644
--- a/src/test/rustdoc-js/generics.js
+++ b/src/test/rustdoc-js/generics.js
@@ -1,10 +1,12 @@
 // exact-check
 
 const QUERY = [
-  '"R<P>"',
-  '"P"',
-  'P',
-  '"ExtraCreditStructMulti<ExtraCreditInnerMulti, ExtraCreditInnerMulti>"',
+    '"R<P>"',
+    '"P"',
+    'P',
+    '"ExtraCreditStructMulti<ExtraCreditInnerMulti, ExtraCreditInnerMulti>"',
+    'TraitCat',
+    'TraitDog',
 ];
 
 const EXPECTED = [
@@ -30,9 +32,11 @@ const EXPECTED = [
     {
         'returned': [
             { 'path': 'generics', 'name': 'alef' },
+            { 'path': 'generics', 'name': 'bet' },
         ],
         'in_args': [
             { 'path': 'generics', 'name': 'alpha' },
+            { 'path': 'generics', 'name': 'beta' },
         ],
     },
     {
@@ -41,4 +45,14 @@ const EXPECTED = [
         ],
         'returned': [],
     },
+    {
+        'in_args': [
+            { 'path': 'generics', 'name': 'gamma' },
+        ],
+    },
+    {
+        'in_args': [
+            { 'path': 'generics', 'name': 'gamma' },
+        ],
+    },
 ];
diff --git a/src/test/rustdoc-js/generics.rs b/src/test/rustdoc-js/generics.rs
index a0dc086e9f9..5e11a6d6018 100644
--- a/src/test/rustdoc-js/generics.rs
+++ b/src/test/rustdoc-js/generics.rs
@@ -19,3 +19,8 @@ pub fn extracreditlabhomework(
 pub fn redherringmatchforextracredit(
     _param: ExtraCreditStructMulti<ExtraCreditInnerMulti, ()>
 ) { loop {} }
+
+pub trait TraitCat {}
+pub trait TraitDog {}
+
+pub fn gamma<T: TraitCat + TraitDog>(t: T) {}