Rollup merge of #118194 - notriddle:notriddle/tuple-unit, r=GuillaumeGomez

rustdoc: search for tuples and unit by type with `()`

This feature extends rustdoc to support the syntax that most users will naturally attempt to use to search for tuples. Part of https://github.com/rust-lang/rust/issues/60485

Function signature searches already support tuples and unit. The explicit name `primitive:tuple` and `primitive:unit` can be used to match a tuple or unit, while `()` will match either one. It also follows the direction set by the actual language for parens as a group, so `(u8,)` will only match a tuple, while `(u8)` will match a plain, unwrapped byte—thanks to loose search semantics, it will also match the tuple.

## Preview

* [`option<t>, option<u> -> (t, u)`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=option%3Ct%3E%2C option%3Cu%3E -%3E (t%2C u)>)
* [`[t] -> (t,)`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=[t] -%3E (t%2C)>)
* [`(ipaddr,) -> socketaddr`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=(ipaddr%2C) -%3E socketaddr>)

## Motivation

When type-based search was first landed, it was directly [described as incomplete][a comment].

[a comment]: https://github.com/rust-lang/rust/pull/23289#issuecomment-79437386

Filling out the missing functionality is going to mean adding support for more of Rust's [type expression] syntax, such as tuples (in this PR), references, raw pointers, function pointers, and closures.

[type expression]: https://doc.rust-lang.org/reference/types.html#type-expressions

