Rollup merge of #119468 - notriddle:notriddle/compression, r=GuillaumeGomez

rustdoc-search: tighter encoding for f index

Depends on https://github.com/rust-lang/rust/pull/119457

Two optimizations for the function signature search:

* Instead of using JSON arrays, like `[1,20]`, it uses VLQ
  hex with no commas, like `[aAd]`.
* This also adds backrefs: if you have more than one function
  with exactly the same signature, it'll not only store it once,
  it'll *decode* it once, and store in the typeIdMap only once.

Based partially on discussions on zulip:
https://rust-lang.zulipchat.com/#narrow/stream/266220-t-rustdoc/topic/search.20index.20size

Performance
-----------

https://notriddle.com/rustdoc-html-demo-8/compression-perf-v2/index.html

### memory/time profiler output (for more details, consult the above link)

<table>
<thead><tr><th>benchmark<th>before<th>after</tr></thead>
<tbody>
<tr><th>arti<td>

```
user: 002.789 s
sys:  000.390 s
wall: 002.096 s
child_RSS_high:     440796 KiB
group_mem_high:     414924 KiB
```

</td><td>

```
user: 002.295 s
sys:  000.278 s
wall: 001.738 s
child_RSS_high:     314588 KiB
group_mem_high:     285220 KiB
```

</td></tr><tr><th>cortex-m<td>

```
user: 000.127 s
sys:  000.030 s
wall: 000.134 s
child_RSS_high:      60264 KiB
group_mem_high:      23824 KiB
```

</td><td>

```
user: 000.136 s
sys:  000.038 s
wall: 000.137 s
child_RSS_high:      59204 KiB
group_mem_high:      22712 KiB
```

</td></tr><tr><th>sqlx<td>

```
user: 000.887 s
sys:  000.118 s
wall: 000.592 s
child_RSS_high:     190408 KiB
group_mem_high:     157804 KiB
```

</td><td>

```
user: 000.798 s
sys:  000.101 s
wall: 000.525 s
child_RSS_high:     159292 KiB
group_mem_high:     126292 KiB
```

</td></tr><tr><th>stm32f4<td>

```
user: 013.884 s
sys:  005.399 s
wall: 013.149 s
child_RSS_high:    1942244 KiB
group_mem_high:    1954916 KiB
```

</td><td>

```
user: 006.128 s
sys:  003.297 s
wall: 007.994 s
child_RSS_high:    1038108 KiB
group_mem_high:    1023900 KiB
```

</td></tr><tr><th>ripgrep<td>

```
user: 000.441 s
sys:  000.063 s
wall: 000.264 s
child_RSS_high:     109180 KiB
group_mem_high:      74272 KiB
```

</td><td>

```
user: 000.408 s
sys:  000.044 s
wall: 000.238 s
child_RSS_high:     101488 KiB
group_mem_high:      66000 KiB
```

</td></tr></tbody></table>

Size change
-----------

standard library without gzip:

```console
$ du -bs search-index-old.js search-index-new.js
4976370 search-index-old.js
4404391 search-index-new.js
```

((4976370-4404391)/4404391)*100% = 12.9%

with gzip:

```console
$ du -hs search-index-old.js.gz search-index-new.js.gz
520K    search-index-old.js.gz
504K    search-index-new.js.gz

$ du -bs search-index-old.js.gz search-index-new.js.gz
522092  search-index-old.js.gz
507654  search-index-new.js.gz
```

((522092-507654)/507654)*100% = 2.8%

Benchmarks are similarly shrunk.

Without gzip:

```console
$ du -hs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.js
10555067        tmp/arti/toolchain_old/doc/search-index.js
8921236 tmp/arti/toolchain_new/doc/search-index.js
77018   tmp/cortex-m/toolchain_old/doc/search-index.js
66676   tmp/cortex-m/toolchain_new/doc/search-index.js
2876330 tmp/sqlx/toolchain_old/doc/search-index.js
2436812 tmp/sqlx/toolchain_new/doc/search-index.js
63632890        tmp/stm32f4/toolchain_old/doc/search-index.js
52337438        tmp/stm32f4/toolchain_new/doc/search-index.js
631150  tmp/ripgrep/toolchain_old/doc/search-index.js
541646  tmp/ripgrep/toolchain_new/doc/search-index.js
```

With gzip:

```console
$ du -bs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.js.gz
1618852 tmp/arti/toolchain_old/doc/search-index.js.gz
1582007 tmp/arti/toolchain_new/doc/search-index.js.gz
16109   tmp/cortex-m/toolchain_old/doc/search-index.js.gz
15831   tmp/cortex-m/toolchain_new/doc/search-index.js.gz
422257  tmp/sqlx/toolchain_old/doc/search-index.js.gz
411507  tmp/sqlx/toolchain_new/doc/search-index.js.gz
4454761 tmp/stm32f4/toolchain_old/doc/search-index.js.gz
4334924 tmp/stm32f4/toolchain_new/doc/search-index.js.gz
98312   tmp/ripgrep/toolchain_old/doc/search-index.js.gz
96864   tmp/ripgrep/toolchain_new/doc/search-index.js.gz

$ du -hs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.j
s.gz
1.6M    tmp/arti/toolchain_old/doc/search-index.js.gz
1.6M    tmp/arti/toolchain_new/doc/search-index.js.gz
24K     tmp/cortex-m/toolchain_old/doc/search-index.js.gz
24K     tmp/cortex-m/toolchain_new/doc/search-index.js.gz
424K    tmp/sqlx/toolchain_old/doc/search-index.js.gz
412K    tmp/sqlx/toolchain_new/doc/search-index.js.gz
4.3M    tmp/stm32f4/toolchain_old/doc/search-index.js.gz
4.2M    tmp/stm32f4/toolchain_new/doc/search-index.js.gz
108K    tmp/ripgrep/toolchain_old/doc/search-index.js.gz
104K    tmp/ripgrep/toolchain_new/doc/search-index.js.gz
```

2 files changed, 128 insertions, 68 deletions

diff --git a/src/librustdoc/html/static/js/externs.js b/src/librustdoc/html/static/js/externs.js
index 93709e4e830..d24148b9556 100644
--- a/src/librustdoc/html/static/js/externs.js
+++ b/src/librustdoc/html/static/js/externs.js
@@ -200,3 +200,59 @@ let FunctionSearchType;
  * }}
  */
 let FunctionType;
+
+/**
+ * The raw search data for a given crate. `n`, `t`, `d`, `i`, and `f`
+ * are arrays with the same length. `q`, `a`, and `c` use a sparse
+ * representation for compactness.
+ *
+ * `n[i]` contains the name of an item.
+ *
+ * `t[i]` contains the type of that item
+ * (as a string of characters that represent an offset in `itemTypes`).
+ *
+ * `d[i]` contains the description of that item.
+ *
+ * `q` contains the full paths of the items. For compactness, it is a set of
+ * (index, path) pairs used to create a map. If a given index `i` is
+ * not present, this indicates "same as the last index present".
+ *
+ * `i[i]` contains an item's parent, usually a module. For compactness,
+ * it is a set of indexes into the `p` array.
+ *
+ * `f` contains function signatures, or `0` if the item isn't a function.
+ * More information on how they're encoded can be found in rustc-dev-guide
+ *
+ * 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.
+ *
+ * b[i] contains an item's impl disambiguator. This is only present if an item
+ * is defined in an impl block and, the impl block's type has more than one associated
+ * item with the same name.
+ *
+ * `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 list of path/type pairs. It is used for parents and function parameters.
+ *
+ * `c` is an array of item indices that are deprecated.
+ * @typedef {{
+ *   doc: string,
+ *   a: Object,
+ *   n: Array<string>,
+ *   t: String,
+ *   d: Array<string>,
+ *   q: Array<[Number, string]>,
+ *   i: Array<Number>,
+ *   f: string,
+ *   p: Array<Object>,
+ *   b: Array<[Number, String]>,
+ *   c: Array<Number>
+ * }}
+ */
+let RawSearchIndexCrate;
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index e6263db3283..e0708485fc0 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -2767,19 +2767,65 @@ ${item.displayPath}<span class="${type}">${name}</span>\
      * The raw function search type format is generated using serde in
      * librustdoc/html/render/mod.rs: impl Serialize for IndexItemFunctionType
      *
