src/librustdoc/html/static/js/search.js

   1 /* global addClass, getNakedUrl, getSettingValue, hasOwnPropertyRustdoc, initSearch, onEach */
   2 /* global onEachLazy, removeClass, searchState, browserSupportsHistoryApi */
   3
   4 "use strict";
   5
   6 (function() {
   7 // This mapping table should match the discriminants of
   8 // `rustdoc::formats::item_type::ItemType` type in Rust.
   9 const itemTypes = [
  10     "mod",
  11     "externcrate",
  12     "import",
  13     "struct",
  14     "enum",
  15     "fn",
  16     "type",
  17     "static",
  18     "trait",
  19     "impl",
  20     "tymethod",
  21     "method",
  22     "structfield",
  23     "variant",
  24     "macro",
  25     "primitive",
  26     "associatedtype",
  27     "constant",
  28     "associatedconstant",
  29     "union",
  30     "foreigntype",
  31     "keyword",
  32     "existential",
  33     "attr",
  34     "derive",
  35     "traitalias",
  36 ];
  37
  38 // used for special search precedence
  39 const TY_PRIMITIVE = itemTypes.indexOf("primitive");
  40 const TY_KEYWORD = itemTypes.indexOf("keyword");
  41
  42 // In the search display, allows to switch between tabs.
  43 function printTab(nb) {
  44     let iter = 0;
  45     let foundCurrentTab = false;
  46     let foundCurrentResultSet = false;
  47     onEachLazy(document.getElementById("titles").childNodes, elem => {
  48         if (nb === iter) {
  49             addClass(elem, "selected");
  50             foundCurrentTab = true;
  51         } else {
  52             removeClass(elem, "selected");
  53         }
  54         iter += 1;
  55     });
  56     iter = 0;
  57     onEachLazy(document.getElementById("results").childNodes, elem => {
  58         if (nb === iter) {
  59             addClass(elem, "active");
  60             foundCurrentResultSet = true;
  61         } else {
  62             removeClass(elem, "active");
  63         }
  64         iter += 1;
  65     });
  66     if (foundCurrentTab && foundCurrentResultSet) {
  67         searchState.currentTab = nb;
  68     } else if (nb != 0) {
  69         printTab(0);
  70     }
  71 }
  72
  73 /**
  74  * A function to compute the Levenshtein distance between two strings
  75  * Licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported
  76  * Full License can be found at http://creativecommons.org/licenses/by-sa/3.0/legalcode
  77  * This code is an unmodified version of the code written by Marco de Wit
  78  * and was found at https://stackoverflow.com/a/18514751/745719
  79  */
  80 const levenshtein_row2 = [];
  81 function levenshtein(s1, s2) {
  82     if (s1 === s2) {
  83         return 0;
  84     }
  85     const s1_len = s1.length, s2_len = s2.length;
  86     if (s1_len && s2_len) {
  87         let i1 = 0, i2 = 0, a, b, c, c2;
  88         const row = levenshtein_row2;
  89         while (i1 < s1_len) {
  90             row[i1] = ++i1;
  91         }
  92         while (i2 < s2_len) {
  93             c2 = s2.charCodeAt(i2);
  94             a = i2;
  95             ++i2;
  96             b = i2;
  97             for (i1 = 0; i1 < s1_len; ++i1) {
  98                 c = a + (s1.charCodeAt(i1) !== c2 ? 1 : 0);
  99                 a = row[i1];
 100                 b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
 101                 row[i1] = b;
 102             }
 103         }
 104         return b;
 105     }
 106     return s1_len + s2_len;
 107 }
 108
 109 window.initSearch = rawSearchIndex => {
 110     const MAX_LEV_DISTANCE = 3;
 111     const MAX_RESULTS = 200;
 112     const GENERICS_DATA = 2;
 113     const NAME = 0;
 114     const INPUTS_DATA = 0;
 115     const OUTPUT_DATA = 1;
 116     const NO_TYPE_FILTER = -1;
 117     /**
 118      *  @type {Array<Row>}
 119      */
 120     let searchIndex;
 121     let currentResults;
 122     const ALIASES = Object.create(null);
 123     const params = searchState.getQueryStringParams();
 124
 125     // Populate search bar with query string search term when provided,
 126     // but only if the input bar is empty. This avoid the obnoxious issue
 127     // where you start trying to do a search, and the index loads, and
 128     // suddenly your search is gone!
 129     if (searchState.input.value === "") {
 130         searchState.input.value = params.search || "";
 131     }
 132
 133     function isWhitespace(c) {
 134         return " \t\n\r".indexOf(c) !== -1;
 135     }
 136
 137     function isSpecialStartCharacter(c) {
 138         return "<\"".indexOf(c) !== -1;
 139     }
 140
 141     function isEndCharacter(c) {
 142         return ",>-".indexOf(c) !== -1;
 143     }
 144
 145     function isStopCharacter(c) {
 146         return isWhitespace(c) || isEndCharacter(c);
 147     }
 148
 149     function isErrorCharacter(c) {
 150         return "()".indexOf(c) !== -1;
 151     }
 152
 153     function itemTypeFromName(typename) {
 154         for (let i = 0, len = itemTypes.length; i < len; ++i) {
 155             if (itemTypes[i] === typename) {
 156                 return i;
 157             }
 158         }
 159
 160         throw new Error("Unknown type filter `" + typename + "`");
 161     }
 162
 163     /**
 164      * If we encounter a `"`, then we try to extract the string from it until we find another `"`.
 165      *
 166      * This function will throw an error in the following cases:
 167      * * There is already another string element.
 168      * * We are parsing a generic argument.
 169      * * There is more than one element.
 170      * * There is no closing `"`.
 171      *
 172      * @param {ParsedQuery} query
 173      * @param {ParserState} parserState
 174      * @param {boolean} isInGenerics
 175      */
 176     function getStringElem(query, parserState, isInGenerics) {
 177         if (isInGenerics) {
 178             throw new Error("`\"` cannot be used in generics");
 179         } else if (query.literalSearch) {
 180             throw new Error("Cannot have more than one literal search element");
 181         } else if (parserState.totalElems - parserState.genericsElems > 0) {
 182             throw new Error("Cannot use literal search when there is more than one element");
 183         }
 184         parserState.pos += 1;
 185         const start = parserState.pos;
 186         const end = getIdentEndPosition(parserState);
 187         if (parserState.pos >= parserState.length) {
 188             throw new Error("Unclosed `\"`");
 189         } else if (parserState.userQuery[end] !== "\"") {
 190             throw new Error(`Unexpected \`${parserState.userQuery[end]}\` in a string element`);
 191         } else if (start === end) {
 192             throw new Error("Cannot have empty string element");
 193         }
 194         // To skip the quote at the end.
 195         parserState.pos += 1;
 196         query.literalSearch = true;
 197     }
 198
 199     /**
 200      * Returns `true` if the current parser position is starting with "::".
 201      *
 202      * @param {ParserState} parserState
 203      *
 204      * @return {boolean}
 205      */
 206     function isPathStart(parserState) {
 207         return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) == "::";
 208     }
 209
 210     /**
 211      * Returns `true` if the current parser position is starting with "->".
 212      *
 213      * @param {ParserState} parserState
 214      *
 215      * @return {boolean}
 216      */
 217     function isReturnArrow(parserState) {
 218         return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) == "->";
 219     }
 220
 221     /**
 222      * Returns `true` if the given `c` character is valid for an ident.
 223      *
 224      * @param {string} c
 225      *
 226      * @return {boolean}
 227      */
 228     function isIdentCharacter(c) {
 229         return (
 230             c === "_" ||
 231             (c >= "0" && c <= "9") ||
 232             (c >= "a" && c <= "z") ||
 233             (c >= "A" && c <= "Z"));
 234     }
 235
 236     /**
 237      * Returns `true` if the given `c` character is a separator.
 238      *
 239      * @param {string} c
 240      *
 241      * @return {boolean}
 242      */
 243     function isSeparatorCharacter(c) {
 244         return c === "," || isWhitespaceCharacter(c);
 245     }
 246
 247     /**
 248      * Returns `true` if the given `c` character is a whitespace.
 249      *
 250      * @param {string} c
 251      *
 252      * @return {boolean}
 253      */
 254     function isWhitespaceCharacter(c) {
 255         return c === " " || c === "\t";
 256     }
 257
 258     /**
 259      * @param {ParsedQuery} query
 260      * @param {ParserState} parserState
 261      * @param {string} name                  - Name of the query element.
 262      * @param {Array<QueryElement>} generics - List of generics of this query element.
 263      *
 264      * @return {QueryElement}                - The newly created `QueryElement`.
 265      */
 266     function createQueryElement(query, parserState, name, generics, isInGenerics) {
 267         if (name === "*" || (name.length === 0 && generics.length === 0)) {
 268             return;
 269         }
 270         if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) {
 271             throw new Error("You cannot have more than one element if you use quotes");
 272         }
 273         const pathSegments = name.split("::");
 274         if (pathSegments.length > 1) {
 275             for (let i = 0, len = pathSegments.length; i < len; ++i) {
 276                 const pathSegment = pathSegments[i];
 277
 278                 if (pathSegment.length === 0) {
 279                     if (i === 0) {
 280                         throw new Error("Paths cannot start with `::`");
 281                     } else if (i + 1 === len) {
 282                         throw new Error("Paths cannot end with `::`");
 283                     }
 284                     throw new Error("Unexpected `::::`");
 285                 }
 286             }
 287         }
 288         // In case we only have something like `<p>`, there is no name.
 289         if (pathSegments.length === 0 || (pathSegments.length === 1 && pathSegments[0] === "")) {
 290             throw new Error("Found generics without a path");
 291         }
 292         parserState.totalElems += 1;
 293         if (isInGenerics) {
 294             parserState.genericsElems += 1;
 295         }
 296         return {
 297             name: name,
 298             fullPath: pathSegments,
 299             pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1),
 300             pathLast: pathSegments[pathSegments.length - 1],
 301             generics: generics,
 302         };
 303     }
 304
 305     /**
 306      * This function goes through all characters until it reaches an invalid ident character or the
 307      * end of the query. It returns the position of the last character of the ident.
 308      *
 309      * @param {ParserState} parserState
 310      *
 311      * @return {integer}
 312      */
 313     function getIdentEndPosition(parserState) {
 314         let end = parserState.pos;
 315         let foundExclamation = false;
 316         while (parserState.pos < parserState.length) {
 317             const c = parserState.userQuery[parserState.pos];
 318             if (!isIdentCharacter(c)) {
 319                 if (c === "!") {
 320                     if (foundExclamation) {
 321                         throw new Error("Cannot have more than one `!` in an ident");
 322                     } else if (parserState.pos + 1 < parserState.length &&
 323                         isIdentCharacter(parserState.userQuery[parserState.pos + 1])
 324                     ) {
 325                         throw new Error("`!` can only be at the end of an ident");
 326                     }
 327                     foundExclamation = true;
 328                 } else if (isErrorCharacter(c)) {
 329                     throw new Error(`Unexpected \`${c}\``);
 330                 } else if (
 331                     isStopCharacter(c) ||
 332                     isSpecialStartCharacter(c) ||
 333                     isSeparatorCharacter(c)
 334                 ) {
 335                     break;
 336                 } else if (c === ":") { // If we allow paths ("str::string" for example).
 337                     if (!isPathStart(parserState)) {
 338                         break;
 339                     }
 340                     // Skip current ":".
 341                     parserState.pos += 1;
 342                     foundExclamation = false;
 343                 } else {
 344                     throw new Error(`Unexpected \`${c}\``);
 345                 }
 346             }
 347             parserState.pos += 1;
 348             end = parserState.pos;
 349         }
 350         return end;
 351     }
 352
 353     /**
 354      * @param {ParsedQuery} query
 355      * @param {ParserState} parserState
 356      * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added.
 357      * @param {boolean} isInGenerics
 358      */
 359     function getNextElem(query, parserState, elems, isInGenerics) {
 360         const generics = [];
 361
 362         let start = parserState.pos;
 363         let end;
 364         // We handle the strings on their own mostly to make code easier to follow.
 365         if (parserState.userQuery[parserState.pos] === "\"") {
 366             start += 1;
 367             getStringElem(query, parserState, isInGenerics);
 368             end = parserState.pos - 1;
 369         } else {
 370             end = getIdentEndPosition(parserState);
 371         }
 372         if (parserState.pos < parserState.length &&
 373             parserState.userQuery[parserState.pos] === "<"
 374         ) {
 375             if (isInGenerics) {
 376                 throw new Error("Unexpected `<` after `<`");
 377             } else if (start >= end) {
 378                 throw new Error("Found generics without a path");
 379             }
 380             parserState.pos += 1;
 381             getItemsBefore(query, parserState, generics, ">");
 382         }
 383         if (start >= end && generics.length === 0) {
 384             return;
 385         }
 386         elems.push(
 387             createQueryElement(
 388                 query,
 389                 parserState,
 390                 parserState.userQuery.slice(start, end),
 391                 generics,
 392                 isInGenerics
 393             )
 394         );
 395     }
 396
 397     /**
 398      * This function parses the next query element until it finds `endChar`, calling `getNextElem`
 399      * to collect each element.
 400      *
 401      * If there is no `endChar`, this function will implicitly stop at the end without raising an
 402      * error.
 403      *
 404      * @param {ParsedQuery} query
 405      * @param {ParserState} parserState
 406      * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added.
 407      * @param {string} endChar            - This function will stop when it'll encounter this
 408      *                                      character.
 409      */
 410     function getItemsBefore(query, parserState, elems, endChar) {
 411         let foundStopChar = true;
 412
 413         while (parserState.pos < parserState.length) {
 414             const c = parserState.userQuery[parserState.pos];
 415             if (c === endChar) {
 416                 break;
 417             } else if (isSeparatorCharacter(c)) {
 418                 parserState.pos += 1;
 419                 foundStopChar = true;
 420                 continue;
 421             } else if (c === ":" && isPathStart(parserState)) {
 422                 throw new Error("Unexpected `::`: paths cannot start with `::`");
 423             } else if (c === ":" || isEndCharacter(c)) {
 424                 let extra = "";
 425                 if (endChar === ">") {
 426                     extra = "`<`";
 427                 } else if (endChar === "") {
 428                     extra = "`->`";
 429                 }
 430                 throw new Error("Unexpected `" + c + "` after " + extra);
 431             }
 432             if (!foundStopChar) {
 433                 if (endChar !== "") {
 434                     throw new Error(`Expected \`,\`, \` \` or \`${endChar}\`, found \`${c}\``);
 435                 }
 436                 throw new Error(`Expected \`,\` or \` \`, found \`${c}\``);
 437             }
 438             const posBefore = parserState.pos;
 439             getNextElem(query, parserState, elems, endChar === ">");
 440             // This case can be encountered if `getNextElem` encounted a "stop character" right from
 441             // the start. For example if you have `,,` or `<>`. In this case, we simply move up the
 442             // current position to continue the parsing.
 443             if (posBefore === parserState.pos) {
 444                 parserState.pos += 1;
 445             }
 446             foundStopChar = false;
 447         }
 448         // We are either at the end of the string or on the `endChar`` character, let's move forward
 449         // in any case.
 450         parserState.pos += 1;
 451     }
 452
 453     /**
 454      * Checks that the type filter doesn't have unwanted characters like `<>` (which are ignored
 455      * if empty).
 456      *
 457      * @param {ParserState} parserState
 458      */
 459     function checkExtraTypeFilterCharacters(parserState) {
 460         const query = parserState.userQuery;
 461
 462         for (let pos = 0; pos < parserState.pos; ++pos) {
 463             if (!isIdentCharacter(query[pos]) && !isWhitespaceCharacter(query[pos])) {
 464                 throw new Error(`Unexpected \`${query[pos]}\` in type filter`);
 465             }
 466         }
 467     }
 468
 469     /**
 470      * Parses the provided `query` input to fill `parserState`. If it encounters an error while
 471      * parsing `query`, it'll throw an error.
 472      *
 473      * @param {ParsedQuery} query
 474      * @param {ParserState} parserState
 475      */
 476     function parseInput(query, parserState) {
 477         let c, before;
 478         let foundStopChar = true;
 479
 480         while (parserState.pos < parserState.length) {
 481             c = parserState.userQuery[parserState.pos];
 482             if (isStopCharacter(c)) {
 483                 foundStopChar = true;
 484                 if (isSeparatorCharacter(c)) {
 485                     parserState.pos += 1;
 486                     continue;
 487                 } else if (c === "-" || c === ">") {
 488                     if (isReturnArrow(parserState)) {
 489                         break;
 490                     }
 491                     throw new Error(`Unexpected \`${c}\` (did you mean \`->\`?)`);
 492                 }
 493                 throw new Error(`Unexpected \`${c}\``);
 494             } else if (c === ":" && !isPathStart(parserState)) {
 495                 if (parserState.typeFilter !== null) {
 496                     throw new Error("Unexpected `:`");
 497                 }
 498                 if (query.elems.length === 0) {
 499                     throw new Error("Expected type filter before `:`");
 500                 } else if (query.elems.length !== 1 || parserState.totalElems !== 1) {
 501                     throw new Error("Unexpected `:`");
 502                 } else if (query.literalSearch) {
 503                     throw new Error("You cannot use quotes on type filter");
 504                 }
 505                 checkExtraTypeFilterCharacters(parserState);
 506                 // The type filter doesn't count as an element since it's a modifier.
 507                 parserState.typeFilter = query.elems.pop().name;
 508                 parserState.pos += 1;
 509                 parserState.totalElems = 0;
 510                 query.literalSearch = false;
 511                 foundStopChar = true;
 512                 continue;
 513             }
 514             if (!foundStopChar) {
 515                 if (parserState.typeFilter !== null) {
 516                     throw new Error(`Expected \`,\`, \` \` or \`->\`, found \`${c}\``);
 517                 }
 518                 throw new Error(`Expected \`,\`, \` \`, \`:\` or \`->\`, found \`${c}\``);
 519             }
 520             before = query.elems.length;
 521             getNextElem(query, parserState, query.elems, false);
 522             if (query.elems.length === before) {
 523                 // Nothing was added, weird... Let's increase the position to not remain stuck.
 524                 parserState.pos += 1;
 525             }
 526             foundStopChar = false;
 527         }
 528         while (parserState.pos < parserState.length) {
 529             c = parserState.userQuery[parserState.pos];
 530             if (isReturnArrow(parserState)) {
 531                 parserState.pos += 2;
 532                 // Get returned elements.
 533                 getItemsBefore(query, parserState, query.returned, "");
 534                 // Nothing can come afterward!
 535                 if (query.returned.length === 0) {
 536                     throw new Error("Expected at least one item after `->`");
 537                 }
 538                 break;
 539             } else {
 540                 parserState.pos += 1;
 541             }
 542         }
 543     }
 544
 545     /**
 546      * Takes the user search input and returns an empty `ParsedQuery`.
 547      *
 548      * @param {string} userQuery
 549      *
 550      * @return {ParsedQuery}
 551      */
 552     function newParsedQuery(userQuery) {
 553         return {
 554             original: userQuery,
 555             userQuery: userQuery.toLowerCase(),
 556             typeFilter: NO_TYPE_FILTER,
 557             elems: [],
 558             returned: [],
 559             // Total number of "top" elements (does not include generics).
 560             foundElems: 0,
 561             literalSearch: false,
 562             error: null,
 563         };
 564     }
 565
 566     /**
 567      * Build an URL with search parameters.
 568      *
 569      * @param {string} search            - The current search being performed.
 570      * @param {string|null} filterCrates - The current filtering crate (if any).
 571      *
 572      * @return {string}
 573      */
 574     function buildUrl(search, filterCrates) {
 575         let extra = "?search=" + encodeURIComponent(search);
 576
 577         if (filterCrates !== null) {
 578             extra += "&filter-crate=" + encodeURIComponent(filterCrates);
 579         }
 580         return getNakedUrl() + extra + window.location.hash;
 581     }
 582
 583     /**
 584      * Return the filtering crate or `null` if there is none.
 585      *
 586      * @return {string|null}
 587      */
 588     function getFilterCrates() {
 589         const elem = document.getElementById("crate-search");
 590
 591         if (elem &&
 592             elem.value !== "All crates" &&
 593             hasOwnPropertyRustdoc(rawSearchIndex, elem.value)
 594         ) {
 595             return elem.value;
 596         }
 597         return null;
 598     }
 599
 600     /**
 601      * Parses the query.
 602      *
 603      * The supported syntax by this parser is as follow:
 604      *
 605      * ident = *(ALPHA / DIGIT / "_") [!]
 606      * path = ident *(DOUBLE-COLON ident)
 607      * arg = path [generics]
 608      * arg-without-generic = path
 609      * type-sep = COMMA/WS *(COMMA/WS)
 610      * nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep)
 611      * nonempty-arg-list-without-generics = *(type-sep) arg-without-generic
 612      *                                      *(type-sep arg-without-generic) *(type-sep)
 613      * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list-without-generics ] *(type-sep)
 614      *            CLOSE-ANGLE-BRACKET/EOF
 615      * return-args = RETURN-ARROW *(type-sep) nonempty-arg-list
 616      *
 617      * exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ]
 618      * type-search = [type-filter *WS COLON] [ nonempty-arg-list ] [ return-args ]
 619      *
 620      * query = *WS (exact-search / type-search) *WS
 621      *
 622      * type-filter = (
 623      *     "mod" /
 624      *     "externcrate" /
 625      *     "import" /
 626      *     "struct" /
 627      *     "enum" /
 628      *     "fn" /
 629      *     "type" /
 630      *     "static" /
 631      *     "trait" /
 632      *     "impl" /
 633      *     "tymethod" /
 634      *     "method" /
 635      *     "structfield" /
 636      *     "variant" /
 637      *     "macro" /
 638      *     "primitive" /
 639      *     "associatedtype" /
 640      *     "constant" /
 641      *     "associatedconstant" /
 642      *     "union" /
 643      *     "foreigntype" /
 644      *     "keyword" /
 645      *     "existential" /
 646      *     "attr" /
 647      *     "derive" /
 648      *     "traitalias")
 649      *
 650      * OPEN-ANGLE-BRACKET = "<"
 651      * CLOSE-ANGLE-BRACKET = ">"
 652      * COLON = ":"
 653      * DOUBLE-COLON = "::"
 654      * QUOTE = %x22
 655      * COMMA = ","
 656      * RETURN-ARROW = "->"
 657      *
 658      * ALPHA = %x41-5A / %x61-7A ; A-Z / a-z
 659      * DIGIT = %x30-39
 660      * WS = %x09 / " "
 661      *
 662      * @param  {string} val     - The user query
 663      *
 664      * @return {ParsedQuery}    - The parsed query
 665      */
 666     function parseQuery(userQuery) {
 667         userQuery = userQuery.trim();
 668         const parserState = {
 669             length: userQuery.length,
 670             pos: 0,
 671             // Total number of elements (includes generics).
 672             totalElems: 0,
 673             genericsElems: 0,
 674             typeFilter: null,
 675             userQuery: userQuery.toLowerCase(),
 676         };
 677         let query = newParsedQuery(userQuery);
 678
 679         try {
 680             parseInput(query, parserState);
 681             if (parserState.typeFilter !== null) {
 682                 let typeFilter = parserState.typeFilter;
 683                 if (typeFilter === "const") {
 684                     typeFilter = "constant";
 685                 }
 686                 query.typeFilter = itemTypeFromName(typeFilter);
 687             }
 688         } catch (err) {
 689             query = newParsedQuery(userQuery);
 690             query.error = err.message;
 691             query.typeFilter = -1;
 692             return query;
 693         }
 694
 695         if (!query.literalSearch) {
 696             // If there is more than one element in the query, we switch to literalSearch in any
 697             // case.
 698             query.literalSearch = parserState.totalElems > 1;
 699         }
 700         query.foundElems = query.elems.length + query.returned.length;
 701         return query;
 702     }
 703
 704     /**
 705      * Creates the query results.
 706      *
 707      * @param {Array<Result>} results_in_args
 708      * @param {Array<Result>} results_returned
 709      * @param {Array<Result>} results_in_args
 710      * @param {ParsedQuery} parsedQuery
 711      *
 712      * @return {ResultsTable}
 713      */
 714     function createQueryResults(results_in_args, results_returned, results_others, parsedQuery) {
 715         return {
 716             "in_args": results_in_args,
 717             "returned": results_returned,
 718             "others": results_others,
 719             "query": parsedQuery,
 720         };
 721     }
 722
 723     /**
 724      * Executes the parsed query and builds a {ResultsTable}.
 725      *
 726      * @param  {ParsedQuery} parsedQuery - The parsed user query
 727      * @param  {Object} searchWords      - The list of search words to query against
 728      * @param  {Object} [filterCrates]   - Crate to search in if defined
 729      *
 730      * @return {ResultsTable}
 731      */
 732     function execQuery(parsedQuery, searchWords, filterCrates) {
 733         const results_others = {}, results_in_args = {}, results_returned = {};
 734
 735         function transformResults(results) {
 736             const duplicates = {};
 737             const out = [];
 738
 739             for (const result of results) {
 740                 if (result.id > -1) {
 741                     const obj = searchIndex[result.id];
 742                     obj.lev = result.lev;
 743                     const res = buildHrefAndPath(obj);
 744                     obj.displayPath = pathSplitter(res[0]);
 745                     obj.fullPath = obj.displayPath + obj.name;
 746                     // To be sure than it some items aren't considered as duplicate.
 747                     obj.fullPath += "|" + obj.ty;
 748
 749                     if (duplicates[obj.fullPath]) {
 750                         continue;
 751                     }
 752                     duplicates[obj.fullPath] = true;
 753
 754                     obj.href = res[1];
 755                     out.push(obj);
 756                     if (out.length >= MAX_RESULTS) {
 757                         break;
 758                     }
 759                 }
 760             }
 761             return out;
 762         }
 763
 764         function sortResults(results, isType) {
 765             const userQuery = parsedQuery.userQuery;
 766             const ar = [];
 767             for (const entry in results) {
 768                 if (hasOwnPropertyRustdoc(results, entry)) {
 769                     const result = results[entry];
 770                     result.word = searchWords[result.id];
 771                     result.item = searchIndex[result.id] || {};
 772                     ar.push(result);
 773                 }
 774             }
 775             results = ar;
 776             // if there are no results then return to default and fail
 777             if (results.length === 0) {
 778                 return [];
 779             }
 780
 781             results.sort((aaa, bbb) => {
 782                 let a, b;
 783
 784                 // sort by exact match with regard to the last word (mismatch goes later)
 785                 a = (aaa.word !== userQuery);
 786                 b = (bbb.word !== userQuery);
 787                 if (a !== b) {
 788                     return a - b;
 789                 }
 790
 791                 // Sort by non levenshtein results and then levenshtein results by the distance
 792                 // (less changes required to match means higher rankings)
 793                 a = (aaa.lev);
 794                 b = (bbb.lev);
 795                 if (a !== b) {
 796                     return a - b;
 797                 }
 798
 799                 // sort by crate (non-current crate goes later)
 800                 a = (aaa.item.crate !== window.currentCrate);
 801                 b = (bbb.item.crate !== window.currentCrate);
 802                 if (a !== b) {
 803                     return a - b;
 804                 }
 805
 806                 // sort by item name length (longer goes later)
 807                 a = aaa.word.length;
 808                 b = bbb.word.length;
 809                 if (a !== b) {
 810                     return a - b;
 811                 }
 812
 813                 // sort by item name (lexicographically larger goes later)
 814                 a = aaa.word;
 815                 b = bbb.word;
 816                 if (a !== b) {
 817                     return (a > b ? +1 : -1);
 818                 }
 819
 820                 // sort by index of keyword in item name (no literal occurrence goes later)
 821                 a = (aaa.index < 0);
 822                 b = (bbb.index < 0);
 823                 if (a !== b) {
 824                     return a - b;
 825                 }
 826                 // (later literal occurrence, if any, goes later)
 827                 a = aaa.index;
 828                 b = bbb.index;
 829                 if (a !== b) {
 830                     return a - b;
 831                 }
 832
 833                 // special precedence for primitive and keyword pages
 834                 if ((aaa.item.ty === TY_PRIMITIVE && bbb.item.ty !== TY_KEYWORD) ||
 835                     (aaa.item.ty === TY_KEYWORD && bbb.item.ty !== TY_PRIMITIVE)) {
 836                     return -1;
 837                 }
 838                 if ((bbb.item.ty === TY_PRIMITIVE && aaa.item.ty !== TY_PRIMITIVE) ||
 839                     (bbb.item.ty === TY_KEYWORD && aaa.item.ty !== TY_KEYWORD)) {
 840                     return 1;
 841                 }
 842
 843                 // sort by description (no description goes later)
 844                 a = (aaa.item.desc === "");
 845                 b = (bbb.item.desc === "");
 846                 if (a !== b) {
 847                     return a - b;
 848                 }
 849
 850                 // sort by type (later occurrence in `itemTypes` goes later)
 851                 a = aaa.item.ty;
 852                 b = bbb.item.ty;
 853                 if (a !== b) {
 854                     return a - b;
 855                 }
 856
 857                 // sort by path (lexicographically larger goes later)
 858                 a = aaa.item.path;
 859                 b = bbb.item.path;
 860                 if (a !== b) {
 861                     return (a > b ? +1 : -1);
 862                 }
 863
 864                 // que sera, sera
 865                 return 0;
 866             });
 867
 868             let nameSplit = null;
 869             if (parsedQuery.elems.length === 1) {
 870                 const hasPath = typeof parsedQuery.elems[0].path === "undefined";
 871                 nameSplit = hasPath ? null : parsedQuery.elems[0].path;
 872             }
 873
 874             for (const result of results) {
 875                 // this validation does not make sense when searching by types
 876                 if (result.dontValidate) {
 877                     continue;
 878                 }
 879                 const name = result.item.name.toLowerCase(),
 880                     path = result.item.path.toLowerCase(),
 881                     parent = result.item.parent;
 882
 883                 if (!isType && !validateResult(name, path, nameSplit, parent)) {
 884                     result.id = -1;
 885                 }
 886             }
 887             return transformResults(results);
 888         }
 889
 890         /**
 891          * This function checks if the object (`row`) generics match the given type (`elem`)
 892          * generics. If there are no generics on `row`, `defaultLev` is returned.
 893          *
 894          * @param {Row} row            - The object to check.
 895          * @param {QueryElement} elem  - The element from the parsed query.
 896          * @param {integer} defaultLev - This is the value to return in case there are no generics.
 897          *
 898          * @return {integer}           - Returns the best match (if any) or `MAX_LEV_DISTANCE + 1`.
 899          */
 900         function checkGenerics(row, elem, defaultLev) {
 901             if (row.length <= GENERICS_DATA || row[GENERICS_DATA].length === 0) {
 902                 return elem.generics.length === 0 ? defaultLev : MAX_LEV_DISTANCE + 1;
 903             } else if (row[GENERICS_DATA].length > 0 && row[GENERICS_DATA][0][NAME] === "") {
 904                 if (row.length > GENERICS_DATA) {
 905                     return checkGenerics(row[GENERICS_DATA][0], elem, defaultLev);
 906                 }
 907                 return elem.generics.length === 0 ? defaultLev : MAX_LEV_DISTANCE + 1;
 908             }
 909             // The names match, but we need to be sure that all generics kinda
 910             // match as well.
 911             let elem_name;
 912             if (elem.generics.length > 0 && row[GENERICS_DATA].length >= elem.generics.length) {
 913                 const elems = Object.create(null);
 914                 for (const entry of row[GENERICS_DATA]) {
 915                     elem_name = entry[NAME];
 916                     if (elem_name === "") {
 917                         // Pure generic, needs to check into it.
 918                         if (checkGenerics(entry, elem, MAX_LEV_DISTANCE + 1) !== 0) {
 919                             return MAX_LEV_DISTANCE + 1;
 920                         }
 921                         continue;
 922                     }
 923                     if (elems[elem_name] === undefined) {
 924                         elems[elem_name] = 0;
 925                     }
 926                     elems[elem_name] += 1;
 927                 }
 928                 // We need to find the type that matches the most to remove it in order
 929                 // to move forward.
 930                 for (const generic of elem.generics) {
 931                     let match = null;
 932                     if (elems[generic.name]) {
 933                         match = generic.name;
 934                     } else {
 935                         for (elem_name in elems) {
 936                             if (!hasOwnPropertyRustdoc(elems, elem_name)) {
 937                                 continue;
 938                             }
 939                             if (elem_name === generic) {
 940                                 match = elem_name;
 941                                 break;
 942                             }
 943                         }
 944                     }
 945                     if (match === null) {
 946                         return MAX_LEV_DISTANCE + 1;
 947                     }
 948                     elems[match] -= 1;
 949                     if (elems[match] === 0) {
 950                         delete elems[match];
 951                     }
 952                 }
 953                 return 0;
 954             }
 955             return MAX_LEV_DISTANCE + 1;
 956         }
 957
 958         /**
 959           * This function checks if the object (`row`) matches the given type (`elem`) and its
 960           * generics (if any).
 961           *
 962           * @param {Row} row
 963           * @param {QueryElement} elem    - The element from the parsed query.
 964           *
 965           * @return {integer} - Returns a Levenshtein distance to the best match.
 966           */
 967         function checkIfInGenerics(row, elem) {
 968             let lev = MAX_LEV_DISTANCE + 1;
 969             for (const entry of row[GENERICS_DATA]) {
 970                 lev = Math.min(checkType(entry, elem, true), lev);
 971                 if (lev === 0) {
 972                     break;
 973                 }
 974             }
 975             return lev;
 976         }
 977
 978         /**
 979           * This function checks if the object (`row`) matches the given type (`elem`) and its
 980           * generics (if any).
 981           *
 982           * @param {Row} row
 983           * @param {QueryElement} elem      - The element from the parsed query.
 984           * @param {boolean} literalSearch
 985           *
 986           * @return {integer} - Returns a Levenshtein distance to the best match. If there is
 987           *                     no match, returns `MAX_LEV_DISTANCE + 1`.
 988           */
 989         function checkType(row, elem, literalSearch) {
 990             if (row[NAME].length === 0) {
 991                 // This is a pure "generic" search, no need to run other checks.
 992                 if (row.length > GENERICS_DATA) {
 993                     return checkIfInGenerics(row, elem);
 994                 }
 995                 return MAX_LEV_DISTANCE + 1;
 996             }
 997
 998             let lev = levenshtein(row[NAME], elem.name);
 999             if (literalSearch) {
1000                 if (lev !== 0) {
1001                     // The name didn't match, let's try to check if the generics do.
1002                     if (elem.generics.length === 0) {
1003                         const checkGeneric = (row.length > GENERICS_DATA &&
1004                             row[GENERICS_DATA].length > 0);
1005                         if (checkGeneric && row[GENERICS_DATA]
1006                             .findIndex(tmp_elem => tmp_elem[NAME] === elem.name) !== -1) {
1007                             return 0;
1008                         }
1009                     }
1010                     return MAX_LEV_DISTANCE + 1;
1011                 } else if (elem.generics.length > 0) {
1012                     return checkGenerics(row, elem, MAX_LEV_DISTANCE + 1);
1013                 }
1014                 return 0;
1015             } else if (row.length > GENERICS_DATA) {
1016                 if (elem.generics.length === 0) {
1017                     if (lev === 0) {
1018                         return 0;
1019                     }
1020                     // The name didn't match so we now check if the type we're looking for is inside
1021                     // the generics!
1022                     lev = checkIfInGenerics(row, elem);
1023                     // Now whatever happens, the returned distance is "less good" so we should mark
1024                     // it as such, and so we add 0.5 to the distance to make it "less good".
1025                     return lev + 0.5;
1026                 } else if (lev > MAX_LEV_DISTANCE) {
1027                     // So our item's name doesn't match at all and has generics.
1028                     //
1029                     // Maybe it's present in a sub generic? For example "f<A<B<C>>>()", if we're
1030                     // looking for "B<C>", we'll need to go down.
1031                     return checkIfInGenerics(row, elem);
1032                 } else {
1033                     // At this point, the name kinda match and we have generics to check, so
1034                     // let's go!
1035                     const tmp_lev = checkGenerics(row, elem, lev);
1036                     if (tmp_lev > MAX_LEV_DISTANCE) {
1037                         return MAX_LEV_DISTANCE + 1;
1038                     }
1039                     // We compute the median value of both checks and return it.
1040                     return (tmp_lev + lev) / 2;
1041                 }
1042             } else if (elem.generics.length > 0) {
1043                 // In this case, we were expecting generics but there isn't so we simply reject this
1044                 // one.
1045                 return MAX_LEV_DISTANCE + 1;
1046             }
1047             // No generics on our query or on the target type so we can return without doing
1048             // anything else.
1049             return lev;
1050         }
1051
1052         /**
1053          * This function checks if the object (`row`) has an argument with the given type (`elem`).
1054          *
1055          * @param {Row} row
1056          * @param {QueryElement} elem    - The element from the parsed query.
1057          * @param {integer} typeFilter
1058          *
1059          * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
1060          *                      match, returns `MAX_LEV_DISTANCE + 1`.
1061          */
1062         function findArg(row, elem, typeFilter) {
1063             let lev = MAX_LEV_DISTANCE + 1;
1064
1065             if (row && row.type && row.type[INPUTS_DATA] && row.type[INPUTS_DATA].length > 0) {
1066                 for (const input of row.type[INPUTS_DATA]) {
1067                     if (!typePassesFilter(typeFilter, input[1])) {
1068                         continue;
1069                     }
1070                     lev = Math.min(lev, checkType(input, elem, parsedQuery.literalSearch));
1071                     if (lev === 0) {
1072                         return 0;
1073                     }
1074                 }
1075             }
1076             return parsedQuery.literalSearch ? MAX_LEV_DISTANCE + 1 : lev;
1077         }
1078
1079         /**
1080          * This function checks if the object (`row`) returns the given type (`elem`).
1081          *
1082          * @param {Row} row
1083          * @param {QueryElement} elem   - The element from the parsed query.
1084          * @param {integer} typeFilter
1085          *
1086          * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
1087          *                      match, returns `MAX_LEV_DISTANCE + 1`.
1088          */
1089         function checkReturned(row, elem, typeFilter) {
1090             let lev = MAX_LEV_DISTANCE + 1;
1091
1092             if (row && row.type && row.type.length > OUTPUT_DATA) {
1093                 let ret = row.type[OUTPUT_DATA];
1094                 if (typeof ret[0] === "string") {
1095                     ret = [ret];
1096                 }
1097                 for (const ret_ty of ret) {
1098                     if (!typePassesFilter(typeFilter, ret_ty[1])) {
1099                         continue;
1100                     }
1101                     lev = Math.min(lev, checkType(ret_ty, elem, parsedQuery.literalSearch));
1102                     if (lev === 0) {
1103                         return 0;
1104                     }
1105                 }
1106             }
1107             return parsedQuery.literalSearch ? MAX_LEV_DISTANCE + 1 : lev;
1108         }
1109
1110         function checkPath(contains, ty) {
1111             if (contains.length === 0) {
1112                 return 0;
1113             }
1114             let ret_lev = MAX_LEV_DISTANCE + 1;
1115             const path = ty.path.split("::");
1116
1117             if (ty.parent && ty.parent.name) {
1118                 path.push(ty.parent.name.toLowerCase());
1119             }
1120
1121             const length = path.length;
1122             const clength = contains.length;
1123             if (clength > length) {
1124                 return MAX_LEV_DISTANCE + 1;
1125             }
1126             for (let i = 0; i < length; ++i) {
1127                 if (i + clength > length) {
1128                     break;
1129                 }
1130                 let lev_total = 0;
1131                 let aborted = false;
1132                 for (let x = 0; x < clength; ++x) {
1133                     const lev = levenshtein(path[i + x], contains[x]);
1134                     if (lev > MAX_LEV_DISTANCE) {
1135                         aborted = true;
1136                         break;
1137                     }
1138                     lev_total += lev;
1139                 }
1140                 if (!aborted) {
1141                     ret_lev = Math.min(ret_lev, Math.round(lev_total / clength));
1142                 }
1143             }
1144             return ret_lev;
1145         }
1146
1147         function typePassesFilter(filter, type) {
1148             // No filter or Exact mach
1149             if (filter <= NO_TYPE_FILTER || filter === type) return true;
1150
1151             // Match related items
1152             const name = itemTypes[type];
1153             switch (itemTypes[filter]) {
1154                 case "constant":
1155                     return name === "associatedconstant";
1156                 case "fn":
1157                     return name === "method" || name === "tymethod";
1158                 case "type":
1159                     return name === "primitive" || name === "associatedtype";
1160                 case "trait":
1161                     return name === "traitalias";
1162             }
1163
1164             // No match
1165             return false;
1166         }
1167
1168         function createAliasFromItem(item) {
1169             return {
1170                 crate: item.crate,
1171                 name: item.name,
1172                 path: item.path,
1173                 desc: item.desc,
1174                 ty: item.ty,
1175                 parent: item.parent,
1176                 type: item.type,
1177                 is_alias: true,
1178             };
1179         }
1180
1181         function handleAliases(ret, query, filterCrates) {
1182             const lowerQuery = query.toLowerCase();
1183             // We separate aliases and crate aliases because we want to have current crate
1184             // aliases to be before the others in the displayed results.
1185             const aliases = [];
1186             const crateAliases = [];
1187             if (filterCrates !== null) {
1188                 if (ALIASES[filterCrates] && ALIASES[filterCrates][lowerQuery]) {
1189                     const query_aliases = ALIASES[filterCrates][lowerQuery];
1190                     for (const alias of query_aliases) {
1191                         aliases.push(createAliasFromItem(searchIndex[alias]));
1192                     }
1193                 }
1194             } else {
1195                 Object.keys(ALIASES).forEach(crate => {
1196                     if (ALIASES[crate][lowerQuery]) {
1197                         const pushTo = crate === window.currentCrate ? crateAliases : aliases;
1198                         const query_aliases = ALIASES[crate][lowerQuery];
1199                         for (const alias of query_aliases) {
1200                             pushTo.push(createAliasFromItem(searchIndex[alias]));
1201                         }
1202                     }
1203                 });
1204             }
1205
1206             const sortFunc = (aaa, bbb) => {
1207                 if (aaa.path < bbb.path) {
1208                     return 1;
1209                 } else if (aaa.path === bbb.path) {
1210                     return 0;
1211                 }
1212                 return -1;
1213             };
1214             crateAliases.sort(sortFunc);
1215             aliases.sort(sortFunc);
1216
1217             const pushFunc = alias => {
1218                 alias.alias = query;
1219                 const res = buildHrefAndPath(alias);
1220                 alias.displayPath = pathSplitter(res[0]);
1221                 alias.fullPath = alias.displayPath + alias.name;
1222                 alias.href = res[1];
1223
1224                 ret.others.unshift(alias);
1225                 if (ret.others.length > MAX_RESULTS) {
1226                     ret.others.pop();
1227                 }
1228             };
1229             onEach(aliases, pushFunc);
1230             onEach(crateAliases, pushFunc);
1231         }
1232
1233         /**
1234          * This function adds the given result into the provided `results` map if it matches the
1235          * following condition:
1236          *
1237          * * If it is a "literal search" (`parsedQuery.literalSearch`), then `lev` must be 0.
1238          * * If it is not a "literal search", `lev` must be <= `MAX_LEV_DISTANCE`.
1239          *
1240          * The `results` map contains information which will be used to sort the search results:
1241          *
1242          * * `fullId` is a `string`` used as the key of the object we use for the `results` map.
1243          * * `id` is the index in both `searchWords` and `searchIndex` arrays for this element.
1244          * * `index` is an `integer`` used to sort by the position of the word in the item's name.
1245          * * `lev` is the main metric used to sort the search results.
1246          *
1247          * @param {Results} results
1248          * @param {string} fullId
1249          * @param {integer} id
1250          * @param {integer} index
1251          * @param {integer} lev
1252          */
1253         function addIntoResults(results, fullId, id, index, lev) {
1254             if (lev === 0 || (!parsedQuery.literalSearch && lev <= MAX_LEV_DISTANCE)) {
1255                 if (results[fullId] !== undefined) {
1256                     const result = results[fullId];
1257                     if (result.dontValidate || result.lev <= lev) {
1258                         return;
1259                     }
1260                 }
1261                 results[fullId] = {
1262                     id: id,
1263                     index: index,
1264                     dontValidate: parsedQuery.literalSearch,
1265                     lev: lev,
1266                 };
1267             }
1268         }
1269
1270         /**
1271          * This function is called in case the query is only one element (with or without generics).
1272          * This element will be compared to arguments' and returned values' items and also to items.
1273          *
1274          * Other important thing to note: since there is only one element, we use levenshtein
1275          * distance for name comparisons.
1276          *
1277          * @param {Row} row
1278          * @param {integer} pos              - Position in the `searchIndex`.
1279          * @param {QueryElement} elem        - The element from the parsed query.
1280          * @param {Results} results_others   - Unqualified results (not in arguments nor in
1281          *                                     returned values).
1282          * @param {Results} results_in_args  - Matching arguments results.
1283          * @param {Results} results_returned - Matching returned arguments results.
1284          */
1285         function handleSingleArg(
1286             row,
1287             pos,
1288             elem,
1289             results_others,
1290             results_in_args,
1291             results_returned
1292         ) {
1293             if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
1294                 return;
1295             }
1296             let lev, lev_add = 0, index = -1;
1297             const fullId = row.id;
1298
1299             const in_args = findArg(row, elem, parsedQuery.typeFilter);
1300             const returned = checkReturned(row, elem, parsedQuery.typeFilter);
1301
1302             addIntoResults(results_in_args, fullId, pos, index, in_args);
1303             addIntoResults(results_returned, fullId, pos, index, returned);
1304
1305             if (!typePassesFilter(parsedQuery.typeFilter, row.ty)) {
1306                 return;
1307             }
1308             const searchWord = searchWords[pos];
1309
1310             if (parsedQuery.literalSearch) {
1311                 if (searchWord === elem.name) {
1312                     addIntoResults(results_others, fullId, pos, -1, 0);
1313                 }
1314                 return;
1315             }
1316
1317             // No need to check anything else if it's a "pure" generics search.
1318             if (elem.name.length === 0) {
1319                 if (row.type !== null) {
1320                     lev = checkGenerics(row.type, elem, MAX_LEV_DISTANCE + 1);
1321                     addIntoResults(results_others, fullId, pos, index, lev);
1322                 }
1323                 return;
1324             }
1325
1326             if (elem.fullPath.length > 1) {
1327                 lev = checkPath(elem.pathWithoutLast, row);
1328                 if (lev > MAX_LEV_DISTANCE || (parsedQuery.literalSearch && lev !== 0)) {
1329                     return;
1330                 } else if (lev > 0) {
1331                     lev_add = lev / 10;
1332                 }
1333             }
1334
1335             if (searchWord.indexOf(elem.pathLast) > -1 ||
1336                 row.normalizedName.indexOf(elem.pathLast) > -1
1337             ) {
1338                 // filter type: ... queries
1339                 if (!results_others[fullId] !== undefined) {
1340                     index = row.normalizedName.indexOf(elem.pathLast);
1341                 }
1342             }
1343             lev = levenshtein(searchWord, elem.pathLast);
1344             if (lev > 0 && elem.pathLast.length > 2 && searchWord.indexOf(elem.pathLast) > -1) {
1345                 if (elem.pathLast.length < 6) {
1346                     lev = 1;
1347                 } else {
1348                     lev = 0;
1349                 }
1350             }
1351             lev += lev_add;
1352             if (lev > MAX_LEV_DISTANCE) {
1353                 return;
1354             } else if (index !== -1 && elem.fullPath.length < 2) {
1355                 lev -= 1;
1356             }
1357             if (lev < 0) {
1358                 lev = 0;
1359             }
1360             addIntoResults(results_others, fullId, pos, index, lev);
1361         }
1362
1363         /**
1364          * This function is called in case the query has more than one element. In this case, it'll
1365          * try to match the items which validates all the elements. For `aa -> bb` will look for
1366          * functions which have a parameter `aa` and has `bb` in its returned values.
1367          *
1368          * @param {Row} row
1369          * @param {integer} pos      - Position in the `searchIndex`.
1370          * @param {Object} results
1371          */
1372         function handleArgs(row, pos, results) {
1373             if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
1374                 return;
1375             }
1376
1377             let totalLev = 0;
1378             let nbLev = 0;
1379
1380             // If the result is too "bad", we return false and it ends this search.
1381             function checkArgs(elems, callback) {
1382                 for (const elem of elems) {
1383                     // There is more than one parameter to the query so all checks should be "exact"
1384                     const lev = callback(row, elem, NO_TYPE_FILTER);
1385                     if (lev <= 1) {
1386                         nbLev += 1;
1387                         totalLev += lev;
1388                     } else {
1389                         return false;
1390                     }
1391                 }
1392                 return true;
1393             }
1394             if (!checkArgs(parsedQuery.elems, findArg)) {
1395                 return;
1396             }
1397             if (!checkArgs(parsedQuery.returned, checkReturned)) {
1398                 return;
1399             }
1400
1401             if (nbLev === 0) {
1402                 return;
1403             }
1404             const lev = Math.round(totalLev / nbLev);
1405             addIntoResults(results, row.id, pos, 0, lev);
1406         }
1407
1408         function innerRunQuery() {
1409             let elem, i, nSearchWords, in_returned, row;
1410
1411             if (parsedQuery.foundElems === 1) {
1412                 if (parsedQuery.elems.length === 1) {
1413                     elem = parsedQuery.elems[0];
1414                     for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1415                         // It means we want to check for this element everywhere (in names, args and
1416                         // returned).
1417                         handleSingleArg(
1418                             searchIndex[i],
1419                             i,
1420                             elem,
1421                             results_others,
1422                             results_in_args,
1423                             results_returned
1424                         );
1425                     }
1426                 } else if (parsedQuery.returned.length === 1) {
1427                     // We received one returned argument to check, so looking into returned values.
1428                     elem = parsedQuery.returned[0];
1429                     for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1430                         row = searchIndex[i];
1431                         in_returned = checkReturned(row, elem, parsedQuery.typeFilter);
1432                         addIntoResults(results_others, row.id, i, -1, in_returned);
1433                     }
1434                 }
1435             } else if (parsedQuery.foundElems > 0) {
1436                 for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1437                     handleArgs(searchIndex[i], i, results_others);
1438                 }
1439             }
1440         }
1441
1442         if (parsedQuery.error === null) {
1443             innerRunQuery();
1444         }
1445
1446         const ret = createQueryResults(
1447             sortResults(results_in_args, true),
1448             sortResults(results_returned, true),
1449             sortResults(results_others, false),
1450             parsedQuery);
1451         handleAliases(ret, parsedQuery.original.replace(/"/g, ""), filterCrates);
1452         if (parsedQuery.error !== null && ret.others.length !== 0) {
1453             // It means some doc aliases were found so let's "remove" the error!
1454             ret.query.error = null;
1455         }
1456         return ret;
1457     }
1458
1459     /**
1460      * Validate performs the following boolean logic. For example:
1461      * "File::open" will give IF A PARENT EXISTS => ("file" && "open")
1462      * exists in (name || path || parent) OR => ("file" && "open") exists in
1463      * (name || path )
1464      *
1465      * This could be written functionally, but I wanted to minimise
1466      * functions on stack.
1467      *
1468      * @param  {string} name   - The name of the result
1469      * @param  {string} path   - The path of the result
1470      * @param  {string} keys   - The keys to be used (["file", "open"])
1471      * @param  {Object} parent - The parent of the result
1472      *
1473      * @return {boolean}       - Whether the result is valid or not
1474      */
1475     function validateResult(name, path, keys, parent) {
1476         if (!keys || !keys.length) {
1477             return true;
1478         }
1479         for (const key of keys) {
1480             // each check is for validation so we negate the conditions and invalidate
1481             if (!(
1482                 // check for an exact name match
1483                 name.indexOf(key) > -1 ||
1484                 // then an exact path match
1485                 path.indexOf(key) > -1 ||
1486                 // next if there is a parent, check for exact parent match
1487                 (parent !== undefined && parent.name !== undefined &&
1488                     parent.name.toLowerCase().indexOf(key) > -1) ||
1489                 // lastly check to see if the name was a levenshtein match
1490                 levenshtein(name, key) <= MAX_LEV_DISTANCE)) {
1491                 return false;
1492             }
1493         }
1494         return true;
1495     }
1496
1497     function nextTab(direction) {
1498         const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length;
1499         searchState.focusedByTab[searchState.currentTab] = document.activeElement;
1500         printTab(next);
1501         focusSearchResult();
1502     }
1503
1504     // Focus the first search result on the active tab, or the result that
1505     // was focused last time this tab was active.
1506     function focusSearchResult() {
1507         const target = searchState.focusedByTab[searchState.currentTab] ||
1508             document.querySelectorAll(".search-results.active a").item(0) ||
1509             document.querySelectorAll("#titles > button").item(searchState.currentTab);
1510         if (target) {
1511             target.focus();
1512         }
1513     }
1514
1515     function buildHrefAndPath(item) {
1516         let displayPath;
1517         let href;
1518         const type = itemTypes[item.ty];
1519         const name = item.name;
1520         let path = item.path;
1521
1522         if (type === "mod") {
1523             displayPath = path + "::";
1524             href = window.rootPath + path.replace(/::/g, "/") + "/" +
1525                    name + "/index.html";
1526         } else if (type === "import") {
1527             displayPath = item.path + "::";
1528             href = window.rootPath + item.path.replace(/::/g, "/") + "/index.html#reexport." + name;
1529         } else if (type === "primitive" || type === "keyword") {
1530             displayPath = "";
1531             href = window.rootPath + path.replace(/::/g, "/") +
1532                    "/" + type + "." + name + ".html";
1533         } else if (type === "externcrate") {
1534             displayPath = "";
1535             href = window.rootPath + name + "/index.html";
1536         } else if (item.parent !== undefined) {
1537             const myparent = item.parent;
1538             let anchor = "#" + type + "." + name;
1539             const parentType = itemTypes[myparent.ty];
1540             let pageType = parentType;
1541             let pageName = myparent.name;
1542
1543             if (parentType === "primitive") {
1544                 displayPath = myparent.name + "::";
1545             } else if (type === "structfield" && parentType === "variant") {
1546                 // Structfields belonging to variants are special: the
1547                 // final path element is the enum name.
1548                 const enumNameIdx = item.path.lastIndexOf("::");
1549                 const enumName = item.path.substr(enumNameIdx + 2);
1550                 path = item.path.substr(0, enumNameIdx);
1551                 displayPath = path + "::" + enumName + "::" + myparent.name + "::";
1552                 anchor = "#variant." + myparent.name + ".field." + name;
1553                 pageType = "enum";
1554                 pageName = enumName;
1555             } else {
1556                 displayPath = path + "::" + myparent.name + "::";
1557             }
1558             href = window.rootPath + path.replace(/::/g, "/") +
1559                    "/" + pageType +
1560                    "." + pageName +
1561                    ".html" + anchor;
1562         } else {
1563             displayPath = item.path + "::";
1564             href = window.rootPath + item.path.replace(/::/g, "/") +
1565                    "/" + type + "." + name + ".html";
1566         }
1567         return [displayPath, href];
1568     }
1569
1570     function escape(content) {
1571         const h1 = document.createElement("h1");
1572         h1.textContent = content;
1573         return h1.innerHTML;
1574     }
1575
1576     function pathSplitter(path) {
1577         const tmp = "<span>" + path.replace(/::/g, "::</span><span>");
1578         if (tmp.endsWith("<span>")) {
1579             return tmp.slice(0, tmp.length - 6);
1580         }
1581         return tmp;
1582     }
1583
1584     /**
1585      * Render a set of search results for a single tab.
1586      * @param {Array<?>}    array   - The search results for this tab
1587      * @param {ParsedQuery} query
1588      * @param {boolean}     display - True if this is the active tab
1589      */
1590     function addTab(array, query, display) {
1591         let extraClass = "";
1592         if (display === true) {
1593             extraClass = " active";
1594         }
1595
1596         const output = document.createElement("div");
1597         let length = 0;
1598         if (array.length > 0) {
1599             output.className = "search-results " + extraClass;
1600
1601             array.forEach(item => {
1602                 const name = item.name;
1603                 const type = itemTypes[item.ty];
1604
1605                 length += 1;
1606
1607                 let extra = "";
1608                 if (type === "primitive") {
1609                     extra = " <i>(primitive type)</i>";
1610                 } else if (type === "keyword") {
1611                     extra = " <i>(keyword)</i>";
1612                 }
1613
1614                 const link = document.createElement("a");
1615                 link.className = "result-" + type;
1616                 link.href = item.href;
1617
1618                 const wrapper = document.createElement("div");
1619                 const resultName = document.createElement("div");
1620                 resultName.className = "result-name";
1621
1622                 if (item.is_alias) {
1623                     const alias = document.createElement("span");
1624                     alias.className = "alias";
1625
1626                     const bold = document.createElement("b");
1627                     bold.innerText = item.alias;
1628                     alias.appendChild(bold);
1629
1630                     alias.insertAdjacentHTML(
1631                         "beforeend",
1632                         "<span class=\"grey\"><i>&nbsp;- see&nbsp;</i></span>");
1633
1634                     resultName.appendChild(alias);
1635                 }
1636                 resultName.insertAdjacentHTML(
1637                     "beforeend",
1638                     item.displayPath + "<span class=\"" + type + "\">" + name + extra + "</span>");
1639                 wrapper.appendChild(resultName);
1640
1641                 const description = document.createElement("div");
1642                 description.className = "desc";
1643                 const spanDesc = document.createElement("span");
1644                 spanDesc.insertAdjacentHTML("beforeend", item.desc);
1645
1646                 description.appendChild(spanDesc);
1647                 wrapper.appendChild(description);
1648                 link.appendChild(wrapper);
1649                 output.appendChild(link);
1650             });
1651         } else if (query.error === null) {
1652             output.className = "search-failed" + extraClass;
1653             output.innerHTML = "No results :(<br/>" +
1654                 "Try on <a href=\"https://duckduckgo.com/?q=" +
1655                 encodeURIComponent("rust " + query.userQuery) +
1656                 "\">DuckDuckGo</a>?<br/><br/>" +
1657                 "Or try looking in one of these:<ul><li>The <a " +
1658                 "href=\"https://doc.rust-lang.org/reference/index.html\">Rust Reference</a> " +
1659                 " for technical details about the language.</li><li><a " +
1660                 "href=\"https://doc.rust-lang.org/rust-by-example/index.html\">Rust By " +
1661                 "Example</a> for expository code examples.</a></li><li>The <a " +
1662                 "href=\"https://doc.rust-lang.org/book/index.html\">Rust Book</a> for " +
1663                 "introductions to language features and the language itself.</li><li><a " +
1664                 "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" +
1665                 " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>";
1666         }
1667         return [output, length];
1668     }
1669
1670     function makeTabHeader(tabNb, text, nbElems) {
1671         if (searchState.currentTab === tabNb) {
1672             return "<button class=\"selected\">" + text +
1673                    " <div class=\"count\">(" + nbElems + ")</div></button>";
1674         }
1675         return "<button>" + text + " <div class=\"count\">(" + nbElems + ")</div></button>";
1676     }
1677
1678     /**
1679      * @param {ResultsTable} results
1680      * @param {boolean} go_to_first
1681      * @param {string} filterCrates
1682      */
1683     function showResults(results, go_to_first, filterCrates) {
1684         const search = searchState.outputElement();
1685         if (go_to_first || (results.others.length === 1
1686             && getSettingValue("go-to-only-result") === "true"
1687             // By default, the search DOM element is "empty" (meaning it has no children not
1688             // text content). Once a search has been run, it won't be empty, even if you press
1689             // ESC or empty the search input (which also "cancels" the search).
1690             && (!search.firstChild || search.firstChild.innerText !== searchState.loadingText))
1691         ) {
1692             const elem = document.createElement("a");
1693             elem.href = results.others[0].href;
1694             removeClass(elem, "active");
1695             // For firefox, we need the element to be in the DOM so it can be clicked.
1696             document.body.appendChild(elem);
1697             elem.click();
1698             return;
1699         }
1700         if (results.query === undefined) {
1701             results.query = parseQuery(searchState.input.value);
1702         }
1703
1704         currentResults = results.query.userQuery;
1705
1706         const ret_others = addTab(results.others, results.query, true);
1707         const ret_in_args = addTab(results.in_args, results.query, false);
1708         const ret_returned = addTab(results.returned, results.query, false);
1709
1710         // Navigate to the relevant tab if the current tab is empty, like in case users search
1711         // for "-> String". If they had selected another tab previously, they have to click on
1712         // it again.
1713         let currentTab = searchState.currentTab;
1714         if ((currentTab === 0 && ret_others[1] === 0) ||
1715                 (currentTab === 1 && ret_in_args[1] === 0) ||
1716                 (currentTab === 2 && ret_returned[1] === 0)) {
1717             if (ret_others[1] !== 0) {
1718                 currentTab = 0;
1719             } else if (ret_in_args[1] !== 0) {
1720                 currentTab = 1;
1721             } else if (ret_returned[1] !== 0) {
1722                 currentTab = 2;
1723             }
1724         }
1725
1726         let crates = "";
1727         if (window.ALL_CRATES.length > 1) {
1728             crates = " in <select id=\"crate-search\"><option value=\"All crates\">" +
1729                 "All crates</option>";
1730             for (const c of window.ALL_CRATES) {
1731                 crates += `<option value="${c}" ${c == filterCrates && "selected"}>${c}</option>`;
1732             }
1733             crates += "</select>";
1734         }
1735
1736         let typeFilter = "";
1737         if (results.query.typeFilter !== NO_TYPE_FILTER) {
1738             typeFilter = " (type: " + escape(itemTypes[results.query.typeFilter]) + ")";
1739         }
1740
1741         let output = "<div id=\"search-settings\">" +
1742             `<h1 class="search-results-title">Results for ${escape(results.query.userQuery)}` +
1743             `${typeFilter}</h1> in ${crates} </div>`;
1744         if (results.query.error !== null) {
1745             output += `<h3>Query parser error: "${results.query.error}".</h3>`;
1746             output += "<div id=\"titles\">" +
1747                 makeTabHeader(0, "In Names", ret_others[1]) +
1748                 "</div>";
1749             currentTab = 0;
1750         } else if (results.query.foundElems <= 1 && results.query.returned.length === 0) {
1751             output += "<div id=\"titles\">" +
1752                 makeTabHeader(0, "In Names", ret_others[1]) +
1753                 makeTabHeader(1, "In Parameters", ret_in_args[1]) +
1754                 makeTabHeader(2, "In Return Types", ret_returned[1]) +
1755                 "</div>";
1756         } else {
1757             const signatureTabTitle =
1758                 results.query.elems.length === 0 ? "In Function Return Types" :
1759                 results.query.returned.length === 0 ? "In Function Parameters" :
1760                 "In Function Signatures";
1761             output += "<div id=\"titles\">" +
1762                 makeTabHeader(0, signatureTabTitle, ret_others[1]) +
1763                 "</div>";
1764             currentTab = 0;
1765         }
1766
1767         const resultsElem = document.createElement("div");
1768         resultsElem.id = "results";
1769         resultsElem.appendChild(ret_others[0]);
1770         resultsElem.appendChild(ret_in_args[0]);
1771         resultsElem.appendChild(ret_returned[0]);
1772
1773         search.innerHTML = output;
1774         const crateSearch = document.getElementById("crate-search");
1775         if (crateSearch) {
1776             crateSearch.addEventListener("input", updateCrate);
1777         }
1778         search.appendChild(resultsElem);
1779         // Reset focused elements.
1780         searchState.showResults(search);
1781         const elems = document.getElementById("titles").childNodes;
1782         searchState.focusedByTab = [];
1783         let i = 0;
1784         for (const elem of elems) {
1785             const j = i;
1786             elem.onclick = () => printTab(j);
1787             searchState.focusedByTab.push(null);
1788             i += 1;
1789         }
1790         printTab(currentTab);
1791     }
1792
1793     /**
1794      * Perform a search based on the current state of the search input element
1795      * and display the results.
1796      * @param {Event}   [e]       - The event that triggered this search, if any
1797      * @param {boolean} [forced]
1798      */
1799     function search(e, forced) {
1800         const params = searchState.getQueryStringParams();
1801         const query = parseQuery(searchState.input.value.trim());
1802
1803         if (e) {
1804             e.preventDefault();
1805         }
1806
1807         if (!forced && query.userQuery === currentResults) {
1808             if (query.userQuery.length > 0) {
1809                 putBackSearch();
1810             }
1811             return;
1812         }
1813
1814         let filterCrates = getFilterCrates();
1815
1816         // In case we have no information about the saved crate and there is a URL query parameter,
1817         // we override it with the URL query parameter.
1818         if (filterCrates === null && params["filter-crate"] !== undefined) {
1819             filterCrates = params["filter-crate"];
1820         }
1821
1822         // Update document title to maintain a meaningful browser history
1823         searchState.title = "Results for " + query.original + " - Rust";
1824
1825         // Because searching is incremental by character, only the most
1826         // recent search query is added to the browser history.
1827         if (browserSupportsHistoryApi()) {
1828             const newURL = buildUrl(query.original, filterCrates);
1829
1830             if (!history.state && !params.search) {
1831                 history.pushState(null, "", newURL);
1832             } else {
1833                 history.replaceState(null, "", newURL);
1834             }
1835         }
1836
1837         showResults(
1838             execQuery(query, searchWords, filterCrates),
1839             params.go_to_first,
1840             filterCrates);
1841     }
1842
1843     function buildIndex(rawSearchIndex) {
1844         searchIndex = [];
1845         /**
1846          * @type {Array<string>}
1847          */
1848         const searchWords = [];
1849         let i, word;
1850         let currentIndex = 0;
1851         let id = 0;
1852
1853         for (const crate in rawSearchIndex) {
1854             if (!hasOwnPropertyRustdoc(rawSearchIndex, crate)) {
1855                 continue;
1856             }
1857
1858             let crateSize = 0;
1859
1860             /**
1861              * The raw search data for a given crate. `n`, `t`, `d`, and `q`, `i`, and `f`
1862              * are arrays with the same length. n[i] contains the name of an item.
1863              * t[i] contains the type of that item (as a small integer that represents an
1864              * offset in `itemTypes`). d[i] contains the description of that item.
1865              *
1866              * q[i] contains the full path of the item, or an empty string indicating
1867              * "same as q[i-1]".
1868              *
1869              * i[i], f[i] are a mystery.
1870              *
1871              * `a` defines aliases with an Array of pairs: [name, offset], where `offset`
1872              * points into the n/t/d/q/i/f arrays.
1873              *
1874              * `doc` contains the description of the crate.
1875              *
1876              * `p` is a mystery and isn't the same length as n/t/d/q/i/f.
1877              *
1878              * @type {{
1879              *   doc: string,
1880              *   a: Object,
1881              *   n: Array<string>,
1882              *   t: Array<Number>,
1883              *   d: Array<string>,
1884              *   q: Array<string>,
1885              *   i: Array<Number>,
1886              *   f: Array<Array<?>>,
1887              *   p: Array<Object>,
1888              * }}
1889              */
1890             const crateCorpus = rawSearchIndex[crate];
1891
1892             searchWords.push(crate);
1893             // This object should have exactly the same set of fields as the "row"
1894             // object defined below. Your JavaScript runtime will thank you.
1895             // https://mathiasbynens.be/notes/shapes-ics
1896             const crateRow = {
1897                 crate: crate,
1898                 ty: 1, // == ExternCrate
1899                 name: crate,
1900                 path: "",
1901                 desc: crateCorpus.doc,
1902                 parent: undefined,
1903                 type: null,
1904                 id: id,
1905                 normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""),
1906             };
1907             id += 1;
1908             searchIndex.push(crateRow);
1909             currentIndex += 1;
1910
1911             // an array of (Number) item types
1912             const itemTypes = crateCorpus.t;
1913             // an array of (String) item names
1914             const itemNames = crateCorpus.n;
1915             // an array of (String) full paths (or empty string for previous path)
1916             const itemPaths = crateCorpus.q;
1917             // an array of (String) descriptions
1918             const itemDescs = crateCorpus.d;
1919             // an array of (Number) the parent path index + 1 to `paths`, or 0 if none
1920             const itemParentIdxs = crateCorpus.i;
1921             // an array of (Object | null) the type of the function, if any
1922             const itemFunctionSearchTypes = crateCorpus.f;
1923             // an array of [(Number) item type,
1924             //              (String) name]
1925             const paths = crateCorpus.p;
1926             // an array of [(String) alias name
1927             //             [Number] index to items]
1928             const aliases = crateCorpus.a;
1929
1930             // convert `rawPaths` entries into object form
1931             let len = paths.length;
1932             for (i = 0; i < len; ++i) {
1933                 paths[i] = {ty: paths[i][0], name: paths[i][1]};
1934             }
1935
1936             // convert `item*` into an object form, and construct word indices.
1937             //
1938             // before any analysis is performed lets gather the search terms to
1939             // search against apart from the rest of the data.  This is a quick
1940             // operation that is cached for the life of the page state so that
1941             // all other search operations have access to this cached data for
1942             // faster analysis operations
1943             len = itemTypes.length;
1944             let lastPath = "";
1945             for (i = 0; i < len; ++i) {
1946                 // This object should have exactly the same set of fields as the "crateRow"
1947                 // object defined above.
1948                 if (typeof itemNames[i] === "string") {
1949                     word = itemNames[i].toLowerCase();
1950                     searchWords.push(word);
1951                 } else {
1952                     word = "";
1953                     searchWords.push("");
1954                 }
1955                 const row = {
1956                     crate: crate,
1957                     ty: itemTypes[i],
1958                     name: itemNames[i],
1959                     path: itemPaths[i] ? itemPaths[i] : lastPath,
1960                     desc: itemDescs[i],
1961                     parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
1962                     type: itemFunctionSearchTypes[i],
1963                     id: id,
1964                     normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
1965                 };
1966                 id += 1;
1967                 searchIndex.push(row);
1968                 lastPath = row.path;
1969                 crateSize += 1;
1970             }
1971
1972             if (aliases) {
1973                 ALIASES[crate] = Object.create(null);
1974                 for (const alias_name in aliases) {
1975                     if (!hasOwnPropertyRustdoc(aliases, alias_name)) {
1976                         continue;
1977                     }
1978
1979                     if (!hasOwnPropertyRustdoc(ALIASES[crate], alias_name)) {
1980                         ALIASES[crate][alias_name] = [];
1981                     }
1982                     for (const local_alias of aliases[alias_name]) {
1983                         ALIASES[crate][alias_name].push(local_alias + currentIndex);
1984                     }
1985                 }
1986             }
1987             currentIndex += crateSize;
1988         }
1989         return searchWords;
1990     }
1991
1992     /**
1993      * Callback for when the search form is submitted.
1994      * @param {Event} [e] - The event that triggered this call, if any
1995      */
1996     function onSearchSubmit(e) {
1997         e.preventDefault();
1998         searchState.clearInputTimeout();
1999         search();
2000     }
2001
2002     function putBackSearch() {
2003         const search_input = searchState.input;
2004         if (!searchState.input) {
2005             return;
2006         }
2007         if (search_input.value !== "" && !searchState.isDisplayed()) {
2008             searchState.showResults();
2009             if (browserSupportsHistoryApi()) {
2010                 history.replaceState(null, "",
2011                     buildUrl(search_input.value, getFilterCrates()));
2012             }
2013             document.title = searchState.title;
2014         }
2015     }
2016
2017     function registerSearchEvents() {
2018         const searchAfter500ms = () => {
2019             searchState.clearInputTimeout();
2020             if (searchState.input.value.length === 0) {
2021                 if (browserSupportsHistoryApi()) {
2022                     history.replaceState(null, window.currentCrate + " - Rust",
2023                         getNakedUrl() + window.location.hash);
2024                 }
2025                 searchState.hideResults();
2026             } else {
2027                 searchState.timeout = setTimeout(search, 500);
2028             }
2029         };
2030         searchState.input.onkeyup = searchAfter500ms;
2031         searchState.input.oninput = searchAfter500ms;
2032         document.getElementsByClassName("search-form")[0].onsubmit = onSearchSubmit;
2033         searchState.input.onchange = e => {
2034             if (e.target !== document.activeElement) {
2035                 // To prevent doing anything when it's from a blur event.
2036                 return;
2037             }
2038             // Do NOT e.preventDefault() here. It will prevent pasting.
2039             searchState.clearInputTimeout();
2040             // zero-timeout necessary here because at the time of event handler execution the
2041             // pasted content is not in the input field yet. Shouldn’t make any difference for
2042             // change, though.
2043             setTimeout(search, 0);
2044         };
2045         searchState.input.onpaste = searchState.input.onchange;
2046
2047         searchState.outputElement().addEventListener("keydown", e => {
2048             // We only handle unmodified keystrokes here. We don't want to interfere with,
2049             // for instance, alt-left and alt-right for history navigation.
2050             if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) {
2051                 return;
2052             }
2053             // up and down arrow select next/previous search result, or the
2054             // search box if we're already at the top.
2055             if (e.which === 38) { // up
2056                 const previous = document.activeElement.previousElementSibling;
2057                 if (previous) {
2058                     previous.focus();
2059                 } else {
2060                     searchState.focus();
2061                 }
2062                 e.preventDefault();
2063             } else if (e.which === 40) { // down
2064                 const next = document.activeElement.nextElementSibling;
2065                 if (next) {
2066                     next.focus();
2067                 }
2068                 const rect = document.activeElement.getBoundingClientRect();
2069                 if (window.innerHeight - rect.bottom < rect.height) {
2070                     window.scrollBy(0, rect.height);
2071                 }
2072                 e.preventDefault();
2073             } else if (e.which === 37) { // left
2074                 nextTab(-1);
2075                 e.preventDefault();
2076             } else if (e.which === 39) { // right
2077                 nextTab(1);
2078                 e.preventDefault();
2079             }
2080         });
2081
2082         searchState.input.addEventListener("keydown", e => {
2083             if (e.which === 40) { // down
2084                 focusSearchResult();
2085                 e.preventDefault();
2086             }
2087         });
2088
2089         searchState.input.addEventListener("focus", () => {
2090             putBackSearch();
2091         });
2092
2093         searchState.input.addEventListener("blur", () => {
2094             searchState.input.placeholder = searchState.input.origPlaceholder;
2095         });
2096
2097         // Push and pop states are used to add search results to the browser
2098         // history.
2099         if (browserSupportsHistoryApi()) {
2100             // Store the previous <title> so we can revert back to it later.
2101             const previousTitle = document.title;
2102
2103             window.addEventListener("popstate", e => {
2104                 const params = searchState.getQueryStringParams();
2105                 // Revert to the previous title manually since the History
2106                 // API ignores the title parameter.
2107                 document.title = previousTitle;
2108                 // When browsing forward to search results the previous
2109                 // search will be repeated, so the currentResults are
2110                 // cleared to ensure the search is successful.
2111                 currentResults = null;
2112                 // Synchronize search bar with query string state and
2113                 // perform the search. This will empty the bar if there's
2114                 // nothing there, which lets you really go back to a
2115                 // previous state with nothing in the bar.
2116                 if (params.search && params.search.length > 0) {
2117                     searchState.input.value = params.search;
2118                     // Some browsers fire "onpopstate" for every page load
2119                     // (Chrome), while others fire the event only when actually
2120                     // popping a state (Firefox), which is why search() is
2121                     // called both here and at the end of the startSearch()
2122                     // function.
2123                     search(e);
2124                 } else {
2125                     searchState.input.value = "";
2126                     // When browsing back from search results the main page
2127                     // visibility must be reset.
2128                     searchState.hideResults();
2129                 }
2130             });
2131         }
2132
2133         // This is required in firefox to avoid this problem: Navigating to a search result
2134         // with the keyboard, hitting enter, and then hitting back would take you back to
2135         // the doc page, rather than the search that should overlay it.
2136         // This was an interaction between the back-forward cache and our handlers
2137         // that try to sync state between the URL and the search input. To work around it,
2138         // do a small amount of re-init on page show.
2139         window.onpageshow = () => {
2140             const qSearch = searchState.getQueryStringParams().search;
2141             if (searchState.input.value === "" && qSearch) {
2142                 searchState.input.value = qSearch;
2143             }
2144             search();
2145         };
2146     }
2147
2148     function updateCrate(ev) {
2149         if (ev.target.value === "All crates") {
2150             // If we don't remove it from the URL, it'll be picked up again by the search.
2151             const params = searchState.getQueryStringParams();
2152             const query = searchState.input.value.trim();
2153             if (!history.state && !params.search) {
2154                 history.pushState(null, "", buildUrl(query, null));
2155             } else {
2156                 history.replaceState(null, "", buildUrl(query, null));
2157             }
2158         }
2159         // In case you "cut" the entry from the search input, then change the crate filter
2160         // before paste back the previous search, you get the old search results without
2161         // the filter. To prevent this, we need to remove the previous results.
2162         currentResults = null;
2163         search(undefined, true);
2164     }
2165
2166     /**
2167      *  @type {Array<string>}
2168      */
2169     const searchWords = buildIndex(rawSearchIndex);
2170     registerSearchEvents();
2171
2172     function runSearchIfNeeded() {
2173         // If there's a search term in the URL, execute the search now.
2174         if (searchState.getQueryStringParams().search) {
2175             search();
2176         }
2177     }
2178
2179     runSearchIfNeeded();
2180 };
2181
2182 if (window.searchIndex !== undefined) {
2183     initSearch(window.searchIndex);
2184 }
2185
2186 })();