Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

6 files changed, 542 insertions, 440 deletions

diff --git a/src/librustdoc/html/static/js/externs.js b/src/librustdoc/html/static/js/externs.js
index ecbe15a59..4c81a0979 100644
--- a/src/librustdoc/html/static/js/externs.js
+++ b/src/librustdoc/html/static/js/externs.js
@@ -66,6 +66,11 @@ let Row;
 let ResultsTable;
 
 /**
+ * @typedef {Map<String, ResultObject>}
+ */
+let Results;
+
+/**
  * @typedef {{
  *     desc: string,
  *     displayPath: string,
@@ -80,7 +85,7 @@ let ResultsTable;
  *     ty: number,
  * }}
  */
-let Results;
+let ResultObject;
 
 /**
  * A pair of [inputs, outputs], or 0 for null. This is stored in the search index.
diff --git a/src/librustdoc/html/static/js/main.js b/src/librustdoc/html/static/js/main.js
index 5e8c0e8d1..6f5987e68 100644
--- a/src/librustdoc/html/static/js/main.js
+++ b/src/librustdoc/html/static/js/main.js
@@ -1,20 +1,9 @@
 // Local js definitions:
 /* global addClass, getSettingValue, hasClass, searchState */
-/* global onEach, onEachLazy, removeClass */
+/* global onEach, onEachLazy, removeClass, getVar */
 
 "use strict";
 