There does seem to be demand for this sort of thing, such as [this Discord message](https://discord.com/channels/442252698964721669/443150878111694848/1042145740065099796) expressing regret at rustdoc not supporting tuples in search queries.

## Reference description (from the Rustdoc book)

<table>
<thead>
  <tr>
    <th>Shorthand</th>
    <th>Explicit names</th>
  </tr>
</thead>
<tbody>
  <tr><td colspan="2">Before this PR</td></tr>
  <tr>
    <td><code>[]</code></td>
    <td><code>primitive:slice</code> and/or <code>primitive:array</code></td>
  </tr>
  <tr>
    <td><code>[T]</code></td>
    <td><code>primitive:slice&lt;T&gt;</code> and/or <code>primitive:array&lt;T&gt;</code></td>
  </tr>
  <tr>
    <td><code>!</code></td>
    <td><code>primitive:never</code></td>
  </tr>
  <tr><td colspan="2">After this PR</td></tr>
  <tr>
    <td><code>()</code></td>
    <td><code>primitive:unit</code> and/or <code>primitive:tuple</code></td>
  </tr>
  <tr>
    <td><code>(T)</code></td>
    <td><code>T</code></td>
  </tr>
  <tr>
    <td><code>(T,)</code></td>
    <td><code>primitive:tuple&lt;T&gt;</code></td>
  </tr>
</tbody>
</table>

A single type expression wrapped in parens is the same as that type expression, since parens act as the grouping operator. If they're empty, though, they will match both `unit` and `tuple`, and if there's more than one type (or a trailing or leading comma) it is the same as `primitive:tuple<...>`.

However, since items can be left out of the query, `(T)` will still return 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>`.

## Future direction

The [type expression grammar](https://doc.rust-lang.org/reference/types.html#type-expressions) from the Reference is given below:

<pre><code>Syntax
    Type :
        TypeNoBounds
        | <a href="https://doc.rust-lang.org/reference/types/impl-trait.html">ImplTraitType</a>
        | <a href="https://doc.rust-lang.org/reference/types/trait-object.html">TraitObjectType</a>
<br>
    TypeNoBounds :
        <a href="https://doc.rust-lang.org/reference/types.html#parenthesized-types">ParenthesizedType</a>
        | <a href="https://doc.rust-lang.org/reference/types/impl-trait.html">ImplTraitTypeOneBound</a>
        | <a href="https://doc.rust-lang.org/reference/types/trait-object.html">TraitObjectTypeOneBound</a>
        | <a href="https://doc.rust-lang.org/reference/paths.html#paths-in-types">TypePath</a>
        | <a href="https://doc.rust-lang.org/reference/types/tuple.html#tuple-types">TupleType</a>
        | <a href="https://doc.rust-lang.org/reference/types/never.html">NeverType</a>
        | <a href="https://doc.rust-lang.org/reference/types/pointer.html#raw-pointers-const-and-mut">RawPointerType</a>
        | <a href="https://doc.rust-lang.org/reference/types/pointer.html#shared-references-">ReferenceType</a>
        | <a href="https://doc.rust-lang.org/reference/types/array.html">ArrayType</a>
        | <a href="https://doc.rust-lang.org/reference/types/slice.html">SliceType</a>
        | <a href="https://doc.rust-lang.org/reference/types/inferred.html">InferredType</a>
        | <a href="https://doc.rust-lang.org/reference/paths.html#qualified-paths">QualifiedPathInType</a>
        | <a href="https://doc.rust-lang.org/reference/types/function-pointer.html">BareFunctionType</a>
        | <a href="https://doc.rust-lang.org/reference/macros.html#macro-invocation">MacroInvocation</a>
</code></pre>

ImplTraitType and TraitObjectType (and ImplTraitTypeOneBound and TraitObjectTypeOneBound) are not yet implemented. They would mostly desugar to `trait:`, similarly to how `!` desugars to `primitive:never`.

ParenthesizedType and TuplePath are added in this PR.

TypePath is already implemented (except const generics, which is not planned, and function-like trait syntax, which is planned as part of closure support).

NeverType is already implemented.

RawPointerType and ReferenceType require parsing and fixes to the search index to store this information, but otherwise their behavior seems simple enough. Just like tuples and slices, `&T` would be equivalent to `primitive:reference<T>`, `&mut T` would be equivalent to `primitive:reference<keyword:mut, T>`, `*T` would be equivalent to `primitive:pointer<T>`, `*mut T` would be equivalent to `primitive:pointer<keyword:mut, T>`, and `*const T` would be equivalent to `primitive:pointer<keyword:const, T>`. Lifetime generics support is not planned, because lifetime subtyping seems too complicated.

ArrayType is subsumed by SliceType right now. Implementing const generics is not planned, because it seems like it would require a lot of implementation complexity for not much gain.

InferredType isn't really covered right now. Its semantics in a search context are not obvious.

QualifiedPathInType is not implemented, and it is not planned. I would need a use case to justify it, and act as a guide for what the exact semantics should be.

BareFunctionType is not implemented. Along with function-like trait syntax, which is formally considered a TypePath, it's the biggest missing feature to be able to do structured searches over generic APIs like `Option`.

MacroInvocation is not parsed (macro names are, but they don't mean the same thing here at all). Those are gone by the time Rustdoc sees the source code.

2 files changed, 74 insertions, 29 deletions

diff --git a/src/librustdoc/html/render/search_index.rs b/src/librustdoc/html/render/search_index.rs
index e49df400c83..cb059082f85 100644
--- a/src/librustdoc/html/render/search_index.rs
+++ b/src/librustdoc/html/render/search_index.rs
@@ -566,6 +566,9 @@ fn get_index_type_id(
         // The type parameters are converted to generics in `simplify_fn_type`
         clean::Slice(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Slice)),
         clean::Array(_, _) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Array)),
+        clean::Tuple(ref n) if n.is_empty() => {
+            Some(RenderTypeId::Primitive(clean::PrimitiveType::Unit))
+        }
         clean::Tuple(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Tuple)),
         clean::QPath(ref data) => {
             if data.self_type.is_self_type()
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index e0708485fc0..a5e2bc1c7af 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -260,6 +260,18 @@ function initSearch(rawSearchIndex) {
      * Special type name IDs for searching by both array and slice (`[]` syntax).
      */
     let typeNameIdOfArrayOrSlice;
+    /**
+     * Special type name IDs for searching by tuple.
+     */
+    let typeNameIdOfTuple;
+    /**
+     * Special type name IDs for searching by unit.
+     */
+    let typeNameIdOfUnit;
+    /**
+     * Special type name IDs for searching by both tuple and unit (`()` syntax).
+     */
+    let typeNameIdOfTupleOrUnit;
 
     /**
      * Add an item to the type Name->ID map, or, if one already exists, use it.
@@ -295,11 +307,7 @@ function initSearch(rawSearchIndex) {
     }
 
     function isEndCharacter(c) {
-        return "=,>-]".indexOf(c) !== -1;
-    }
-
-    function isErrorCharacter(c) {
-        return "()".indexOf(c) !== -1;
+        return "=,>-])".indexOf(c) !== -1;
     }
 
     function itemTypeFromName(typename) {
@@ -585,8 +593,6 @@ function initSearch(rawSearchIndex) {
                         throw ["Unexpected ", "!", ": it can only be at the end of an ident"];
                     }
                     foundExclamation = parserState.pos;
-                } else if (isErrorCharacter(c)) {
-                    throw ["Unexpected ", c];
                 } else if (isPathSeparator(c)) {
                     if (c === ":") {
                         if (!isPathStart(parserState)) {
@@ -616,11 +622,14 @@ function initSearch(rawSearchIndex) {
                     }
                 } else if (
                     c === "[" ||
+                    c === "(" ||
                     isEndCharacter(c) ||
                     isSpecialStartCharacter(c) ||
                     isSeparatorCharacter(c)
                 ) {
                     break;
+                } else if (parserState.pos > 0) {
+                    throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1]];
                 } else {
                     throw ["Unexpected ", c];
                 }
@@ -661,15 +670,24 @@ function initSearch(rawSearchIndex) {
         skipWhitespace(parserState);
         let start = parserState.pos;
         let end;
-        if (parserState.userQuery[parserState.pos] === "[") {
+        if ("[(".indexOf(parserState.userQuery[parserState.pos]) !== -1) {
+let endChar = ")";
+let name = "()";
+let friendlyName = "tuple";
+
+if (parserState.userQuery[parserState.pos] === "[") {
+    endChar = "]";
+    name = "[]";
+    friendlyName = "slice";
+}
             parserState.pos += 1;
-            getItemsBefore(query, parserState, generics, "]");
+            const { foundSeparator } = getItemsBefore(query, parserState, generics, endChar);
             const typeFilter = parserState.typeFilter;
             const isInBinding = parserState.isInBinding;
             if (typeFilter !== null && typeFilter !== "primitive") {
                 throw [
                     "Invalid search type: primitive ",
-                    "[]",
+                    name,
                     " and ",
                     typeFilter,
                     " both specified",
@@ -677,27 +695,31 @@ function initSearch(rawSearchIndex) {
             }
             parserState.typeFilter = null;
             parserState.isInBinding = null;
-            parserState.totalElems += 1;
-            if (isInGenerics) {
-                parserState.genericsElems += 1;
-            }
             for (const gen of generics) {
                 if (gen.bindingName !== null) {
-                    throw ["Type parameter ", "=", " cannot be within slice ", "[]"];
+                    throw ["Type parameter ", "=", ` cannot be within ${friendlyName} `, name];
                 }
             }
-            elems.push({
-                name: "[]",
-                id: null,
-                fullPath: ["[]"],
-                pathWithoutLast: [],
-                pathLast: "[]",
-                normalizedPathLast: "[]",
-                generics,
-                typeFilter: "primitive",
-                bindingName: isInBinding,
-                bindings: new Map(),
-            });
+            if (name === "()" && !foundSeparator && generics.length === 1 && typeFilter === null) {
+                elems.push(generics[0]);
+            } else {
+                parserState.totalElems += 1;
+                if (isInGenerics) {
+                    parserState.genericsElems += 1;
+                }
+                elems.push({
+                    name: name,
+                    id: null,
+                    fullPath: [name],
+                    pathWithoutLast: [],
+                    pathLast: name,
+                    normalizedPathLast: name,
+                    generics,
+                    bindings: new Map(),
+                    typeFilter: "primitive",
+                    bindingName: isInBinding,
+                });
+            }
         } else {
             const isStringElem = parserState.userQuery[start] === "\"";
             // We handle the strings on their own mostly to make code easier to follow.
@@ -770,9 +792,11 @@ function initSearch(rawSearchIndex) {
      * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added.
      * @param {string} endChar            - This function will stop when it'll encounter this
      *                                      character.
+     * @returns {{foundSeparator: bool}}
      */
     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.
@@ -786,6 +810,8 @@ function initSearch(rawSearchIndex) {
             extra = "<";
         } else if (endChar === "]") {
             extra = "[";
+        } else if (endChar === ")") {
+            extra = "(";
         } else if (endChar === "") {
             extra = "->";
         } else {
@@ -802,6 +828,7 @@ function initSearch(rawSearchIndex) {
             } else if (isSeparatorCharacter(c)) {
                 parserState.pos += 1;
                 foundStopChar = true;
+                foundSeparator = true;
                 continue;
             } else if (c === ":" && isPathStart(parserState)) {
                 throw ["Unexpected ", "::", ": paths cannot start with ", "::"];
@@ -879,6 +906,8 @@ function initSearch(rawSearchIndex) {
 
         parserState.typeFilter = oldTypeFilter;
         parserState.isInBinding = oldIsInBinding;
+
+        return { foundSeparator };
     }
 
     /**
@@ -926,6 +955,8 @@ function initSearch(rawSearchIndex) {
                         break;
                     }
                     throw ["Unexpected ", c, " (did you mean ", "->", "?)"];
+                } else if (parserState.pos > 0) {
+                    throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1]];
                 }
                 throw ["Unexpected ", c];
             } else if (c === ":" && !isPathStart(parserState)) {
@@ -1599,6 +1630,11 @@ function initSearch(rawSearchIndex) {
                 ) {
                     // [] matches primitive:array or primitive:slice
                     // if it matches, then we're fine, and this is an appropriate match candidate
+                } else if (queryElem.id === typeNameIdOfTupleOrUnit &&
+                    (fnType.id === typeNameIdOfTuple || fnType.id === typeNameIdOfUnit)
+                ) {
+                    // () matches primitive:tuple or primitive:unit
+                    // if it matches, then we're fine, and this is an appropriate match candidate
                 } else if (fnType.id !== queryElem.id || queryElem.id === null) {
                     return false;
                 }
@@ -1792,7 +1828,7 @@ function initSearch(rawSearchIndex) {
                 if (row.id > 0 && elem.id > 0 && elem.pathWithoutLast.length === 0 &&
                     typePassesFilter(elem.typeFilter, row.ty) && elem.generics.length === 0 &&
                     // special case
-                    elem.id !== typeNameIdOfArrayOrSlice
+                    elem.id !== typeNameIdOfArrayOrSlice && elem.id !== typeNameIdOfTupleOrUnit
                 ) {
                     return row.id === elem.id || checkIfInList(
                         row.generics,
@@ -2886,12 +2922,15 @@ ${item.displayPath}<span class="${type}">${name}</span>\
      */
     function buildFunctionTypeFingerprint(type, output, fps) {
         let input = type.id;
-        // All forms of `[]` get collapsed down to one thing in the bloom filter.
+        // All forms of `[]`/`()` get collapsed down to one thing in the bloom filter.
         // Differentiating between arrays and slices, if the user asks for it, is
         // still done in the matching algorithm.
         if (input === typeNameIdOfArray || input === typeNameIdOfSlice) {
             input = typeNameIdOfArrayOrSlice;
         }
+        if (input === typeNameIdOfTuple || input === typeNameIdOfUnit) {
+            input = typeNameIdOfTupleOrUnit;
+        }
         // http://burtleburtle.net/bob/hash/integer.html
         // ~~ is toInt32. It's used before adding, so
         // the number stays in safe integer range.
@@ -2991,7 +3030,10 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         // that can be searched using `[]` syntax.
         typeNameIdOfArray = buildTypeMapIndex("array");
         typeNameIdOfSlice = buildTypeMapIndex("slice");
+        typeNameIdOfTuple = buildTypeMapIndex("tuple");
+        typeNameIdOfUnit = buildTypeMapIndex("unit");
         typeNameIdOfArrayOrSlice = buildTypeMapIndex("[]");
+        typeNameIdOfTupleOrUnit = buildTypeMapIndex("()");
 
         // Function type fingerprints are 128-bit bloom filters that are used to
         // estimate the distance between function and query.