rustdoc-search: add search query syntax `Fn(T) -> U`

This is implemented, in addition to the ML-style one,
because Rust does it. If we don't, we'll never hear the end of it.

This commit also refactors some duplicate parts of the parser
into a dedicated function.

2 files changed, 95 insertions, 64 deletions

diff --git a/src/doc/rustdoc/src/read-documentation/search.md b/src/doc/rustdoc/src/read-documentation/search.md
index d17e41bcde7..e2def14b357 100644
--- a/src/doc/rustdoc/src/read-documentation/search.md
+++ b/src/doc/rustdoc/src/read-documentation/search.md
@@ -153,16 +153,26 @@ will match these queries:
 
 But it *does not* match `Result<Vec, u8>` or `Result<u8<Vec>>`.
 
+To search for a function that accepts a function as a parameter,
+like `Iterator::all`, wrap the nested signature in parenthesis,
+as in [`Iterator<T>, (T -> bool) -> bool`][iterator-all].
+You can also search for a specific closure trait,
+such as `Iterator<T>, (FnMut(T) -> bool) -> bool`,
+but you need to know which one you want.
+
+[iterator-all]: ../../std/vec/struct.Vec.html?search=Iterator<T>%2C+(T+->+bool)+->+bool&filter-crate=std
+
 ### Primitives with Special Syntax
 
-| Shorthand | Explicit names                                   |
-| --------- | ------------------------------------------------ |
-| `[]`      | `primitive:slice` and/or `primitive:array`       |
-| `[T]`     | `primitive:slice<T>` and/or `primitive:array<T>` |
-| `()`      | `primitive:unit` and/or `primitive:tuple`        |
-| `(T)`     | `T`                                              |
-| `(T,)`    | `primitive:tuple<T>`                             |
-| `!`       | `primitive:never`                                |
+| Shorthand        | Explicit names                                    |
+| ---------------- | ------------------------------------------------- |
+| `[]`             | `primitive:slice` and/or `primitive:array`        |
+| `[T]`            | `primitive:slice<T>` and/or `primitive:array<T>`  |
+| `()`             | `primitive:unit` and/or `primitive:tuple`         |
+| `(T)`            | `T`                                               |
+| `(T,)`           | `primitive:tuple<T>`                              |
+| `!`              | `primitive:never`                                 |
+| `(T, U -> V, W)` | `fn(T, U) -> (V, W)`, `Fn`, `FnMut`, and `FnOnce` |
 
 When searching for `[]`, Rustdoc will return search results with either slices
 or arrays. If you know which one you want, you can force it to return results
@@ -182,6 +192,10 @@ results for types that match tuples, even though it also matches the type on
 its own. That is, `(u32)` matches `(u32,)` for the exact same reason that it
 also matches `Result<u32, Error>`.
 
+The `->` operator has lower precedence than comma. If it's not wrapped
+in brackets, it delimits the return value for the function being searched for.
+To search for functions that take functions as parameters, use parenthesis.
+
 ### Limitations and quirks of type-based search
 
 Type-based search is still a buggy, experimental, work-in-progress feature.
@@ -220,9 +234,6 @@ Most of these limitations should be addressed in future version of Rustdoc.
 
   * Searching for lifetimes is not supported.
 
-  * It's impossible to search for closures based on their parameters or
-    return values.
-
   * It's impossible to search based on the length of an array.
 
 ## Item filtering
