Merging upstream version 1.76.0+dfsg1.

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

8 files changed, 1336 insertions, 643 deletions

diff --git a/src/librustdoc/html/static/css/noscript.css b/src/librustdoc/html/static/css/noscript.css
index fe0cf6dc8..390e81277 100644
--- a/src/librustdoc/html/static/css/noscript.css
+++ b/src/librustdoc/html/static/css/noscript.css
@@ -9,7 +9,7 @@ rules.
 	margin-left: 0 !important;
 }
 
-#copy-path {
+#copy-path, #sidebar-button, .sidebar-resizer {
 	/* It requires JS to work so no need to display it in this case. */
 	display: none;
 }
@@ -132,6 +132,8 @@ nav.sub {
 	--scrape-example-help-hover-color: #000;
 	--scrape-example-code-wrapper-background-start: rgba(255, 255, 255, 1);
 	--scrape-example-code-wrapper-background-end: rgba(255, 255, 255, 0);
+	--sidebar-resizer-hover: hsl(207, 90%, 66%);
+	--sidebar-resizer-active: hsl(207, 90%, 54%);
 }
 /* End theme: light */
 
@@ -238,6 +240,8 @@ nav.sub {
 		--scrape-example-help-hover-color: #fff;
 		--scrape-example-code-wrapper-background-start: rgba(53, 53, 53, 1);
 		--scrape-example-code-wrapper-background-end: rgba(53, 53, 53, 0);
+		--sidebar-resizer-hover: hsl(207, 30%, 54%);
+		--sidebar-resizer-active: hsl(207, 90%, 54%);
 	}
 /* End theme: dark */
 }
diff --git a/src/librustdoc/html/static/css/rustdoc.css b/src/librustdoc/html/static/css/rustdoc.css
index 9efdcd601..c4e97ded1 100644
--- a/src/librustdoc/html/static/css/rustdoc.css
+++ b/src/librustdoc/html/static/css/rustdoc.css
@@ -9,6 +9,12 @@
 :root {
 	--nav-sub-mobile-padding: 8px;
 	--search-typename-width: 6.75rem;
+	/* DEFAULT_SIDEBAR_WIDTH
+	   see main.js for information on these values
+	   and on the RUSTDOC_MOBILE_BREAKPOINT */
+	--desktop-sidebar-width: 200px;
+	--src-sidebar-width: 300px;
+	--desktop-sidebar-z-index: 100;
 }
 
 /* See FiraSans-LICENSE.txt for the Fira Sans license. */
@@ -205,7 +211,7 @@ ul.all-items {
 
 #toggle-all-docs,
 a.anchor,
-.small-section-header a,
+.section-header a,
 #src-sidebar a,
 .rust a,
 .sidebar h2 a,
@@ -383,13 +389,15 @@ img {
 
 .sidebar {
 	font-size: 0.875rem;
-	flex: 0 0 200px;
+	flex: 0 0 var(--desktop-sidebar-width);
+	width: var(--desktop-sidebar-width);
 	overflow-y: scroll;
 	overscroll-behavior: contain;
 	position: sticky;
 	height: 100vh;
 	top: 0;
 	left: 0;
+	z-index: var(--desktop-sidebar-z-index);
 }
 
 .rustdoc.src .sidebar {
@@ -398,7 +406,94 @@ img {
 	overflow-x: hidden;
 	/* The sidebar is by default hidden  */
 	overflow-y: hidden;
-	z-index: 1;
+}
+
+.hide-sidebar .sidebar,
+.hide-sidebar .sidebar-resizer {
+	display: none;
+}
+
+.sidebar-resizer {
+	touch-action: none;
+	width: 9px;
+	cursor: col-resize;
+	z-index: calc(var(--desktop-sidebar-z-index) + 1);
+	position: fixed;
+	height: 100%;
+	/* make sure there's a 1px gap between the scrollbar and resize handle */
+	left: calc(var(--desktop-sidebar-width) + 1px);
+}
+
+.rustdoc.src .sidebar-resizer {
+	/* when closed, place resizer glow on top of the normal src sidebar border (no need to worry
+	   about sidebar) */
+	left: 49px;
+}
+
+.src-sidebar-expanded .rustdoc.src .sidebar-resizer {
+	/* for src sidebar, gap is already provided by 1px border on sidebar itself, so place resizer
+	   to right of it */
+	left: var(--src-sidebar-width);
+}
+
+.sidebar-resizing {
+	-moz-user-select: none;
+	-webkit-user-select: none;
+	-ms-user-select: none;
+	user-select: none;
+}
+
+.sidebar-resizing * {
+	cursor: col-resize !important;
+}
+
+.sidebar-resizing .sidebar {
+	position: fixed;
+}
+.sidebar-resizing > body {
+	padding-left: var(--resizing-sidebar-width);
+}
+
+.sidebar-resizer:hover,
+.sidebar-resizer:active,
+.sidebar-resizer:focus,
+.sidebar-resizer.active {
+	width: 10px;
+	margin: 0;
+	/* when active or hovered, place resizer glow on top of the sidebar (right next to, or even
+	   on top of, the scrollbar) */
+	left: var(--desktop-sidebar-width);
+	border-left: solid 1px var(--sidebar-resizer-hover);
+}
+
+.src-sidebar-expanded .rustdoc.src .sidebar-resizer:hover,
+.src-sidebar-expanded .rustdoc.src .sidebar-resizer:active,
+.src-sidebar-expanded .rustdoc.src .sidebar-resizer:focus,
+.src-sidebar-expanded .rustdoc.src .sidebar-resizer.active {
+	/* when active or hovered, place resizer glow on top of the normal src sidebar border */
+	left: calc(var(--src-sidebar-width) - 1px);
+}
+
+@media (pointer: coarse) {
+	.sidebar-resizer {
+		/* too easy to hit the resizer while trying to hit the [-] toggle */
+		display: none !important;
+	}
+}
+
+.sidebar-resizer.active {
+	/* make the resize tool bigger when actually resizing, to avoid :hover styles on other stuff
+		while resizing */
+	padding: 0 140px;
+	width: 2px;
+	margin-left: -140px;
+	border-left: none;
+}
+.sidebar-resizer.active:before {
+	border-left: solid 2px var(--sidebar-resizer-active);
+	display: block;
+	height: 100%;
+	content: "";
 }
 
 .sidebar, .mobile-topbar, .sidebar-menu-toggle,
@@ -416,7 +511,8 @@ img {
 
 .src-sidebar-expanded .src .sidebar {
 	overflow-y: auto;
-	flex-basis: 300px;
+	flex-basis: var(--src-sidebar-width);
+	width: var(--src-sidebar-width);
 }
 
 .src-sidebar-expanded .src .sidebar > *:not(#src-sidebar-toggle) {
@@ -477,6 +573,7 @@ ul.block, .block li {
 	display: block;
 	padding: 0.25rem; /* 4px */
 	margin-left: -0.25rem;
+	margin-right: 0.25rem;
 }
 
 .sidebar h2 {
@@ -703,11 +800,8 @@ pre, .rustdoc.src .example-wrap {
 	background: var(--table-alt-row-background-color);
 }
 
-/* Shift "where ..." part of method or fn definition down a line */
-.method .where,
-.fn .where,
-.where.fmt-newline {
-	display: block;
+/* "where ..." clauses with block display are also smaller */
+div.where {
 	white-space: pre-wrap;
 	font-size: 0.875rem;
 }
@@ -742,13 +836,13 @@ nav.sub {
 	margin: 0 0 15px 0;
 }
 
-.small-section-header {
+.section-header {
 	/* fields use <span> tags, but should get their own lines */
 	display: block;
 	position: relative;
 }
 
-.small-section-header:hover > .anchor, .impl:hover > .anchor,
+.section-header:hover > .anchor, .impl:hover > .anchor,
 .trait-impl:hover > .anchor, .variant:hover > .anchor {
 	display: initial;
 }
@@ -761,11 +855,11 @@ nav.sub {
 .anchor.field {
 	left: -5px;
 }
-.small-section-header > .anchor {
+.section-header > .anchor {
 	left: -15px;
 	padding-right: 8px;
 }
-h2.small-section-header > .anchor {
+h2.section-header > .anchor {
 	padding-right: 6px;
 }
 
@@ -778,7 +872,7 @@ h2.small-section-header > .anchor {
 	text-decoration: underline;
 }
 
-.crate.block a.current { font-weight: 500; }
+.crate.block li.current a { font-weight: 500; }
 
 /*  In most contexts we use `overflow-wrap: anywhere` to ensure that we can wrap
 	as much as needed on mobile (see
@@ -965,7 +1059,7 @@ so that we can apply CSS-filters to change the arrow color in themes */
 	position: absolute;
 	top: 100%;
 	right: 0;
-	z-index: 2;
+	z-index: calc(var(--desktop-sidebar-z-index) + 1);
 	margin-top: 7px;
 	border-radius: 3px;
 	border: 1px solid var(--border-color);
@@ -1084,15 +1178,9 @@ so that we can apply CSS-filters to change the arrow color in themes */
 }
 
 .item-info .stab {
-	/* This min-height is needed to unify the height of the stab elements because some of them
-	   have emojis.
-	*/
-	min-height: 36px;
-	display: flex;
+	display: block;
 	padding: 3px;
 	margin-bottom: 5px;
-	align-items: center;
-	vertical-align: text-bottom;
 }
 .item-name .stab {
 	margin-left: 0.3125em;
@@ -1115,17 +1203,26 @@ so that we can apply CSS-filters to change the arrow color in themes */
 	color: var(--stab-code-color);
 }
 
-.stab .emoji {
+.stab .emoji, .item-info .stab::before {
 	font-size: 1.25rem;
+}
+.stab .emoji {
 	margin-right: 0.3rem;
 }
+.item-info .stab::before {
+	/* ensure badges with emoji and without it have same height */
+	content: "\0";
+	width: 0;
+	display: inline-block;
+	color: transparent;
+}
 
 /* Black one-pixel outline around emoji shapes */
 .emoji {
 	text-shadow:
 		1px 0 0 black,
 		-1px 0 0 black,
-		0  1px 0 black,
+		0 1px 0 black,
 		0 -1px 0 black;
 }
 
@@ -1478,7 +1575,20 @@ a.tooltip:hover::after {
 	margin-left: 4px;
 	display: flex;
 }
-#settings-menu > a, #help-button > a {
+#sidebar-button {
+	display: none;
+}
+.hide-sidebar #sidebar-button {
+	display: flex;
+	margin-right: 4px;
+	position: fixed;
+	left: 6px;
+	height: 34px;
+	width: 34px;
+	background-color: var(--main-background-color);
+	z-index: 1;
+}
+#settings-menu > a, #help-button > a, #sidebar-button > a {
 	display: flex;
 	align-items: center;
 	justify-content: center;
@@ -1493,10 +1603,21 @@ a.tooltip:hover::after {
 }
 
 #settings-menu > a:hover, #settings-menu > a:focus,
-#help-button > a:hover, #help-button > a:focus {
+#help-button > a:hover, #help-button > a:focus,
+#sidebar-button > a:hover, #sidebar-button > a:focus {
 	border-color: var(--settings-button-border-focus);
 }
 
+#sidebar-button > a:before {
+	content: url('data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 22 22" \
+		fill="none" stroke="black">\
+		<rect x="1" y="1" width="20" height="20" ry="1.5" stroke-width="1.5"/>\
+		<circle cx="4.375" cy="4.375" r="1" stroke-width=".75"/>\
+		<path d="m7.6121 3v16 M5.375 7.625h-2 m2 3h-2 m2 3h-2" stroke-width="1.25"/></svg>');
+	width: 22px;
+	height: 22px;
+}
+
 #copy-path {
 	color: var(--copy-path-button-color);
 	background: var(--main-background-color);
@@ -1711,7 +1832,7 @@ However, it's not needed with smaller screen width because the doc/code block is
 /*
 WARNING: RUSTDOC_MOBILE_BREAKPOINT MEDIA QUERY
 If you update this line, then you also need to update the line with the same warning
-in src-script.js
+in src-script.js and main.js
 */
 @media (max-width: 700px) {
 	/* When linking to an item with an `id` (for instance, by clicking a link in the sidebar,
@@ -1722,6 +1843,10 @@ in src-script.js
 		scroll-margin-top: 45px;
 	}
 
+	.hide-sidebar #sidebar-button {
+		position: static;
+	}
+
 	.rustdoc {
 		/* Sidebar should overlay main content, rather than pushing main content to the right.
 		   Turn off `display: flex` on the body element. */
@@ -1750,7 +1875,8 @@ in src-script.js
 	/* Hide the logo and item name from the sidebar. Those are displayed
 	   in the mobile-topbar instead. */
 	.sidebar .logo-container,
-	.sidebar .location {
+	.sidebar .location,
+	.sidebar-resizer {
 		display: none;
 	}
 
@@ -1818,6 +1944,10 @@ in src-script.js
 		top: 0;
 	}
 
+	.hide-sidebar .mobile-topbar {
+		display: none;
+	}
+
 	.sidebar-menu-toggle {
 		width: 45px;
 		/* Rare exception to specifying font sizes in rem. Since this is acting
@@ -1827,6 +1957,10 @@ in src-script.js
 		color: var(--main-color);
 	}
 
+	.hide-sidebar .sidebar-menu-toggle {
+		display: none;
+	}
+
 	.sidebar-elems {
 		margin-top: 1em;
 	}
@@ -1870,6 +2004,17 @@ in src-script.js
 		display: none;
 	}
 
+	/* sidebar button becomes topbar button */
+	#sidebar-button > a:before {
+		content: url('data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" \
+			viewBox="0 0 22 22" fill="none" stroke="black">\
+			<rect x="1" y="1" width="20" height="20" ry="1.5" stroke-width="1.5"/>\
+			<circle cx="4.375" cy="4.375" r="1" stroke-width=".75"/>\
+			<path d="m3 7.375h16m0-3h-4" stroke-width="1.25"/></svg>');
+		width: 22px;
+		height: 22px;
+	}
+
 	/* Display an alternating layout on tablets and phones */
 	.item-table, .item-row, .item-table > li, .item-table > li > div,
 	.search-results > a, .search-results > a > div {
@@ -2274,6 +2419,8 @@ in src-script.js
 	--scrape-example-help-hover-color: #000;
 	--scrape-example-code-wrapper-background-start: rgba(255, 255, 255, 1);
 	--scrape-example-code-wrapper-background-end: rgba(255, 255, 255, 0);
+	--sidebar-resizer-hover: hsl(207, 90%, 66%);
+	--sidebar-resizer-active: hsl(207, 90%, 54%);
 }
 /* End theme: light */
 
@@ -2379,6 +2526,8 @@ in src-script.js
 	--scrape-example-help-hover-color: #fff;
 	--scrape-example-code-wrapper-background-start: rgba(53, 53, 53, 1);
 	--scrape-example-code-wrapper-background-end: rgba(53, 53, 53, 0);
+	--sidebar-resizer-hover: hsl(207, 30%, 54%);
+	--sidebar-resizer-active: hsl(207, 90%, 54%);
 }
 /* End theme: dark */
 
@@ -2488,6 +2637,8 @@ Original by Dempfi (https://github.com/dempfi/ayu)
 	--scrape-example-help-hover-color: #fff;
 	--scrape-example-code-wrapper-background-start: rgba(15, 20, 25, 1);
 	--scrape-example-code-wrapper-background-end: rgba(15, 20, 25, 0);
+	--sidebar-resizer-hover: hsl(34, 50%, 33%);
+	--sidebar-resizer-active: hsl(34, 100%, 66%);
 }
 
 :root[data-theme="ayu"] h1,
@@ -2519,6 +2670,7 @@ Original by Dempfi (https://github.com/dempfi/ayu)
 }
 
 :root[data-theme="ayu"] .sidebar .current,
+:root[data-theme="ayu"] .sidebar .current a,
 :root[data-theme="ayu"] .sidebar a:hover,
 :root[data-theme="ayu"] #src-sidebar div.files > a:hover,
 :root[data-theme="ayu"] details.dir-entry summary:hover,
@@ -2569,7 +2721,8 @@ Original by Dempfi (https://github.com/dempfi/ayu)
 	border-bottom: 1px solid rgba(242, 151, 24, 0.3);
 }
 
-:root[data-theme="ayu"] #settings-menu > a img {
+:root[data-theme="ayu"] #settings-menu > a img,
+:root[data-theme="ayu"] #sidebar-button > a:before {
 	filter: invert(100);
 }
 /* End theme: ayu */
diff --git a/src/librustdoc/html/static/js/externs.js b/src/librustdoc/html/static/js/externs.js
index c7811b43d..93709e4e8 100644
--- a/src/librustdoc/html/static/js/externs.js
+++ b/src/librustdoc/html/static/js/externs.js
@@ -14,6 +14,7 @@ function initSearch(searchIndex){}
  *     pathWithoutLast: Array<string>,
  *     pathLast: string,
  *     generics: Array<QueryElement>,
+ *     bindings: Map<integer, Array<QueryElement>>,
  * }}
  */
 let QueryElement;
@@ -24,6 +25,7 @@ let QueryElement;
  *      totalElems: number,
  *      typeFilter: (null|string),
  *      userQuery: string,
+ *      isInBinding: (null|string),
  * }}
  */
 let ParserState;
@@ -40,6 +42,7 @@ let ParserState;
  *     totalElems: number,
  *     literalSearch: boolean,
  *     corrections: Array<{from: string, to: integer}>,
+ *     typeFingerprint: Uint32Array,
  * }}
  */
 let ParsedQuery;
