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

4 files changed, 20 insertions, 17 deletions

diff --git a/src/librustdoc/clean/types.rs b/src/librustdoc/clean/types.rs
index 4132e187c72..49a91240b6a 100644
--- a/src/librustdoc/clean/types.rs
+++ b/src/librustdoc/clean/types.rs
@@ -914,7 +914,7 @@ impl Attributes {
             .collect()
     }
 
-    crate fn get_doc_aliases(&self) -> FxHashSet<String> {
+    crate fn get_doc_aliases(&self) -> Box<[String]> {
         let mut aliases = FxHashSet::default();
 
         for attr in self.other_attrs.lists(sym::doc).filter(|a| a.has_name(sym::alias)) {
@@ -931,7 +931,7 @@ impl Attributes {
                 aliases.insert(attr.value_str().map(|s| s.to_string()).unwrap());
             }
         }
-        aliases
+        aliases.into_iter().collect::<Vec<String>>().into()
     }
 }
 
diff --git a/src/librustdoc/formats/cache.rs b/src/librustdoc/formats/cache.rs
index 01bceb1d910..7100cc87b0c 100644
--- a/src/librustdoc/formats/cache.rs
+++ b/src/librustdoc/formats/cache.rs
@@ -309,15 +309,8 @@ impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
                             parent,
                             parent_idx: None,
                             search_type: get_index_search_type(&item, &self.empty_cache, self.tcx),
+                            aliases: item.attrs.get_doc_aliases(),
                         });
-
-                        for alias in item.attrs.get_doc_aliases() {
-                            self.cache
-                                .aliases
-                                .entry(alias.to_lowercase())
-                                .or_insert(Vec::new())
-                                .push(self.cache.search_index.len() - 1);
-                        }
                     }
                 }
                 (Some(parent), None) if is_inherent_impl_item => {
diff --git a/src/librustdoc/html/render/cache.rs b/src/librustdoc/html/render/cache.rs
index 5d49a494727..022afee3105 100644
--- a/src/librustdoc/html/render/cache.rs
+++ b/src/librustdoc/html/render/cache.rs
@@ -82,19 +82,28 @@ 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;
 
+    // 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.
     let mut lastpath = String::new();
diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs
index 07bd26a4c5e..cb5ca5b5e64 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.