@@ -239,19 +250,21 @@ Item filters can be used in both name-based and type signature-based searches.
 
 ```text
 ident = *(ALPHA / DIGIT / "_")
-path = ident *(DOUBLE-COLON ident) [!]
+path = ident *(DOUBLE-COLON ident) [BANG]
 slice-like = OPEN-SQUARE-BRACKET [ nonempty-arg-list ] CLOSE-SQUARE-BRACKET
 tuple-like = OPEN-PAREN [ nonempty-arg-list ] CLOSE-PAREN
-arg = [type-filter *WS COLON *WS] (path [generics] / slice-like / tuple-like / [!])
+arg = [type-filter *WS COLON *WS] (path [generics] / slice-like / tuple-like)
 type-sep = COMMA/WS *(COMMA/WS)
-nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep)
+nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep) [ return-args ]
 generic-arg-list = *(type-sep) arg [ EQUAL arg ] *(type-sep arg [ EQUAL arg ]) *(type-sep)
-generics = OPEN-ANGLE-BRACKET [ generic-arg-list ] *(type-sep)
+normal-generics = OPEN-ANGLE-BRACKET [ generic-arg-list ] *(type-sep)
             CLOSE-ANGLE-BRACKET
+fn-like-generics = OPEN-PAREN [ nonempty-arg-list ] CLOSE-PAREN [ RETURN-ARROW arg ]
+generics = normal-generics / fn-like-generics
 return-args = RETURN-ARROW *(type-sep) nonempty-arg-list
 
 exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ]
-type-search = [ nonempty-arg-list ] [ return-args ]
+type-search = [ nonempty-arg-list ]
 
 query = *WS (exact-search / type-search) *WS
 
@@ -296,6 +309,7 @@ QUOTE = %x22
 COMMA = ","
 RETURN-ARROW = "->"
 EQUAL = "="
+BANG = "!"
 
 ALPHA = %x41-5A / %x61-7A ; A-Z / a-z
 DIGIT = %x30-39
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index 6c285ba6f51..73ac5608479 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 */
 
@@ -578,7 +579,10 @@ function initSearch(rawSearchIndex) {
                 // Syntactically, bindings are parsed as generics,
                 // but the query engine treats them differently.
                 if (gen.bindingName !== null) {
-                    bindings.set(gen.bindingName.name, [gen, ...gen.bindingName.generics]);
+                    if (gen.name !== null) {
+                        gen.bindingName.generics.unshift(gen);
+                    }
+                    bindings.set(gen.bindingName.name, gen.bindingName.generics);
                     return false;
                 }
                 return true;
@@ -678,6 +682,38 @@ function initSearch(rawSearchIndex) {
         return end;
     }
 
+    function getFilteredNextElem(query, parserState, elems, isInGenerics) {
+        const start = parserState.pos;
+        if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) {
+            throw ["Expected type filter before ", ":"];
+        }
+        getNextElem(query, parserState, elems, isInGenerics);
+        if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) {
+            if (parserState.typeFilter !== null) {
+                throw [
+                    "Unexpected ",
+                    ":",
+                    " (expected path after type filter ",
+                    parserState.typeFilter + ":",
+                    ")",
+                ];
+            }
+            if (elems.length === 0) {
+                throw ["Expected type filter before ", ":"];
+            } else if (query.literalSearch) {
+                throw ["Cannot use quotes on type filter"];
+            }
+            // The type filter doesn't count as an element since it's a modifier.
+            const typeFilterElem = elems.pop();
+            checkExtraTypeFilterCharacters(start, parserState);
+            parserState.typeFilter = typeFilterElem.name;
+            parserState.pos += 1;
+            parserState.totalElems -= 1;
+            query.literalSearch = false;
+            getNextElem(query, parserState, elems, isInGenerics);
+        }
+    }
+
     /**
      * @param {ParsedQuery} query
      * @param {ParserState} parserState
@@ -752,6 +788,32 @@ function initSearch(rawSearchIndex) {
                 }
                 parserState.pos += 1;
                 getItemsBefore(query, parserState, generics, ">");
+            } else if (parserState.pos < parserState.length &&
+                parserState.userQuery[parserState.pos] === "("
+            ) {
+                if (start >= end) {
+                    throw ["Found generics without a path"];
+                }
+                if (parserState.isInBinding) {
+                    throw ["Unexpected ", "(", " after ", "="];
+                }
+                parserState.pos += 1;
+                const typeFilter = parserState.typeFilter;
+                parserState.typeFilter = null;
+                getItemsBefore(query, parserState, generics, ")");
+                skipWhitespace(parserState);
+                if (isReturnArrow(parserState)) {
+                    parserState.pos += 2;
+                    skipWhitespace(parserState);
+                    getFilteredNextElem(query, parserState, generics, isInGenerics);
+                    generics[generics.length - 1].bindingName = makePrimitiveElement("output");
+                } else {
+                    generics.push(makePrimitiveElement(null, {
+                        bindingName: makePrimitiveElement("output"),
+                        typeFilter: null,
+                    }));
+                }
+                parserState.typeFilter = typeFilter;
             }
             if (isStringElem) {
                 skipWhitespace(parserState);
@@ -811,7 +873,6 @@ function initSearch(rawSearchIndex) {
     function getItemsBefore(query, parserState, elems, endChar) {
         let foundStopChar = true;
         let foundSeparator = false;
-        let start = parserState.pos;
 
         // If this is a generic, keep the outer item's type filter around.
         const oldTypeFilter = parserState.typeFilter;
@@ -874,24 +935,6 @@ function initSearch(rawSearchIndex) {
                 continue;
             } else if (c === ":" && isPathStart(parserState)) {
                 throw ["Unexpected ", "::", ": paths cannot start with ", "::"];
-            }  else if (c === ":") {
-                if (parserState.typeFilter !== null) {
-                    throw ["Unexpected ", ":"];
-                }
-                if (elems.length === 0) {
-                    throw ["Expected type filter before ", ":"];
-                } else if (query.literalSearch) {
-                    throw ["Cannot use quotes on type filter"];
-                }
-                // The type filter doesn't count as an element since it's a modifier.
-                const typeFilterElem = elems.pop();
-                checkExtraTypeFilterCharacters(start, parserState);
-                parserState.typeFilter = typeFilterElem.name;
-                parserState.pos += 1;
-                parserState.totalElems -= 1;
-                query.literalSearch = false;
-                foundStopChar = true;
-                continue;
             } else if (isEndCharacter(c)) {
                 throw ["Unexpected ", c, " after ", extra];
             }
@@ -926,8 +969,7 @@ function initSearch(rawSearchIndex) {
                 ];
             }
             const posBefore = parserState.pos;
-            start = parserState.pos;
-            getNextElem(query, parserState, elems, endChar !== "");
+            getFilteredNextElem(query, parserState, elems, endChar !== "");
             if (endChar !== "" && parserState.pos >= parserState.length) {
                 throw ["Unclosed ", extra];
             }
@@ -1004,7 +1046,6 @@ function initSearch(rawSearchIndex) {
      */
     function parseInput(query, parserState) {
         let foundStopChar = true;
-        let start = parserState.pos;
 
         while (parserState.pos < parserState.length) {
             const c = parserState.userQuery[parserState.pos];
@@ -1022,29 +1063,6 @@ function initSearch(rawSearchIndex) {
                     throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1]];
                 }
                 throw ["Unexpected ", c];
-            } else if (c === ":" && !isPathStart(parserState)) {
-                if (parserState.typeFilter !== null) {
-                    throw [
-                        "Unexpected ",
-                        ":",
-                        " (expected path after type filter ",
-                        parserState.typeFilter + ":",
-                        ")",
-                    ];
-                } else if (query.elems.length === 0) {
-                    throw ["Expected type filter before ", ":"];
-                } else if (query.literalSearch) {
-                    throw ["Cannot use quotes on type filter"];
-                }
-                // The type filter doesn't count as an element since it's a modifier.
-                const typeFilterElem = query.elems.pop();
-                checkExtraTypeFilterCharacters(start, parserState);
-                parserState.typeFilter = typeFilterElem.name;
-                parserState.pos += 1;
-                parserState.totalElems -= 1;
-                query.literalSearch = false;
-                foundStopChar = true;
-                continue;
             } else if (c === " ") {
                 skipWhitespace(parserState);
                 continue;
@@ -1080,8 +1098,7 @@ function initSearch(rawSearchIndex) {
                 ];
             }
             const before = query.elems.length;
-            start = parserState.pos;
-            getNextElem(query, parserState, query.elems, false);
+            getFilteredNextElem(query, parserState, query.elems, false);
             if (query.elems.length === before) {
                 // Nothing was added, weird... Let's increase the position to not remain stuck.
                 parserState.pos += 1;