Auto merge of #98475 - notriddle:notriddle/index-fn-signatures, r=GuillaumeGomez

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

2 files changed, 187 insertions, 35 deletions

diff --git a/src/librustdoc/html/static/js/externs.js b/src/librustdoc/html/static/js/externs.js
index defdc20132e..ecbe15a59da 100644
--- a/src/librustdoc/html/static/js/externs.js
+++ b/src/librustdoc/html/static/js/externs.js
@@ -81,3 +81,62 @@ let ResultsTable;
  * }}
  */
 let Results;
+
+/**
+ * A pair of [inputs, outputs], or 0 for null. This is stored in the search index.
+ * The JavaScript deserializes this into FunctionSearchType.
+ *
+ * Numeric IDs are *ONE-indexed* into the paths array (`p`). Zero is used as a sentinel for `null`
+ * because `null` is four bytes while `0` is one byte.
+ *
+ * An input or output can be encoded as just a number if there is only one of them, AND
+ * it has no generics. The no generics rule exists to avoid ambiguity: imagine if you had
+ * a function with a single output, and that output had a single generic:
+ *
+ *     fn something() -> Result<usize, usize>
+ *
+ * If output was allowed to be any RawFunctionType, it would look like this
+ *
+ *     [[], [50, [3, 3]]]
+ *
+ * The problem is that the above output could be interpreted as either a type with ID 50 and two
+ * generics, or it could be interpreted as a pair of types, the first one with ID 50 and the second
+ * with ID 3 and a single generic parameter that is also ID 3. We avoid this ambiguity by choosing
+ * in favor of the pair of types interpretation. This is why the `(number|Array<RawFunctionType>)`
+ * is used instead of `(RawFunctionType|Array<RawFunctionType>)`.
+ *
+ * @typedef {(
+ *     0 |
+ *     [(number|Array<RawFunctionType>)] |
+ *     [(number|Array<RawFunctionType>), (number|Array<RawFunctionType>)]
+ * )}
+ */
+let RawFunctionSearchType;
+
+/**
+ * A single function input or output type. This is either a single path ID, or a pair of
+ * [path ID, generics].
+ *
+ * Numeric IDs are *ONE-indexed* into the paths array (`p`). Zero is used as a sentinel for `null`
+ * because `null` is four bytes while `0` is one byte.
+ *
+ * @typedef {number | [number, Array<RawFunctionType>]}
+ */
+let RawFunctionType;
+
+/**
+ * @typedef {{
+ *     inputs: Array<FunctionType>,
+ *     outputs: Array<FunctionType>,
+ * }}
+ */
+let FunctionSearchType;
+
+/**
+ * @typedef {{
+ *     name: (null|string),
+ *     ty: (null|number),
+ *     generics: Array<FunctionType>,
+ * }}
+ */
+let FunctionType;
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index cb1609d4983..75c7bd45a29 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,97 @@ function initSearch(rawSearchIndex) {
             filterCrates);
     }
 
+    /**
+     * Convert a list of RawFunctionType / ID to object-based FunctionType.
+     *
+     * Crates often have lots of functions in them, and it's common to have a large number of
+     * functions that operate on a small set of data types, so the search index compresses them
+     * by encoding function parameter and return types as indexes into an array of names.
+     *
+     * Even when a general-purpose compression algorithm is used, this is still a win. I checked.
+     * https://github.com/rust-lang/rust/pull/98475#issue-1284395985
+     *
+     * The format for individual function types is encoded in
+     * librustdoc/html/render/mod.rs: impl Serialize for RenderType
+     *
+     * @param {null|Array<RawFunctionType>} types
+     * @param {Array<{name: string, ty: number}>} lowercasePaths
+     *
+     * @return {Array<FunctionSearchType>}
+     */
+    function buildItemSearchTypeAll(types, lowercasePaths) {
+        const PATH_INDEX_DATA = 0;
+        const GENERICS_DATA = 1;
+        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 {
+                // `0` is used as a sentinel because it's fewer bytes than `null`
+                name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
+                ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
+                generics: generics,
+            };
+        });
+    }
+
+    /**
+     * Convert from RawFunctionSearchType to FunctionSearchType.
+     *
+     * Crates often have lots of functions in them, and function signatures are sometimes complex,
+     * so rustdoc uses a pretty tight encoding for them. This function converts it to a simpler,
+     * object-based encoding so that the actual search code is more readable and easier to debug.
+     *
+     * The raw function search type format is generated using serde in
+     * librustdoc/html/render/mod.rs: impl Serialize for IndexItemFunctionType
+     *
+     * @param {RawFunctionSearchType} functionSearchType
+     * @param {Array<{name: string, ty: number}>} lowercasePaths
+     *
+     * @return {null|FunctionSearchType}
+     */
+    function buildFunctionSearchType(functionSearchType, lowercasePaths) {
+        const INPUTS_DATA = 0;
+        const OUTPUT_DATA = 1;
+        // `0` is used as a sentinel because it's fewer bytes than `null`
+        if (functionSearchType === 0) {
+            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 = [];
+        }
+        return {
+            inputs, output,
+        };
+    }
+
     function buildIndex(rawSearchIndex) {
         searchIndex = [];
         /**
@@ -1862,14 +1942,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 +1967,7 @@ function initSearch(rawSearchIndex) {
              *   d: Array<string>,
              *   q: Array<string>,
              *   i: Array<Number>,
-             *   f: Array<Array<?>>,
+             *   f: Array<RawFunctionSearchType>,
              *   p: Array<Object>,
              * }}
              */
@@ -1923,9 +2011,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 +2048,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, ""),
                 };