@@ -191,8 +194,9 @@ let FunctionSearchType;
 /**
  * @typedef {{
  *     id: (null|number),
- *     ty: (null|number),
+ *     ty: number,
  *     generics: Array<FunctionType>,
+ *     bindings: Map<integer, Array<FunctionType>>,
  * }}
  */
 let FunctionType;
diff --git a/src/librustdoc/html/static/js/main.js b/src/librustdoc/html/static/js/main.js
index 7c052606a..63ab56053 100644
--- a/src/librustdoc/html/static/js/main.js
+++ b/src/librustdoc/html/static/js/main.js
@@ -1,5 +1,5 @@
 // Local js definitions:
-/* global addClass, getSettingValue, hasClass, searchState */
+/* global addClass, getSettingValue, hasClass, searchState, updateLocalStorage */
 /* global onEach, onEachLazy, removeClass, getVar */
 
 "use strict";
@@ -25,19 +25,9 @@ function showMain() {
     removeClass(document.getElementById(MAIN_ID), "hidden");
 }
 
-function elemIsInParent(elem, parent) {
-    while (elem && elem !== document.body) {
-        if (elem === parent) {
-            return true;
-        }
-        elem = elem.parentElement;
-    }
-    return false;
-}
-
 function blurHandler(event, parentElem, hideCallback) {
-    if (!elemIsInParent(document.activeElement, parentElem) &&
-        !elemIsInParent(event.relatedTarget, parentElem)
+    if (!parentElem.contains(document.activeElement) &&
+        !parentElem.contains(event.relatedTarget)
     ) {
         hideCallback();
     }
@@ -54,7 +44,7 @@ function setMobileTopbar() {
     if (mobileTopbar) {
         const mobileTitle = document.createElement("h2");
         mobileTitle.className = "location";
-        if (hasClass(document.body, "crate")) {
+        if (hasClass(document.querySelector(".rustdoc"), "crate")) {
             mobileTitle.innerText = `Crate ${window.currentCrate}`;
         } else if (locationTitle) {
             mobileTitle.innerHTML = locationTitle.innerHTML;
@@ -485,7 +475,7 @@ function preLoadCss(cssUrl) {
                 return;
             }
 
-            const modpath = hasClass(document.body, "mod") ? "../" : "";
+            const modpath = hasClass(document.querySelector(".rustdoc"), "mod") ? "../" : "";
 
             const h3 = document.createElement("h3");
             h3.innerHTML = `<a href="${modpath}index.html#${id}">${longty}</a>`;
@@ -505,7 +495,7 @@ function preLoadCss(cssUrl) {
                 }
                 const link = document.createElement("a");
                 link.href = path;
-                if (link.href === current_page) {
+                if (path === current_page) {
                     link.className = "current";
                 }
                 link.textContent = name;
@@ -867,12 +857,12 @@ function preLoadCss(cssUrl) {
         for (const crate of window.ALL_CRATES) {
             const link = document.createElement("a");
             link.href = window.rootPath + crate + "/index.html";
-            if (window.rootPath !== "./" && crate === window.currentCrate) {
-                link.className = "current";
-            }
             link.textContent = crate;
 
             const li = document.createElement("li");
+            if (window.rootPath !== "./" && crate === window.currentCrate) {
+                li.className = "current";
+            }
             li.appendChild(link);
             ul.appendChild(li);
         }
@@ -1118,7 +1108,7 @@ function preLoadCss(cssUrl) {
             if (ev.pointerType !== "mouse") {
                 return;
             }
-            if (!e.TOOLTIP_FORCE_VISIBLE && !elemIsInParent(ev.relatedTarget, e)) {
+            if (!e.TOOLTIP_FORCE_VISIBLE && !e.contains(ev.relatedTarget)) {
                 // See "Tooltip pointer leave gesture" below.
                 setTooltipHoverTimeout(e, false);
                 addClass(wrapper, "fade-out");
@@ -1178,10 +1168,10 @@ function preLoadCss(cssUrl) {
 
     function tooltipBlurHandler(event) {
         if (window.CURRENT_TOOLTIP_ELEMENT &&
-            !elemIsInParent(document.activeElement, window.CURRENT_TOOLTIP_ELEMENT) &&
-            !elemIsInParent(event.relatedTarget, window.CURRENT_TOOLTIP_ELEMENT) &&
-            !elemIsInParent(document.activeElement, window.CURRENT_TOOLTIP_ELEMENT.TOOLTIP_BASE) &&
-            !elemIsInParent(event.relatedTarget, window.CURRENT_TOOLTIP_ELEMENT.TOOLTIP_BASE)
+            !window.CURRENT_TOOLTIP_ELEMENT.contains(document.activeElement) &&
+            !window.CURRENT_TOOLTIP_ELEMENT.contains(event.relatedTarget) &&
+            !window.CURRENT_TOOLTIP_ELEMENT.TOOLTIP_BASE.contains(document.activeElement) &&
+            !window.CURRENT_TOOLTIP_ELEMENT.TOOLTIP_BASE.contains(event.relatedTarget)
         ) {
             // Work around a difference in the focus behaviour between Firefox, Chrome, and Safari.
             // When I click the button on an already-opened tooltip popover, Safari
@@ -1248,8 +1238,8 @@ function preLoadCss(cssUrl) {
             if (ev.pointerType !== "mouse") {
                 return;
             }
-            if (!e.TOOLTIP_FORCE_VISIBLE &&
-                !elemIsInParent(ev.relatedTarget, window.CURRENT_TOOLTIP_ELEMENT)) {
+            if (!e.TOOLTIP_FORCE_VISIBLE && window.CURRENT_TOOLTIP_ELEMENT &&
+                !window.CURRENT_TOOLTIP_ELEMENT.contains(ev.relatedTarget)) {
                 // Tooltip pointer leave gesture:
                 //
                 // Designing a good hover microinteraction is a matter of guessing user
@@ -1328,8 +1318,7 @@ function preLoadCss(cssUrl) {
 
         const infos = [
             `For a full list of all search features, take a look <a \
-href="https://doc.rust-lang.org/${channel}/rustdoc/how-to-read-rustdoc.html\
-#the-search-interface">here</a>.`,
+href="https://doc.rust-lang.org/${channel}/rustdoc/read-documentation/search.html">here</a>.`,
             "Prefix searches with a type followed by a colon (e.g., <code>fn:</code>) to \
              restrict the search to a given item kind.",
             "Accepted kinds are: <code>fn</code>, <code>mod</code>, <code>struct</code>, \
@@ -1484,6 +1473,264 @@ href="https://doc.rust-lang.org/${channel}/rustdoc/how-to-read-rustdoc.html\
     searchState.setup();
 }());
 
+// Hide, show, and resize the sidebar
+//
+// The body class and CSS variable are initially set up in storage.js,
+// but in this file, we implement:
+//
+//   * the show sidebar button, which appears if the sidebar is hidden
+//     and, by clicking on it, will bring it back
+//   * the sidebar resize handle, which appears only on large viewports
+//     with a [fine precision pointer] to allow the user to change
+//     the size of the sidebar
+//
+// [fine precision pointer]: https://developer.mozilla.org/en-US/docs/Web/CSS/@media/pointer
+(function() {
+    // 100 is the size of the logo
+    // don't let the sidebar get smaller than that, or it'll get squished
+    const SIDEBAR_MIN = 100;
+    // Don't let the sidebar get bigger than this
+    const SIDEBAR_MAX = 500;
+    // Don't let the body (including the gutter) get smaller than this
+    //
+    // WARNING: RUSTDOC_MOBILE_BREAKPOINT MEDIA QUERY
+    // Acceptable values for BODY_MIN are constrained by the mobile breakpoint
+    // (which is the minimum size of the whole page where the sidebar exists)
+    // and the default sidebar width:
+    //
+    //     BODY_MIN <= RUSTDOC_MOBILE_BREAKPOINT - DEFAULT_SIDEBAR_WIDTH
+    //
+    // At the time of this writing, the DEFAULT_SIDEBAR_WIDTH on src pages is
+    // 300px, and the RUSTDOC_MOBILE_BREAKPOINT is 700px, so BODY_MIN must be
+    // at most 400px. Otherwise, it would start out at the default size, then
+    // grabbing the resize handle would suddenly cause it to jank to
+    // its contraint-generated maximum.
+    const RUSTDOC_MOBILE_BREAKPOINT = 700;
+    const BODY_MIN = 400;
+    // At half-way past the minimum size, vanish the sidebar entirely
+    const SIDEBAR_VANISH_THRESHOLD = SIDEBAR_MIN / 2;
+
+    // Toolbar button to show the sidebar.
+    //
+    // On small, "mobile-sized" viewports, it's not persistent and it
+    // can only be activated by going into Settings and hiding the nav bar.
+    // On larger, "desktop-sized" viewports (though that includes many
+    // tablets), it's fixed-position, appears in the left side margin,
+    // and it can be activated by resizing the sidebar into nothing.
+    const sidebarButton = document.getElementById("sidebar-button");
+    if (sidebarButton) {
+        sidebarButton.addEventListener("click", e => {
+            removeClass(document.documentElement, "hide-sidebar");
+            updateLocalStorage("hide-sidebar", "false");
+            e.preventDefault();
+        });
+    }
+
+    // Pointer capture.
+    //
+    // Resizing is a single-pointer gesture. Any secondary pointer is ignored
+    let currentPointerId = null;
+
+    // "Desired" sidebar size.
+    //
+    // This is stashed here for window resizing. If the sidebar gets
+    // shrunk to maintain BODY_MIN, and then the user grows the window again,
+    // it gets the sidebar to restore its size.
+    let desiredSidebarSize = null;
+
+    // Sidebar resize debouncer.
+    //
+    // The sidebar itself is resized instantly, but the body HTML can be too
+    // big for that, causing reflow jank. To reduce this, we queue up a separate
+    // animation frame and throttle it.
+    let pendingSidebarResizingFrame = false;
+
+    // If this page has no sidebar at all, bail out.
+    const resizer = document.querySelector(".sidebar-resizer");
+    const sidebar = document.querySelector(".sidebar");
+    if (!resizer || !sidebar) {
+        return;
+    }
+
+    // src page and docs page use different variables, because the contents of
+    // the sidebar are so different that it's reasonable to thing the user
+    // would want them to have different sizes
+    const isSrcPage = hasClass(document.body, "src");
+
+    // Call this function to hide the sidebar when using the resize handle
+    //
+    // This function also nulls out the sidebar width CSS variable and setting,
+    // causing it to return to its default. This does not happen if you do it
+    // from settings.js, which uses a separate function. It's done here because
+    // the minimum sidebar size is rather uncomfortable, and it must pass
+    // through that size when using the shrink-to-nothing gesture.
+    function hideSidebar() {
+        if (isSrcPage) {
+            window.rustdocCloseSourceSidebar();
+            updateLocalStorage("src-sidebar-width", null);
+            // [RUSTDOCIMPL] CSS variable fast path
+            //
+            // The sidebar width variable is attached to the <html> element by
+            // storage.js, because the sidebar and resizer don't exist yet.
+            // But the resize code, in `resize()`, sets the property on the
+            // sidebar and resizer elements (which are the only elements that
+            // use the variable) to avoid recalculating CSS on the entire
+            // document on every frame.
+            //
+            // So, to clear it, we need to clear all three.
+            document.documentElement.style.removeProperty("--src-sidebar-width");
+            sidebar.style.removeProperty("--src-sidebar-width");
+            resizer.style.removeProperty("--src-sidebar-width");
+        } else {
+            addClass(document.documentElement, "hide-sidebar");
+            updateLocalStorage("hide-sidebar", "true");
+            updateLocalStorage("desktop-sidebar-width", null);
+            document.documentElement.style.removeProperty("--desktop-sidebar-width");
+            sidebar.style.removeProperty("--desktop-sidebar-width");
+            resizer.style.removeProperty("--desktop-sidebar-width");
+        }
+    }
+
+    // Call this function to show the sidebar from the resize handle.
+    // On docs pages, this can only happen if the user has grabbed the resize
+    // handle, shrunk the sidebar down to nothing, and then pulls back into
+    // the visible range without releasing it. You can, however, grab the
+    // resize handle on a source page with the sidebar closed, because it
+    // remains visible all the time on there.
+    function showSidebar() {
+        if (isSrcPage) {
+            window.rustdocShowSourceSidebar();
+        } else {
+            removeClass(document.documentElement, "hide-sidebar");
+            updateLocalStorage("hide-sidebar", "false");
+        }
+    }
+
+    /**
+     * Call this to set the correct CSS variable and setting.
+     * This function doesn't enforce size constraints. Do that before calling it!
+     *
+     * @param {number} size - CSS px width of the sidebar.
+     */
+    function changeSidebarSize(size) {
+        if (isSrcPage) {
+            updateLocalStorage("src-sidebar-width", size);
+            // [RUSTDOCIMPL] CSS variable fast path
+            //
+            // While this property is set on the HTML element at load time,
+            // because the sidebar isn't actually loaded yet,
+            // we scope this update to the sidebar to avoid hitting a slow
+            // path in WebKit.
+            sidebar.style.setProperty("--src-sidebar-width", size + "px");
+            resizer.style.setProperty("--src-sidebar-width", size + "px");
+        } else {
+            updateLocalStorage("desktop-sidebar-width", size);
+            sidebar.style.setProperty("--desktop-sidebar-width", size + "px");
+            resizer.style.setProperty("--desktop-sidebar-width", size + "px");
+        }
+    }
+
+    // Check if the sidebar is hidden. Since src pages and doc pages have
+    // different settings, this function has to check that.
+    function isSidebarHidden() {
+        return isSrcPage ?
+            !hasClass(document.documentElement, "src-sidebar-expanded") :
+            hasClass(document.documentElement, "hide-sidebar");
+    }
+
+    // Respond to the resize handle event.
+    // This function enforces size constraints, and implements the
+    // shrink-to-nothing gesture based on thresholds defined above.
+    function resize(e) {
+        if (currentPointerId === null || currentPointerId !== e.pointerId) {
+            return;
+        }
+        e.preventDefault();
+        const pos = e.clientX - sidebar.offsetLeft - 3;
+        if (pos < SIDEBAR_VANISH_THRESHOLD) {
+            hideSidebar();
+        } else if (pos >= SIDEBAR_MIN) {
+            if (isSidebarHidden()) {
+                showSidebar();
+            }
+            // don't let the sidebar get wider than SIDEBAR_MAX, or the body narrower
+            // than BODY_MIN
+            const constrainedPos = Math.min(pos, window.innerWidth - BODY_MIN, SIDEBAR_MAX);
+            changeSidebarSize(constrainedPos);
+            desiredSidebarSize = constrainedPos;
+            if (pendingSidebarResizingFrame !== false) {
+                clearTimeout(pendingSidebarResizingFrame);
+            }
+            pendingSidebarResizingFrame = setTimeout(() => {
+                if (currentPointerId === null || pendingSidebarResizingFrame === false) {
+                    return;
+                }
+                pendingSidebarResizingFrame = false;
+                document.documentElement.style.setProperty(
+                    "--resizing-sidebar-width",
+                    desiredSidebarSize + "px"
+                );
+            }, 100);
+        }
+    }
+    // Respond to the window resize event.
+    window.addEventListener("resize", () => {
+        if (window.innerWidth < RUSTDOC_MOBILE_BREAKPOINT) {
+            return;
+        }
+        stopResize();
+        if (desiredSidebarSize >= (window.innerWidth - BODY_MIN)) {
+            changeSidebarSize(window.innerWidth - BODY_MIN);
+        } else if (desiredSidebarSize !== null && desiredSidebarSize > SIDEBAR_MIN) {
+            changeSidebarSize(desiredSidebarSize);
+        }
+    });
+    function stopResize(e) {
+        if (currentPointerId === null) {
+            return;
+        }
+        if (e) {
+            e.preventDefault();
+        }
+        desiredSidebarSize = sidebar.getBoundingClientRect().width;
+        removeClass(resizer, "active");
+        window.removeEventListener("pointermove", resize, false);
+        window.removeEventListener("pointerup", stopResize, false);
+        removeClass(document.documentElement, "sidebar-resizing");
+        document.documentElement.style.removeProperty( "--resizing-sidebar-width");
+        if (resizer.releasePointerCapture) {
+            resizer.releasePointerCapture(currentPointerId);
+            currentPointerId = null;
+        }
+    }
+    function initResize(e) {
+        if (currentPointerId !== null || e.altKey || e.ctrlKey || e.metaKey || e.button !== 0) {
+            return;
+        }
+        if (resizer.setPointerCapture) {
+            resizer.setPointerCapture(e.pointerId);
+            if (!resizer.hasPointerCapture(e.pointerId)) {
+                // unable to capture pointer; something else has it
+                // on iOS, this usually means you long-clicked a link instead
+                resizer.releasePointerCapture(e.pointerId);
+                return;
+            }
+            currentPointerId = e.pointerId;
+        }
+        e.preventDefault();
+        window.addEventListener("pointermove", resize, false);
+        window.addEventListener("pointercancel", stopResize, false);
+        window.addEventListener("pointerup", stopResize, false);
+        addClass(resizer, "active");
+        addClass(document.documentElement, "sidebar-resizing");
+        const pos = e.clientX - sidebar.offsetLeft - 3;
+        document.documentElement.style.setProperty( "--resizing-sidebar-width", pos + "px");
+        desiredSidebarSize = null;
+    }
+    resizer.addEventListener("pointerdown", initResize, false);
+}());
+
+// This section handles the copy button that appears next to the path breadcrumbs
 (function() {
     let reset_button_timeout = null;
 
diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js
index 48c9a53a2..e824a1fd4 100644
--- a/src/librustdoc/html/static/js/search.js
+++ b/src/librustdoc/html/static/js/search.js
@@ -18,36 +18,38 @@ if (!Array.prototype.toSpliced) {
 // This mapping table should match the discriminants of
 // `rustdoc::formats::item_type::ItemType` type in Rust.
 const itemTypes = [
+    "keyword",
+    "primitive",
     "mod",
     "externcrate",
     "import",
-    "struct",
+    "struct", // 5
     "enum",
     "fn",
     "type",
     "static",
-    "trait",
+    "trait", // 10
     "impl",
     "tymethod",
     "method",
     "structfield",
-    "variant",
+    "variant", // 15
     "macro",
-    "primitive",
     "associatedtype",
     "constant",
     "associatedconstant",
-    "union",
+    "union", // 20
     "foreigntype",
-    "keyword",
     "existential",
     "attr",
     "derive",
-    "traitalias",
+    "traitalias", // 25
     "generic",
 ];
 
 const longItemTypes = [
+    "keyword",
+    "primitive type",
     "module",
     "extern crate",
     "re-export",
@@ -63,13 +65,11 @@ const longItemTypes = [
     "struct field",
     "enum variant",
     "macro",
-    "primitive type",
     "assoc type",
     "constant",
     "assoc const",
     "union",
     "foreign type",
-    "keyword",
     "existential type",
     "attribute macro",
     "derive macro",
@@ -77,15 +77,9 @@ const longItemTypes = [
 ];
 
 // used for special search precedence
-const TY_PRIMITIVE = itemTypes.indexOf("primitive");
-const TY_KEYWORD = itemTypes.indexOf("keyword");
 const TY_GENERIC = itemTypes.indexOf("generic");
 const ROOT_PATH = typeof window !== "undefined" ? window.rootPath : "../";
 
-function hasOwnPropertyRustdoc(obj, property) {
-    return Object.prototype.hasOwnProperty.call(obj, property);
-}
-
 // In the search display, allows to switch between tabs.
 function printTab(nb) {
     let iter = 0;
@@ -240,12 +234,16 @@ function initSearch(rawSearchIndex) {
      *  @type {Array<Row>}
      */
     let searchIndex;
+    /**
+     *  @type {Uint32Array}
+     */
+    let functionTypeFingerprint;
     let currentResults;
     /**
      * Map from normalized type names to integers. Used to make type search
      * more efficient.
      *
-     * @type {Map<string, integer>}
+     * @type {Map<string, {id: integer, assocOnly: boolean}>}
      */
     let typeNameIdMap;
     const ALIASES = new Map();
@@ -272,37 +270,32 @@ function initSearch(rawSearchIndex) {
      * get the same ID.
      *
      * @param {string} name
+     * @param {boolean} isAssocType - True if this is an assoc type
      *
      * @returns {integer}
      */
-    function buildTypeMapIndex(name) {
+    function buildTypeMapIndex(name, isAssocType) {
         if (name === "" || name === null) {
             return null;
         }
 
         if (typeNameIdMap.has(name)) {
-            return typeNameIdMap.get(name);
+            const obj = typeNameIdMap.get(name);
+            obj.assocOnly = isAssocType && obj.assocOnly;
+            return obj.id;
         } else {
             const id = typeNameIdMap.size;
-            typeNameIdMap.set(name, id);
+            typeNameIdMap.set(name, {id, assocOnly: isAssocType});
             return id;
         }
     }
 
-    function isWhitespace(c) {
-        return " \t\n\r".indexOf(c) !== -1;
-    }
-
     function isSpecialStartCharacter(c) {
         return "<\"".indexOf(c) !== -1;
     }
 
     function isEndCharacter(c) {
-        return ",>-]".indexOf(c) !== -1;
-    }
-
-    function isStopCharacter(c) {
-        return isEndCharacter(c);
+        return "=,>-]".indexOf(c) !== -1;
     }
 
     function isErrorCharacter(c) {
@@ -398,7 +391,7 @@ function initSearch(rawSearchIndex) {
      * @return {boolean}
      */
     function isSeparatorCharacter(c) {
-        return c === ",";
+        return c === "," || c === "=";
     }
 
 /**
@@ -410,7 +403,7 @@ function initSearch(rawSearchIndex) {
      * @return {boolean}
      */
     function isPathSeparator(c) {
-        return c === ":" || isWhitespace(c);
+        return c === ":" || c === " ";
     }
 
     /**
@@ -427,7 +420,7 @@ function initSearch(rawSearchIndex) {
             const c = parserState.userQuery[pos - 1];
             if (c === lookingFor) {
                 return true;
-            } else if (!isWhitespace(c)) {
+            } else if (c !== " ") {
                 break;
             }
             pos -= 1;
@@ -456,7 +449,7 @@ function initSearch(rawSearchIndex) {
     function skipWhitespace(parserState) {
         while (parserState.pos < parserState.userQuery.length) {
             const c = parserState.userQuery[parserState.pos];
-            if (!isWhitespace(c)) {
+            if (c !== " ") {
                 break;
             }
             parserState.pos += 1;
@@ -475,8 +468,6 @@ function initSearch(rawSearchIndex) {
         const path = name.trim();
         if (path.length === 0 && generics.length === 0) {
             throw ["Unexpected ", parserState.userQuery[parserState.pos]];
-        } else if (path === "*") {
-            throw ["Unexpected ", "*"];
         }
         if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) {
             throw ["Cannot have more than one element if you use quotes"];
@@ -500,28 +491,30 @@ function initSearch(rawSearchIndex) {
                     " does not accept generic parameters",
                 ];
             }
+            const bindingName = parserState.isInBinding;
+            parserState.isInBinding = null;
             return {
                 name: "never",
                 id: null,
                 fullPath: ["never"],
                 pathWithoutLast: [],
                 pathLast: "never",
+                normalizedPathLast: "never",
                 generics: [],
+                bindings: new Map(),
                 typeFilter: "primitive",
+                bindingName,
             };
         }
+        const quadcolon = /::\s*::/.exec(path);
         if (path.startsWith("::")) {
             throw ["Paths cannot start with ", "::"];
         } else if (path.endsWith("::")) {
             throw ["Paths cannot end with ", "::"];
-        } else if (path.includes("::::")) {
-            throw ["Unexpected ", "::::"];
-        } else if (path.includes(" ::")) {
-            throw ["Unexpected ", " ::"];
-        } else if (path.includes(":: ")) {
-            throw ["Unexpected ", ":: "];
-        }
-        const pathSegments = path.split(/::|\s+/);
+        } else if (quadcolon !== null) {
+            throw ["Unexpected ", quadcolon[0]];
+        }
+        const pathSegments = path.split(/(?:::\s*)|(?:\s+(?:::\s*)?)/);
         // In case we only have something like `<p>`, there is no name.
         if (pathSegments.length === 0 || (pathSegments.length === 1 && pathSegments[0] === "")) {
             if (generics.length > 0 || prevIs(parserState, ">")) {
@@ -542,14 +535,29 @@ function initSearch(rawSearchIndex) {
         if (isInGenerics) {
             parserState.genericsElems += 1;
         }
+        const bindingName = parserState.isInBinding;
+        parserState.isInBinding = null;
+        const bindings = new Map();
+        const pathLast = pathSegments[pathSegments.length - 1];
         return {
             name: name.trim(),
             id: null,
             fullPath: pathSegments,
             pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1),
-            pathLast: pathSegments[pathSegments.length - 1],
-            generics: generics,
+            pathLast,
+            normalizedPathLast: pathLast.replace(/_/g, ""),
+            generics: generics.filter(gen => {
+                // Syntactically, bindings are parsed as generics,
+                // but the query engine treats them differently.
+                if (gen.bindingName !== null) {
+                    bindings.set(gen.bindingName.name, [gen, ...gen.bindingName.generics]);
+                    return false;
+                }
+                return true;
+            }),
+            bindings,
             typeFilter,
+            bindingName,
         };
     }
 
@@ -589,7 +597,7 @@ function initSearch(rawSearchIndex) {
                     } else {
                         while (parserState.pos + 1 < parserState.length) {
                             const next_c = parserState.userQuery[parserState.pos + 1];
-                            if (!isWhitespace(next_c)) {
+                            if (next_c !== " ") {
                                 break;
                             }
                             parserState.pos += 1;
@@ -608,7 +616,7 @@ function initSearch(rawSearchIndex) {
                     }
                 } else if (
                     c === "[" ||
-                    isStopCharacter(c) ||
+                    isEndCharacter(c) ||
                     isSpecialStartCharacter(c) ||
                     isSeparatorCharacter(c)
                 ) {
@@ -657,6 +665,7 @@ function initSearch(rawSearchIndex) {
             parserState.pos += 1;
             getItemsBefore(query, parserState, generics, "]");
             const typeFilter = parserState.typeFilter;
+            const isInBinding = parserState.isInBinding;
             if (typeFilter !== null && typeFilter !== "primitive") {
                 throw [
                     "Invalid search type: primitive ",
@@ -667,18 +676,27 @@ function initSearch(rawSearchIndex) {
                 ];
             }
             parserState.typeFilter = null;
+            parserState.isInBinding = null;
             parserState.totalElems += 1;
             if (isInGenerics) {
                 parserState.genericsElems += 1;
             }
+            for (const gen of generics) {
+                if (gen.bindingName !== null) {
+                    throw ["Type parameter ", "=", " cannot be within slice ", "[]"];
+                }
+            }
             elems.push({
                 name: "[]",
                 id: null,
                 fullPath: ["[]"],
                 pathWithoutLast: [],
                 pathLast: "[]",
+                normalizedPathLast: "[]",
                 generics,
                 typeFilter: "primitive",
+                bindingName: isInBinding,
+                bindings: new Map(),
             });
         } else {
             const isStringElem = parserState.userQuery[start] === "\"";
@@ -705,15 +723,38 @@ function initSearch(rawSearchIndex) {
             if (start >= end && generics.length === 0) {
                 return;
             }
-            elems.push(
-                createQueryElement(
-                    query,
-                    parserState,
-                    parserState.userQuery.slice(start, end),
-                    generics,
-                    isInGenerics
-                )
-            );
+            if (parserState.userQuery[parserState.pos] === "=") {
+                if (parserState.isInBinding) {
+                    throw ["Cannot write ", "=", " twice in a binding"];
+                }
+                if (!isInGenerics) {
+                    throw ["Type parameter ", "=", " must be within generics list"];
+                }
+                const name = parserState.userQuery.slice(start, end).trim();
+                if (name === "!") {
+                    throw ["Type parameter ", "=", " key cannot be ", "!", " never type"];
+                }
+                if (name.includes("!")) {
+                    throw ["Type parameter ", "=", " key cannot be ", "!", " macro"];
+                }
+                if (name.includes("::")) {
+                    throw ["Type parameter ", "=", " key cannot contain ", "::", " path"];
+                }
+                if (name.includes(":")) {
+                    throw ["Type parameter ", "=", " key cannot contain ", ":", " type"];
+                }
+                parserState.isInBinding = { name, generics };
+            } else {
+                elems.push(
+                    createQueryElement(
+                        query,
+                        parserState,
+                        parserState.userQuery.slice(start, end),
+                        generics,
+                        isInGenerics
+                    )
+                );
+            }
         }
     }
 
@@ -737,6 +778,8 @@ function initSearch(rawSearchIndex) {
         // If this is a generic, keep the outer item's type filter around.
         const oldTypeFilter = parserState.typeFilter;
         parserState.typeFilter = null;
+        const oldIsInBinding = parserState.isInBinding;
+        parserState.isInBinding = null;
 
         let extra = "";
         if (endChar === ">") {
@@ -752,6 +795,9 @@ function initSearch(rawSearchIndex) {
         while (parserState.pos < parserState.length) {
             const c = parserState.userQuery[parserState.pos];
             if (c === endChar) {
+                if (parserState.isInBinding) {
+                    throw ["Unexpected ", endChar, " after ", "="];
+                }
                 break;
             } else if (isSeparatorCharacter(c)) {
                 parserState.pos += 1;
@@ -791,7 +837,9 @@ function initSearch(rawSearchIndex) {
                     throw [
                         "Expected ",
                         ",",
-                        " or ",
+                        ", ",
+                        "=",
+                        ", or ",
                         endChar,
                         ...extra,
                         ", found ",
@@ -801,6 +849,8 @@ function initSearch(rawSearchIndex) {
                 throw [
                     "Expected ",
                     ",",
+                    " or ",
+                    "=",
                     ...extra,
                     ", found ",
                     c,
@@ -828,6 +878,7 @@ function initSearch(rawSearchIndex) {
         parserState.pos += 1;
 
         parserState.typeFilter = oldTypeFilter;
+        parserState.isInBinding = oldIsInBinding;
     }
 
     /**
@@ -865,7 +916,7 @@ function initSearch(rawSearchIndex) {
 
         while (parserState.pos < parserState.length) {
             const c = parserState.userQuery[parserState.pos];
-            if (isStopCharacter(c)) {
+            if (isEndCharacter(c)) {
                 foundStopChar = true;
                 if (isSeparatorCharacter(c)) {
                     parserState.pos += 1;
@@ -900,7 +951,7 @@ function initSearch(rawSearchIndex) {
                 query.literalSearch = false;
                 foundStopChar = true;
                 continue;
-            } else if (isWhitespace(c)) {
+            } else if (c === " ") {
                 skipWhitespace(parserState);
                 continue;
             }
@@ -991,6 +1042,8 @@ function initSearch(rawSearchIndex) {
             correction: null,
             proposeCorrectionFrom: null,
             proposeCorrectionTo: null,
+            // bloom filter build from type ids
+            typeFingerprint: new Uint32Array(4),
         };
     }
 
@@ -1021,7 +1074,7 @@ function initSearch(rawSearchIndex) {
 
         if (elem &&
             elem.value !== "all crates" &&
-            hasOwnPropertyRustdoc(rawSearchIndex, elem.value)
+            rawSearchIndex.has(elem.value)
         ) {
             return elem.value;
         }
@@ -1054,8 +1107,13 @@ function initSearch(rawSearchIndex) {
             for (const elem2 of elem.generics) {
                 convertTypeFilterOnElem(elem2);
             }
+            for (const constraints of elem.bindings.values()) {
+                for (const constraint of constraints) {
+                    convertTypeFilterOnElem(constraint);
+                }
+            }
         }
-        userQuery = userQuery.trim();
+        userQuery = userQuery.trim().replace(/\r|\n|\t/g, " ");
         const parserState = {
             length: userQuery.length,
             pos: 0,
@@ -1063,6 +1121,7 @@ function initSearch(rawSearchIndex) {
             totalElems: 0,
             genericsElems: 0,
             typeFilter: null,
+            isInBinding: null,
             userQuery: userQuery.toLowerCase(),
         };
         let query = newParsedQuery(userQuery);
@@ -1080,7 +1139,6 @@ function initSearch(rawSearchIndex) {
             query.error = err;
             return query;
         }
-
         if (!query.literalSearch) {
             // If there is more than one element in the query, we switch to literalSearch in any
             // case.
@@ -1114,13 +1172,12 @@ function initSearch(rawSearchIndex) {
      * Executes the parsed query and builds a {ResultsTable}.
      *
      * @param  {ParsedQuery} parsedQuery - The parsed user query
-     * @param  {Object} searchWords      - The list of search words to query against
      * @param  {Object} [filterCrates]   - Crate to search in if defined
      * @param  {Object} [currentCrate]   - Current crate, to rank results from this crate higher
      *
      * @return {ResultsTable}
      */
-    function execQuery(parsedQuery, searchWords, filterCrates, currentCrate) {
+    function execQuery(parsedQuery, filterCrates, currentCrate) {
         const results_others = new Map(), results_in_args = new Map(),
             results_returned = new Map();
 
@@ -1178,8 +1235,8 @@ function initSearch(rawSearchIndex) {
             const userQuery = parsedQuery.userQuery;
             const result_list = [];
             for (const result of results.values()) {
-                result.word = searchWords[result.id];
-                result.item = searchIndex[result.id] || {};
+                result.item = searchIndex[result.id];
+                result.word = searchIndex[result.id].word;
                 result_list.push(result);
             }
 
@@ -1251,16 +1308,6 @@ function initSearch(rawSearchIndex) {
                     return (a > b ? +1 : -1);
                 }
 
-                // special precedence for primitive and keyword pages
-                if ((aaa.item.ty === TY_PRIMITIVE && bbb.item.ty !== TY_KEYWORD) ||
-                    (aaa.item.ty === TY_KEYWORD && bbb.item.ty !== TY_PRIMITIVE)) {
-                    return -1;
-                }
-                if ((bbb.item.ty === TY_PRIMITIVE && aaa.item.ty !== TY_PRIMITIVE) ||
-                    (bbb.item.ty === TY_KEYWORD && aaa.item.ty !== TY_KEYWORD)) {
-                    return 1;
-                }
-
                 // sort by description (no description goes later)
                 a = (aaa.item.desc === "");
                 b = (bbb.item.desc === "");
@@ -1286,59 +1333,10 @@ function initSearch(rawSearchIndex) {
                 return 0;
             });
 
-            let nameSplit = null;
-            if (parsedQuery.elems.length === 1) {
-                const hasPath = typeof parsedQuery.elems[0].path === "undefined";
-                nameSplit = hasPath ? null : parsedQuery.elems[0].path;
-            }
-
-            for (const result of result_list) {
-                // this validation does not make sense when searching by types
-                if (result.dontValidate) {
-                    continue;
-                }
-                const name = result.item.name.toLowerCase(),
-                    path = result.item.path.toLowerCase(),
-                    parent = result.item.parent;
-
-                if (!isType && !validateResult(name, path, nameSplit, parent)) {
-                    result.id = -1;
-                }
-            }
             return transformResults(result_list);
         }
 
         /**
-         * This function checks generics in search query `queryElem` can all be found in the
-         * search index (`fnType`),
-         *
-         * This function returns `true` if it matches, and also writes the results to mgensInout.
-         * It returns `false` if no match is found, and leaves mgensInout untouched.
-         *
-         * @param {FunctionType} fnType                - The object to check.
-         * @param {QueryElement} queryElem             - The element from the parsed query.
-         * @param {[FunctionType]} whereClause         - Trait bounds for generic items.
-         * @param {Map<number,number>|null} mgensInout - Map functions generics to query generics.
-         *
-         * @return {boolean} - Returns true if a match, false otherwise.
-         */
-        function checkGenerics(fnType, queryElem, whereClause, mgensInout) {
-            return unifyFunctionTypes(
-                fnType.generics,
-                queryElem.generics,
-                whereClause,
-                mgensInout,
-                mgens => {
-                    if (mgensInout) {
-                        for (const [fid, qid] of mgens.entries()) {
-                            mgensInout.set(fid, qid);
-                        }
-                    }
-                    return true;
-                }
-            );
-        }
-        /**
          * This function checks if a list of search query `queryElems` can all be found in the
          * search index (`fnTypes`).
          *
@@ -1348,7 +1346,7 @@ function initSearch(rawSearchIndex) {
          * then this function will try with a different solution, or bail with false if it
          * runs out of candidates.
          *
-         * @param {Array<FunctionType>} fnTypes - The objects to check.
+         * @param {Array<FunctionType>} fnTypesIn - The objects to check.
          * @param {Array<QueryElement>} queryElems - The elements from the parsed query.
          * @param {[FunctionType]} whereClause - Trait bounds for generic items.
          * @param {Map<number,number>|null} mgensIn
@@ -1359,9 +1357,9 @@ function initSearch(rawSearchIndex) {
          */
         function unifyFunctionTypes(fnTypesIn, queryElems, whereClause, mgensIn, solutionCb) {
             /**
-             * @type Map<integer, integer>
+             * @type Map<integer, integer>|null
              */
-            let mgens = new Map(mgensIn);
+            const mgens = mgensIn === null ? null : new Map(mgensIn);
             if (queryElems.length === 0) {
                 return !solutionCb || solutionCb(mgens);
             }
@@ -1369,204 +1367,249 @@ function initSearch(rawSearchIndex) {
                 return false;
             }
             const ql = queryElems.length;
-            let fl = fnTypesIn.length;
+            const fl = fnTypesIn.length;
+
+            // One element fast path / base case
+            if (ql === 1 && queryElems[0].generics.length === 0
+                && queryElems[0].bindings.size === 0) {
+                const queryElem = queryElems[0];
+                for (const fnType of fnTypesIn) {
+                    if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) {
+                        continue;
+                    }
+                    if (fnType.id < 0 && queryElem.id < 0) {
+                        if (mgens && mgens.has(fnType.id) &&
+                            mgens.get(fnType.id) !== queryElem.id) {
+                            continue;
+                        }
+                        const mgensScratch = new Map(mgens);
+                        mgensScratch.set(fnType.id, queryElem.id);
+                        if (!solutionCb || solutionCb(mgensScratch)) {
+                            return true;
+                        }
+                    } else if (!solutionCb || solutionCb(mgens ? new Map(mgens) : null)) {
+                        // unifyFunctionTypeIsMatchCandidate already checks that ids match
+                        return true;
+                    }
+                }
+                for (const fnType of fnTypesIn) {
+                    if (!unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
+                        continue;
+                    }
+                    if (fnType.id < 0) {
+                        if (mgens && mgens.has(fnType.id) &&
+                            mgens.get(fnType.id) !== 0) {
+                            continue;
+                        }
+                        const mgensScratch = new Map(mgens);
+                        mgensScratch.set(fnType.id, 0);
+                        if (unifyFunctionTypes(
+                            whereClause[(-fnType.id) - 1],
+                            queryElems,
+                            whereClause,
+                            mgensScratch,
+                            solutionCb
+                        )) {
+                            return true;
+                        }
+                    } else if (unifyFunctionTypes(
+                        [...fnType.generics, ...Array.from(fnType.bindings.values()).flat() ],
+                        queryElems,
+                        whereClause,
+                        mgens ? new Map(mgens) : null,
+                        solutionCb
+                    )) {
+                        return true;
+                    }
+                }
+                return false;
+            }
+
+            // Multiple element recursive case
             /**
              * @type Array<FunctionType>
              */
-            let fnTypes = fnTypesIn.slice();
+            const fnTypes = fnTypesIn.slice();
             /**
-             * loop works by building up a solution set in the working arrays
+             * Algorithm works by building up a solution set in the working arrays
              * fnTypes gets mutated in place to make this work, while queryElems
-             * is left alone
+             * is left alone.
+             *
+             * It works backwards, because arrays can be cheaply truncated that way.
              *
-             *                                  vvvvvvv `i` points here
-             * queryElems = [ good, good, good, unknown, unknown ],
-             * fnTypes    = [ good, good, good, unknown, unknown ],
-             *                ----------------  ^^^^^^^^^^^^^^^^ `j` iterates after `i`,
-             *                |                                   looking for candidates
-             *                everything before `i` is the
-             *                current working solution
+             *                         vvvvvvv `queryElem`
+             * queryElems = [ unknown, unknown, good, good, good ]
+             * fnTypes    = [ unknown, unknown, good, good, good ]
+             *                ^^^^^^^^^^^^^^^^ loop over these elements to find candidates
              *
              * Everything in the current working solution is known to be a good
              * match, but it might not be the match we wind up going with, because
              * there might be more than one candidate match, and we need to try them all
              * before giving up. So, to handle this, it backtracks on failure.
-             *
-             * @type Array<{
-             *     "fnTypesScratch": Array<FunctionType>,
-             *     "queryElemsOffset": integer,
-             *     "fnTypesOffset": integer
-             * }>
              */
-            const backtracking = [];
-            let i = 0;
-            let j = 0;
-            const backtrack = () => {
-                while (backtracking.length !== 0) {
-                    // this session failed, but there are other possible solutions
-                    // to backtrack, reset to (a copy of) the old array, do the swap or unboxing
-                    const {
-                        fnTypesScratch,
-                        mgensScratch,
-                        queryElemsOffset,
-                        fnTypesOffset,
-                        unbox,
-                    } = backtracking.pop();
-                    mgens = new Map(mgensScratch);
-                    const fnType = fnTypesScratch[fnTypesOffset];
-                    const queryElem = queryElems[queryElemsOffset];
-                    if (unbox) {
-                        if (fnType.id < 0) {
-                            if (mgens.has(fnType.id) && mgens.get(fnType.id) !== 0) {
-                                continue;
-                            }
-                            mgens.set(fnType.id, 0);
-                        }
-                        const generics = fnType.id < 0 ?
-                            whereClause[(-fnType.id) - 1] :
-                            fnType.generics;
-                        fnTypes = fnTypesScratch.toSpliced(fnTypesOffset, 1, ...generics);
-                        fl = fnTypes.length;
-                        // re-run the matching algorithm on this item
-                        i = queryElemsOffset - 1;
-                    } else {
-                        if (fnType.id < 0) {
-                            if (mgens.has(fnType.id) && mgens.get(fnType.id) !== queryElem.id) {
-                                continue;
-                            }
-                            mgens.set(fnType.id, queryElem.id);
-                        }
-                        fnTypes = fnTypesScratch.slice();
-                        fl = fnTypes.length;
-                        const tmp = fnTypes[queryElemsOffset];
-                        fnTypes[queryElemsOffset] = fnTypes[fnTypesOffset];
-                        fnTypes[fnTypesOffset] = tmp;
-                        // this is known as a good match; go to the next one
-                        i = queryElemsOffset;
-                    }
-                    return true;
+            const flast = fl - 1;
+            const qlast = ql - 1;
+            const queryElem = queryElems[qlast];
+            let queryElemsTmp = null;
+            for (let i = flast; i >= 0; i -= 1) {
+                const fnType = fnTypes[i];
+                if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) {
+                    continue;
                 }
-                return false;
-            };
-            for (i = 0; i !== ql; ++i) {
-                const queryElem = queryElems[i];
-                /**
-                 * list of potential function types that go with the current query element.
-                 * @type Array<integer>
-                 */
-                const matchCandidates = [];
-                let fnTypesScratch = null;
-                let mgensScratch = null;
-                // don't try anything before `i`, because they've already been
-                // paired off with the other query elements
-                for (j = i; j !== fl; ++j) {
-                    const fnType = fnTypes[j];
-                    if (unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) {
-                        if (!fnTypesScratch) {
-                            fnTypesScratch = fnTypes.slice();
+                let mgensScratch;
+                if (fnType.id < 0) {
+                    mgensScratch = new Map(mgens);
+                    if (mgensScratch.has(fnType.id)
+                        && mgensScratch.get(fnType.id) !== queryElem.id) {
+                        continue;
+                    }
+                    mgensScratch.set(fnType.id, queryElem.id);
+                } else {
+                    mgensScratch = mgens;
+                }
+                // fnTypes[i] is a potential match
+                // fnTypes[flast] is the last item in the list
+                // swap them, and drop the potential match from the list
+                // check if the remaining function types also match
+                fnTypes[i] = fnTypes[flast];
+                fnTypes.length = flast;
+                if (!queryElemsTmp) {
+                    queryElemsTmp = queryElems.slice(0, qlast);
+                }
+                const passesUnification = unifyFunctionTypes(
+                    fnTypes,
+                    queryElemsTmp,
+                    whereClause,
+                    mgensScratch,
+                    mgensScratch => {
+                        if (fnType.generics.length === 0 && queryElem.generics.length === 0
+                            && fnType.bindings.size === 0 && queryElem.bindings.size === 0) {
+                            return !solutionCb || solutionCb(mgensScratch);
                         }
-                        unifyFunctionTypes(
-                            fnType.generics,
-                            queryElem.generics,
+                        const solution = unifyFunctionTypeCheckBindings(
+                            fnType,
+                            queryElem,
                             whereClause,
-                            mgens,
-                            mgensScratch => {
-                                matchCandidates.push({
-                                    fnTypesScratch,
-                                    mgensScratch,
-                                    queryElemsOffset: i,
-                                    fnTypesOffset: j,
-                                    unbox: false,
-                                });
-                                return false; // "reject" all candidates to gather all of them
-                            }
+                            mgensScratch
                         );
-                    }
-                    if (unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
-                        if (!fnTypesScratch) {
-                            fnTypesScratch = fnTypes.slice();
+                        if (!solution) {
+                            return false;
                         }
-                        if (!mgensScratch) {
-                            mgensScratch = new Map(mgens);
+                        const simplifiedGenerics = solution.simplifiedGenerics;
+                        for (const simplifiedMgens of solution.mgens) {
+                            const passesUnification = unifyFunctionTypes(
+                                simplifiedGenerics,
+                                queryElem.generics,
+                                whereClause,
+                                simplifiedMgens,
+                                solutionCb
+                            );
+                            if (passesUnification) {
+                                return true;
+                            }
                         }
-                        backtracking.push({
-                            fnTypesScratch,
-                            mgensScratch,
-                            queryElemsOffset: i,
-                            fnTypesOffset: j,
-                            unbox: true,
-                        });
-                    }
-                }
-                if (matchCandidates.length === 0) {
-                    if (backtrack()) {
-                        continue;
-                    } else {
                         return false;
                     }
+                );
+                if (passesUnification) {
+                    return true;
                 }
-                // use the current candidate
-                const {fnTypesOffset: candidate, mgensScratch: mgensNew} = matchCandidates.pop();
-                if (fnTypes[candidate].id < 0 && queryElems[i].id < 0) {
-                    mgens.set(fnTypes[candidate].id, queryElems[i].id);
-                }
-                for (const [fid, qid] of mgensNew) {
-                    mgens.set(fid, qid);
-                }
-                // `i` and `j` are paired off
-                // `queryElems[i]` is left in place
-                // `fnTypes[j]` is swapped with `fnTypes[i]` to pair them off
-                const tmp = fnTypes[candidate];
-                fnTypes[candidate] = fnTypes[i];
-                fnTypes[i] = tmp;
-                // write other candidates to backtracking queue
-                for (const otherCandidate of matchCandidates) {
-                    backtracking.push(otherCandidate);
-                }
-                // If we're on the last item, check the solution with the callback
-                // backtrack if the callback says its unsuitable
-                while (i === (ql - 1) && solutionCb && !solutionCb(mgens)) {
-                    if (!backtrack()) {
-                        return false;
+                // backtrack
+                fnTypes[flast] = fnTypes[i];
+                fnTypes[i] = fnType;
+                fnTypes.length = fl;
+            }
+            for (let i = flast; i >= 0; i -= 1) {
+                const fnType = fnTypes[i];
+                if (!unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) {
+                    continue;
+                }
+                let mgensScratch;
+                if (fnType.id < 0) {
+                    mgensScratch = new Map(mgens);
+                    if (mgensScratch.has(fnType.id) && mgensScratch.get(fnType.id) !== 0) {
+                        continue;
                     }
+                    mgensScratch.set(fnType.id, 0);
+                } else {
+                    mgensScratch = mgens;
+                }
+                const generics = fnType.id < 0 ?
+                    whereClause[(-fnType.id) - 1] :
+                    fnType.generics;
+                const bindings = fnType.bindings ?
+                    Array.from(fnType.bindings.values()).flat() :
+                    [];
+                const passesUnification = unifyFunctionTypes(
+                    fnTypes.toSpliced(i, 1, ...generics, ...bindings),
+                    queryElems,
+                    whereClause,
+                    mgensScratch,
+                    solutionCb
+                );
+                if (passesUnification) {
+                    return true;
                 }
             }
-            return true;
+            return false;
         }
-        function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens) {
+        /**
+         * Check if this function is a match candidate.
+         *
+         * This function is all the fast checks that don't require backtracking.
+         * It checks that two items are not named differently, and is load-bearing for that.
+         * It also checks that, if the query has generics, the function type must have generics
+         * or associated type bindings: that's not load-bearing, but it prevents unnecessary
+         * backtracking later.
+         *
+         * @param {FunctionType} fnType
+         * @param {QueryElement} queryElem
+         * @param {[FunctionSearchType]} whereClause - Trait bounds for generic items.
+         * @param {Map<number,number>|null} mgensIn - Map functions generics to query generics.
+         * @returns {boolean}
+         */
+        function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgensIn) {
             // type filters look like `trait:Read` or `enum:Result`
             if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) {
                 return false;
             }
             // fnType.id < 0 means generic
             // queryElem.id < 0 does too
-            // mgens[fnType.id] = queryElem.id
-            // or, if mgens[fnType.id] = 0, then we've matched this generic with a bare trait
+            // mgensIn[fnType.id] = queryElem.id
+            // or, if mgensIn[fnType.id] = 0, then we've matched this generic with a bare trait
             // and should make that same decision everywhere it appears
             if (fnType.id < 0 && queryElem.id < 0) {
-                if (mgens.has(fnType.id) && mgens.get(fnType.id) !== queryElem.id) {
-                    return false;
-                }
-                for (const [fid, qid] of mgens.entries()) {
-                    if (fnType.id !== fid && queryElem.id === qid) {
+                if (mgensIn) {
+                    if (mgensIn.has(fnType.id) && mgensIn.get(fnType.id) !== queryElem.id) {
                         return false;
                     }
-                    if (fnType.id === fid && queryElem.id !== qid) {
-                        return false;
+                    for (const [fid, qid] of mgensIn.entries()) {
+                        if (fnType.id !== fid && queryElem.id === qid) {
+                            return false;
+                        }
+                        if (fnType.id === fid && queryElem.id !== qid) {
+                            return false;
+                        }
                     }
                 }
+                return true;
             } else {
                 if (queryElem.id === typeNameIdOfArrayOrSlice &&
                     (fnType.id === typeNameIdOfSlice || fnType.id === typeNameIdOfArray)
                 ) {
                     // [] matches primitive:array or primitive:slice
                     // if it matches, then we're fine, and this is an appropriate match candidate
-                } else if (fnType.id !== queryElem.id) {
+                } else if (fnType.id !== queryElem.id || queryElem.id === null) {
                     return false;
                 }
                 // If the query elem has generics, and the function doesn't,
                 // it can't match.
-                if (fnType.generics.length === 0 && queryElem.generics.length !== 0) {
+                if ((fnType.generics.length + fnType.bindings.size) === 0 &&
+                    queryElem.generics.length !== 0
+                ) {
+                    return false;
+                }
+                if (fnType.bindings.size < queryElem.bindings.size) {
                     return false;
                 }
                 // If the query element is a path (it contains `::`), we need to check if this
@@ -1595,9 +1638,87 @@ function initSearch(rawSearchIndex) {
                         return false;
                     }
                 }
+                return true;
+            }
+        }
+        /**
+         * This function checks the associated type bindings. Any that aren't matched get converted
+         * to generics, and this function returns an array of the function's generics with these
+         * simplified bindings added to them. That is, it takes a path like this:
+         *
+         *     Iterator<Item=u32>
+         *
+         * ... if queryElem itself has an `Item=` in it, then this function returns an empty array.
+         * But if queryElem contains no Item=, then this function returns a one-item array with the
+         * ID of u32 in it, and the rest of the matching engine acts as if `Iterator<u32>` were
+         * the type instead.
+         *
+         * @param {FunctionType} fnType
+         * @param {QueryElement} queryElem
+         * @param {[FunctionType]} whereClause - Trait bounds for generic items.
+         * @param {Map<number,number>} mgensIn - Map functions generics to query generics.
+         *                                            Never modified.
+         * @returns {false|{mgens: [Map<number,number>], simplifiedGenerics: [FunctionType]}}
+         */
+        function unifyFunctionTypeCheckBindings(fnType, queryElem, whereClause, mgensIn) {
+            if (fnType.bindings.size < queryElem.bindings.size) {
+                return false;
+            }
+            let simplifiedGenerics = fnType.generics || [];
+            if (fnType.bindings.size > 0) {
+                let mgensSolutionSet = [mgensIn];
+                for (const [name, constraints] of queryElem.bindings.entries()) {
+                    if (mgensSolutionSet.length === 0) {
+                        return false;
+                    }
+                    if (!fnType.bindings.has(name)) {
+                        return false;
+                    }
+                    const fnTypeBindings = fnType.bindings.get(name);
+                    mgensSolutionSet = mgensSolutionSet.flatMap(mgens => {
+                        const newSolutions = [];
+                        unifyFunctionTypes(
+                            fnTypeBindings,
+                            constraints,
+                            whereClause,
+                            mgens,
+                            newMgens => {
+                                newSolutions.push(newMgens);
+                                // return `false` makes unifyFunctionTypes return the full set of
+                                // possible solutions
+                                return false;
+                            }
+                        );
+                        return newSolutions;
+                    });
+                }
+                if (mgensSolutionSet.length === 0) {
+                    return false;
+                }
+                const binds = Array.from(fnType.bindings.entries()).flatMap(entry => {
+                    const [name, constraints] = entry;
+                    if (queryElem.bindings.has(name)) {
+                        return [];
+                    } else {
+                        return constraints;
+                    }
+                });
+                if (simplifiedGenerics.length > 0) {
+                    simplifiedGenerics = [...simplifiedGenerics, ...binds];
+                } else {
+                    simplifiedGenerics = binds;
+                }
+                return { simplifiedGenerics, mgens: mgensSolutionSet };
             }
-            return true;
+            return { simplifiedGenerics, mgens: [mgensIn] };
         }
+        /**
+         * @param {FunctionType} fnType
+         * @param {QueryElement} queryElem
+         * @param {[FunctionType]} whereClause - Trait bounds for generic items.
+         * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
+         * @returns {boolean}
+         */
         function unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens) {
             if (fnType.id < 0 && queryElem.id >= 0) {
                 if (!whereClause) {
@@ -1605,16 +1726,29 @@ function initSearch(rawSearchIndex) {
                 }
                 // mgens[fnType.id] === 0 indicates that we committed to unboxing this generic
                 // mgens[fnType.id] === null indicates that we haven't decided yet
-                if (mgens.has(fnType.id) && mgens.get(fnType.id) !== 0) {
+                if (mgens && mgens.has(fnType.id) && mgens.get(fnType.id) !== 0) {
                     return false;
                 }
+                // Where clauses can represent cyclical data.
+                // `null` prevents it from trying to unbox in an infinite loop
+                const mgensTmp = new Map(mgens);
+                mgensTmp.set(fnType.id, null);
                 // This is only a potential unbox if the search query appears in the where clause
                 // for example, searching `Read -> usize` should find
                 // `fn read_all<R: Read>(R) -> Result<usize>`
                 // generic `R` is considered "unboxed"
-                return checkIfInList(whereClause[(-fnType.id) - 1], queryElem, whereClause);
-            } else if (fnType.generics && fnType.generics.length > 0) {
-                return checkIfInList(fnType.generics, queryElem, whereClause);
+                return checkIfInList(
+                    whereClause[(-fnType.id) - 1],
+                    queryElem,
+                    whereClause,
+                    mgensTmp
+                );
+            } else if (fnType.generics.length > 0 || fnType.bindings.size > 0) {
+                const simplifiedGenerics = [
+                    ...fnType.generics,
+                    ...Array.from(fnType.bindings.values()).flat(),
+                ];
+                return checkIfInList(simplifiedGenerics, queryElem, whereClause, mgens);
             }
             return false;
         }
@@ -1626,12 +1760,13 @@ function initSearch(rawSearchIndex) {
           * @param {Array<FunctionType>} list
           * @param {QueryElement} elem          - The element from the parsed query.
           * @param {[FunctionType]} whereClause - Trait bounds for generic items.
+         * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
           *
           * @return {boolean} - Returns true if found, false otherwise.
           */
-        function checkIfInList(list, elem, whereClause) {
+        function checkIfInList(list, elem, whereClause, mgens) {
             for (const entry of list) {
-                if (checkType(entry, elem, whereClause)) {
+                if (checkType(entry, elem, whereClause, mgens)) {
                     return true;
                 }
             }
@@ -1645,42 +1780,29 @@ function initSearch(rawSearchIndex) {
           * @param {Row} row
           * @param {QueryElement} elem          - The element from the parsed query.
           * @param {[FunctionType]} whereClause - Trait bounds for generic items.
+         * @param {Map<number,number>|null} mgens - Map functions generics to query generics.
           *
           * @return {boolean} - Returns true if the type matches, false otherwise.
           */
-        function checkType(row, elem, whereClause) {
-            if (row.id === null) {
-                // This is a pure "generic" search, no need to run other checks.
-                return row.generics.length > 0
-                    ? checkIfInList(row.generics, elem, whereClause)
-                    : false;
-            }
-
-            if (row.id < 0 && elem.id >= 0) {
-                const gid = (-row.id) - 1;
-                return checkIfInList(whereClause[gid], elem, whereClause);
-            }
-
-            if (row.id < 0 && elem.id < 0) {
-                return true;
-            }
-
-            const matchesExact = row.id === elem.id;
-            const matchesArrayOrSlice = elem.id === typeNameIdOfArrayOrSlice &&
-                (row.id === typeNameIdOfSlice || row.id === typeNameIdOfArray);
-
-            if ((matchesExact || matchesArrayOrSlice) &&
-                typePassesFilter(elem.typeFilter, row.ty)) {
-                if (elem.generics.length > 0) {
-                    return checkGenerics(row, elem, whereClause, new Map());
+        function checkType(row, elem, whereClause, mgens) {
+            if (row.bindings.size === 0 && elem.bindings.size === 0) {
+                if (elem.id < 0) {
+                    return row.id < 0 || checkIfInList(row.generics, elem, whereClause, mgens);
+                }
+                if (row.id > 0 && elem.id > 0 && elem.pathWithoutLast.length === 0 &&
+                    typePassesFilter(elem.typeFilter, row.ty) && elem.generics.length === 0 &&
+                    // special case
+                    elem.id !== typeNameIdOfArrayOrSlice
+                ) {
+                    return row.id === elem.id || checkIfInList(
+                        row.generics,
+                        elem,
+                        whereClause,
+                        mgens
+                    );
                 }
-                return true;
             }
-
-            // If the current item does not match, try [unboxing] the generic.
-            // [unboxing]:
-            //   https://ndmitchell.com/downloads/slides-hoogle_fast_type_searching-09_aug_2008.pdf
-            return checkIfInList(row.generics, elem, whereClause);
+            return unifyFunctionTypes([row], [elem], whereClause, mgens);
         }
 
         function checkPath(contains, ty, maxEditDistance) {
@@ -1696,26 +1818,16 @@ function initSearch(rawSearchIndex) {
 
             const length = path.length;
             const clength = contains.length;
-            if (clength > length) {
-                return maxEditDistance + 1;
-            }
-            for (let i = 0; i < length; ++i) {
-                if (i + clength > length) {
-                    break;
-                }
+            pathiter: for (let i = length - clength; i >= 0; i -= 1) {
                 let dist_total = 0;
-                let aborted = false;
                 for (let x = 0; x < clength; ++x) {
                     const dist = editDistance(path[i + x], contains[x], maxEditDistance);
                     if (dist > maxEditDistance) {
-                        aborted = true;
-                        break;
+                        continue pathiter;
                     }
                     dist_total += dist;
                 }
-                if (!aborted) {
-                    ret_dist = Math.min(ret_dist, Math.round(dist_total / clength));
-                }
+                ret_dist = Math.min(ret_dist, Math.round(dist_total / clength));
             }
             return ret_dist;
         }
@@ -1819,7 +1931,7 @@ function initSearch(rawSearchIndex) {
          * 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.
+         * * `id` is the index in the `searchIndex` array for this element.
          * * `index` is an `integer`` used to sort by the position of the word in the item's name.
          * * `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
@@ -1833,8 +1945,7 @@ function initSearch(rawSearchIndex) {
          * @param {integer} path_dist
          */
         function addIntoResults(results, fullId, id, index, dist, path_dist, maxEditDistance) {
-            const inBounds = dist <= maxEditDistance || index !== -1;
-            if (dist === 0 || (!parsedQuery.literalSearch && inBounds)) {
+            if (dist <= maxEditDistance || index !== -1) {
                 if (results.has(fullId)) {
                     const result = results.get(fullId);
                     if (result.dontValidate || result.dist <= dist) {
@@ -1878,40 +1989,44 @@ function initSearch(rawSearchIndex) {
             if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
                 return;
             }
-            let index = -1, path_dist = 0;
+            let path_dist = 0;
             const fullId = row.id;
-            const searchWord = searchWords[pos];
 
-            const in_args = row.type && row.type.inputs
-                && checkIfInList(row.type.inputs, elem, row.type.where_clause);
-            if (in_args) {
-                // path_dist is 0 because no parent path information is currently stored
-                // in the search index
-                addIntoResults(results_in_args, fullId, pos, -1, 0, 0, maxEditDistance);
-            }
-            const returned = row.type && row.type.output
-                && checkIfInList(row.type.output, elem, row.type.where_clause);
-            if (returned) {
-                addIntoResults(results_returned, fullId, pos, -1, 0, 0, maxEditDistance);
+            // fpDist is a minimum possible type distance, where "type distance" is the number of
+            // atoms in the function not present in the query
+            const tfpDist = compareTypeFingerprints(
+                fullId,
+                parsedQuery.typeFingerprint
+            );
+            if (tfpDist !== null) {
+                const in_args = row.type && row.type.inputs
+                    && checkIfInList(row.type.inputs, elem, row.type.where_clause);
+                const returned = row.type && row.type.output
+                    && checkIfInList(row.type.output, elem, row.type.where_clause);
+                if (in_args) {
+                    results_in_args.max_dist = Math.max(results_in_args.max_dist || 0, tfpDist);
+                    const maxDist = results_in_args.size < MAX_RESULTS ?
+                        (tfpDist + 1) :
+                        results_in_args.max_dist;
+                    addIntoResults(results_in_args, fullId, pos, -1, tfpDist, 0, maxDist);
+                }
+                if (returned) {
+                    results_returned.max_dist = Math.max(results_returned.max_dist || 0, tfpDist);
+                    const maxDist = results_returned.size < MAX_RESULTS ?
+                        (tfpDist + 1) :
+                        results_returned.max_dist;
+                    addIntoResults(results_returned, fullId, pos, -1, tfpDist, 0, maxDist);
+                }
             }
 
             if (!typePassesFilter(elem.typeFilter, row.ty)) {
                 return;
             }
 
-            const row_index = row.normalizedName.indexOf(elem.pathLast);
-            const word_index = searchWord.indexOf(elem.pathLast);
-
-            // lower indexes are "better" matches
-            // rank based on the "best" match
-            if (row_index === -1) {
-                index = word_index;
-            } else if (word_index === -1) {
-                index = row_index;
-            } else if (word_index < row_index) {
-                index = word_index;
-            } else {
-                index = row_index;
+            let index = row.word.indexOf(elem.pathLast);
+            const normalizedIndex = row.normalizedName.indexOf(elem.pathLast);
+            if (index === -1 || (index > normalizedIndex && normalizedIndex !== -1)) {
+                index = normalizedIndex;
             }
 
             if (elem.fullPath.length > 1) {
@@ -1922,13 +2037,13 @@ function initSearch(rawSearchIndex) {
             }
 
             if (parsedQuery.literalSearch) {
-                if (searchWord === elem.name) {
+                if (row.word === elem.pathLast) {
                     addIntoResults(results_others, fullId, pos, index, 0, path_dist);
                 }
                 return;
             }
 
-            const dist = editDistance(searchWord, elem.pathLast, maxEditDistance);
+            const dist = editDistance(row.normalizedName, elem.normalizedPathLast, maxEditDistance);
 
             if (index === -1 && dist + path_dist > maxEditDistance) {
                 return;
@@ -1951,6 +2066,17 @@ function initSearch(rawSearchIndex) {
                 return;
             }
 
+            const tfpDist = compareTypeFingerprints(
+                row.id,
+                parsedQuery.typeFingerprint
+            );
+            if (tfpDist === null) {
+                return;
+            }
+            if (results.size >= MAX_RESULTS && tfpDist > results.max_dist) {
+                return;
+            }
+
             // If the result is too "bad", we return false and it ends this search.
             if (!unifyFunctionTypes(
                 row.type.inputs,
@@ -1969,12 +2095,11 @@ function initSearch(rawSearchIndex) {
                 return;
             }
 
-            addIntoResults(results, row.id, pos, 0, 0, 0, Number.MAX_VALUE);
+            results.max_dist = Math.max(results.max_dist || 0, tfpDist);
+            addIntoResults(results, row.id, pos, 0, tfpDist, 0, Number.MAX_VALUE);
         }
 
         function innerRunQuery() {
-            let elem, i, nSearchWords, in_returned, row;
-
             let queryLen = 0;
             for (const elem of parsedQuery.elems) {
                 queryLen += elem.name.length;
@@ -2000,17 +2125,20 @@ function initSearch(rawSearchIndex) {
              * See `buildTypeMapIndex` for more information.
              *
              * @param {QueryElement} elem
+             * @param {boolean} isAssocType
              */
-            function convertNameToId(elem) {
-                if (typeNameIdMap.has(elem.pathLast)) {
-                    elem.id = typeNameIdMap.get(elem.pathLast);
+            function convertNameToId(elem, isAssocType) {
+                if (typeNameIdMap.has(elem.normalizedPathLast) &&
+                    (isAssocType || !typeNameIdMap.get(elem.normalizedPathLast).assocOnly)) {
+                    elem.id = typeNameIdMap.get(elem.normalizedPathLast).id;
                 } else if (!parsedQuery.literalSearch) {
                     let match = null;
                     let matchDist = maxEditDistance + 1;
                     let matchName = "";
-                    for (const [name, id] of typeNameIdMap) {
-                        const dist = editDistance(name, elem.pathLast, maxEditDistance);
-                        if (dist <= matchDist && dist <= maxEditDistance) {
+                    for (const [name, {id, assocOnly}] of typeNameIdMap) {
+                        const dist = editDistance(name, elem.normalizedPathLast, maxEditDistance);
+                        if (dist <= matchDist && dist <= maxEditDistance &&
+                            (isAssocType || !assocOnly)) {
                             if (dist === matchDist && matchName > name) {
                                 continue;
                             }
@@ -2025,7 +2153,7 @@ function initSearch(rawSearchIndex) {
                     elem.id = match;
                 }
                 if ((elem.id === null && parsedQuery.totalElems > 1 && elem.typeFilter === -1
-                     && elem.generics.length === 0)
+                     && elem.generics.length === 0 && elem.bindings.size === 0)
                     || elem.typeFilter === TY_GENERIC) {
                     if (genericSymbols.has(elem.name)) {
                         elem.id = genericSymbols.get(elem.name);
@@ -2068,19 +2196,40 @@ function initSearch(rawSearchIndex) {
                 for (const elem2 of elem.generics) {
                     convertNameToId(elem2);
                 }
+                elem.bindings = new Map(Array.from(elem.bindings.entries())
+                    .map(entry => {
+                        const [name, constraints] = entry;
+                        if (!typeNameIdMap.has(name)) {
+                            parsedQuery.error = [
+                                "Type parameter ",
+                                name,
+                                " does not exist",
+                            ];
+                            return [null, []];
+                        }
+                        for (const elem2 of constraints) {
+                            convertNameToId(elem2);
+                        }
+
+                        return [typeNameIdMap.get(name).id, constraints];
+                    })
+                );
             }
 
+            const fps = new Set();
             for (const elem of parsedQuery.elems) {
                 convertNameToId(elem);
+                buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps);
             }
             for (const elem of parsedQuery.returned) {
                 convertNameToId(elem);
+                buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps);
             }
 
-            if (parsedQuery.foundElems === 1) {
+            if (parsedQuery.foundElems === 1 && parsedQuery.returned.length === 0) {
                 if (parsedQuery.elems.length === 1) {
-                    elem = parsedQuery.elems[0];
-                    for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
+                    const elem = parsedQuery.elems[0];
+                    for (let i = 0, nSearchIndex = searchIndex.length; i < nSearchIndex; ++i) {
                         // It means we want to check for this element everywhere (in names, args and
                         // returned).
                         handleSingleArg(
@@ -2093,30 +2242,25 @@ function initSearch(rawSearchIndex) {
                             maxEditDistance
                         );
                     }
-                } else if (parsedQuery.returned.length === 1) {
-                    // We received one returned argument to check, so looking into returned values.
-                    elem = parsedQuery.returned[0];
-                    for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
-                        row = searchIndex[i];
-                        in_returned = row.type && unifyFunctionTypes(
-                            row.type.output,
-                            parsedQuery.returned,
-                            row.type.where_clause
-                        );
-                        if (in_returned) {
-                            addIntoResults(
-                                results_others,
-                                row.id,
-                                i,
-                                -1,
-                                0,
-                                Number.MAX_VALUE
-                            );
-                        }
-                    }
                 }
             } else if (parsedQuery.foundElems > 0) {
-                for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
+                // Sort input and output so that generic type variables go first and
+                // types with generic parameters go last.
+                // That's because of the way unification is structured: it eats off
+                // the end, and hits a fast path if the last item is a simple atom.
+                const sortQ = (a, b) => {
+                    const ag = a.generics.length === 0 && a.bindings.size === 0;
+                    const bg = b.generics.length === 0 && b.bindings.size === 0;
+                    if (ag !== bg) {
+                        return ag - bg;
+                    }
+                    const ai = a.id > 0;
+                    const bi = b.id > 0;
+                    return ai - bi;
+                };
+                parsedQuery.elems.sort(sortQ);
+                parsedQuery.returned.sort(sortQ);
+                for (let i = 0, nSearchIndex = searchIndex.length; i < nSearchIndex; ++i) {
                     handleArgs(searchIndex[i], i, results_others);
                 }
             }
@@ -2139,44 +2283,6 @@ function initSearch(rawSearchIndex) {
         return ret;
     }
 
-    /**
-     * Validate performs the following boolean logic. For example:
-     * "File::open" will give IF A PARENT EXISTS => ("file" && "open")
-     * exists in (name || path || parent) OR => ("file" && "open") exists in
-     * (name || path )
-     *
-     * This could be written functionally, but I wanted to minimise
-     * functions on stack.
-     *
-     * @param  {string} name   - The name of the result
-     * @param  {string} path   - The path of the result
-     * @param  {string} keys   - The keys to be used (["file", "open"])
-     * @param  {Object} parent - The parent of the result
-     *
-     * @return {boolean}       - Whether the result is valid or not
-     */
-    function validateResult(name, path, keys, parent, maxEditDistance) {
-        if (!keys || !keys.length) {
-            return true;
-        }
-        for (const key of keys) {
-            // each check is for validation so we negate the conditions and invalidate
-            if (!(
-                // check for an exact name match
-                name.indexOf(key) > -1 ||
-                // then an exact path match
-                path.indexOf(key) > -1 ||
-                // 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 an editDistance match
-                editDistance(name, key, maxEditDistance) <= maxEditDistance)) {
-                return false;
-            }
-        }
-        return true;
-    }
-
     function nextTab(direction) {
         const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length;
         searchState.focusedByTab[searchState.currentTab] = document.activeElement;
@@ -2269,13 +2375,9 @@ function initSearch(rawSearchIndex) {
      * @param {boolean}     display - True if this is the active tab
      */
     function addTab(array, query, display) {
-        let extraClass = "";
-        if (display === true) {
-            extraClass = " active";
-        }
+        const extraClass = display ? " active" : "";
 
         const output = document.createElement("div");
-        let length = 0;
         if (array.length > 0) {
             output.className = "search-results " + extraClass;
 
@@ -2285,8 +2387,6 @@ function initSearch(rawSearchIndex) {
                 const longType = longItemTypes[item.ty];
                 const typeName = longType.length !== 0 ? `${longType}` : "?";
 
-                length += 1;
-
                 const link = document.createElement("a");
                 link.className = "result-" + type;
                 link.href = item.href;
@@ -2334,7 +2434,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                 "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" +
                 " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>";
         }
-        return [output, length];
+        return [output, array.length];
     }
 
     function makeTabHeader(tabNb, text, nbElems) {
@@ -2413,11 +2513,10 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         }
 
         let crates = "";
-        const crates_list = Object.keys(rawSearchIndex);
-        if (crates_list.length > 1) {
+        if (rawSearchIndex.size > 1) {
             crates = " in&nbsp;<div id=\"crate-search-div\"><select id=\"crate-search\">" +
                 "<option value=\"all crates\">all crates</option>";
-            for (const c of crates_list) {
+            for (const c of rawSearchIndex.keys()) {
                 crates += `<option value="${c}" ${c === filterCrates && "selected"}>${c}</option>`;
             }
             crates += "</select></div>";
@@ -2514,13 +2613,9 @@ ${item.displayPath}<span class="${type}">${name}</span>\
     /**
      * Perform a search based on the current state of the search input element
      * and display the results.
-     * @param {Event}   [e]       - The event that triggered this search, if any
      * @param {boolean} [forced]
      */
-    function search(e, forced) {
-        if (e) {
-            e.preventDefault();
-        }
+    function search(forced) {
         const query = parseQuery(searchState.input.value.trim());
         let filterCrates = getFilterCrates();
 
@@ -2549,7 +2644,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         updateSearchHistory(buildUrl(query.original, filterCrates));
 
         showResults(
-            execQuery(query, searchWords, filterCrates, window.currentCrate),
+            execQuery(query, filterCrates, window.currentCrate),
             params.go_to_first,
             filterCrates);
     }
@@ -2581,19 +2676,42 @@ ${item.displayPath}<span class="${type}">${name}</span>\
      *
      * @param {RawFunctionType} type
      */
-    function buildItemSearchType(type, lowercasePaths) {
+    function buildItemSearchType(type, lowercasePaths, isAssocType) {
         const PATH_INDEX_DATA = 0;
         const GENERICS_DATA = 1;
-        let pathIndex, generics;
+        const BINDINGS_DATA = 2;
+        let pathIndex, generics, bindings;
         if (typeof type === "number") {
             pathIndex = type;
             generics = [];
+            bindings = new Map();
         } else {
             pathIndex = type[PATH_INDEX_DATA];
             generics = buildItemSearchTypeAll(
                 type[GENERICS_DATA],
                 lowercasePaths
             );
+            if (type.length > BINDINGS_DATA) {
+                bindings = new Map(type[BINDINGS_DATA].map(binding => {
+                    const [assocType, constraints] = binding;
+                    // Associated type constructors are represented sloppily in rustdoc's
+                    // type search, to make the engine simpler.
+                    //
+                    // MyType<Output<T>=Result<T>> is equivalent to MyType<Output<Result<T>>=T>
+                    // and both are, essentially
+                    // MyType<Output=(T, Result<T>)>, except the tuple isn't actually there.
+                    // It's more like the value of a type binding is naturally an array,
+                    // which rustdoc calls "constraints".
+                    //
+                    // As a result, the key should never have generics on it.
+                    return [
+                        buildItemSearchType(assocType, lowercasePaths, true).id,
+                        buildItemSearchTypeAll(constraints, lowercasePaths),
+                    ];
+                }));
+            } else {
+                bindings = new Map();
+            }
         }
         if (pathIndex < 0) {
             // types less than 0 are generic parameters
@@ -2603,6 +2721,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                 ty: TY_GENERIC,
                 path: null,
                 generics,
+                bindings,
             };
         }
         if (pathIndex === 0) {
@@ -2612,14 +2731,16 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                 ty: null,
                 path: null,
                 generics,
+                bindings,
             };
         }
         const item = lowercasePaths[pathIndex - 1];
         return {
-            id: buildTypeMapIndex(item.name),
+            id: buildTypeMapIndex(item.name, isAssocType),
             ty: item.ty,
             path: item.path,
             generics,
+            bindings,
         };
     }
 
@@ -2679,14 +2800,119 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         };
     }
 
+    /**
+     * Type fingerprints allow fast, approximate matching of types.
+     *
+     * This algo creates a compact representation of the type set using a Bloom filter.
+     * This fingerprint is used three ways:
+     *
+     * - It accelerates the matching algorithm by checking the function fingerprint against the
+     *   query fingerprint. If any bits are set in the query but not in the function, it can't
+     *   match.
+     *
+     * - The fourth section has the number of distinct items in the set.
+     *   This is the distance function, used for filtering and for sorting.
+     *
+     * [^1]: Distance is the relatively naive metric of counting the number of distinct items in
+     * the function that are not present in the query.
+     *
+     * @param {FunctionType|QueryElement} type - a single type
+     * @param {Uint32Array} output - write the fingerprint to this data structure: uses 128 bits
+     * @param {Set<number>} fps - Set of distinct items
+     */
+    function buildFunctionTypeFingerprint(type, output, fps) {
+        let input = type.id;
+        // All forms of `[]` get collapsed down to one thing in the bloom filter.
+        // Differentiating between arrays and slices, if the user asks for it, is
+        // still done in the matching algorithm.
+        if (input === typeNameIdOfArray || input === typeNameIdOfSlice) {
+            input = typeNameIdOfArrayOrSlice;
+        }
+        // http://burtleburtle.net/bob/hash/integer.html
+        // ~~ is toInt32. It's used before adding, so
+        // the number stays in safe integer range.
+        const hashint1 = k => {
+            k = (~~k + 0x7ed55d16) + (k << 12);
+            k = (k ^ 0xc761c23c) ^ (k >>> 19);
+            k = (~~k + 0x165667b1) + (k << 5);
+            k = (~~k + 0xd3a2646c) ^ (k << 9);
+            k = (~~k + 0xfd7046c5) + (k << 3);
+            return (k ^ 0xb55a4f09) ^ (k >>> 16);
+        };
+        const hashint2 = k => {
+            k = ~k + (k << 15);
+            k ^= k >>> 12;
+            k += k << 2;
+            k ^= k >>> 4;
+            k = Math.imul(k, 2057);
+            return k ^ (k >> 16);
+        };
+        if (input !== null) {
+            const h0a = hashint1(input);
+            const h0b = hashint2(input);
+            // Less Hashing, Same Performance: Building a Better Bloom Filter
+            // doi=10.1.1.72.2442
+            const h1a = ~~(h0a + Math.imul(h0b, 2));
+            const h1b = ~~(h0a + Math.imul(h0b, 3));
+            const h2a = ~~(h0a + Math.imul(h0b, 4));
+            const h2b = ~~(h0a + Math.imul(h0b, 5));
+            output[0] |= (1 << (h0a % 32)) | (1 << (h1b % 32));
+            output[1] |= (1 << (h1a % 32)) | (1 << (h2b % 32));
+            output[2] |= (1 << (h2a % 32)) | (1 << (h0b % 32));
+            fps.add(input);
+        }
+        for (const g of type.generics) {
+            buildFunctionTypeFingerprint(g, output, fps);
+        }
+        const fb = {
+            id: null,
+            ty: 0,
+            generics: [],
+            bindings: new Map(),
+        };
+        for (const [k, v] of type.bindings.entries()) {
+            fb.id = k;
+            fb.generics = v;
+            buildFunctionTypeFingerprint(fb, output, fps);
+        }
+        output[3] = fps.size;
+    }
+
+    /**
+     * Compare the query fingerprint with the function fingerprint.
+     *
+     * @param {{number}} fullId - The function
+     * @param {{Uint32Array}} queryFingerprint - The query
+     * @returns {number|null} - Null if non-match, number if distance
+     *                          This function might return 0!
+     */
+    function compareTypeFingerprints(fullId, queryFingerprint) {
+        const fh0 = functionTypeFingerprint[fullId * 4];
+        const fh1 = functionTypeFingerprint[(fullId * 4) + 1];
+        const fh2 = functionTypeFingerprint[(fullId * 4) + 2];
+        const [qh0, qh1, qh2] = queryFingerprint;
+        // Approximate set intersection with bloom filters.
+        // This can be larger than reality, not smaller, because hashes have
+        // the property that if they've got the same value, they hash to the
+        // same thing. False positives exist, but not false negatives.
+        const [in0, in1, in2] = [fh0 & qh0, fh1 & qh1, fh2 & qh2];
+        // Approximate the set of items in the query but not the function.
+        // This might be smaller than reality, but cannot be bigger.
+        //
+        // | in_ | qh_ | XOR | Meaning                                          |
+        // | --- | --- | --- | ------------------------------------------------ |
+        // |  0  |  0  |  0  | Not present                                      |
+        // |  1  |  0  |  1  | IMPOSSIBLE because `in_` is `fh_ & qh_`          |
+        // |  1  |  1  |  0  | If one or both is false positive, false negative |
+        // |  0  |  1  |  1  | Since in_ has no false negatives, must be real   |
+        if ((in0 ^ qh0) || (in1 ^ qh1) || (in2 ^ qh2)) {
+            return null;
+        }
+        return functionTypeFingerprint[(fullId * 4) + 3];
+    }
+
     function buildIndex(rawSearchIndex) {
         searchIndex = [];
-        /**
-         * List of normalized search words (ASCII lowercased, and undescores removed).
-         *
-         * @type {Array<string>}
-         */
-        const searchWords = [];
         typeNameIdMap = new Map();
         const charA = "A".charCodeAt(0);
         let currentIndex = 0;
@@ -2698,81 +2924,86 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         typeNameIdOfSlice = buildTypeMapIndex("slice");
         typeNameIdOfArrayOrSlice = buildTypeMapIndex("[]");
 
-        for (const crate in rawSearchIndex) {
-            if (!hasOwnPropertyRustdoc(rawSearchIndex, crate)) {
-                continue;
-            }
-
-            let crateSize = 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>
-             * }}
-             */
-            const crateCorpus = rawSearchIndex[crate];
+        // Function type fingerprints are 128-bit bloom filters that are used to
+        // estimate the distance between function and query.
+        // This loop counts the number of items to allocate a fingerprint for.
+        for (const crate of rawSearchIndex.values()) {
+            // Each item gets an entry in the fingerprint array, and the crate
+            // does, too
+            id += crate.t.length + 1;
+        }
+        functionTypeFingerprint = new Uint32Array((id + 1) * 4);
 
-            searchWords.push(crate);
+        // 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.
             // https://mathiasbynens.be/notes/shapes-ics
             const crateRow = {
                 crate: crate,
-                ty: 1, // == ExternCrate
+                ty: 3, // == ExternCrate
                 name: crate,
                 path: "",
                 desc: crateCorpus.doc,
                 parent: undefined,
                 type: null,
                 id: id,
+                word: crate,
                 normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""),
                 deprecated: null,
                 implDisambiguator: null,
@@ -2840,13 +3071,34 @@ ${item.displayPath}<span class="${type}">${name}</span>\
             len = itemTypes.length;
             for (let i = 0; i < len; ++i) {
                 let word = "";
-                // This object should have exactly the same set of fields as the "crateRow"
-                // object defined above.
                 if (typeof itemNames[i] === "string") {
                     word = itemNames[i].toLowerCase();
                 }
-                searchWords.push(word);
                 const path = itemPaths.has(i) ? itemPaths.get(i) : lastPath;
+                let type = null;
+                if (itemFunctionSearchTypes[i] !== 0) {
+                    type = buildFunctionSearchType(
+                        itemFunctionSearchTypes[i],
+                        lowercasePaths
+                    );
+                    if (type) {
+                        const fp = functionTypeFingerprint.subarray(id * 4, (id + 1) * 4);
+                        const fps = new Set();
+                        for (const t of type.inputs) {
+                            buildFunctionTypeFingerprint(t, fp, fps);
+                        }
+                        for (const t of type.output) {
+                            buildFunctionTypeFingerprint(t, fp, fps);
+                        }
+                        for (const w of type.where_clause) {
+                            for (const t of w) {
+                                buildFunctionTypeFingerprint(t, fp, fps);
+                            }
+                        }
+                    }
+                }
+                // This object should have exactly the same set of fields as the "crateRow"
+                // object defined above.
                 const row = {
                     crate: crate,
                     ty: itemTypes.charCodeAt(i) - charA,
@@ -2854,11 +3106,9 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                     path: path,
                     desc: itemDescs[i],
                     parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
-                    type: buildFunctionSearchType(
-                        itemFunctionSearchTypes[i],
-                        lowercasePaths
-                    ),
+                    type,
                     id: id,
+                    word,
                     normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
                     deprecated: deprecatedItems.has(i),
                     implDisambiguator: implDisambiguator.has(i) ? implDisambiguator.get(i) : null,
@@ -2866,14 +3116,13 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                 id += 1;
                 searchIndex.push(row);
                 lastPath = row.path;
-                crateSize += 1;
             }
 
             if (aliases) {
                 const currentCrateAliases = new Map();
                 ALIASES.set(crate, currentCrateAliases);
                 for (const alias_name in aliases) {
-                    if (!hasOwnPropertyRustdoc(aliases, alias_name)) {
+                    if (!Object.prototype.hasOwnProperty.call(aliases, alias_name)) {
                         continue;
                     }
 
@@ -2889,9 +3138,8 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                     }
                 }
             }
-            currentIndex += crateSize;
+            currentIndex += itemTypes.length;
         }
-        return searchWords;
     }
 
     /**
@@ -3031,7 +3279,8 @@ ${item.displayPath}<span class="${type}">${name}</span>\
                     // popping a state (Firefox), which is why search() is
                     // called both here and at the end of the startSearch()
                     // function.
-                    search(e);
+                    e.preventDefault();
+                    search();
                 } else {
                     searchState.input.value = "";
                     // When browsing back from search results the main page
@@ -3066,13 +3315,10 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         // before paste back the previous search, you get the old search results without
         // the filter. To prevent this, we need to remove the previous results.
         currentResults = null;
-        search(undefined, true);
+        search(true);
     }
 
-    /**
-     *  @type {Array<string>}
-     */
-    const searchWords = buildIndex(rawSearchIndex);
+    buildIndex(rawSearchIndex);
     if (typeof window !== "undefined") {
         registerSearchEvents();
         // If there's a search term in the URL, execute the search now.
@@ -3086,7 +3332,6 @@ ${item.displayPath}<span class="${type}">${name}</span>\
         exports.execQuery = execQuery;
         exports.parseQuery = parseQuery;
     }
-    return searchWords;
 }
 
 if (typeof window !== "undefined") {
@@ -3097,7 +3342,7 @@ if (typeof window !== "undefined") {
 } else {
     // Running in Node, not a browser. Run initSearch just to produce the
     // exports.
-    initSearch({});
+    initSearch(new Map());
 }
 
 
diff --git a/src/librustdoc/html/static/js/settings.js b/src/librustdoc/html/static/js/settings.js
index 63947789c..2b42fbebb 100644
--- a/src/librustdoc/html/static/js/settings.js
+++ b/src/librustdoc/html/static/js/settings.js
@@ -1,6 +1,6 @@
 // Local js definitions:
 /* global getSettingValue, updateLocalStorage, updateTheme */
-/* global addClass, removeClass, onEach, onEachLazy, blurHandler, elemIsInParent */
+/* global addClass, removeClass, onEach, onEachLazy, blurHandler */
 /* global MAIN_ID, getVar, getSettingsButton */
 
 "use strict";
@@ -29,6 +29,13 @@
                     window.rustdoc_remove_line_numbers_from_examples();
                 }
                 break;
+            case "hide-sidebar":
+                if (value === true) {
+                    addClass(document.documentElement, "hide-sidebar");
+                } else {
+                    removeClass(document.documentElement, "hide-sidebar");
+                }
+                break;
         }
     }
 
@@ -187,6 +194,11 @@
                 "default": false,
             },
             {
+                "name": "Hide persistent navigation bar",
+                "js_name": "hide-sidebar",
+                "default": false,
+            },
+            {
                 "name": "Disable keyboard shortcuts",
                 "js_name": "disable-shortcuts",
                 "default": false,
@@ -216,6 +228,13 @@
 
     function displaySettings() {
         settingsMenu.style.display = "";
+        onEachLazy(settingsMenu.querySelectorAll("input[type='checkbox']"), el => {
+            const val = getSettingValue(el.id);
+            const checked = val === "true";
+            if (checked !== el.checked && val !== null) {
+                el.checked = checked;
+            }
+        });
     }
 
     function settingsBlurHandler(event) {
@@ -232,7 +251,7 @@
         const settingsButton = getSettingsButton();
         const settingsMenu = document.getElementById("settings");
         settingsButton.onclick = event => {
-            if (elemIsInParent(event.target, settingsMenu)) {
+            if (settingsMenu.contains(event.target)) {
                 return;
             }
             event.preventDefault();
diff --git a/src/librustdoc/html/static/js/src-script.js b/src/librustdoc/html/static/js/src-script.js
index 679c2341f..fc1d2d378 100644
--- a/src/librustdoc/html/static/js/src-script.js
+++ b/src/librustdoc/html/static/js/src-script.js
@@ -71,16 +71,31 @@ function createDirEntry(elem, parent, fullPath, hasFoundFile) {
     return hasFoundFile;
 }
 
+let toggleLabel;
+
+function getToggleLabel() {
+    toggleLabel = toggleLabel || document.querySelector("#src-sidebar-toggle button");
+    return toggleLabel;
+}
+
+window.rustdocCloseSourceSidebar = () => {
+    removeClass(document.documentElement, "src-sidebar-expanded");
+    getToggleLabel().innerText = ">";
+    updateLocalStorage("source-sidebar-show", "false");
+};
+
+window.rustdocShowSourceSidebar = () => {
+    addClass(document.documentElement, "src-sidebar-expanded");
+    getToggleLabel().innerText = "<";
+    updateLocalStorage("source-sidebar-show", "true");
+};
+
 function toggleSidebar() {
     const child = this.parentNode.children[0];
     if (child.innerText === ">") {
-        addClass(document.documentElement, "src-sidebar-expanded");
-        child.innerText = "<";
-        updateLocalStorage("source-sidebar-show", "true");
+        window.rustdocShowSourceSidebar();
     } else {
-        removeClass(document.documentElement, "src-sidebar-expanded");
-        child.innerText = ">";
-        updateLocalStorage("source-sidebar-show", "false");
+        window.rustdocCloseSourceSidebar();
     }
 }
 
@@ -118,10 +133,10 @@ function createSrcSidebar() {
     title.className = "title";
     title.innerText = "Files";
     sidebar.appendChild(title);
-    Object.keys(srcIndex).forEach(key => {
-        srcIndex[key][NAME_OFFSET] = key;
-        hasFoundFile = createDirEntry(srcIndex[key], sidebar, "", hasFoundFile);
-    });
+    for (const [key, source] of srcIndex) {
+        source[NAME_OFFSET] = key;
+        hasFoundFile = createDirEntry(source, sidebar, "", hasFoundFile);
+    }
 
     container.appendChild(sidebar);
     // Focus on the current file in the source files sidebar.
@@ -131,12 +146,8 @@ function createSrcSidebar() {
     }
 }
 
-const lineNumbersRegex = /^#?(\d+)(?:-(\d+))?$/;
-
-function highlightSrcLines(match) {
-    if (typeof match === "undefined") {
-        match = window.location.hash.match(lineNumbersRegex);
-    }
+function highlightSrcLines() {
+    const match = window.location.hash.match(/^#?(\d+)(?:-(\d+))?$/);
     if (!match) {
         return;
     }
@@ -218,12 +229,7 @@ const handleSrcHighlight = (function() {
     };
 }());
 
-window.addEventListener("hashchange", () => {
-    const match = window.location.hash.match(lineNumbersRegex);
-    if (match) {
-        return highlightSrcLines(match);
-    }
-});
+window.addEventListener("hashchange", highlightSrcLines);
 
 onEachLazy(document.getElementsByClassName("src-line-numbers"), el => {
     el.addEventListener("click", handleSrcHighlight);
diff --git a/src/librustdoc/html/static/js/storage.js b/src/librustdoc/html/static/js/storage.js
index c69641092..ac9c6f377 100644
--- a/src/librustdoc/html/static/js/storage.js
+++ b/src/librustdoc/html/static/js/storage.js
@@ -51,22 +51,11 @@ function removeClass(elem, className) {
  * Run a callback for every element of an Array.
  * @param {Array<?>}    arr        - The array to iterate over
  * @param {function(?)} func       - The callback
- * @param {boolean}     [reversed] - Whether to iterate in reverse
  */
-function onEach(arr, func, reversed) {
-    if (arr && arr.length > 0) {
-        if (reversed) {
-            for (let i = arr.length - 1; i >= 0; --i) {
-                if (func(arr[i])) {
-                    return true;
-                }
-            }
-        } else {
-            for (const elem of arr) {
-                if (func(elem)) {
-                    return true;
-                }
-            }
+function onEach(arr, func) {
+    for (const elem of arr) {
+        if (func(elem)) {
+            return true;
         }
     }
     return false;
@@ -80,14 +69,12 @@ function onEach(arr, func, reversed) {
  * https://developer.mozilla.org/en-US/docs/Web/API/NodeList
  * @param {NodeList<?>|HTMLCollection<?>} lazyArray  - An array to iterate over
  * @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) {
+function onEachLazy(lazyArray, func) {
     return onEach(
         Array.prototype.slice.call(lazyArray),
-        func,
-        reversed);
+        func);
 }
 
 function updateLocalStorage(name, value) {
@@ -196,11 +183,38 @@ if (getSettingValue("use-system-theme") !== "false" && window.matchMedia) {
 
 updateTheme();
 
+// Hide, show, and resize the sidebar at page load time
+//
+// This needs to be done here because this JS is render-blocking,
+// so that the sidebar doesn't "jump" after appearing on screen.
+// The user interaction to change this is set up in main.js.
 if (getSettingValue("source-sidebar-show") === "true") {
     // At this point in page load, `document.body` is not available yet.
     // Set a class on the `<html>` element instead.
     addClass(document.documentElement, "src-sidebar-expanded");
 }
+if (getSettingValue("hide-sidebar") === "true") {
+    // At this point in page load, `document.body` is not available yet.
+    // Set a class on the `<html>` element instead.
+    addClass(document.documentElement, "hide-sidebar");
+}
+function updateSidebarWidth() {
+    const desktopSidebarWidth = getSettingValue("desktop-sidebar-width");
+    if (desktopSidebarWidth && desktopSidebarWidth !== "null") {
+        document.documentElement.style.setProperty(
+            "--desktop-sidebar-width",
+            desktopSidebarWidth + "px"
+        );
+    }
+    const srcSidebarWidth = getSettingValue("src-sidebar-width");
+    if (srcSidebarWidth && srcSidebarWidth !== "null") {
+        document.documentElement.style.setProperty(
+            "--src-sidebar-width",
+            srcSidebarWidth + "px"
+        );
+    }
+}
+updateSidebarWidth();
 
 // If we navigate away (for example to a settings page), and then use the back or
 // forward button to get back to a page, the theme may have changed in the meantime.
@@ -214,5 +228,6 @@ if (getSettingValue("source-sidebar-show") === "true") {
 window.addEventListener("pageshow", ev => {
     if (ev.persisted) {
         setTimeout(updateTheme, 0);
+        setTimeout(updateSidebarWidth, 0);
     }
 });