Rollup merge of #83835 - notriddle:sort-index, r=ollie27

rustdoc: sort search index items for compression

This should not affect the appearance of the docs pages themselves.

This makes the pre-compressed search index smaller, thanks to the
empty-string path duplication format, and also the gzipped version,
by giving the algorithm more structure to work with.

    rust$ wc -c search-index-old.js search-index-new.js
    2628334 search-index-old.js
    2586181 search-index-new.js
    5214515 total
    rust$ gzip search-index-*
    rust$ wc -c search-index-old.js.gz search-index-new.js.gz
    239486 search-index-old.js.gz
    237386 search-index-new.js.gz
    476872 total

2 files changed, 23 insertions, 9 deletions

diff --git a/src/librustdoc/html/render/cache.rs b/src/librustdoc/html/render/cache.rs
index 5d49a494727..2265905dcba 100644
--- a/src/librustdoc/html/render/cache.rs
+++ b/src/librustdoc/html/render/cache.rs
@@ -82,18 +82,31 @@ crate fn build_index<'tcx>(krate: &clean::Crate, cache: &mut Cache, tcx: TyCtxt<
                 parent: Some(did),
                 parent_idx: None,
                 search_type: get_index_search_type(&item, cache, tcx),
+                aliases: item.attrs.get_doc_aliases(),
             });
-            for alias in item.attrs.get_doc_aliases() {
-                cache
-                    .aliases
-                    .entry(alias.to_lowercase())
-                    .or_insert(Vec::new())
-                    .push(cache.search_index.len() - 1);
-            }
         }
     }
 
-    let Cache { ref mut search_index, ref paths, ref mut aliases, .. } = *cache;
+    let Cache { ref mut search_index, ref paths, .. } = *cache;
+
+    // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
+    // we need the alias element to have an array of items.
+    let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
+
+    // Sort search index items. This improves the compressibility of the search index.
+    search_index.sort_unstable_by(|k1, k2| {
+        // `sort_unstable_by_key` produces lifetime errors
+        let k1 = (&k1.path, &k1.name, &k1.ty, &k1.parent);
+        let k2 = (&k2.path, &k2.name, &k2.ty, &k2.parent);
+        std::cmp::Ord::cmp(&k1, &k2)
+    });
+
+    // Set up alias indexes.
+    for (i, item) in search_index.iter().enumerate() {
+        for alias in &item.aliases[..] {
+            aliases.entry(alias.to_lowercase()).or_insert(Vec::new()).push(i);
+        }
+    }
 
     // Reduce `DefId` in paths into smaller sequential numbers,
     // and prune the paths that do not appear in the index.
@@ -201,7 +214,7 @@ crate fn build_index<'tcx>(krate: &clean::Crate, cache: &mut Cache, tcx: TyCtxt<
             doc: crate_doc,
             items: crate_items,
             paths: crate_paths,
-            aliases,
+            aliases: &aliases,
         })
         .expect("failed serde conversion")
         // All these `replace` calls are because we have to go through JS string for JSON content.
diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index bf57e3c37d3..fb433bf8a8d 100644
--- a/src/librustdoc/html/render/mod.rs
+++ b/src/librustdoc/html/render/mod.rs
@@ -164,6 +164,7 @@ crate struct IndexItem {
     crate parent: Option<DefId>,
     crate parent_idx: Option<usize>,
     crate search_type: Option<IndexItemFunctionType>,
+    crate aliases: Box<[String]>,
 }
 
 /// A type used for the search index.