fix(rustdoc): generics search

This commit adds a test case for generics, re-adds generics data
to the search index, and tweaks function indexing to use less space in JSON.

This reverts commit 14ca89446c076bcf484d3d05bd991a4b7985a409.

8 files changed, 191 insertions, 19 deletions

diff --git a/src/librustdoc/html/render/cache.rs b/src/librustdoc/html/render/cache.rs
index 4372ece5c01..0734d2670cc 100644
--- a/src/librustdoc/html/render/cache.rs
+++ b/src/librustdoc/html/render/cache.rs
@@ -219,6 +219,7 @@ crate fn get_index_search_type<'tcx>(
 fn get_index_type(clean_type: &clean::Type) -> RenderType {
     RenderType {
         name: get_index_type_name(clean_type, true).map(|s| s.as_str().to_ascii_lowercase()),
+        generics: get_generics(clean_type),
     }
 }
 
@@ -251,6 +252,23 @@ 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
diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index 6e73b2a5bef..0583efa92ff 100644
--- a/src/librustdoc/html/render/mod.rs
+++ b/src/librustdoc/html/render/mod.rs
@@ -96,6 +96,7 @@ crate struct IndexItem {
 #[derive(Debug)]
 crate struct RenderType {
     name: Option<String>,
+    generics: Option<Vec<String>>,
 }
 
 /// Full type of functions/methods in the search index.
@@ -149,7 +150,13 @@ impl Serialize for TypeWithKind {
     where
         S: Serializer,
     {
-        (&self.ty.name, self.kind).serialize(serializer)
+        let mut seq = serializer.serialize_seq(None)?;
+        seq.serialize_element(&self.ty.name)?;
+        seq.serialize_element(&self.kind)?;
+        if let Some(generics) = &self.ty.generics {
+            seq.serialize_element(generics)?;
+        }
+        seq.end()
     }
 }
 
diff --git a/src/librustdoc/html/static/search.js b/src/librustdoc/html/static/search.js
index f6343e4c3d2..a7fc0b831f4 100644
--- a/src/librustdoc/html/static/search.js
+++ b/src/librustdoc/html/static/search.js
@@ -106,7 +106,7 @@ function levenshtein(s1, s2) {
 window.initSearch = function(rawSearchIndex) {
     var MAX_LEV_DISTANCE = 3;
     var MAX_RESULTS = 200;
-    var GENERICS_DATA = 1;
+    var GENERICS_DATA = 2;
     var NAME = 0;
     var INPUTS_DATA = 0;
     var OUTPUT_DATA = 1;
@@ -306,6 +306,9 @@ window.initSearch = function(rawSearchIndex) {
                     var elems = Object.create(null);
                     var elength = obj[GENERICS_DATA].length;
                     for (var x = 0; x < elength; ++x) {
+                        if (!elems[getObjectNameFromId(obj[GENERICS_DATA][x])]) {
+                            elems[getObjectNameFromId(obj[GENERICS_DATA][x])] = 0;
+                        }
                         elems[getObjectNameFromId(obj[GENERICS_DATA][x])] += 1;
                     }
                     var total = 0;
@@ -354,10 +357,13 @@ window.initSearch = function(rawSearchIndex) {
                 if (literalSearch) {
                     if (val.generics && val.generics.length !== 0) {
                         if (obj.length > GENERICS_DATA &&
-                              obj[GENERICS_DATA].length >= val.generics.length) {
+                             obj[GENERICS_DATA].length > 0) {
                             var elems = Object.create(null);
                             len = obj[GENERICS_DATA].length;
                             for (x = 0; x < len; ++x) {
+                                if (!elems[getObjectNameFromId(obj[GENERICS_DATA][x])]) {
+                                    elems[getObjectNameFromId(obj[GENERICS_DATA][x])] = 0;
+                                }
                                 elems[getObjectNameFromId(obj[GENERICS_DATA][x])] += 1;
                             }
 
@@ -375,26 +381,23 @@ window.initSearch = function(rawSearchIndex) {
                             if (allFound) {
                                 return true;
                             }
-                        } else {
-                            return false;
                         }
+                        return false;
                     }
                     return true;
-                }
-                // 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);
-                    if (tmp_lev <= MAX_LEV_DISTANCE) {
-                        return tmp_lev;
-                    }
                 } else {
-                    return 0;
+                    // 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);
+                        if (tmp_lev <= MAX_LEV_DISTANCE) {
+                            return tmp_lev;
+                        }
+                    }
                 }
-            }
-            // Names didn't match so let's check if one of the generic types could.
-            if (literalSearch) {
-                 if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
+            } else if (literalSearch) {
+                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;
@@ -1167,7 +1170,48 @@ window.initSearch = function(rawSearchIndex) {
             return ret;
         }
 
-        var queries = query.raw.split(",");
+        // Split search query by ",", while respecting angle bracket nesting.
+        // Since "<" is an alias for the Ord family of traits, it also uses
+        // lookahead to distinguish "<"-as-less-than from "<"-as-angle-bracket.
+        //
+        // tokenizeQuery("A<B, C>, D") == ["A<B, C>", "D"]
+        // tokenizeQuery("A<B, C, D") == ["A<B", "C", "D"]
+        function tokenizeQuery(raw) {
+            var i, matched;
+            var l = raw.length;
+            var depth = 0;
+            var nextAngle = /(<|>)/g;
+            var ret = [];
+            var start = 0;
+            for (i = 0; i < l; ++i) {
+                switch (raw[i]) {
+                    case "<":
+                        nextAngle.lastIndex = i + 1;
+                        matched = nextAngle.exec(raw);
+                        if (matched && matched[1] === '>') {
+                            depth += 1;
+                        }
+                        break;
+                    case ">":
+                        if (depth > 0) {
+                            depth -= 1;
+                        }
+                        break;
+                    case ",":
+                        if (depth === 0) {
+                            ret.push(raw.substring(start, i));
+                            start = i + 1;
+                        }
+                        break;
+                }
+            }
+            if (start !== i) {
+                ret.push(raw.substring(start, i));
+            }
+            return ret;
+        }
+
+        var queries = tokenizeQuery(query.raw);
         var results = {
             "in_args": [],
             "returned": [],
diff --git a/src/test/rustdoc-js-std/alias-4.js b/src/test/rustdoc-js-std/alias-4.js
new file mode 100644
index 00000000000..bf2bb4d2981
--- /dev/null
+++ b/src/test/rustdoc-js-std/alias-4.js
@@ -0,0 +1,7 @@
+const QUERY = '<';
+
+const EXPECTED = {
+    'others': [
+        { 'name': 'Ord' },
+    ],
+};
diff --git a/src/test/rustdoc-js/generics-trait.js b/src/test/rustdoc-js/generics-trait.js
new file mode 100644
index 00000000000..7876622435b
--- /dev/null
+++ b/src/test/rustdoc-js/generics-trait.js
@@ -0,0 +1,23 @@
+const QUERY = [
+    'Result<SomeTrait>',
+    'OtherThingxxxxxxxx',
+];
+
+const EXPECTED = [
+    {
+        'in_args': [
+            { 'path': 'generics_trait', 'name': 'beta' },
+        ],
+        'returned': [
+            { 'path': 'generics_trait', 'name': 'bet' },
+        ],
+    },
+    {
+        'in_args': [
+            { 'path': 'generics_trait', 'name': 'alpha' },
+        ],
+        'returned': [
+            { 'path': 'generics_trait', 'name': 'alef' },
+        ],
+    },
+];
diff --git a/src/test/rustdoc-js/generics-trait.rs b/src/test/rustdoc-js/generics-trait.rs
new file mode 100644
index 00000000000..20db117ccd5
--- /dev/null
+++ b/src/test/rustdoc-js/generics-trait.rs
@@ -0,0 +1,8 @@
+pub trait SomeTrait {}
+pub trait OtherThingxxxxxxxx {}
+
+pub fn alef<T: OtherThingxxxxxxxx>() -> Result<T, ()> { loop {} }
+pub fn bet<T: SomeTrait>() -> Result<T, ()> { loop {} }
+
+pub fn alpha<T: OtherThingxxxxxxxx>(_param: Result<T, ()>) { loop {} }
+pub fn beta<T: SomeTrait>(_param: Result<T, ()>) { loop {} }
diff --git a/src/test/rustdoc-js/generics.js b/src/test/rustdoc-js/generics.js
new file mode 100644
index 00000000000..49a80ae2360
--- /dev/null
+++ b/src/test/rustdoc-js/generics.js
@@ -0,0 +1,44 @@
+// exact-check
+
+const QUERY = [
+  '"R<P>"',
+  '"P"',
+  'P',
+  '"ExtraCreditStructMulti<ExtraCreditInnerMulti, ExtraCreditInnerMulti>"',
+];
+
+const EXPECTED = [
+    {
+        'returned': [
+            { 'path': 'generics', 'name': 'alef' },
+        ],
+        'in_args': [
+            { 'path': 'generics', 'name': 'alpha' },
+        ],
+    },
+    {
+        'others': [
+            { 'path': 'generics', 'name': 'P' },
+        ],
+        'returned': [
+            { 'path': 'generics', 'name': 'alef' },
+        ],
+        'in_args': [
+            { 'path': 'generics', 'name': 'alpha' },
+        ],
+    },
+    {
+        'returned': [
+            { 'path': 'generics', 'name': 'alef' },
+        ],
+        'in_args': [
+            { 'path': 'generics', 'name': 'alpha' },
+        ],
+    },
+    {
+        'in_args': [
+            { 'path': 'generics', 'name': 'extracreditlabhomework' },
+        ],
+        'returned': [],
+    },
+];
diff --git a/src/test/rustdoc-js/generics.rs b/src/test/rustdoc-js/generics.rs
new file mode 100644
index 00000000000..a0dc086e9f9
--- /dev/null
+++ b/src/test/rustdoc-js/generics.rs
@@ -0,0 +1,21 @@
+pub struct P;
+pub struct Q;
+pub struct R<T>(T);
+
+// returns test
+pub fn alef() -> R<P> { loop {} }
+pub fn bet() -> R<Q> { loop {} }
+
+// in_args test
+pub fn alpha(_x: R<P>) { loop {} }
+pub fn beta(_x: R<Q>) { loop {} }
+
+// test case with multiple appearances of the same type
+pub struct ExtraCreditStructMulti<T, U> { t: T, u: U }
+pub struct ExtraCreditInnerMulti {}
+pub fn extracreditlabhomework(
+    _param: ExtraCreditStructMulti<ExtraCreditInnerMulti, ExtraCreditInnerMulti>
+) { loop {} }
+pub fn redherringmatchforextracredit(
+    _param: ExtraCreditStructMulti<ExtraCreditInnerMulti, ()>
+) { loop {} }