rustdoc: reference function signature types from the `p` array

This reduces the size of the function signature index, because
it's common to have many functions that operate on the same types.

    $ wc -c search-index-old.js search-index-new.js
    5224374 search-index-old.js
    3932314 search-index-new.js

By my math, this reduces the uncompressed size of the search index by 32%.
On compressed signatures, the wins are less drastic, a mere 8%:

    $ wc -c search-index-old.js.gz search-index-new.js.gz
    404532 search-index-old.js.gz
    371635 search-index-new.js.gz

1 files changed, 96 insertions, 35 deletions

diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index cb1609d4983..54057627c92 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -114,10 +114,6 @@ function levenshtein(s1, s2) {
 function initSearch(rawSearchIndex) {
     const MAX_LEV_DISTANCE = 3;
     const MAX_RESULTS = 200;
-    const GENERICS_DATA = 2;
-    const NAME = 0;
-    const INPUTS_DATA = 0;
-    const OUTPUT_DATA = 1;
     const NO_TYPE_FILTER = -1;
     /**
      *  @type {Array<Row>}
@@ -895,21 +891,18 @@ function initSearch(rawSearchIndex) {
          * @return {integer}           - Returns the best match (if any) or `MAX_LEV_DISTANCE + 1`.
          */
         function checkGenerics(row, elem, defaultLev) {
-            if (row.length <= GENERICS_DATA || row[GENERICS_DATA].length === 0) {
-                return elem.generics.length === 0 ? defaultLev : MAX_LEV_DISTANCE + 1;
-            } else if (row[GENERICS_DATA].length > 0 && row[GENERICS_DATA][0][NAME] === "") {
-                if (row.length > GENERICS_DATA) {
-                    return checkGenerics(row[GENERICS_DATA][0], elem, defaultLev);
-                }
+            if (row.generics.length === 0) {
                 return elem.generics.length === 0 ? defaultLev : MAX_LEV_DISTANCE + 1;
+            } else if (row.generics.length > 0 && row.generics[0].name === null) {
+                return checkGenerics(row.generics[0], elem, defaultLev);
             }
             // The names match, but we need to be sure that all generics kinda
             // match as well.
             let elem_name;
-            if (elem.generics.length > 0 && row[GENERICS_DATA].length >= elem.generics.length) {
+            if (elem.generics.length > 0 && row.generics.length >= elem.generics.length) {
                 const elems = Object.create(null);
-                for (const entry of row[GENERICS_DATA]) {
-                    elem_name = entry[NAME];
+                for (const entry of row.generics) {
+                    elem_name = entry.name;
                     if (elem_name === "") {
                         // Pure generic, needs to check into it.
                         if (checkGenerics(entry, elem, MAX_LEV_DISTANCE + 1) !== 0) {
@@ -963,7 +956,7 @@ function initSearch(rawSearchIndex) {
           */
         function checkIfInGenerics(row, elem) {
             let lev = MAX_LEV_DISTANCE + 1;
-            for (const entry of row[GENERICS_DATA]) {
+            for (const entry of row.generics) {
                 lev = Math.min(checkType(entry, elem, true), lev);
                 if (lev === 0) {
                     break;
@@ -984,23 +977,22 @@ function initSearch(rawSearchIndex) {
           *                     no match, returns `MAX_LEV_DISTANCE + 1`.
           */
         function checkType(row, elem, literalSearch) {
-            if (row[NAME].length === 0) {
+            if (row.name === null) {
                 // This is a pure "generic" search, no need to run other checks.
-                if (row.length > GENERICS_DATA) {
+                if (row.generics.length > 0) {
                     return checkIfInGenerics(row, elem);
                 }
                 return MAX_LEV_DISTANCE + 1;
             }
 
-            let lev = levenshtein(row[NAME], elem.name);
+            let lev = levenshtein(row.name, elem.name);
             if (literalSearch) {
                 if (lev !== 0) {
                     // The name didn't match, let's try to check if the generics do.
                     if (elem.generics.length === 0) {
-                        const checkGeneric = (row.length > GENERICS_DATA &&
-                            row[GENERICS_DATA].length > 0);
-                        if (checkGeneric && row[GENERICS_DATA]
-                            .findIndex(tmp_elem => tmp_elem[NAME] === elem.name) !== -1) {
+                        const checkGeneric = row.generics.length > 0;
+                        if (checkGeneric && row.generics
+                            .findIndex(tmp_elem => tmp_elem.name === elem.name) !== -1) {
                             return 0;
                         }
                     }
@@ -1009,7 +1001,7 @@ function initSearch(rawSearchIndex) {
                     return checkGenerics(row, elem, MAX_LEV_DISTANCE + 1);
                 }
                 return 0;
-            } else if (row.length > GENERICS_DATA) {
+            } else if (row.generics.length > 0) {
                 if (elem.generics.length === 0) {
                     if (lev === 0) {
                         return 0;
@@ -1059,9 +1051,9 @@ function initSearch(rawSearchIndex) {
         function findArg(row, elem, typeFilter) {
             let lev = MAX_LEV_DISTANCE + 1;
 
-            if (row && row.type && row.type[INPUTS_DATA] && row.type[INPUTS_DATA].length > 0) {
-                for (const input of row.type[INPUTS_DATA]) {
-                    if (!typePassesFilter(typeFilter, input[1])) {
+            if (row && row.type && row.type.inputs && row.type.inputs.length > 0) {
+                for (const input of row.type.inputs) {
+                    if (!typePassesFilter(typeFilter, input.ty)) {
                         continue;
                     }
                     lev = Math.min(lev, checkType(input, elem, parsedQuery.literalSearch));
@@ -1086,13 +1078,10 @@ function initSearch(rawSearchIndex) {
         function checkReturned(row, elem, typeFilter) {
             let lev = MAX_LEV_DISTANCE + 1;
 
-            if (row && row.type && row.type.length > OUTPUT_DATA) {
-                let ret = row.type[OUTPUT_DATA];
-                if (typeof ret[0] === "string") {
-                    ret = [ret];
-                }
+            if (row && row.type && row.type.output.length > 0) {
+                const ret = row.type.output;
                 for (const ret_ty of ret) {
-                    if (!typePassesFilter(typeFilter, ret_ty[1])) {
+                    if (!typePassesFilter(typeFilter, ret_ty.ty)) {
                         continue;
                     }
                     lev = Math.min(lev, checkType(ret_ty, elem, parsedQuery.literalSearch));
@@ -1836,6 +1825,65 @@ function initSearch(rawSearchIndex) {
             filterCrates);
     }
 
+    function buildItemSearchTypeAll(types, lowercasePaths) {
+        const PATH_INDEX_DATA = 0;
+        const GENERICS_DATA = 1;
+        if (types === null) {
+            return [];
+        }
+        return types.map(type => {
+            let pathIndex, generics;
+            if (typeof type === "number") {
+                pathIndex = type;
+                generics = [];
+            } else {
+                pathIndex = type[PATH_INDEX_DATA];
+                generics = buildItemSearchTypeAll(type[GENERICS_DATA], lowercasePaths);
+            }
+            return {
+                name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
+                ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
+                generics: generics,
+            };
+        });
+    }
+
+    function buildFunctionSearchType(functionSearchType, lowercasePaths) {
+        const INPUTS_DATA = 0;
+        const OUTPUT_DATA = 1;
+        if (functionSearchType === 0 || functionSearchType === null) {
+            return null;
+        }
+        let inputs, output;
+        if (typeof functionSearchType[INPUTS_DATA] === "number") {
+            const pathIndex = functionSearchType[INPUTS_DATA];
+            inputs = [{
+                name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
+                ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
+                generics: [],
+            }];
+        } else {
+            inputs = buildItemSearchTypeAll(functionSearchType[INPUTS_DATA], lowercasePaths);
+        }
+        if (functionSearchType.length > 1) {
+            if (typeof functionSearchType[OUTPUT_DATA] === "number") {
+                const pathIndex = functionSearchType[OUTPUT_DATA];
+                output = [{
+                    name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
+                    ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
+                    generics: [],
+                }];
+            } else {
+                output = buildItemSearchTypeAll(functionSearchType[OUTPUT_DATA], lowercasePaths);
+            }
+        } else {
+            output = null;
+        }
+        return {
+            inputs, output,
+        };
+    }
+
     function buildIndex(rawSearchIndex) {
         searchIndex = [];
         /**
@@ -1862,14 +1910,22 @@ function initSearch(rawSearchIndex) {
              * q[i] contains the full path of the item, or an empty string indicating
              * "same as q[i-1]".
              *
-             * i[i], f[i] are a mystery.
+             * i[i] contains an item's parent, usually a module. For compactness,
+             * it is a set of indexes into the `p` array.
+             *
+             * f[i] contains function signatures, or `0` if the item isn't a function.
+             * Functions are themselves encoded as arrays. The first item is a list of
+             * types representing the function's inputs, and the second list item is a list
+             * of types representing the function's output. Tuples are flattened.
+             * Types are also represented as arrays; the first item is an index into the `p`
+             * array, while the second is a list of types representing any generic parameters.
              *
              * `a` defines aliases with an Array of pairs: [name, offset], where `offset`
              * points into the n/t/d/q/i/f arrays.
              *
              * `doc` contains the description of the crate.
              *
-             * `p` is a mystery and isn't the same length as n/t/d/q/i/f.
+             * `p` is a list of path/type pairs. It is used for parents and function parameters.
              *
              * @type {{
              *   doc: string,
@@ -1879,7 +1935,7 @@ function initSearch(rawSearchIndex) {
              *   d: Array<string>,
              *   q: Array<string>,
              *   i: Array<Number>,
-             *   f: Array<Array<?>>,
+             *   f: Array<0 | Object>,
              *   p: Array<Object>,
              * }}
              */
@@ -1923,9 +1979,14 @@ function initSearch(rawSearchIndex) {
             //             [Number] index to items]
             const aliases = crateCorpus.a;
 
+            // an array of [{name: String, ty: Number}]
+            const lowercasePaths = [];
+
             // convert `rawPaths` entries into object form
+            // generate normalizedPaths for function search mode
             let len = paths.length;
             for (i = 0; i < len; ++i) {
+                lowercasePaths.push({ty: paths[i][0], name: paths[i][1].toLowerCase()});
                 paths[i] = {ty: paths[i][0], name: paths[i][1]};
             }
 
@@ -1955,7 +2016,7 @@ function initSearch(rawSearchIndex) {
                     path: itemPaths[i] ? itemPaths[i] : lastPath,
                     desc: itemDescs[i],
                     parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
-                    type: itemFunctionSearchTypes[i],
+                    type: buildFunctionSearchType(itemFunctionSearchTypes[i], lowercasePaths),
                     id: id,
                     normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
                 };