rustdoc-search: depth limit `T<U>` -> `U` unboxing

Profiler output:
https://notriddle.com/rustdoc-html-demo-9/search-unbox-limit/

This is a performance enhancement aimed at a problem I found while
using type-driven search on the Rust compiler. It is caused by
[`Interner`], a trait with 41 associated types, many of which
recurse back to `Self` again.

This caused search.js to struggle. It eventually terminates,
after about 10 minutes of turning my PC into a space header, but it's
doing `41!` unifications and that's too slow.

[`Interner`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.Interner.html

1 files changed, 108 insertions, 31 deletions

diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index 7995a33f09f..41fab540dc2 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -1,3 +1,4 @@
+// ignore-tidy-filelength
 /* global addClass, getNakedUrl, getSettingValue */
 /* global onEachLazy, removeClass, searchState, browserSupportsHistoryApi, exports */
 
@@ -80,6 +81,13 @@ const longItemTypes = [
 const TY_GENERIC = itemTypes.indexOf("generic");
 const ROOT_PATH = typeof window !== "undefined" ? window.rootPath : "../";
 
+// Hard limit on how deep to recurse into generics when doing type-driven search.
+// This needs limited, partially because
+// a search for `Ty` shouldn't match `WithInfcx<ParamEnvAnd<Vec<ConstTy<Interner<Ty=Ty>>>>>`,
+// but mostly because this is the simplest and most principled way to limit the number
+// of permutations we need to check.
+const UNBOXING_LIMIT = 5;
+
 // In the search display, allows to switch between tabs.
 function printTab(nb) {
     let iter = 0;
@@ -1383,10 +1391,23 @@ if (parserState.userQuery[parserState.pos] === "[") {
          * @param {Map<number,number>|null} mgensIn
          *     - Map functions generics to query generics (never modified).
          * @param {null|Map<number,number> -> bool} solutionCb - Called for each `mgens` solution.
+         * @param {number} unboxingDepth
+         *     - Limit checks that Ty matches Vec<Ty>,
+         *       but not Vec<ParamEnvAnd<WithInfcx<ConstTy<Interner<Ty=Ty>>>>>
          *
          * @return {boolean} - Returns true if a match, false otherwise.
          */
-        function unifyFunctionTypes(fnTypesIn, queryElems, whereClause, mgensIn, solutionCb) {
+        function unifyFunctionTypes(
+            fnTypesIn,
+            queryElems,
+            whereClause,
+            mgensIn,
+            solutionCb,
+            unboxingDepth
+        ) {
+            if (unboxingDepth >= UNBOXING_LIMIT) {
+                return false;
+            }
             /**
              * @type Map<integer, integer>|null
              */
@@ -1405,7 +1426,7 @@ if (parserState.userQuery[parserState.pos] === "[") {
                 && queryElems[0].bindings.size === 0) {
                 const queryElem = queryElems[0];
                 for (const fnType of fnTypesIn) {
-                    if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) {
+                    if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgens)) {
                         continue;
                     }
                     if (fnType.id < 0 && queryElem.id < 0) {
@@ -1424,7 +1445,13 @@ if (parserState.userQuery[parserState.pos] === "[") {
                     }
                 }
                 for (const fnType of fnTypesIn) {
-                    if (!unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
+                    if (!unifyFunctionTypeIsUnboxCandidate(
+                        fnType,
+                        queryElem,
+                        whereClause,
+                        mgens,
+                        unboxingDepth + 1
+                    )) {
                         continue;
                     }
                     if (fnType.id < 0) {
@@ -1439,7 +1466,8 @@ if (parserState.userQuery[parserState.pos] === "[") {
                             queryElems,
                             whereClause,
                             mgensScratch,
-                            solutionCb
+                            solutionCb,
+                            unboxingDepth + 1
                         )) {
                             return true;
                         }
@@ -1448,7 +1476,8 @@ if (parserState.userQuery[parserState.pos] === "[") {
                         queryElems,
                         whereClause,
                         mgens ? new Map(mgens) : null,
-                        solutionCb
+                        solutionCb,
+                        unboxingDepth + 1
                     )) {
                         return true;
                     }
@@ -1484,7 +1513,7 @@ if (parserState.userQuery[parserState.pos] === "[") {
             let queryElemsTmp = null;
             for (let i = flast; i >= 0; i -= 1) {
                 const fnType = fnTypes[i];
-                if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) {
+                if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgens)) {
                     continue;
                 }
                 let mgensScratch;
@@ -1521,7 +1550,8 @@ if (parserState.userQuery[parserState.pos] === "[") {
                             fnType,
                             queryElem,
                             whereClause,
-                            mgensScratch
+                            mgensScratch,
+                            unboxingDepth
                         );
                         if (!solution) {
                             return false;
@@ -1533,14 +1563,16 @@ if (parserState.userQuery[parserState.pos] === "[") {
                                 queryElem.generics,
                                 whereClause,
                                 simplifiedMgens,
-                                solutionCb
+                                solutionCb,
+                                unboxingDepth
                             );
                             if (passesUnification) {
                                 return true;
                             }
                         }
                         return false;
-                    }
+                    },
+                    unboxingDepth
                 );
                 if (passesUnification) {
                     return true;
@@ -1552,7 +1584,13 @@ if (parserState.userQuery[parserState.pos] === "[") {
             }
             for (let i = flast; i >= 0; i -= 1) {
                 const fnType = fnTypes[i];
-                if (!unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
+                if (!unifyFunctionTypeIsUnboxCandidate(
+                    fnType,
+                    queryElem,
+                    whereClause,
+                    mgens,
+                    unboxingDepth + 1
+                )) {
                     continue;
                 }
                 let mgensScratch;
@@ -1576,7 +1614,8 @@ if (parserState.userQuery[parserState.pos] === "[") {
                     queryElems,
                     whereClause,
                     mgensScratch,
-                    solutionCb
+                    solutionCb,
+                    unboxingDepth + 1
                 );
                 if (passesUnification) {
                     return true;
@@ -1595,11 +1634,10 @@ if (parserState.userQuery[parserState.pos] === "[") {
          *
          * @param {FunctionType} fnType
          * @param {QueryElement} queryElem
-         * @param {[FunctionSearchType]} whereClause - Trait bounds for generic items.
          * @param {Map<number,number>|null} mgensIn - Map functions generics to query generics.
          * @returns {boolean}
          */
-        function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgensIn) {
+        function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgensIn) {
             // type filters look like `trait:Read` or `enum:Result`
             if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) {
                 return false;
@@ -1694,9 +1732,16 @@ if (parserState.userQuery[parserState.pos] === "[") {
          * @param {[FunctionType]} whereClause - Trait bounds for generic items.
          * @param {Map<number,number>} mgensIn - Map functions generics to query generics.
          *                                            Never modified.
+         * @param {number} unboxingDepth
          * @returns {false|{mgens: [Map<number,number>], simplifiedGenerics: [FunctionType]}}
          */
-        function unifyFunctionTypeCheckBindings(fnType, queryElem, whereClause, mgensIn) {
+        function unifyFunctionTypeCheckBindings(
+            fnType,
+            queryElem,
+            whereClause,
+            mgensIn,
+            unboxingDepth
+        ) {
             if (fnType.bindings.size < queryElem.bindings.size) {
                 return false;
             }
@@ -1723,7 +1768,8 @@ if (parserState.userQuery[parserState.pos] === "[") {
                                 // return `false` makes unifyFunctionTypes return the full set of
                                 // possible solutions
                                 return false;
-                            }
+                            },
+                            unboxingDepth
                         );
                         return newSolutions;
                     });
@@ -1753,9 +1799,19 @@ if (parserState.userQuery[parserState.pos] === "[") {
          * @param {QueryElement} queryElem
          * @param {[FunctionType]} whereClause - Trait bounds for generic items.
          * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
+         * @param {number} unboxingDepth
          * @returns {boolean}
          */
-        function unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens) {
+        function unifyFunctionTypeIsUnboxCandidate(
+            fnType,
+            queryElem,
+            whereClause,
+            mgens,
+            unboxingDepth
+        ) {
+            if (unboxingDepth >= UNBOXING_LIMIT) {
+                return false;
+            }
             if (fnType.id < 0 && queryElem.id >= 0) {
                 if (!whereClause) {
                     return false;
@@ -1777,14 +1833,21 @@ if (parserState.userQuery[parserState.pos] === "[") {
                     whereClause[(-fnType.id) - 1],
                     queryElem,
                     whereClause,
-                    mgensTmp
+                    mgensTmp,
+                    unboxingDepth
                 );
             } else if (fnType.generics.length > 0 || fnType.bindings.size > 0) {
                 const simplifiedGenerics = [
                     ...fnType.generics,
                     ...Array.from(fnType.bindings.values()).flat(),
                 ];
-                return checkIfInList(simplifiedGenerics, queryElem, whereClause, mgens);
+                return checkIfInList(
+                    simplifiedGenerics,
+                    queryElem,
+                    whereClause,
+                    mgens,
+                    unboxingDepth
+                );
             }
             return false;
         }
@@ -1796,13 +1859,14 @@ if (parserState.userQuery[parserState.pos] === "[") {
           * @param {Array<FunctionType>} list
           * @param {QueryElement} elem          - The element from the parsed query.
           * @param {[FunctionType]} whereClause - Trait bounds for generic items.
-         * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
+          * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
+          * @param {number} unboxingDepth
           *
           * @return {boolean} - Returns true if found, false otherwise.
           */
-        function checkIfInList(list, elem, whereClause, mgens) {
+        function checkIfInList(list, elem, whereClause, mgens, unboxingDepth) {
             for (const entry of list) {
-                if (checkType(entry, elem, whereClause, mgens)) {
+                if (checkType(entry, elem, whereClause, mgens, unboxingDepth)) {
                     return true;
                 }
             }
@@ -1816,14 +1880,23 @@ if (parserState.userQuery[parserState.pos] === "[") {
           * @param {Row} row
           * @param {QueryElement} elem          - The element from the parsed query.
           * @param {[FunctionType]} whereClause - Trait bounds for generic items.
-         * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
+          * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
           *
           * @return {boolean} - Returns true if the type matches, false otherwise.
           */
-        function checkType(row, elem, whereClause, mgens) {
+        function checkType(row, elem, whereClause, mgens, unboxingDepth) {
+            if (unboxingDepth >= UNBOXING_LIMIT) {
+                return false;
+            }
             if (row.bindings.size === 0 && elem.bindings.size === 0) {
-                if (elem.id < 0) {
-                    return row.id < 0 || checkIfInList(row.generics, elem, whereClause, mgens);
+                if (elem.id < 0 && mgens === null) {
+                    return row.id < 0 || checkIfInList(
+                        row.generics,
+                        elem,
+                        whereClause,
+                        mgens,
+                        unboxingDepth + 1
+                    );
                 }
                 if (row.id > 0 && elem.id > 0 && elem.pathWithoutLast.length === 0 &&
                     typePassesFilter(elem.typeFilter, row.ty) && elem.generics.length === 0 &&
@@ -1834,11 +1907,12 @@ if (parserState.userQuery[parserState.pos] === "[") {
                         row.generics,
                         elem,
                         whereClause,
-                        mgens
+                        mgens,
+                        unboxingDepth
                     );
                 }
             }
-            return unifyFunctionTypes([row], [elem], whereClause, mgens);
+            return unifyFunctionTypes([row], [elem], whereClause, mgens, null, unboxingDepth);
         }
 
         /**
@@ -2053,9 +2127,9 @@ if (parserState.userQuery[parserState.pos] === "[") {
             );
             if (tfpDist !== null) {
                 const in_args = row.type && row.type.inputs
-                    && checkIfInList(row.type.inputs, elem, row.type.where_clause);
+                    && checkIfInList(row.type.inputs, elem, row.type.where_clause, null, 0);
                 const returned = row.type && row.type.output
-                    && checkIfInList(row.type.output, elem, row.type.where_clause);
+                    && checkIfInList(row.type.output, elem, row.type.where_clause, null, 0);
                 if (in_args) {
                     results_in_args.max_dist = Math.max(results_in_args.max_dist || 0, tfpDist);
                     const maxDist = results_in_args.size < MAX_RESULTS ?
@@ -2141,9 +2215,12 @@ if (parserState.userQuery[parserState.pos] === "[") {
                         row.type.output,
                         parsedQuery.returned,
                         row.type.where_clause,
-                        mgens
+                        mgens,
+                        null,
+                        0 // unboxing depth
                     );
-                }
+                },
+                0 // unboxing depth
             )) {
                 return;
             }