Rollup merge of #122247 - notriddle:notriddle/search-unbox-limit, r=GuillaumeGomez

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

Profiler output:
https://notriddle.com/rustdoc-html-demo-9/search-unbox-limit/ (the only significant change is that one of the `rust` tests went from 378416ms to 16ms).

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

4 files changed, 366 insertions, 31 deletions

diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index 73ac5608479..875ebe2fc90 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -81,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;
@@ -1458,10 +1465,23 @@ function initSearch(rawSearchIndex) {
          * @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
              */
@@ -1480,7 +1500,7 @@ function initSearch(rawSearchIndex) {
                 && 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) {
@@ -1499,7 +1519,13 @@ function initSearch(rawSearchIndex) {
                     }
                 }
                 for (const fnType of fnTypesIn) {
-                    if (!unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
+                    if (!unifyFunctionTypeIsUnboxCandidate(
+                        fnType,
+                        queryElem,
+                        whereClause,
+                        mgens,
+                        unboxingDepth + 1
+                    )) {
                         continue;
                     }
                     if (fnType.id < 0) {
@@ -1514,7 +1540,8 @@ function initSearch(rawSearchIndex) {
                             queryElems,
                             whereClause,
                             mgensScratch,
-                            solutionCb
+                            solutionCb,
+                            unboxingDepth + 1
                         )) {
                             return true;
                         }
@@ -1523,7 +1550,8 @@ function initSearch(rawSearchIndex) {
                         queryElems,
                         whereClause,
                         mgens ? new Map(mgens) : null,
-                        solutionCb
+                        solutionCb,
+                        unboxingDepth + 1
                     )) {
                         return true;
                     }
@@ -1559,7 +1587,7 @@ function initSearch(rawSearchIndex) {
             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;
@@ -1596,7 +1624,8 @@ function initSearch(rawSearchIndex) {
                             fnType,
                             queryElem,
                             whereClause,
-                            mgensScratch
+                            mgensScratch,
+                            unboxingDepth
                         );
                         if (!solution) {
                             return false;
@@ -1608,14 +1637,16 @@ function initSearch(rawSearchIndex) {
                                 queryElem.generics,
                                 whereClause,
                                 simplifiedMgens,
-                                solutionCb
+                                solutionCb,
+                                unboxingDepth
                             );
                             if (passesUnification) {
                                 return true;
                             }
                         }
                         return false;
-                    }
+                    },
+                    unboxingDepth
                 );
                 if (passesUnification) {
                     return true;
@@ -1627,7 +1658,13 @@ function initSearch(rawSearchIndex) {
             }
             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;
@@ -1651,7 +1688,8 @@ function initSearch(rawSearchIndex) {
                     queryElems,
                     whereClause,
                     mgensScratch,
-                    solutionCb
+                    solutionCb,
+                    unboxingDepth + 1
                 );
                 if (passesUnification) {
                     return true;
@@ -1670,11 +1708,10 @@ function initSearch(rawSearchIndex) {
          *
          * @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;
@@ -1775,9 +1812,16 @@ function initSearch(rawSearchIndex) {
          * @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;
             }
@@ -1804,7 +1848,8 @@ function initSearch(rawSearchIndex) {
                                 // return `false` makes unifyFunctionTypes return the full set of
                                 // possible solutions
                                 return false;
-                            }
+                            },
+                            unboxingDepth
                         );
                         return newSolutions;
                     });
@@ -1834,9 +1879,19 @@ function initSearch(rawSearchIndex) {
          * @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;
@@ -1858,14 +1913,21 @@ function initSearch(rawSearchIndex) {
                     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;
         }
@@ -1877,13 +1939,14 @@ function initSearch(rawSearchIndex) {
           * @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;
                 }
             }
@@ -1897,14 +1960,23 @@ function initSearch(rawSearchIndex) {
           * @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 &&
@@ -1916,11 +1988,12 @@ function initSearch(rawSearchIndex) {
                         row.generics,
                         elem,
                         whereClause,
-                        mgens
+                        mgens,
+                        unboxingDepth
                     );
                 }
             }
