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