-// Get a value from the rustdoc-vars div, which is used to convey data from
-// Rust to the JS. If there is no such element, return null.
-function getVar(name) {
-    const el = document.getElementById("rustdoc-vars");
-    if (el) {
-        return el.attributes["data-" + name].value;
-    } else {
-        return null;
-    }
-}
-
 // Given a basename (e.g. "storage") and an extension (e.g. ".js"), return a URL
 // for a resource under the root-path, with the resource-suffix.
 function resourcePath(basename, extension) {
@@ -187,6 +176,15 @@ function loadCss(cssUrl) {
     document.getElementsByTagName("head")[0].appendChild(link);
 }
 
+function preLoadCss(cssUrl) {
+    // https://developer.mozilla.org/en-US/docs/Web/HTML/Link_types/preload
+    const link = document.createElement("link");
+    link.href = cssUrl;
+    link.rel = "preload";
+    link.as = "style";
+    document.getElementsByTagName("head")[0].appendChild(link);
+}
+
 (function() {
     const isHelpPage = window.location.pathname.endsWith("/help.html");
 
@@ -207,6 +205,23 @@ function loadCss(cssUrl) {
         // hopefully be loaded when the JS will generate the settings content.
         loadCss(getVar("static-root-path") + getVar("settings-css"));
         loadScript(getVar("static-root-path") + getVar("settings-js"));
+        preLoadCss(getVar("static-root-path") + getVar("theme-light-css"));
+        preLoadCss(getVar("static-root-path") + getVar("theme-dark-css"));
+        preLoadCss(getVar("static-root-path") + getVar("theme-ayu-css"));
+        // Pre-load all theme CSS files, so that switching feels seamless.
+        //
+        // When loading settings.html as a standalone page, the equivalent HTML is
+        // generated in context.rs.
+        setTimeout(() => {
+            const themes = getVar("themes").split(",");
+            for (const theme of themes) {
+                // if there are no themes, do nothing
+                // "".split(",") == [""]
+                if (theme !== "") {
+                    preLoadCss(getVar("root-path") + theme + ".css");
+                }
+            }
+        }, 0);
     };
 
     window.searchState = {
@@ -311,16 +326,6 @@ function loadCss(cssUrl) {
         },
     };
 
-    function getPageId() {
-        if (window.location.hash) {
-            const tmp = window.location.hash.replace(/^#/, "");
-            if (tmp.length > 0) {
-                return tmp;
-            }
-        }
-        return null;
-    }
-
     const toggleAllDocsId = "toggle-all-docs";
     let savedHash = "";
 
@@ -341,12 +346,12 @@ function loadCss(cssUrl) {
             }
         }
         // This part is used in case an element is not visible.
-        if (savedHash !== window.location.hash) {
-            savedHash = window.location.hash;
-            if (savedHash.length === 0) {
-                return;
+        const pageId = window.location.hash.replace(/^#/, "");
+        if (savedHash !== pageId) {
+            savedHash = pageId;
+            if (pageId !== "") {
+                expandSection(pageId);
             }
-            expandSection(savedHash.slice(1)); // we remove the '#'
         }
     }
 
@@ -685,11 +690,6 @@ function loadCss(cssUrl) {
             }
 
         });
-
-        const pageId = getPageId();
-        if (pageId !== null) {
-            expandSection(pageId);
-        }
     }());
 
     window.rustdoc_add_line_numbers_to_examples = () => {
@@ -725,65 +725,18 @@ function loadCss(cssUrl) {
         window.rustdoc_add_line_numbers_to_examples();
     }
 
-    let oldSidebarScrollPosition = null;
-
-    // Scroll locking used both here and in source-script.js
-
-    window.rustdocMobileScrollLock = function() {
-        const mobile_topbar = document.querySelector(".mobile-topbar");
-        if (window.innerWidth <= window.RUSTDOC_MOBILE_BREAKPOINT) {
-            // This is to keep the scroll position on mobile.
-            oldSidebarScrollPosition = window.scrollY;
-            document.body.style.width = `${document.body.offsetWidth}px`;
-            document.body.style.position = "fixed";
-            document.body.style.top = `-${oldSidebarScrollPosition}px`;
-            if (mobile_topbar) {
-                mobile_topbar.style.top = `${oldSidebarScrollPosition}px`;
-                mobile_topbar.style.position = "relative";
-            }
-        } else {
-            oldSidebarScrollPosition = null;
-        }
-    };
-
-    window.rustdocMobileScrollUnlock = function() {
-        const mobile_topbar = document.querySelector(".mobile-topbar");
-        if (oldSidebarScrollPosition !== null) {
-            // This is to keep the scroll position on mobile.
-            document.body.style.width = "";
-            document.body.style.position = "";
-            document.body.style.top = "";
-            if (mobile_topbar) {
-                mobile_topbar.style.top = "";
-                mobile_topbar.style.position = "";
-            }
-            // The scroll position is lost when resetting the style, hence why we store it in
-            // `oldSidebarScrollPosition`.
-            window.scrollTo(0, oldSidebarScrollPosition);
-            oldSidebarScrollPosition = null;
-        }
-    };
-
     function showSidebar() {
         window.hideAllModals(false);
-        window.rustdocMobileScrollLock();
         const sidebar = document.getElementsByClassName("sidebar")[0];
         addClass(sidebar, "shown");
     }
 
     function hideSidebar() {
-        window.rustdocMobileScrollUnlock();
         const sidebar = document.getElementsByClassName("sidebar")[0];
         removeClass(sidebar, "shown");
     }
 
     window.addEventListener("resize", () => {
-        if (window.innerWidth > window.RUSTDOC_MOBILE_BREAKPOINT &&
-            oldSidebarScrollPosition !== null) {
-            // If the user opens the sidebar in "mobile" mode, and then grows the browser window,
-            // we need to switch away from mobile mode and make the main content area scrollable.
-            hideSidebar();
-        }
         if (window.CURRENT_TOOLTIP_ELEMENT) {
             // As a workaround to the behavior of `contains: layout` used in doc togglers,
             // tooltip popovers are positioned using javascript.
@@ -996,9 +949,7 @@ function loadCss(cssUrl) {
              <code>enum</code>, <code>trait</code>, <code>type</code>, <code>macro</code>, \
              and <code>const</code>.",
             "Search functions by type signature (e.g., <code>vec -&gt; usize</code> or \
-             <code>-&gt; vec</code>)",
-            "Search multiple things at once by splitting your query with comma (e.g., \
-             <code>str,u8</code> or <code>String,struct:Vec,test</code>)",
+             <code>-&gt; vec</code> or <code>String, enum:Cow -&gt; bool</code>)",
             "You can look for items with an exact name by putting double quotes around \
              your request: <code>\"string\"</code>",
             "Look for items inside another one by searching for a path: <code>vec::Vec</code>",
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index b98bced41..929dae81c 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -76,39 +76,111 @@ function printTab(nb) {
 }
 
 /**
- * A function to compute the Levenshtein distance between two strings
- * Licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported
- * Full License can be found at http://creativecommons.org/licenses/by-sa/3.0/legalcode
- * This code is an unmodified version of the code written by Marco de Wit
- * and was found at https://stackoverflow.com/a/18514751/745719
+ * The [edit distance] is a metric for measuring the difference between two strings.
+ *
+ * [edit distance]: https://en.wikipedia.org/wiki/Edit_distance
  */
-const levenshtein_row2 = [];
-function levenshtein(s1, s2) {
-    if (s1 === s2) {
-        return 0;
-    }
-    const s1_len = s1.length, s2_len = s2.length;
-    if (s1_len && s2_len) {
-        let i1 = 0, i2 = 0, a, b, c, c2;
-        const row = levenshtein_row2;
-        while (i1 < s1_len) {
-            row[i1] = ++i1;
-        }
-        while (i2 < s2_len) {
-            c2 = s2.charCodeAt(i2);
-            a = i2;
-            ++i2;
-            b = i2;
-            for (i1 = 0; i1 < s1_len; ++i1) {
-                c = a + (s1.charCodeAt(i1) !== c2 ? 1 : 0);
-                a = row[i1];
-                b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
-                row[i1] = b;
-            }
-        }
-        return b;
-    }
-    return s1_len + s2_len;
+
+/*
+ * This function was translated, mostly line-for-line, from
+ * https://github.com/rust-lang/rust/blob/ff4b772f805ec1e/compiler/rustc_span/src/edit_distance.rs
+ *
+ * The current implementation is the restricted Damerau-Levenshtein algorithm. It is restricted
+ * because it does not permit modifying characters that have already been transposed. The specific
+ * algorithm should not matter to the caller of the methods, which is why it is not noted in the
+ * documentation.
+ */
+const editDistanceState = {
+    current: [],
+    prev: [],
+    prevPrev: [],
+    calculate: function calculate(a, b, limit) {
+        // Ensure that `b` is the shorter string, minimizing memory use.
+        if (a.length < b.length) {
+            const aTmp = a;
+            a = b;
+            b = aTmp;
+        }
+
+        const minDist = a.length - b.length;
+        // If we know the limit will be exceeded, we can return early.
+        if (minDist > limit) {
+            return limit + 1;
+        }
+
+        // Strip common prefix.
+        // We know that `b` is the shorter string, so we don't need to check
+        // `a.length`.
+        while (b.length > 0 && b[0] === a[0]) {
+            a = a.substring(1);
+            b = b.substring(1);
+        }
+        // Strip common suffix.
+        while (b.length > 0 && b[b.length - 1] === a[a.length - 1]) {
+            a = a.substring(0, a.length - 1);
+            b = b.substring(0, b.length - 1);
+        }
+
+        // If either string is empty, the distance is the length of the other.
+        // We know that `b` is the shorter string, so we don't need to check `a`.
+        if (b.length === 0) {
+            return minDist;
+        }
+
+        const aLength = a.length;
+        const bLength = b.length;
+
+        for (let i = 0; i <= bLength; ++i) {
+            this.current[i] = 0;
+            this.prev[i] = i;
+            this.prevPrev[i] = Number.MAX_VALUE;
+        }
+
+        // row by row
+        for (let i = 1; i <= aLength; ++i) {
+            this.current[0] = i;
+            const aIdx = i - 1;
+
+            // column by column
+            for (let j = 1; j <= bLength; ++j) {
+                const bIdx = j - 1;
+
+                // There is no cost to substitute a character with itself.
+                const substitutionCost = a[aIdx] === b[bIdx] ? 0 : 1;
+
+                this.current[j] = Math.min(
+                    // deletion
+                    this.prev[j] + 1,
+                    // insertion
+                    this.current[j - 1] + 1,
+                    // substitution
+                    this.prev[j - 1] + substitutionCost
+                );
+
+                if ((i > 1) && (j > 1) && (a[aIdx] === b[bIdx - 1]) && (a[aIdx - 1] === b[bIdx])) {
+                    // transposition
+                    this.current[j] = Math.min(
+                        this.current[j],
+                        this.prevPrev[j - 2] + 1
+                    );
+                }
+            }
+
+            // Rotate the buffers, reusing the memory
+            const prevPrevTmp = this.prevPrev;
+            this.prevPrev = this.prev;
+            this.prev = this.current;
+            this.current = prevPrevTmp;
+        }
+
+        // `prev` because we already rotated the buffers.
+        const distance = this.prev[bLength];
+        return distance <= limit ? distance : (limit + 1);
+    },
+};
+
+function editDistance(a, b, limit) {
+    return editDistanceState.calculate(a, b, limit);
 }
 
 function initSearch(rawSearchIndex) {
@@ -119,7 +191,7 @@ function initSearch(rawSearchIndex) {
      */
     let searchIndex;
     let currentResults;
-    const ALIASES = Object.create(null);
+    const ALIASES = new Map();
 
     function isWhitespace(c) {
         return " \t\n\r".indexOf(c) !== -1;
@@ -282,12 +354,15 @@ function initSearch(rawSearchIndex) {
         if (isInGenerics) {
             parserState.genericsElems += 1;
         }
+        const typeFilter = parserState.typeFilter;
+        parserState.typeFilter = null;
         return {
             name: name,
             fullPath: pathSegments,
             pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1),
             pathLast: pathSegments[pathSegments.length - 1],
             generics: generics,
+            typeFilter,
         };
     }
 
@@ -386,9 +461,7 @@ function initSearch(rawSearchIndex) {
         if (parserState.pos < parserState.length &&
             parserState.userQuery[parserState.pos] === "<"
         ) {
-            if (isInGenerics) {
-                throw ["Unexpected ", "<", " after ", "<"];
-            } else if (start >= end) {
+            if (start >= end) {
                 throw ["Found generics without a path"];
             }
             parserState.pos += 1;
@@ -423,6 +496,11 @@ function initSearch(rawSearchIndex) {
      */
     function getItemsBefore(query, parserState, elems, endChar) {
         let foundStopChar = true;
+        let start = parserState.pos;
+
+        // If this is a generic, keep the outer item's type filter around.
+        const oldTypeFilter = parserState.typeFilter;
+        parserState.typeFilter = null;
 
         while (parserState.pos < parserState.length) {
             const c = parserState.userQuery[parserState.pos];
@@ -434,7 +512,25 @@ function initSearch(rawSearchIndex) {
                 continue;
             } else if (c === ":" && isPathStart(parserState)) {
                 throw ["Unexpected ", "::", ": paths cannot start with ", "::"];
-            } else if (c === ":" || isEndCharacter(c)) {
+            }  else if (c === ":") {
+                if (parserState.typeFilter !== null) {
+                    throw ["Unexpected ", ":"];
+                }
+                if (elems.length === 0) {
+                    throw ["Expected type filter before ", ":"];
+                } else if (query.literalSearch) {
+                    throw ["You 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)) {
                 let extra = "";
                 if (endChar === ">") {
                     extra = "<";
@@ -468,15 +564,10 @@ function initSearch(rawSearchIndex) {
                 ];
             }
             const posBefore = parserState.pos;
+            start = parserState.pos;
             getNextElem(query, parserState, elems, endChar === ">");
-            if (endChar !== "") {
-                if (parserState.pos >= parserState.length) {
-                    throw ["Unclosed ", "<"];
-                }
-                const c2 = parserState.userQuery[parserState.pos];
-                if (!isSeparatorCharacter(c2) && c2 !== endChar) {
-                    throw ["Expected ", endChar, ", found ", c2];
-                }
+            if (endChar !== "" && parserState.pos >= parserState.length) {
+                throw ["Unclosed ", "<"];
             }
             // This case can be encountered if `getNextElem` encountered a "stop character" right
             // from the start. For example if you have `,,` or `<>`. In this case, we simply move up
@@ -492,6 +583,8 @@ function initSearch(rawSearchIndex) {
         // We are either at the end of the string or on the `endChar` character, let's move forward
         // in any case.
         parserState.pos += 1;
+
+        parserState.typeFilter = oldTypeFilter;
     }
 
     /**
@@ -500,10 +593,10 @@ function initSearch(rawSearchIndex) {
      *
      * @param {ParserState} parserState
      */
-    function checkExtraTypeFilterCharacters(parserState) {
+    function checkExtraTypeFilterCharacters(start, parserState) {
         const query = parserState.userQuery;
 
-        for (let pos = 0; pos < parserState.pos; ++pos) {
+        for (let pos = start; pos < parserState.pos; ++pos) {
             if (!isIdentCharacter(query[pos]) && !isWhitespaceCharacter(query[pos])) {
                 throw ["Unexpected ", query[pos], " in type filter"];
             }
@@ -519,6 +612,7 @@ 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];
@@ -540,16 +634,15 @@ function initSearch(rawSearchIndex) {
                 }
                 if (query.elems.length === 0) {
                     throw ["Expected type filter before ", ":"];
-                } else if (query.elems.length !== 1 || parserState.totalElems !== 1) {
-                    throw ["Unexpected ", ":"];
                 } else if (query.literalSearch) {
                     throw ["You cannot use quotes on type filter"];
                 }
-                checkExtraTypeFilterCharacters(parserState);
                 // The type filter doesn't count as an element since it's a modifier.
-                parserState.typeFilter = query.elems.pop().name;
+                const typeFilterElem = query.elems.pop();
+                checkExtraTypeFilterCharacters(start, parserState);
+                parserState.typeFilter = typeFilterElem.name;
                 parserState.pos += 1;
-                parserState.totalElems = 0;
+                parserState.totalElems -= 1;
                 query.literalSearch = false;
                 foundStopChar = true;
                 continue;
@@ -581,6 +674,7 @@ function initSearch(rawSearchIndex) {
                 ];
             }
             const before = query.elems.length;
+            start = parserState.pos;
             getNextElem(query, parserState, query.elems, false);
             if (query.elems.length === before) {
                 // Nothing was added, weird... Let's increase the position to not remain stuck.
@@ -588,6 +682,9 @@ function initSearch(rawSearchIndex) {
             }
             foundStopChar = false;
         }
+        if (parserState.typeFilter !== null) {
+            throw ["Unexpected ", ":", " (expected path after type filter)"];
+        }
         while (parserState.pos < parserState.length) {
             if (isReturnArrow(parserState)) {
                 parserState.pos += 2;
@@ -615,7 +712,6 @@ function initSearch(rawSearchIndex) {
         return {
             original: userQuery,
             userQuery: userQuery.toLowerCase(),
-            typeFilter: NO_TYPE_FILTER,
             elems: [],
             returned: [],
             // Total number of "top" elements (does not include generics).
@@ -666,18 +762,15 @@ function initSearch(rawSearchIndex) {
      *
      * ident = *(ALPHA / DIGIT / "_")
      * path = ident *(DOUBLE-COLON ident) [!]
-     * arg = path [generics]
-     * arg-without-generic = path
+     * arg = [type-filter *WS COLON *WS] path [generics]
      * type-sep = COMMA/WS *(COMMA/WS)
      * nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep)
-     * nonempty-arg-list-without-generics = *(type-sep) arg-without-generic
-     *                                      *(type-sep arg-without-generic) *(type-sep)
-     * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list-without-generics ] *(type-sep)
-     *            CLOSE-ANGLE-BRACKET/EOF
+     * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list ] *(type-sep)
+     *            CLOSE-ANGLE-BRACKET
      * return-args = RETURN-ARROW *(type-sep) nonempty-arg-list
      *
      * exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ]
-     * type-search = [type-filter *WS COLON] [ nonempty-arg-list ] [ return-args ]
+     * type-search = [ nonempty-arg-list ] [ return-args ]
      *
      * query = *WS (exact-search / type-search) *WS
      *
@@ -726,6 +819,20 @@ function initSearch(rawSearchIndex) {
      * @return {ParsedQuery}    - The parsed query
      */
     function parseQuery(userQuery) {
+        function convertTypeFilterOnElem(elem) {
+            if (elem.typeFilter !== null) {
+                let typeFilter = elem.typeFilter;
+                if (typeFilter === "const") {
+                    typeFilter = "constant";
+                }
+                elem.typeFilter = itemTypeFromName(typeFilter);
+            } else {
+                elem.typeFilter = NO_TYPE_FILTER;
+            }
+            for (const elem2 of elem.generics) {
+                convertTypeFilterOnElem(elem2);
+            }
+        }
         userQuery = userQuery.trim();
         const parserState = {
             length: userQuery.length,
@@ -740,17 +847,15 @@ function initSearch(rawSearchIndex) {
 
         try {
             parseInput(query, parserState);
-            if (parserState.typeFilter !== null) {
-                let typeFilter = parserState.typeFilter;
-                if (typeFilter === "const") {
-                    typeFilter = "constant";
-                }
-                query.typeFilter = itemTypeFromName(typeFilter);
+            for (const elem of query.elems) {
+                convertTypeFilterOnElem(elem);
+            }
+            for (const elem of query.returned) {
+                convertTypeFilterOnElem(elem);
             }
         } catch (err) {
             query = newParsedQuery(userQuery);
             query.error = err;
-            query.typeFilter = -1;
             return query;
         }
 
@@ -793,26 +898,34 @@ function initSearch(rawSearchIndex) {
      * @return {ResultsTable}
      */
     function execQuery(parsedQuery, searchWords, filterCrates, currentCrate) {
-        const results_others = {}, results_in_args = {}, results_returned = {};
+        const results_others = new Map(), results_in_args = new Map(),
+            results_returned = new Map();
 
+        /**
+         * Add extra data to result objects, and filter items that have been
+         * marked for removal.
+         *
+         * @param {[ResultObject]} results
+         * @returns {[ResultObject]}
+         */
         function transformResults(results) {
-            const duplicates = {};
+            const duplicates = new Set();
             const out = [];
 
             for (const result of results) {
                 if (result.id > -1) {
                     const obj = searchIndex[result.id];
-                    obj.lev = result.lev;
+                    obj.dist = result.dist;
                     const res = buildHrefAndPath(obj);
                     obj.displayPath = pathSplitter(res[0]);
                     obj.fullPath = obj.displayPath + obj.name;
                     // To be sure than it some items aren't considered as duplicate.
                     obj.fullPath += "|" + obj.ty;
 
-                    if (duplicates[obj.fullPath]) {
+                    if (duplicates.has(obj.fullPath)) {
                         continue;
                     }
-                    duplicates[obj.fullPath] = true;
+                    duplicates.add(obj.fullPath);
 
                     obj.href = res[1];
                     out.push(obj);
@@ -824,24 +937,30 @@ function initSearch(rawSearchIndex) {
             return out;
         }
 
+        /**
+         * This function takes a result map, and sorts it by various criteria, including edit
+         * distance, substring match, and the crate it comes from.
+         *
+         * @param {Results} results
+         * @param {boolean} isType
+         * @param {string} preferredCrate
+         * @returns {[ResultObject]}
+         */
         function sortResults(results, isType, preferredCrate) {
-            const userQuery = parsedQuery.userQuery;
-            const ar = [];
-            for (const entry in results) {
-                if (hasOwnPropertyRustdoc(results, entry)) {
-                    const result = results[entry];
-                    result.word = searchWords[result.id];
-                    result.item = searchIndex[result.id] || {};
-                    ar.push(result);
-                }
-            }
-            results = ar;
             // if there are no results then return to default and fail
-            if (results.length === 0) {
+            if (results.size === 0) {
                 return [];
             }
 
-            results.sort((aaa, bbb) => {
+            const userQuery = parsedQuery.userQuery;
+            const result_list = [];
+            for (const result of results.values()) {
+                result.word = searchWords[result.id];
+                result.item = searchIndex[result.id] || {};
+                result_list.push(result);
+            }
+
+            result_list.sort((aaa, bbb) => {
                 let a, b;
 
                 // sort by exact match with regard to the last word (mismatch goes later)
@@ -860,8 +979,8 @@ function initSearch(rawSearchIndex) {
 
                 // Sort by distance in the path part, if specified
                 // (less changes required to match means higher rankings)
-                a = aaa.path_lev;
-                b = bbb.path_lev;
+                a = aaa.path_dist;
+                b = bbb.path_dist;
                 if (a !== b) {
                     return a - b;
                 }
@@ -875,8 +994,15 @@ function initSearch(rawSearchIndex) {
 
                 // Sort by distance in the name part, the last part of the path
                 // (less changes required to match means higher rankings)
-                a = (aaa.lev);
-                b = (bbb.lev);
+                a = (aaa.dist);
+                b = (bbb.dist);
+                if (a !== b) {
+                    return a - b;
+                }
+
+                // sort deprecated items later
+                a = aaa.item.deprecated;
+                b = bbb.item.deprecated;
                 if (a !== b) {
                     return a - b;
                 }
@@ -943,7 +1069,7 @@ function initSearch(rawSearchIndex) {
                 nameSplit = hasPath ? null : parsedQuery.elems[0].path;
             }
 
-            for (const result of results) {
+            for (const result of result_list) {
                 // this validation does not make sense when searching by types
                 if (result.dontValidate) {
                     continue;
@@ -956,72 +1082,87 @@ function initSearch(rawSearchIndex) {
                     result.id = -1;
                 }
             }
-            return transformResults(results);
+            return transformResults(result_list);
         }
 
         /**
          * This function checks if the object (`row`) generics match the given type (`elem`)
-         * generics. If there are no generics on `row`, `defaultLev` is returned.
+         * generics. If there are no generics on `row`, `defaultDistance` is returned.
          *
-         * @param {Row} row            - The object to check.
-         * @param {QueryElement} elem  - The element from the parsed query.
-         * @param {integer} defaultLev - This is the value to return in case there are no generics.
+         * @param {Row} row                 - The object to check.
+         * @param {QueryElement} elem       - The element from the parsed query.
+         * @param {integer} defaultDistance - This is the value to return in case there are no
+         *                                    generics.
          *
-         * @return {integer}           - Returns the best match (if any) or `maxLevDistance + 1`.
+         * @return {integer}           - Returns the best match (if any) or `maxEditDistance + 1`.
          */
-        function checkGenerics(row, elem, defaultLev, maxLevDistance) {
+        function checkGenerics(row, elem, defaultDistance, maxEditDistance) {
             if (row.generics.length === 0) {
-                return elem.generics.length === 0 ? defaultLev : maxLevDistance + 1;
+                return elem.generics.length === 0 ? defaultDistance : maxEditDistance + 1;
             } else if (row.generics.length > 0 && row.generics[0].name === null) {
-                return checkGenerics(row.generics[0], elem, defaultLev, maxLevDistance);
+                return checkGenerics(row.generics[0], elem, defaultDistance, maxEditDistance);
             }
             // The names match, but we need to be sure that all generics kinda
             // match as well.
-            let elem_name;
             if (elem.generics.length > 0 && row.generics.length >= elem.generics.length) {
-                const elems = Object.create(null);
+                const elems = new Map();
                 for (const entry of row.generics) {
-                    elem_name = entry.name;
-                    if (elem_name === "") {
+                    if (entry.name === "") {
                         // Pure generic, needs to check into it.
-                        if (checkGenerics(entry, elem, maxLevDistance + 1, maxLevDistance) !== 0) {
-                            return maxLevDistance + 1;
+                        if (checkGenerics(entry, elem, maxEditDistance + 1, maxEditDistance)
+                            !== 0) {
+                            return maxEditDistance + 1;
                         }
                         continue;
                     }
-                    if (elems[elem_name] === undefined) {
-                        elems[elem_name] = 0;
+                    let currentEntryElems;
+                    if (elems.has(entry.name)) {
+                        currentEntryElems = elems.get(entry.name);
+                    } else {
+                        currentEntryElems = [];
+                        elems.set(entry.name, currentEntryElems);
                     }
-                    elems[elem_name] += 1;
+                    currentEntryElems.push(entry);
                 }
                 // We need to find the type that matches the most to remove it in order
                 // to move forward.
-                for (const generic of elem.generics) {
-                    let match = null;
-                    if (elems[generic.name]) {
-                        match = generic.name;
-                    } else {
-                        for (elem_name in elems) {
-                            if (!hasOwnPropertyRustdoc(elems, elem_name)) {
-                                continue;
-                            }
-                            if (elem_name === generic) {
-                                match = elem_name;
-                                break;
-                            }
+                const handleGeneric = generic => {
+                    if (!elems.has(generic.name)) {
+                        return false;
+                    }
+                    const matchElems = elems.get(generic.name);
+                    const matchIdx = matchElems.findIndex(tmp_elem => {
+                        if (checkGenerics(tmp_elem, generic, 0, maxEditDistance) !== 0) {
+                            return false;
                         }
+                        return typePassesFilter(generic.typeFilter, tmp_elem.ty);
+                    });
+                    if (matchIdx === -1) {
+                        return false;
+                    }
+                    matchElems.splice(matchIdx, 1);
+                    if (matchElems.length === 0) {
+                        elems.delete(generic.name);
                     }
-                    if (match === null) {
-                        return maxLevDistance + 1;
+                    return true;
+                };
+                // To do the right thing with type filters, we first process generics
+                // that have them, removing matching ones from the "bag," then do the
+                // ones with no type filter, which can match any entry regardless of its
+                // own type.
+                for (const generic of elem.generics) {
+                    if (generic.typeFilter !== -1 && !handleGeneric(generic)) {
+                        return maxEditDistance + 1;
                     }
-                    elems[match] -= 1;
-                    if (elems[match] === 0) {
-                        delete elems[match];
+                }
+                for (const generic of elem.generics) {
+                    if (generic.typeFilter === -1 && !handleGeneric(generic)) {
+                        return maxEditDistance + 1;
                     }
                 }
                 return 0;
             }
-            return maxLevDistance + 1;
+            return maxEditDistance + 1;
         }
 
         /**
@@ -1031,17 +1172,17 @@ function initSearch(rawSearchIndex) {
           * @param {Row} row
           * @param {QueryElement} elem    - The element from the parsed query.
           *
-          * @return {integer} - Returns a Levenshtein distance to the best match.
+          * @return {integer} - Returns an edit distance to the best match.
           */
-        function checkIfInGenerics(row, elem, maxLevDistance) {
-            let lev = maxLevDistance + 1;
+        function checkIfInGenerics(row, elem, maxEditDistance) {
+            let dist = maxEditDistance + 1;
             for (const entry of row.generics) {
-                lev = Math.min(checkType(entry, elem, true, maxLevDistance), lev);
-                if (lev === 0) {
+                dist = Math.min(checkType(entry, elem, true, maxEditDistance), dist);
+                if (dist === 0) {
                     break;
                 }
             }
-            return lev;
+            return dist;
         }
 
         /**
@@ -1052,67 +1193,73 @@ function initSearch(rawSearchIndex) {
           * @param {QueryElement} elem      - The element from the parsed query.
           * @param {boolean} literalSearch
           *
-          * @return {integer} - Returns a Levenshtein distance to the best match. If there is
-          *                     no match, returns `maxLevDistance + 1`.
+          * @return {integer} - Returns an edit distance to the best match. If there is
+          *                     no match, returns `maxEditDistance + 1`.
           */
-        function checkType(row, elem, literalSearch, maxLevDistance) {
+        function checkType(row, elem, literalSearch, maxEditDistance) {
             if (row.name === null) {
                 // This is a pure "generic" search, no need to run other checks.
                 if (row.generics.length > 0) {
-                    return checkIfInGenerics(row, elem, maxLevDistance);
+                    return checkIfInGenerics(row, elem, maxEditDistance);
                 }
-                return maxLevDistance + 1;
+                return maxEditDistance + 1;
             }
 
-            let lev = levenshtein(row.name, elem.name);
+            let dist;
+            if (typePassesFilter(elem.typeFilter, row.ty)) {
+                dist = editDistance(row.name, elem.name, maxEditDistance);
+            } else {
+                dist = maxEditDistance + 1;
+            }
             if (literalSearch) {
-                if (lev !== 0) {
+                if (dist !== 0) {
                     // The name didn't match, let's try to check if the generics do.
                     if (elem.generics.length === 0) {
                         const checkGeneric = row.generics.length > 0;
                         if (checkGeneric && row.generics
-                            .findIndex(tmp_elem => tmp_elem.name === elem.name) !== -1) {
+                            .findIndex(tmp_elem => tmp_elem.name === elem.name &&
+                                typePassesFilter(elem.typeFilter, tmp_elem.ty)) !== -1) {
                             return 0;
                         }
                     }
-                    return maxLevDistance + 1;
+                    return maxEditDistance + 1;
                 } else if (elem.generics.length > 0) {
-                    return checkGenerics(row, elem, maxLevDistance + 1, maxLevDistance);
+                    return checkGenerics(row, elem, maxEditDistance + 1, maxEditDistance);
                 }
                 return 0;
             } else if (row.generics.length > 0) {
                 if (elem.generics.length === 0) {
-                    if (lev === 0) {
+                    if (dist === 0) {
                         return 0;
                     }
                     // The name didn't match so we now check if the type we're looking for is inside
                     // the generics!
-                    lev = Math.min(lev, checkIfInGenerics(row, elem, maxLevDistance));
-                    return lev;
-                } else if (lev > maxLevDistance) {
+                    dist = Math.min(dist, checkIfInGenerics(row, elem, maxEditDistance));
+                    return dist;
+                } else if (dist > maxEditDistance) {
                     // So our item's name doesn't match at all and has generics.
                     //
                     // Maybe it's present in a sub generic? For example "f<A<B<C>>>()", if we're
                     // looking for "B<C>", we'll need to go down.
-                    return checkIfInGenerics(row, elem, maxLevDistance);
+                    return checkIfInGenerics(row, elem, maxEditDistance);
                 } else {
                     // At this point, the name kinda match and we have generics to check, so
                     // let's go!
-                    const tmp_lev = checkGenerics(row, elem, lev, maxLevDistance);
-                    if (tmp_lev > maxLevDistance) {
-                        return maxLevDistance + 1;
+                    const tmp_dist = checkGenerics(row, elem, dist, maxEditDistance);
+                    if (tmp_dist > maxEditDistance) {
+                        return maxEditDistance + 1;
                     }
                     // We compute the median value of both checks and return it.
-                    return (tmp_lev + lev) / 2;
+                    return (tmp_dist + dist) / 2;
                 }
             } else if (elem.generics.length > 0) {
                 // In this case, we were expecting generics but there isn't so we simply reject this
                 // one.
-                return maxLevDistance + 1;
+                return maxEditDistance + 1;
             }
             // No generics on our query or on the target type so we can return without doing
             // anything else.
-            return lev;
+            return dist;
         }
 
         /**
@@ -1120,29 +1267,42 @@ function initSearch(rawSearchIndex) {
          *
          * @param {Row} row
          * @param {QueryElement} elem    - The element from the parsed query.
-         * @param {integer} typeFilter
+         * @param {integer} maxEditDistance
+         * @param {Array<integer>} skipPositions - Do not return one of these positions.
          *
-         * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
-         *                      match, returns `maxLevDistance + 1`.
+         * @return {dist: integer, position: integer} - Returns an edit distance to the best match.
+         *                                              If there is no match, returns
+         *                                              `maxEditDistance + 1` and position: -1.
          */
-        function findArg(row, elem, typeFilter, maxLevDistance) {
-            let lev = maxLevDistance + 1;
+        function findArg(row, elem, maxEditDistance, skipPositions) {
+            let dist = maxEditDistance + 1;
+            let position = -1;
 
             if (row && row.type && row.type.inputs && row.type.inputs.length > 0) {
+                let i = 0;
                 for (const input of row.type.inputs) {
-                    if (!typePassesFilter(typeFilter, input.ty)) {
+                    if (skipPositions.indexOf(i) !== -1) {
+                        i += 1;
                         continue;
                     }
-                    lev = Math.min(
-                        lev,
-                        checkType(input, elem, parsedQuery.literalSearch, maxLevDistance)
+                    const typeDist = checkType(
+                        input,
+                        elem,
+                        parsedQuery.literalSearch,
+                        maxEditDistance
                     );
-                    if (lev === 0) {
-                        return 0;
+                    if (typeDist === 0) {
+                        return {dist: 0, position: i};
                     }
+                    if (typeDist < dist) {
+                        dist = typeDist;
+                        position = i;
+                    }
+                    i += 1;
                 }
             }
-            return parsedQuery.literalSearch ? maxLevDistance + 1 : lev;
+            dist = parsedQuery.literalSearch ? maxEditDistance + 1 : dist;
+            return {dist, position};
         }
 
         /**
@@ -1150,37 +1310,50 @@ function initSearch(rawSearchIndex) {
          *
          * @param {Row} row
          * @param {QueryElement} elem   - The element from the parsed query.
-         * @param {integer} typeFilter
+         * @param {integer} maxEditDistance
+         * @param {Array<integer>} skipPositions - Do not return one of these positions.
          *
-         * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
-         *                      match, returns `maxLevDistance + 1`.
+         * @return {dist: integer, position: integer} - Returns an edit distance to the best match.
+         *                                              If there is no match, returns
+         *                                              `maxEditDistance + 1` and position: -1.
          */
-        function checkReturned(row, elem, typeFilter, maxLevDistance) {
-            let lev = maxLevDistance + 1;
+        function checkReturned(row, elem, maxEditDistance, skipPositions) {
+            let dist = maxEditDistance + 1;
+            let position = -1;
 
             if (row && row.type && row.type.output.length > 0) {
                 const ret = row.type.output;
+                let i = 0;
                 for (const ret_ty of ret) {
-                    if (!typePassesFilter(typeFilter, ret_ty.ty)) {
+                    if (skipPositions.indexOf(i) !== -1) {
+                        i += 1;
                         continue;
                     }
-                    lev = Math.min(
-                        lev,
-                        checkType(ret_ty, elem, parsedQuery.literalSearch, maxLevDistance)
+                    const typeDist = checkType(
+                        ret_ty,
+                        elem,
+                        parsedQuery.literalSearch,
+                        maxEditDistance
                     );
-                    if (lev === 0) {
-                        return 0;
+                    if (typeDist === 0) {
+                        return {dist: 0, position: i};
                     }
+                    if (typeDist < dist) {
+                        dist = typeDist;
+                        position = i;
+                    }
+                    i += 1;
                 }
             }
-            return parsedQuery.literalSearch ? maxLevDistance + 1 : lev;
+            dist = parsedQuery.literalSearch ? maxEditDistance + 1 : dist;
+            return {dist, position};
         }
 
-        function checkPath(contains, ty, maxLevDistance) {
+        function checkPath(contains, ty, maxEditDistance) {
             if (contains.length === 0) {
                 return 0;
             }
-            let ret_lev = maxLevDistance + 1;
+            let ret_dist = maxEditDistance + 1;
             const path = ty.path.split("::");
 
             if (ty.parent && ty.parent.name) {
@@ -1190,27 +1363,27 @@ function initSearch(rawSearchIndex) {
             const length = path.length;
             const clength = contains.length;
             if (clength > length) {
-                return maxLevDistance + 1;
+                return maxEditDistance + 1;
             }
             for (let i = 0; i < length; ++i) {
                 if (i + clength > length) {
                     break;
                 }
-                let lev_total = 0;
+                let dist_total = 0;
                 let aborted = false;
                 for (let x = 0; x < clength; ++x) {
-                    const lev = levenshtein(path[i + x], contains[x]);
-                    if (lev > maxLevDistance) {
+                    const dist = editDistance(path[i + x], contains[x], maxEditDistance);
+                    if (dist > maxEditDistance) {
                         aborted = true;
                         break;
                     }
-                    lev_total += lev;
+                    dist_total += dist;
                 }
                 if (!aborted) {
-                    ret_lev = Math.min(ret_lev, Math.round(lev_total / clength));
+                    ret_dist = Math.min(ret_dist, Math.round(dist_total / clength));
                 }
             }
-            return ret_lev;
+            return ret_dist;
         }
 
         function typePassesFilter(filter, type) {
@@ -1244,6 +1417,7 @@ function initSearch(rawSearchIndex) {
                 parent: item.parent,
                 type: item.type,
                 is_alias: true,
+                deprecated: item.deprecated,
             };
         }
 
@@ -1254,22 +1428,22 @@ function initSearch(rawSearchIndex) {
             const aliases = [];
             const crateAliases = [];
             if (filterCrates !== null) {
-                if (ALIASES[filterCrates] && ALIASES[filterCrates][lowerQuery]) {
-                    const query_aliases = ALIASES[filterCrates][lowerQuery];
+                if (ALIASES.has(filterCrates) && ALIASES.get(filterCrates).has(lowerQuery)) {
+                    const query_aliases = ALIASES.get(filterCrates).get(lowerQuery);
                     for (const alias of query_aliases) {
                         aliases.push(createAliasFromItem(searchIndex[alias]));
                     }
                 }
             } else {
-                Object.keys(ALIASES).forEach(crate => {
-                    if (ALIASES[crate][lowerQuery]) {
+                for (const [crate, crateAliasesIndex] of ALIASES) {
+                    if (crateAliasesIndex.has(lowerQuery)) {
                         const pushTo = crate === currentCrate ? crateAliases : aliases;
-                        const query_aliases = ALIASES[crate][lowerQuery];
+                        const query_aliases = crateAliasesIndex.get(lowerQuery);
                         for (const alias of query_aliases) {
                             pushTo.push(createAliasFromItem(searchIndex[alias]));
                         }
                     }
-                });
+                }
             }
 
             const sortFunc = (aaa, bbb) => {
@@ -1304,41 +1478,41 @@ function initSearch(rawSearchIndex) {
          * This function adds the given result into the provided `results` map if it matches the
          * following condition:
          *
-         * * If it is a "literal search" (`parsedQuery.literalSearch`), then `lev` must be 0.
-         * * If it is not a "literal search", `lev` must be <= `maxLevDistance`.
+         * * If it is a "literal search" (`parsedQuery.literalSearch`), then `dist` must be 0.
+         * * If it is not a "literal search", `dist` must be <= `maxEditDistance`.
          *
          * The `results` map contains information which will be used to sort the search results:
          *
          * * `fullId` is a `string`` used as the key of the object we use for the `results` map.
          * * `id` is the index in both `searchWords` and `searchIndex` arrays for this element.
          * * `index` is an `integer`` used to sort by the position of the word in the item's name.
-         * * `lev` is the main metric used to sort the search results.
-         * * `path_lev` is zero if a single-component search query is used, otherwise it's the
+         * * `dist` is the main metric used to sort the search results.
+         * * `path_dist` is zero if a single-component search query is used, otherwise it's the
          *   distance computed for everything other than the last path component.
          *
          * @param {Results} results
          * @param {string} fullId
          * @param {integer} id
          * @param {integer} index
-         * @param {integer} lev
-         * @param {integer} path_lev
+         * @param {integer} dist
+         * @param {integer} path_dist
          */
-        function addIntoResults(results, fullId, id, index, lev, path_lev, maxLevDistance) {
-            const inBounds = lev <= maxLevDistance || index !== -1;
-            if (lev === 0 || (!parsedQuery.literalSearch && inBounds)) {
-                if (results[fullId] !== undefined) {
-                    const result = results[fullId];
-                    if (result.dontValidate || result.lev <= lev) {
+        function addIntoResults(results, fullId, id, index, dist, path_dist, maxEditDistance) {
+            const inBounds = dist <= maxEditDistance || index !== -1;
+            if (dist === 0 || (!parsedQuery.literalSearch && inBounds)) {
+                if (results.has(fullId)) {
+                    const result = results.get(fullId);
+                    if (result.dontValidate || result.dist <= dist) {
                         return;
                     }
                 }
-                results[fullId] = {
+                results.set(fullId, {
                     id: id,
                     index: index,
                     dontValidate: parsedQuery.literalSearch,
-                    lev: lev,
-                    path_lev: path_lev,
-                };
+                    dist: dist,
+                    path_dist: path_dist,
+                });
             }
         }
 
@@ -1346,7 +1520,7 @@ function initSearch(rawSearchIndex) {
          * This function is called in case the query is only one element (with or without generics).
          * This element will be compared to arguments' and returned values' items and also to items.
          *
-         * Other important thing to note: since there is only one element, we use levenshtein
+         * Other important thing to note: since there is only one element, we use edit
          * distance for name comparisons.
          *
          * @param {Row} row
@@ -1364,24 +1538,24 @@ function initSearch(rawSearchIndex) {
             results_others,
             results_in_args,
             results_returned,
-            maxLevDistance
+            maxEditDistance
         ) {
             if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
                 return;
             }
-            let lev, index = -1, path_lev = 0;
+            let dist, index = -1, path_dist = 0;
             const fullId = row.id;
             const searchWord = searchWords[pos];
 
-            const in_args = findArg(row, elem, parsedQuery.typeFilter, maxLevDistance);
-            const returned = checkReturned(row, elem, parsedQuery.typeFilter, maxLevDistance);
+            const in_args = findArg(row, elem, maxEditDistance, []);
+            const returned = checkReturned(row, elem, maxEditDistance, []);
 
-            // path_lev is 0 because no parent path information is currently stored
+            // path_dist is 0 because no parent path information is currently stored
             // in the search index
-            addIntoResults(results_in_args, fullId, pos, -1, in_args, 0, maxLevDistance);
-            addIntoResults(results_returned, fullId, pos, -1, returned, 0, maxLevDistance);
+            addIntoResults(results_in_args, fullId, pos, -1, in_args.dist, 0, maxEditDistance);
+            addIntoResults(results_returned, fullId, pos, -1, returned.dist, 0, maxEditDistance);
 
-            if (!typePassesFilter(parsedQuery.typeFilter, row.ty)) {
+            if (!typePassesFilter(elem.typeFilter, row.ty)) {
                 return;
             }
 
@@ -1403,34 +1577,34 @@ function initSearch(rawSearchIndex) {
             // No need to check anything else if it's a "pure" generics search.
             if (elem.name.length === 0) {
                 if (row.type !== null) {
-                    lev = checkGenerics(row.type, elem, maxLevDistance + 1, maxLevDistance);
-                    // path_lev is 0 because we know it's empty
-                    addIntoResults(results_others, fullId, pos, index, lev, 0, maxLevDistance);
+                    dist = checkGenerics(row.type, elem, maxEditDistance + 1, maxEditDistance);
+                    // path_dist is 0 because we know it's empty
+                    addIntoResults(results_others, fullId, pos, index, dist, 0, maxEditDistance);
                 }
                 return;
             }
 
             if (elem.fullPath.length > 1) {
-                path_lev = checkPath(elem.pathWithoutLast, row, maxLevDistance);
-                if (path_lev > maxLevDistance) {
+                path_dist = checkPath(elem.pathWithoutLast, row, maxEditDistance);
+                if (path_dist > maxEditDistance) {
                     return;
                 }
             }
 
             if (parsedQuery.literalSearch) {
                 if (searchWord === elem.name) {
-                    addIntoResults(results_others, fullId, pos, index, 0, path_lev);
+                    addIntoResults(results_others, fullId, pos, index, 0, path_dist);
                 }
                 return;
             }
 
-            lev = levenshtein(searchWord, elem.pathLast);
+            dist = editDistance(searchWord, elem.pathLast, maxEditDistance);
 
-            if (index === -1 && lev + path_lev > maxLevDistance) {
+            if (index === -1 && dist + path_dist > maxEditDistance) {
                 return;
             }
 
-            addIntoResults(results_others, fullId, pos, index, lev, path_lev, maxLevDistance);
+            addIntoResults(results_others, fullId, pos, index, dist, path_dist, maxEditDistance);
         }
 
         /**
@@ -1442,22 +1616,29 @@ function initSearch(rawSearchIndex) {
          * @param {integer} pos      - Position in the `searchIndex`.
          * @param {Object} results
          */
-        function handleArgs(row, pos, results, maxLevDistance) {
+        function handleArgs(row, pos, results, maxEditDistance) {
             if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
                 return;
             }
 
-            let totalLev = 0;
-            let nbLev = 0;
+            let totalDist = 0;
+            let nbDist = 0;
 
             // If the result is too "bad", we return false and it ends this search.
             function checkArgs(elems, callback) {
+                const skipPositions = [];
                 for (const elem of elems) {
                     // There is more than one parameter to the query so all checks should be "exact"
-                    const lev = callback(row, elem, NO_TYPE_FILTER, maxLevDistance);
-                    if (lev <= 1) {
-                        nbLev += 1;
-                        totalLev += lev;
+                    const { dist, position } = callback(
+                        row,
+                        elem,
+                        maxEditDistance,
+                        skipPositions
+                    );
+                    if (dist <= 1) {
+                        nbDist += 1;
+                        totalDist += dist;
+                        skipPositions.push(position);
                     } else {
                         return false;
                     }
@@ -1471,11 +1652,11 @@ function initSearch(rawSearchIndex) {
                 return;
             }
 
-            if (nbLev === 0) {
+            if (nbDist === 0) {
                 return;
             }
-            const lev = Math.round(totalLev / nbLev);
-            addIntoResults(results, row.id, pos, 0, lev, 0, maxLevDistance);
+            const dist = Math.round(totalDist / nbDist);
+            addIntoResults(results, row.id, pos, 0, dist, 0, maxEditDistance);
         }
 
         function innerRunQuery() {
@@ -1488,7 +1669,7 @@ function initSearch(rawSearchIndex) {
             for (const elem of parsedQuery.returned) {
                 queryLen += elem.name.length;
             }
-            const maxLevDistance = Math.floor(queryLen / 3);
+            const maxEditDistance = Math.floor(queryLen / 3);
 
             if (parsedQuery.foundElems === 1) {
                 if (parsedQuery.elems.length === 1) {
@@ -1503,7 +1684,7 @@ function initSearch(rawSearchIndex) {
                             results_others,
                             results_in_args,
                             results_returned,
-                            maxLevDistance
+                            maxEditDistance
                         );
                     }
                 } else if (parsedQuery.returned.length === 1) {
@@ -1514,15 +1695,22 @@ function initSearch(rawSearchIndex) {
                         in_returned = checkReturned(
                             row,
                             elem,
-                            parsedQuery.typeFilter,
-                            maxLevDistance
+                            maxEditDistance,
+                            []
+                        );
+                        addIntoResults(
+                            results_others,
+                            row.id,
+                            i,
+                            -1,
+                            in_returned.dist,
+                            maxEditDistance
                         );
-                        addIntoResults(results_others, row.id, i, -1, in_returned, maxLevDistance);
                     }
                 }
             } else if (parsedQuery.foundElems > 0) {
                 for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
-                    handleArgs(searchIndex[i], i, results_others, maxLevDistance);
+                    handleArgs(searchIndex[i], i, results_others, maxEditDistance);
                 }
             }
         }
@@ -1560,7 +1748,7 @@ function initSearch(rawSearchIndex) {
      *
      * @return {boolean}       - Whether the result is valid or not
      */
-    function validateResult(name, path, keys, parent, maxLevDistance) {
+    function validateResult(name, path, keys, parent, maxEditDistance) {
         if (!keys || !keys.length) {
             return true;
         }
@@ -1574,8 +1762,8 @@ function initSearch(rawSearchIndex) {
                 // next if there is a parent, check for exact parent match
                 (parent !== undefined && parent.name !== undefined &&
                     parent.name.toLowerCase().indexOf(key) > -1) ||
-                // lastly check to see if the name was a levenshtein match
-                levenshtein(name, key) <= maxLevDistance)) {
+                // lastly check to see if the name was an editDistance match
+                editDistance(name, key, maxEditDistance) <= maxEditDistance)) {
                 return false;
             }
         }
@@ -1762,11 +1950,7 @@ function initSearch(rawSearchIndex) {
     function showResults(results, go_to_first, filterCrates) {
         const search = searchState.outputElement();
         if (go_to_first || (results.others.length === 1
-            && getSettingValue("go-to-only-result") === "true"
-            // By default, the search DOM element is "empty" (meaning it has no children not
-            // text content). Once a search has been run, it won't be empty, even if you press
-            // ESC or empty the search input (which also "cancels" the search).
-            && (!search.firstChild || search.firstChild.innerText !== searchState.loadingText))
+            && getSettingValue("go-to-only-result") === "true")
         ) {
             const elem = document.createElement("a");
             elem.href = results.others[0].href;
@@ -2064,10 +2248,11 @@ function initSearch(rawSearchIndex) {
              *   n: Array<string>,
              *   t: String,
              *   d: Array<string>,
-             *   q: Array<string>,
+             *   q: Array<[Number, string]>,
              *   i: Array<Number>,
              *   f: Array<RawFunctionSearchType>,
              *   p: Array<Object>,
+             *   c: Array<Number>
              * }}
              */
             const crateCorpus = rawSearchIndex[crate];
@@ -2086,6 +2271,7 @@ function initSearch(rawSearchIndex) {
                 type: null,
                 id: id,
                 normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""),
+                deprecated: null,
             };
             id += 1;
             searchIndex.push(crateRow);
@@ -2095,14 +2281,20 @@ function initSearch(rawSearchIndex) {
             const itemTypes = crateCorpus.t;
             // an array of (String) item names
             const itemNames = crateCorpus.n;
-            // an array of (String) full paths (or empty string for previous path)
-            const itemPaths = crateCorpus.q;
+            // an array of [(Number) item index,
+            //              (String) full path]
+            // an item whose index is not present will fall back to the previous present path
+            // i.e. if indices 4 and 11 are present, but 5-10 and 12-13 are not present,
+            // 5-10 will fall back to the path for 4 and 12-13 will fall back to the path for 11
+            const itemPaths = new Map(crateCorpus.q);
             // an array of (String) descriptions
             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;
+            // an array of (Number) indices for the deprecated items
+            const deprecatedItems = new Set(crateCorpus.c);
             // an array of [(Number) item type,
             //              (String) name]
             const paths = crateCorpus.p;
@@ -2142,12 +2334,13 @@ function initSearch(rawSearchIndex) {
                     crate: crate,
                     ty: itemTypes.charCodeAt(i) - charA,
                     name: itemNames[i],
-                    path: itemPaths[i] ? itemPaths[i] : lastPath,
+                    path: itemPaths.has(i) ? itemPaths.get(i) : lastPath,
                     desc: itemDescs[i],
                     parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
                     type: buildFunctionSearchType(itemFunctionSearchTypes[i], lowercasePaths),
                     id: id,
                     normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
+                    deprecated: deprecatedItems.has(i),
                 };
                 id += 1;
                 searchIndex.push(row);
@@ -2156,17 +2349,22 @@ function initSearch(rawSearchIndex) {
             }
 
             if (aliases) {
-                ALIASES[crate] = Object.create(null);
+                const currentCrateAliases = new Map();
+                ALIASES.set(crate, currentCrateAliases);
                 for (const alias_name in aliases) {
                     if (!hasOwnPropertyRustdoc(aliases, alias_name)) {
                         continue;
                     }
 
-                    if (!hasOwnPropertyRustdoc(ALIASES[crate], alias_name)) {
-                        ALIASES[crate][alias_name] = [];
+                    let currentNameAliases;
+                    if (currentCrateAliases.has(alias_name)) {
+                        currentNameAliases = currentCrateAliases.get(alias_name);
+                    } else {
+                        currentNameAliases = [];
+                        currentCrateAliases.set(alias_name, currentNameAliases);
                     }
                     for (const local_alias of aliases[alias_name]) {
-                        ALIASES[crate][alias_name].push(local_alias + currentIndex);
+                        currentNameAliases.push(local_alias + currentIndex);
                     }
                 }
             }
diff --git a/src/librustdoc/html/static/js/settings.js b/src/librustdoc/html/static/js/settings.js
index 1cd552e7f..ebbe6c1ca 100644
--- a/src/librustdoc/html/static/js/settings.js
+++ b/src/librustdoc/html/static/js/settings.js
@@ -86,12 +86,8 @@
             if (settingId === "theme") {
                 const useSystem = getSettingValue("use-system-theme");
                 if (useSystem === "true" || settingValue === null) {
-                    if (useSystem !== "false") {
-                        settingValue = "system preference";
-                    } else {
-                        // This is the default theme.
-                        settingValue = "light";
-                    }
+                    // "light" is the default theme
+                    settingValue = useSystem === "false" ? "light" : "system preference";
                 }
             }
             if (settingValue !== null && settingValue !== "null") {
diff --git a/src/librustdoc/html/static/js/source-script.js b/src/librustdoc/html/static/js/source-script.js
index 6c0f03b5b..9aa755173 100644
--- a/src/librustdoc/html/static/js/source-script.js
+++ b/src/librustdoc/html/static/js/source-script.js
@@ -15,8 +15,13 @@ const NAME_OFFSET = 0;
 const DIRS_OFFSET = 1;
 const FILES_OFFSET = 2;
 
+// WARNING: RUSTDOC_MOBILE_BREAKPOINT MEDIA QUERY
+// If you update this line, then you also need to update the media query with the same
+// warning in rustdoc.css
+const RUSTDOC_MOBILE_BREAKPOINT = 700;
+
 function closeSidebarIfMobile() {
-    if (window.innerWidth < window.RUSTDOC_MOBILE_BREAKPOINT) {
+    if (window.innerWidth < RUSTDOC_MOBILE_BREAKPOINT) {
         updateLocalStorage("source-sidebar-show", "false");
     }
 }
@@ -69,12 +74,10 @@ function createDirEntry(elem, parent, fullPath, hasFoundFile) {
 function toggleSidebar() {
     const child = this.parentNode.children[0];
     if (child.innerText === ">") {
-        window.rustdocMobileScrollLock();
         addClass(document.documentElement, "source-sidebar-expanded");
         child.innerText = "<";
         updateLocalStorage("source-sidebar-show", "true");
     } else {
-        window.rustdocMobileScrollUnlock();
         removeClass(document.documentElement, "source-sidebar-expanded");
         child.innerText = ">";
         updateLocalStorage("source-sidebar-show", "false");
diff --git a/src/librustdoc/html/static/js/storage.js b/src/librustdoc/html/static/js/storage.js
index c72ac254f..93979a944 100644
--- a/src/librustdoc/html/static/js/storage.js
+++ b/src/librustdoc/html/static/js/storage.js
@@ -7,31 +7,15 @@
 
 const darkThemes = ["dark", "ayu"];
 window.currentTheme = document.getElementById("themeStyle");
-window.mainTheme = document.getElementById("mainThemeStyle");
-
-// WARNING: RUSTDOC_MOBILE_BREAKPOINT MEDIA QUERY
-// If you update this line, then you also need to update the media query with the same
-// warning in rustdoc.css
-window.RUSTDOC_MOBILE_BREAKPOINT = 700;
 
 const settingsDataset = (function() {
     const settingsElement = document.getElementById("default-settings");
-    if (settingsElement === null) {
-        return null;
-    }
-    const dataset = settingsElement.dataset;
-    if (dataset === undefined) {
-        return null;
-    }
-    return dataset;
+    return settingsElement && settingsElement.dataset ? settingsElement.dataset : null;
 })();
 
 function getSettingValue(settingName) {
     const current = getCurrentValue(settingName);
-    if (current !== null) {
-        return current;
-    }
-    if (settingsDataset !== null) {
+    if (current === null && settingsDataset !== null) {
         // See the comment for `default_settings.into_iter()` etc. in
         // `Options::from_matches` in `librustdoc/config.rs`.
         const def = settingsDataset[settingName.replace(/-/g,"_")];
@@ -39,31 +23,27 @@ function getSettingValue(settingName) {
             return def;
         }
     }
-    return null;
+    return current;
 }
 
 const localStoredTheme = getSettingValue("theme");
 
-const savedHref = [];
-
 // eslint-disable-next-line no-unused-vars
 function hasClass(elem, className) {
     return elem && elem.classList && elem.classList.contains(className);
 }
 
 function addClass(elem, className) {
-    if (!elem || !elem.classList) {
-        return;
+    if (elem && elem.classList) {
+        elem.classList.add(className);
     }
-    elem.classList.add(className);
 }
 
 // eslint-disable-next-line no-unused-vars
 function removeClass(elem, className) {
-    if (!elem || !elem.classList) {
-        return;
+    if (elem && elem.classList) {
+        elem.classList.remove(className);
     }
-    elem.classList.remove(className);
 }
 
 /**
@@ -73,10 +53,9 @@ function removeClass(elem, className) {
  * @param {boolean}     [reversed] - Whether to iterate in reverse
  */
 function onEach(arr, func, reversed) {
-    if (arr && arr.length > 0 && func) {
+    if (arr && arr.length > 0) {
         if (reversed) {
-            const length = arr.length;
-            for (let i = length - 1; i >= 0; --i) {
+            for (let i = arr.length - 1; i >= 0; --i) {
                 if (func(arr[i])) {
                     return true;
                 }
@@ -102,6 +81,7 @@ function onEach(arr, func, reversed) {
  * @param {function(?)}                   func       - The callback
  * @param {boolean}                       [reversed] - Whether to iterate in reverse
  */
+// eslint-disable-next-line no-unused-vars
 function onEachLazy(lazyArray, func, reversed) {
     return onEach(
         Array.prototype.slice.call(lazyArray),
@@ -125,34 +105,40 @@ function getCurrentValue(name) {
     }
 }
 
-function switchTheme(styleElem, mainStyleElem, newThemeName, saveTheme) {
+// Get a value from the rustdoc-vars div, which is used to convey data from
+// Rust to the JS. If there is no such element, return null.
+const getVar = (function getVar(name) {
+    const el = document.getElementById("rustdoc-vars");
+    return el ? el.attributes["data-" + name].value : null;
+});
+
+function switchTheme(newThemeName, saveTheme) {
     // If this new value comes from a system setting or from the previously
     // saved theme, no need to save it.
     if (saveTheme) {
         updateLocalStorage("theme", newThemeName);
     }
 
-    if (savedHref.length === 0) {
-        onEachLazy(document.getElementsByTagName("link"), el => {
-            savedHref.push(el.href);
-        });
+    let newHref;
+
+    if (newThemeName === "light" || newThemeName === "dark" || newThemeName === "ayu") {
+        newHref = getVar("static-root-path") + getVar("theme-" + newThemeName + "-css");
+    } else {
+        newHref = getVar("root-path") + newThemeName + getVar("resource-suffix") + ".css";
     }
-    const newHref = savedHref.find(url => {
-        const m = url.match(/static\.files\/(.*)-[a-f0-9]{16}\.css$/);
-        if (m && m[1] === newThemeName) {
-            return true;
-        }
-        const m2 = url.match(/\/([^/]*)\.css$/);
-        if (m2 && m2[1].startsWith(newThemeName)) {
-            return true;
-        }
-    });
-    if (newHref && newHref !== styleElem.href) {
-        styleElem.href = newHref;
+
+    if (!window.currentTheme) {
+        document.write(`<link rel="stylesheet" id="themeStyle" href="${newHref}">`);
+        window.currentTheme = document.getElementById("themeStyle");
+    } else if (newHref !== window.currentTheme.href) {
+        window.currentTheme.href = newHref;
     }
 }
 
 const updateTheme = (function() {
+    // only listen to (prefers-color-scheme: dark) because light is the default
+    const mql = window.matchMedia("(prefers-color-scheme: dark)");
+
     /**
      * Update the current theme to match whatever the current combination of
      * * the preference for using the system theme
@@ -163,60 +149,23 @@ const updateTheme = (function() {
      * … dictates that it should be.
      */
     function updateTheme() {
-        const use = (theme, saveTheme) => {
-            switchTheme(window.currentTheme, window.mainTheme, theme, saveTheme);
-        };
-
         // maybe the user has disabled the setting in the meantime!
         if (getSettingValue("use-system-theme") !== "false") {
             const lightTheme = getSettingValue("preferred-light-theme") || "light";
             const darkTheme = getSettingValue("preferred-dark-theme") || "dark";
+            updateLocalStorage("use-system-theme", "true");
 
-            if (isDarkMode()) {
-                use(darkTheme, true);
-            } else {
-                // prefers a light theme, or has no preference
-                use(lightTheme, true);
-            }
+            // use light theme if user prefers it, or has no preference
+            switchTheme(mql.matches ? darkTheme : lightTheme, true);
             // note: we save the theme so that it doesn't suddenly change when
             // the user disables "use-system-theme" and reloads the page or
             // navigates to another page
         } else {
-            use(getSettingValue("theme"), false);
+            switchTheme(getSettingValue("theme"), false);
         }
     }
 
-    // This is always updated below to a function () => bool.
-    let isDarkMode;
-
-    // Determine the function for isDarkMode, and if we have
-    // `window.matchMedia`, set up an event listener on the preferred color
-    // scheme.
-    //
-    // Otherwise, fall back to the prefers-color-scheme value CSS captured in
-    // the "content" property.
-    if (window.matchMedia) {
-        // only listen to (prefers-color-scheme: dark) because light is the default
-        const mql = window.matchMedia("(prefers-color-scheme: dark)");
-
-        isDarkMode = () => mql.matches;
-
-        if (mql.addEventListener) {
-            mql.addEventListener("change", updateTheme);
-        } else {
-            // This is deprecated, see:
-            // https://developer.mozilla.org/en-US/docs/Web/API/MediaQueryList/addListener
-            mql.addListener(updateTheme);
-        }
-    } else {
-        // fallback to the CSS computed value
-        const cssContent = getComputedStyle(document.documentElement)
-            .getPropertyValue("content");
-        // (Note: the double-quotes come from that this is a CSS value, which
-        // might be a length, string, etc.)
-        const cssColorScheme = cssContent || "\"light\"";
-        isDarkMode = () => (cssColorScheme === "\"dark\"");
-    }
+    mql.addEventListener("change", updateTheme);
 
     return updateTheme;
 })();