-            return unifyFunctionTypes([row], [elem], whereClause, mgens);
+            return unifyFunctionTypes([row], [elem], whereClause, mgens, null, unboxingDepth);
         }
 
         /**
@@ -2135,9 +2208,9 @@ function initSearch(rawSearchIndex) {
             );
             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 ?
@@ -2223,9 +2296,12 @@ function initSearch(rawSearchIndex) {
                         row.type.output,
                         parsedQuery.returned,
                         row.type.where_clause,
-                        mgens
+                        mgens,
+                        null,
+                        0 // unboxing depth
                     );
-                }
+                },
+                0 // unboxing depth
             )) {
                 return;
             }
diff --git a/tests/rustdoc-js/auxiliary/interner.rs b/tests/rustdoc-js/auxiliary/interner.rs
new file mode 100644
index 00000000000..c95029be9f0
--- /dev/null
+++ b/tests/rustdoc-js/auxiliary/interner.rs
@@ -0,0 +1,245 @@
+#![feature(associated_type_defaults)]
+
+use std::cmp::Ord;
+use std::fmt::{Debug, Formatter};
+use std::hash::Hash;
+use std::ops::ControlFlow;
+
+pub trait Interner: Sized {
+    type DefId: Copy + Debug + Hash + Ord;
+    type AdtDef: Copy + Debug + Hash + Ord;
+    type GenericArgs: Copy
+        + DebugWithInfcx<Self>
+        + Hash
+        + Ord
+        + IntoIterator<Item = Self::GenericArg>;
+    type GenericArg: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type Term: Copy + Debug + Hash + Ord;
+    type Binder<T: TypeVisitable<Self>>: BoundVars<Self> + TypeSuperVisitable<Self>;
+    type BoundVars: IntoIterator<Item = Self::BoundVar>;
+    type BoundVar;
+    type CanonicalVars: Copy + Debug + Hash + Eq + IntoIterator<Item = CanonicalVarInfo<Self>>;
+    type Ty: Copy
+        + DebugWithInfcx<Self>
+        + Hash
+        + Ord
+        + Into<Self::GenericArg>
+        + IntoKind<Kind = TyKind<Self>>
+        + TypeSuperVisitable<Self>
+        + Flags
+        + Ty<Self>;
+    type Tys: Copy + Debug + Hash + Ord + IntoIterator<Item = Self::Ty>;
+    type AliasTy: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type ParamTy: Copy + Debug + Hash + Ord;
+    type BoundTy: Copy + Debug + Hash + Ord;
+    type PlaceholderTy: Copy + Debug + Hash + Ord + PlaceholderLike;
+    type ErrorGuaranteed: Copy + Debug + Hash + Ord;
+    type BoundExistentialPredicates: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type PolyFnSig: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type AllocId: Copy + Debug + Hash + Ord;
+    type Const: Copy
+        + DebugWithInfcx<Self>
+        + Hash
+        + Ord
+        + Into<Self::GenericArg>
+        + IntoKind<Kind = ConstKind<Self>>
+        + ConstTy<Self>
+        + TypeSuperVisitable<Self>
+        + Flags
+        + Const<Self>;
+    type AliasConst: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type PlaceholderConst: Copy + Debug + Hash + Ord + PlaceholderLike;
+    type ParamConst: Copy + Debug + Hash + Ord;
+    type BoundConst: Copy + Debug + Hash + Ord;
+    type ValueConst: Copy + Debug + Hash + Ord;
+    type ExprConst: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type Region: Copy
+        + DebugWithInfcx<Self>
+        + Hash
+        + Ord
+        + Into<Self::GenericArg>
+        + IntoKind<Kind = RegionKind<Self>>
+        + Flags
+        + Region<Self>;
+    type EarlyParamRegion: Copy + Debug + Hash + Ord;
+    type LateParamRegion: Copy + Debug + Hash + Ord;
+    type BoundRegion: Copy + Debug + Hash + Ord;
+    type InferRegion: Copy + DebugWithInfcx<Self> + Hash + Ord;
+    type PlaceholderRegion: Copy + Debug + Hash + Ord + PlaceholderLike;
+    type Predicate: Copy + Debug + Hash + Eq + TypeSuperVisitable<Self> + Flags;
+    type TraitPredicate: Copy + Debug + Hash + Eq;
+    type RegionOutlivesPredicate: Copy + Debug + Hash + Eq;
+    type TypeOutlivesPredicate: Copy + Debug + Hash + Eq;
+    type ProjectionPredicate: Copy + Debug + Hash + Eq;
+    type NormalizesTo: Copy + Debug + Hash + Eq;
+    type SubtypePredicate: Copy + Debug + Hash + Eq;
+    type CoercePredicate: Copy + Debug + Hash + Eq;
+    type ClosureKind: Copy + Debug + Hash + Eq;
+
+    // Required method
+    fn mk_canonical_var_infos(
+        self,
+        infos: &[CanonicalVarInfo<Self>]
+    ) -> Self::CanonicalVars;
+}
+
+pub trait DebugWithInfcx<I: Interner>: Debug {
+    // Required method
+    fn fmt<Infcx: InferCtxtLike<Interner = I>>(
+        this: WithInfcx<'_, Infcx, &Self>,
+        f: &mut Formatter<'_>
+    ) -> std::fmt::Result;
+}
+
+pub trait TypeVisitable<I: Interner>: Debug + Clone {
+    // Required method
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
+}
+
+pub trait BoundVars<I: Interner> {
+    // Required methods
+    fn bound_vars(&self) -> I::BoundVars;
+    fn has_no_bound_vars(&self) -> bool;
+}
+
+pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> {
+    // Required method
+    fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
+}
+
+pub struct CanonicalVarInfo<I: Interner> {
+    pub kind: CanonicalVarKind<I>,
+}
+
+pub struct CanonicalVarKind<I>(std::marker::PhantomData<I>);
+
+pub struct TyKind<I>(std::marker::PhantomData<I>);
+
+pub trait IntoKind {
+    type Kind;
+
+    // Required method
+    fn kind(self) -> Self::Kind;
+}
+pub trait Flags {
+    // Required methods
+    fn flags(&self) -> TypeFlags;
+    fn outer_exclusive_binder(&self) -> DebruijnIndex;
+}
+pub struct TypeFlags;
+
+pub trait Ty<I: Interner<Ty = Self>> {
+    // Required method
+    fn new_anon_bound(
+        interner: I,
+        debruijn: DebruijnIndex,
+        var: BoundVar
+    ) -> Self;
+}
+
+pub trait PlaceholderLike {
+    // Required methods
+    fn universe(self) -> UniverseIndex;
+    fn var(self) -> BoundVar;
+    fn with_updated_universe(self, ui: UniverseIndex) -> Self;
+    fn new(ui: UniverseIndex, var: BoundVar) -> Self;
+}
+
+pub struct UniverseIndex;
+
+pub struct BoundVar;
+
+pub struct ConstKind<I>(std::marker::PhantomData<I>);
+pub trait Const<I: Interner<Const = Self>> {
+    // Required method
+    fn new_anon_bound(
+        interner: I,
+        debruijn: DebruijnIndex,
+        var: BoundVar,
+        ty: I::Ty
+    ) -> Self;
+}
+
+pub trait ConstTy<I: Interner> {
+    // Required method
+    fn ty(self) -> I::Ty;
+}
+
+pub struct DebruijnIndex;
+
+pub struct RegionKind<I>(std::marker::PhantomData<I>);
+pub trait Region<I: Interner<Region = Self>> {
+    // Required method
+    fn new_anon_bound(
+        interner: I,
+        debruijn: DebruijnIndex,
+        var: BoundVar
+    ) -> Self;
+}
+
+pub trait TypeVisitor<I: Interner>: Sized {
+    type Result: VisitorResult = ();
+
+    // Provided methods
+    fn visit_binder<T: TypeVisitable<I>>(
+        &mut self,
+        t: &I::Binder<T>
+    ) -> Self::Result { unimplemented!() }
+    fn visit_ty(&mut self, t: I::Ty) -> Self::Result { unimplemented!() }
+    fn visit_region(&mut self, _r: I::Region) -> Self::Result { unimplemented!() }
+    fn visit_const(&mut self, c: I::Const) -> Self::Result { unimplemented!() }
+    fn visit_predicate(&mut self, p: I::Predicate) -> Self::Result { unimplemented!() }
+}
+
+pub trait VisitorResult {
+    type Residual;
+
+    // Required methods
+    fn output() -> Self;
+    fn from_residual(residual: Self::Residual) -> Self;
+    fn from_branch(b: ControlFlow<Self::Residual>) -> Self;
+    fn branch(self) -> ControlFlow<Self::Residual>;
+}
+
+impl VisitorResult for () {
+    type Residual = ();
+    fn output() -> Self {}
+    fn from_residual(_: Self::Residual) -> Self {}
+    fn from_branch(_: ControlFlow<Self::Residual>) -> Self {}
+    fn branch(self) -> ControlFlow<Self::Residual> { ControlFlow::Continue(()) }
+}
+
+pub struct WithInfcx<'a, Infcx: InferCtxtLike, T> {
+    pub data: T,
+    pub infcx: &'a Infcx,
+}
+
+pub trait InferCtxtLike {
+    type Interner: Interner;
+
+    // Required methods
+    fn interner(&self) -> Self::Interner;
+    fn universe_of_ty(&self, ty: TyVid) -> Option<UniverseIndex>;
+    fn root_ty_var(&self, vid: TyVid) -> TyVid;
+    fn probe_ty_var(
+        &self,
+        vid: TyVid
+    ) -> Option<<Self::Interner as Interner>::Ty>;
+    fn universe_of_lt(
+        &self,
+        lt: <Self::Interner as Interner>::InferRegion
+    ) -> Option<UniverseIndex>;
+    fn opportunistic_resolve_lt_var(
+        &self,
+        vid: <Self::Interner as Interner>::InferRegion
+    ) -> Option<<Self::Interner as Interner>::Region>;
+    fn universe_of_ct(&self, ct: ConstVid) -> Option<UniverseIndex>;
+    fn root_ct_var(&self, vid: ConstVid) -> ConstVid;
+    fn probe_ct_var(
+        &self,
+        vid: ConstVid
+    ) -> Option<<Self::Interner as Interner>::Const>;
+}
+
+pub struct TyVid;
+pub struct ConstVid;
diff --git a/tests/rustdoc-js/looks-like-rustc-interner.js b/tests/rustdoc-js/looks-like-rustc-interner.js
new file mode 100644
index 00000000000..a4806d23499
--- /dev/null
+++ b/tests/rustdoc-js/looks-like-rustc-interner.js
@@ -0,0 +1,9 @@
+// https://github.com/rust-lang/rust/pull/122247
+// exact-check
+
+const EXPECTED = {
+    'query': 'canonicalvarinfo, intoiterator -> intoiterator',
+    'others': [
+        { 'path': 'looks_like_rustc_interner::Interner', 'name': 'mk_canonical_var_infos' },
+    ],
+};
diff --git a/tests/rustdoc-js/looks-like-rustc-interner.rs b/tests/rustdoc-js/looks-like-rustc-interner.rs
new file mode 100644
index 00000000000..f304e28d952
--- /dev/null
+++ b/tests/rustdoc-js/looks-like-rustc-interner.rs
@@ -0,0 +1,5 @@
+//@ aux-crate:interner=interner.rs
+// https://github.com/rust-lang/rust/pull/122247
+extern crate interner;
+#[doc(inline)]
+pub use interner::*;