-     * @param {RawFunctionSearchType} functionSearchType
+     * @param {{
+     *  string: string,
+     *  offset: number,
+     *  backrefQueue: FunctionSearchType[]
+     * }} itemFunctionDecoder
      * @param {Array<{name: string, ty: number}>} lowercasePaths
      * @param {Map<string, integer>}
      *
      * @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) {
+    function buildFunctionSearchType(itemFunctionDecoder, lowercasePaths) {
+        const c = itemFunctionDecoder.string.charCodeAt(itemFunctionDecoder.offset);
+        itemFunctionDecoder.offset += 1;
+        const [zero, ua, la, ob, cb] = ["0", "@", "`", "{", "}"].map(c => c.charCodeAt(0));
+        // `` ` `` is used as a sentinel because it's fewer bytes than `null`, and decodes to zero
+        // `0` is a backref
+        if (c === la) {
             return null;
         }
+        // sixteen characters after "0" are backref
+        if (c >= zero && c < ua) {
+            return itemFunctionDecoder.backrefQueue[c - zero];
+        }
+        if (c !== ob) {
+            throw ["Unexpected ", c, " in function: expected ", "{", "; this is a bug"];
+        }
+        // call after consuming `{`
+        function decodeList() {
+            let c = itemFunctionDecoder.string.charCodeAt(itemFunctionDecoder.offset);
+            const ret = [];
+            while (c !== cb) {
+                ret.push(decode());
+                c = itemFunctionDecoder.string.charCodeAt(itemFunctionDecoder.offset);
+            }
+            itemFunctionDecoder.offset += 1; // eat cb
+            return ret;
+        }
+        // consumes and returns a list or integer
+        function decode() {
+            let n = 0;
+            let c = itemFunctionDecoder.string.charCodeAt(itemFunctionDecoder.offset);
+            if (c === ob) {
+                itemFunctionDecoder.offset += 1;
+                return decodeList();
+            }
+            while (c < la) {
+                n = (n << 4) | (c & 0xF);
+                itemFunctionDecoder.offset += 1;
+                c = itemFunctionDecoder.string.charCodeAt(itemFunctionDecoder.offset);
+            }
+            // last character >= la
+            n = (n << 4) | (c & 0xF);
+            const [sign, value] = [n & 1, n >> 1];
+            itemFunctionDecoder.offset += 1;
+            return sign ? -value : value;
+        }
+        const functionSearchType = decodeList();
+        const INPUTS_DATA = 0;
+        const OUTPUT_DATA = 1;
         let inputs, output;
         if (typeof functionSearchType[INPUTS_DATA] === "number") {
             inputs = [buildItemSearchType(functionSearchType[INPUTS_DATA], lowercasePaths)];
@@ -2808,9 +2854,14 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                 ? [buildItemSearchType(functionSearchType[i], lowercasePaths)]
                 : buildItemSearchTypeAll(functionSearchType[i], lowercasePaths));
         }
-        return {
+        const ret = {
             inputs, output, where_clause,
         };
+        itemFunctionDecoder.backrefQueue.unshift(ret);
+        if (itemFunctionDecoder.backrefQueue.length > 16) {
+            itemFunctionDecoder.backrefQueue.pop();
+        }
+        return ret;
     }
 
     /**
@@ -2924,6 +2975,11 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         return functionTypeFingerprint[(fullId * 4) + 3];
     }
 
+    /**
+     * Convert raw search index into in-memory search index.
+     *
+     * @param {[string, RawSearchIndexCrate][]} rawSearchIndex
+     */
     function buildIndex(rawSearchIndex) {
         searchIndex = [];
         typeNameIdMap = new Map();
@@ -2950,59 +3006,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         // This loop actually generates the search item indexes, including
         // normalized names, type signature objects and fingerprints, and aliases.
         id = 0;
-        /**
-         * The raw search data for a given crate. `n`, `t`, `d`, `i`, and `f`
-         * are arrays with the same length. `q`, `a`, and `c` use a sparse
-         * representation for compactness.
-         *
-         * `n[i]` contains the name of an item.
-         *
-         * `t[i]` contains the type of that item
-         * (as a string of characters that represent an offset in `itemTypes`).
-         *
-         * `d[i]` contains the description of that item.
-         *
-         * `q` contains the full paths of the items. For compactness, it is a set of
-         * (index, path) pairs used to create a map. If a given index `i` is
-         * not present, this indicates "same as the last index present".
-         *
-         * `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.
-         *
-         * b[i] contains an item's impl disambiguator. This is only present if an item
-         * is defined in an impl block and, the impl block's type has more than one associated
-         * item with the same name.
-         *
-         * `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 list of path/type pairs. It is used for parents and function parameters.
-         *
-         * `c` is an array of item indices that are deprecated.
-         *
-         * @type {{
-         *   doc: string,
-         *   a: Object,
-         *   n: Array<string>,
-         *   t: String,
-         *   d: Array<string>,
-         *   q: Array<[Number, string]>,
-         *   i: Array<Number>,
-         *   f: Array<RawFunctionSearchType>,
-         *   p: Array<Object>,
-         *   b: Array<[Number, String]>,
-         *   c: Array<Number>
-         * }}
-         */
+
         for (const [crate, crateCorpus] of rawSearchIndex) {
             // This object should have exactly the same set of fields as the "row"
             // object defined below. Your JavaScript runtime will thank you.
@@ -3039,8 +3043,12 @@ ${item.displayPath}<span class="${type}">${name}</span>\
             const itemDescs = crateCorpus.d;
             // an array of (Number) the parent path index + 1 to `paths`, or 0 if none
             const itemParentIdxs = crateCorpus.i;
-            // an array of (Object | null) the type of the function, if any
-            const itemFunctionSearchTypes = crateCorpus.f;
+            // a string representing the list of function types
+            const itemFunctionDecoder = {
+                string: crateCorpus.f,
+                offset: 0,
+                backrefQueue: [],
+            };
             // an array of (Number) indices for the deprecated items
             const deprecatedItems = new Set(crateCorpus.c);
             // an array of (Number) indices for the deprecated items
@@ -3088,12 +3096,8 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                     word = itemNames[i].toLowerCase();
                 }
                 const path = itemPaths.has(i) ? itemPaths.get(i) : lastPath;
-                let type = null;
-                if (itemFunctionSearchTypes[i] !== 0) {
-                    type = buildFunctionSearchType(
-                        itemFunctionSearchTypes[i],
-                        lowercasePaths
-                    );
+                const type = buildFunctionSearchType(itemFunctionDecoder, lowercasePaths);
+                if (type !== null) {
                     if (type) {
                         const fp = functionTypeFingerprint.subarray(id * 4, (id + 1) * 4);
                         const fps = new Set();