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

   1 /* global addClass, getNakedUrl, getSettingValue, hasOwnPropertyRustdoc, initSearch, onEach */
   2 /* global onEachLazy, removeClass, searchState, updateLocalStorage */
   3
   4 (function() {
   5 // This mapping table should match the discriminants of
   6 // `rustdoc::html::item_type::ItemType` type in Rust.
   7 var itemTypes = [
   8     "mod",
   9     "externcrate",
  10     "import",
  11     "struct",
  12     "enum",
  13     "fn",
  14     "type",
  15     "static",
  16     "trait",
  17     "impl",
  18     "tymethod",
  19     "method",
  20     "structfield",
  21     "variant",
  22     "macro",
  23     "primitive",
  24     "associatedtype",
  25     "constant",
  26     "associatedconstant",
  27     "union",
  28     "foreigntype",
  29     "keyword",
  30     "existential",
  31     "attr",
  32     "derive",
  33     "traitalias",
  34 ];
  35
  36 // used for special search precedence
  37 var TY_PRIMITIVE = itemTypes.indexOf("primitive");
  38 var TY_KEYWORD = itemTypes.indexOf("keyword");
  39
  40 // In the search display, allows to switch between tabs.
  41 function printTab(nb) {
  42     if (nb === 0 || nb === 1 || nb === 2) {
  43         searchState.currentTab = nb;
  44     }
  45     var nb_copy = nb;
  46     onEachLazy(document.getElementById("titles").childNodes, function(elem) {
  47         if (nb_copy === 0) {
  48             addClass(elem, "selected");
  49         } else {
  50             removeClass(elem, "selected");
  51         }
  52         nb_copy -= 1;
  53     });
  54     onEachLazy(document.getElementById("results").childNodes, function(elem) {
  55         if (nb === 0) {
  56             addClass(elem, "active");
  57         } else {
  58             removeClass(elem, "active");
  59         }
  60         nb -= 1;
  61     });
  62 }
  63
  64 function removeEmptyStringsFromArray(x) {
  65     for (var i = 0, len = x.length; i < len; ++i) {
  66         if (x[i] === "") {
  67             x.splice(i, 1);
  68             i -= 1;
  69         }
  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 var levenshtein_row2 = [];
  81 function levenshtein(s1, s2) {
  82     if (s1 === s2) {
  83         return 0;
  84     }
  85     var s1_len = s1.length, s2_len = s2.length;
  86     if (s1_len && s2_len) {
  87         var i1 = 0, i2 = 0, a, b, c, c2, row = levenshtein_row2;
  88         while (i1 < s1_len) {
  89             row[i1] = ++i1;
  90         }
  91         while (i2 < s2_len) {
  92             c2 = s2.charCodeAt(i2);
  93             a = i2;
  94             ++i2;
  95             b = i2;
  96             for (i1 = 0; i1 < s1_len; ++i1) {
  97                 c = a + (s1.charCodeAt(i1) !== c2 ? 1 : 0);
  98                 a = row[i1];
  99                 b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
 100                 row[i1] = b;
 101             }
 102         }
 103         return b;
 104     }
 105     return s1_len + s2_len;
 106 }
 107
 108 window.initSearch = function(rawSearchIndex) {
 109     var MAX_LEV_DISTANCE = 3;
 110     var MAX_RESULTS = 200;
 111     var GENERICS_DATA = 2;
 112     var NAME = 0;
 113     var INPUTS_DATA = 0;
 114     var OUTPUT_DATA = 1;
 115     var NO_TYPE_FILTER = -1;
 116     /**
 117      *  @type {Array<Row>}
 118      */
 119     var searchIndex;
 120     /**
 121      *  @type {Array<string>}
 122      */
 123     var searchWords;
 124     var currentResults;
 125     var ALIASES = {};
 126     var params = searchState.getQueryStringParams();
 127
 128     // Populate search bar with query string search term when provided,
 129     // but only if the input bar is empty. This avoid the obnoxious issue
 130     // where you start trying to do a search, and the index loads, and
 131     // suddenly your search is gone!
 132     if (searchState.input.value === "") {
 133         searchState.input.value = params.search || "";
 134     }
 135
 136     /**
 137      * Executes the query and returns a list of results for each results tab.
 138      * @param  {Object}        query          - The user query
 139      * @param  {Array<string>} searchWords    - The list of search words to query against
 140      * @param  {string}        [filterCrates] - Crate to search in
 141      * @return {{
 142      *   in_args: Array<?>,
 143      *   returned: Array<?>,
 144      *   others: Array<?>
 145      * }}
 146      */
 147     function execQuery(query, searchWords, filterCrates) {
 148         function itemTypeFromName(typename) {
 149             for (var i = 0, len = itemTypes.length; i < len; ++i) {
 150                 if (itemTypes[i] === typename) {
 151                     return i;
 152                 }
 153             }
 154             return NO_TYPE_FILTER;
 155         }
 156
 157         var valLower = query.query.toLowerCase(),
 158             val = valLower,
 159             typeFilter = itemTypeFromName(query.type),
 160             results = {}, results_in_args = {}, results_returned = {},
 161             split = valLower.split("::");
 162
 163         removeEmptyStringsFromArray(split);
 164
 165         function transformResults(results) {
 166             var duplicates = {};
 167             var out = [];
 168
 169             for (var i = 0, len = results.length; i < len; ++i) {
 170                 var result = results[i];
 171
 172                 if (result.id > -1) {
 173                     var obj = searchIndex[result.id];
 174                     obj.lev = result.lev;
 175                     var res = buildHrefAndPath(obj);
 176                     obj.displayPath = pathSplitter(res[0]);
 177                     obj.fullPath = obj.displayPath + obj.name;
 178                     // To be sure than it some items aren't considered as duplicate.
 179                     obj.fullPath += "|" + obj.ty;
 180
 181                     if (duplicates[obj.fullPath]) {
 182                         continue;
 183                     }
 184                     duplicates[obj.fullPath] = true;
 185
 186                     obj.href = res[1];
 187                     out.push(obj);
 188                     if (out.length >= MAX_RESULTS) {
 189                         break;
 190                     }
 191                 }
 192             }
 193             return out;
 194         }
 195
 196         function sortResults(results, isType) {
 197             var ar = [];
 198             for (var entry in results) {
 199                 if (hasOwnPropertyRustdoc(results, entry)) {
 200                     var result = results[entry];
 201                     result.word = searchWords[result.id];
 202                     result.item = searchIndex[result.id] || {};
 203                     ar.push(result);
 204                 }
 205             }
 206             results = ar;
 207             // if there are no results then return to default and fail
 208             if (results.length === 0) {
 209                 return [];
 210             }
 211
 212             results.sort(function(aaa, bbb) {
 213                 var a, b;
 214
 215                 // sort by exact match with regard to the last word (mismatch goes later)
 216                 a = (aaa.word !== val);
 217                 b = (bbb.word !== val);
 218                 if (a !== b) { return a - b; }
 219
 220                 // Sort by non levenshtein results and then levenshtein results by the distance
 221                 // (less changes required to match means higher rankings)
 222                 a = (aaa.lev);
 223                 b = (bbb.lev);
 224                 if (a !== b) { return a - b; }
 225
 226                 // sort by crate (non-current crate goes later)
 227                 a = (aaa.item.crate !== window.currentCrate);
 228                 b = (bbb.item.crate !== window.currentCrate);
 229                 if (a !== b) { return a - b; }
 230
 231                 // sort by item name length (longer goes later)
 232                 a = aaa.word.length;
 233                 b = bbb.word.length;
 234                 if (a !== b) { return a - b; }
 235
 236                 // sort by item name (lexicographically larger goes later)
 237                 a = aaa.word;
 238                 b = bbb.word;
 239                 if (a !== b) { return (a > b ? +1 : -1); }
 240
 241                 // sort by index of keyword in item name (no literal occurrence goes later)
 242                 a = (aaa.index < 0);
 243                 b = (bbb.index < 0);
 244                 if (a !== b) { return a - b; }
 245                 // (later literal occurrence, if any, goes later)
 246                 a = aaa.index;
 247                 b = bbb.index;
 248                 if (a !== b) { return a - b; }
 249
 250                 // special precedence for primitive and keyword pages
 251                 if ((aaa.item.ty === TY_PRIMITIVE && bbb.item.ty !== TY_KEYWORD) ||
 252                     (aaa.item.ty === TY_KEYWORD && bbb.item.ty !== TY_PRIMITIVE)) {
 253                     return -1;
 254                 }
 255                 if ((bbb.item.ty === TY_PRIMITIVE && aaa.item.ty !== TY_PRIMITIVE) ||
 256                     (bbb.item.ty === TY_KEYWORD && aaa.item.ty !== TY_KEYWORD)) {
 257                     return 1;
 258                 }
 259
 260                 // sort by description (no description goes later)
 261                 a = (aaa.item.desc === "");
 262                 b = (bbb.item.desc === "");
 263                 if (a !== b) { return a - b; }
 264
 265                 // sort by type (later occurrence in `itemTypes` goes later)
 266                 a = aaa.item.ty;
 267                 b = bbb.item.ty;
 268                 if (a !== b) { return a - b; }
 269
 270                 // sort by path (lexicographically larger goes later)
 271                 a = aaa.item.path;
 272                 b = bbb.item.path;
 273                 if (a !== b) { return (a > b ? +1 : -1); }
 274
 275                 // que sera, sera
 276                 return 0;
 277             });
 278
 279             for (var i = 0, len = results.length; i < len; ++i) {
 280                 result = results[i];
 281
 282                 // this validation does not make sense when searching by types
 283                 if (result.dontValidate) {
 284                     continue;
 285                 }
 286                 var name = result.item.name.toLowerCase(),
 287                     path = result.item.path.toLowerCase(),
 288                     parent = result.item.parent;
 289
 290                 if (!isType && !validateResult(name, path, split, parent)) {
 291                     result.id = -1;
 292                 }
 293             }
 294             return transformResults(results);
 295         }
 296
 297         function extractGenerics(val) {
 298             val = val.toLowerCase();
 299             if (val.indexOf("<") !== -1) {
 300                 var values = val.substring(val.indexOf("<") + 1, val.lastIndexOf(">"));
 301                 return {
 302                     name: val.substring(0, val.indexOf("<")),
 303                     generics: values.split(/\s*,\s*/),
 304                 };
 305             }
 306             return {
 307                 name: val,
 308                 generics: [],
 309             };
 310         }
 311
 312         function checkGenerics(obj, val) {
 313             // The names match, but we need to be sure that all generics kinda
 314             // match as well.
 315             var tmp_lev, elem_name;
 316             if (val.generics.length > 0) {
 317                 if (obj.length > GENERICS_DATA &&
 318                       obj[GENERICS_DATA].length >= val.generics.length) {
 319                     var elems = Object.create(null);
 320                     var elength = obj[GENERICS_DATA].length;
 321                     for (var x = 0; x < elength; ++x) {
 322                         if (!elems[obj[GENERICS_DATA][x][NAME]]) {
 323                             elems[obj[GENERICS_DATA][x][NAME]] = 0;
 324                         }
 325                         elems[obj[GENERICS_DATA][x][NAME]] += 1;
 326                     }
 327                     var total = 0;
 328                     var done = 0;
 329                     // We need to find the type that matches the most to remove it in order
 330                     // to move forward.
 331                     var vlength = val.generics.length;
 332                     for (x = 0; x < vlength; ++x) {
 333                         var lev = MAX_LEV_DISTANCE + 1;
 334                         var firstGeneric = val.generics[x];
 335                         var match = null;
 336                         if (elems[firstGeneric]) {
 337                             match = firstGeneric;
 338                             lev = 0;
 339                         } else {
 340                             for (elem_name in elems) {
 341                                 tmp_lev = levenshtein(elem_name, firstGeneric);
 342                                 if (tmp_lev < lev) {
 343                                     lev = tmp_lev;
 344                                     match = elem_name;
 345                                 }
 346                             }
 347                         }
 348                         if (match !== null) {
 349                             elems[match] -= 1;
 350                             if (elems[match] == 0) {
 351                                 delete elems[match];
 352                             }
 353                             total += lev;
 354                             done += 1;
 355                         } else {
 356                             return MAX_LEV_DISTANCE + 1;
 357                         }
 358                     }
 359                     return Math.ceil(total / done);
 360                 }
 361             }
 362             return MAX_LEV_DISTANCE + 1;
 363         }
 364
 365         /**
 366           * This function checks if the object (`obj`) matches the given type (`val`) and its
 367           * generics (if any).
 368           *
 369           * @param {Object} obj
 370           * @param {string} val
 371           * @param {boolean} literalSearch
 372           *
 373           * @return {integer} - Returns a Levenshtein distance to the best match. If there is
 374           *                     no match, returns `MAX_LEV_DISTANCE + 1`.
 375           */
 376         function checkType(obj, val, literalSearch) {
 377             var lev_distance = MAX_LEV_DISTANCE + 1;
 378             var tmp_lev = MAX_LEV_DISTANCE + 1;
 379             var len, x, firstGeneric;
 380             if (obj[NAME] === val.name) {
 381                 if (literalSearch) {
 382                     if (val.generics && val.generics.length !== 0) {
 383                         if (obj.length > GENERICS_DATA &&
 384                              obj[GENERICS_DATA].length > 0) {
 385                             var elems = Object.create(null);
 386                             len = obj[GENERICS_DATA].length;
 387                             for (x = 0; x < len; ++x) {
 388                                 if (!elems[obj[GENERICS_DATA][x][NAME]]) {
 389                                     elems[obj[GENERICS_DATA][x][NAME]] = 0;
 390                                 }
 391                                 elems[obj[GENERICS_DATA][x][NAME]] += 1;
 392                             }
 393
 394                             len = val.generics.length;
 395                             for (x = 0; x < len; ++x) {
 396                                 firstGeneric = val.generics[x];
 397                                 if (elems[firstGeneric]) {
 398                                     elems[firstGeneric] -= 1;
 399                                 } else {
 400                                     // Something wasn't found and this is a literal search so
 401                                     // abort and return a "failing" distance.
 402                                     return MAX_LEV_DISTANCE + 1;
 403                                 }
 404                             }
 405                             // Everything was found, success!
 406                             return 0;
 407                         }
 408                         return MAX_LEV_DISTANCE + 1;
 409                     }
 410                     return 0;
 411                 } else {
 412                     // If the type has generics but don't match, then it won't return at this point.
 413                     // Otherwise, `checkGenerics` will return 0 and it'll return.
 414                     if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length !== 0) {
 415                         tmp_lev = checkGenerics(obj, val);
 416                         if (tmp_lev <= MAX_LEV_DISTANCE) {
 417                             return tmp_lev;
 418                         }
 419                     }
 420                 }
 421             } else if (literalSearch) {
 422                 var found = false;
 423                 if ((!val.generics || val.generics.length === 0) &&
 424                       obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
 425                     found = obj[GENERICS_DATA].some(
 426                         function(gen) {
 427                             return gen[NAME] === val.name;
 428                         });
 429                 }
 430                 return found ? 0 : MAX_LEV_DISTANCE + 1;
 431             }
 432             lev_distance = Math.min(levenshtein(obj[NAME], val.name), lev_distance);
 433             if (lev_distance <= MAX_LEV_DISTANCE) {
 434                 // The generics didn't match but the name kinda did so we give it
 435                 // a levenshtein distance value that isn't *this* good so it goes
 436                 // into the search results but not too high.
 437                 lev_distance = Math.ceil((checkGenerics(obj, val) + lev_distance) / 2);
 438             }
 439             if (obj.length > GENERICS_DATA && obj[GENERICS_DATA].length > 0) {
 440                 // We can check if the type we're looking for is inside the generics!
 441                 var olength = obj[GENERICS_DATA].length;
 442                 for (x = 0; x < olength; ++x) {
 443                     tmp_lev = Math.min(levenshtein(obj[GENERICS_DATA][x][NAME], val.name), tmp_lev);
 444                 }
 445                 if (tmp_lev !== 0) {
 446                     // If we didn't find a good enough result, we go check inside the generics of
 447                     // the generics.
 448                     for (x = 0; x < olength && tmp_lev !== 0; ++x) {
 449                         tmp_lev = Math.min(
 450                             checkType(obj[GENERICS_DATA][x], val, literalSearch),
 451                             tmp_lev
 452                         );
 453                     }
 454                 }
 455             }
 456             // Now whatever happens, the returned distance is "less good" so we should mark it
 457             // as such, and so we add 1 to the distance to make it "less good".
 458             return Math.min(lev_distance, tmp_lev) + 1;
 459         }
 460
 461         /**
 462          * This function checks if the object (`obj`) has an argument with the given type (`val`).
 463          *
 464          * @param {Object} obj
 465          * @param {string} val
 466          * @param {boolean} literalSearch
 467          * @param {integer} typeFilter
 468          *
 469          * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
 470          *                      match, returns `MAX_LEV_DISTANCE + 1`.
 471          */
 472         function findArg(obj, val, literalSearch, typeFilter) {
 473             var lev_distance = MAX_LEV_DISTANCE + 1;
 474
 475             if (obj && obj.type && obj.type[INPUTS_DATA] && obj.type[INPUTS_DATA].length > 0) {
 476                 var length = obj.type[INPUTS_DATA].length;
 477                 for (var i = 0; i < length; i++) {
 478                     var tmp = obj.type[INPUTS_DATA][i];
 479                     if (!typePassesFilter(typeFilter, tmp[1])) {
 480                         continue;
 481                     }
 482                     tmp = checkType(tmp, val, literalSearch);
 483                     if (tmp === 0) {
 484                         return 0;
 485                     } else if (literalSearch) {
 486                         continue;
 487                     }
 488                     lev_distance = Math.min(tmp, lev_distance);
 489                 }
 490             }
 491             return literalSearch ? MAX_LEV_DISTANCE + 1 : lev_distance;
 492         }
 493
 494         function checkReturned(obj, val, literalSearch, typeFilter) {
 495             var lev_distance = MAX_LEV_DISTANCE + 1;
 496
 497             if (obj && obj.type && obj.type.length > OUTPUT_DATA) {
 498                 var ret = obj.type[OUTPUT_DATA];
 499                 if (typeof ret[0] === "string") {
 500                     ret = [ret];
 501                 }
 502                 for (var x = 0, len = ret.length; x < len; ++x) {
 503                     var tmp = ret[x];
 504                     if (!typePassesFilter(typeFilter, tmp[1])) {
 505                         continue;
 506                     }
 507                     tmp = checkType(tmp, val, literalSearch);
 508                     if (tmp === 0) {
 509                         return 0;
 510                     } else if (literalSearch) {
 511                         continue;
 512                     }
 513                     lev_distance = Math.min(tmp, lev_distance);
 514                 }
 515             }
 516             return literalSearch ? MAX_LEV_DISTANCE + 1 : lev_distance;
 517         }
 518
 519         function checkPath(contains, lastElem, ty) {
 520             if (contains.length === 0) {
 521                 return 0;
 522             }
 523             var ret_lev = MAX_LEV_DISTANCE + 1;
 524             var path = ty.path.split("::");
 525
 526             if (ty.parent && ty.parent.name) {
 527                 path.push(ty.parent.name.toLowerCase());
 528             }
 529
 530             var length = path.length;
 531             var clength = contains.length;
 532             if (clength > length) {
 533                 return MAX_LEV_DISTANCE + 1;
 534             }
 535             for (var i = 0; i < length; ++i) {
 536                 if (i + clength > length) {
 537                     break;
 538                 }
 539                 var lev_total = 0;
 540                 var aborted = false;
 541                 for (var x = 0; x < clength; ++x) {
 542                     var lev = levenshtein(path[i + x], contains[x]);
 543                     if (lev > MAX_LEV_DISTANCE) {
 544                         aborted = true;
 545                         break;
 546                     }
 547                     lev_total += lev;
 548                 }
 549                 if (!aborted) {
 550                     ret_lev = Math.min(ret_lev, Math.round(lev_total / clength));
 551                 }
 552             }
 553             return ret_lev;
 554         }
 555
 556         function typePassesFilter(filter, type) {
 557             // No filter
 558             if (filter <= NO_TYPE_FILTER) return true;
 559
 560             // Exact match
 561             if (filter === type) return true;
 562
 563             // Match related items
 564             var name = itemTypes[type];
 565             switch (itemTypes[filter]) {
 566                 case "constant":
 567                     return name === "associatedconstant";
 568                 case "fn":
 569                     return name === "method" || name === "tymethod";
 570                 case "type":
 571                     return name === "primitive" || name === "associatedtype";
 572                 case "trait":
 573                     return name === "traitalias";
 574             }
 575
 576             // No match
 577             return false;
 578         }
 579
 580         function createAliasFromItem(item) {
 581             return {
 582                 crate: item.crate,
 583                 name: item.name,
 584                 path: item.path,
 585                 desc: item.desc,
 586                 ty: item.ty,
 587                 parent: item.parent,
 588                 type: item.type,
 589                 is_alias: true,
 590             };
 591         }
 592
 593         function handleAliases(ret, query, filterCrates) {
 594             // We separate aliases and crate aliases because we want to have current crate
 595             // aliases to be before the others in the displayed results.
 596             var aliases = [];
 597             var crateAliases = [];
 598             if (filterCrates !== undefined) {
 599                 if (ALIASES[filterCrates] && ALIASES[filterCrates][query.search]) {
 600                     var query_aliases = ALIASES[filterCrates][query.search];
 601                     var len = query_aliases.length;
 602                     for (var i = 0; i < len; ++i) {
 603                         aliases.push(createAliasFromItem(searchIndex[query_aliases[i]]));
 604                     }
 605                 }
 606             } else {
 607                 Object.keys(ALIASES).forEach(function(crate) {
 608                     if (ALIASES[crate][query.search]) {
 609                         var pushTo = crate === window.currentCrate ? crateAliases : aliases;
 610                         var query_aliases = ALIASES[crate][query.search];
 611                         var len = query_aliases.length;
 612                         for (var i = 0; i < len; ++i) {
 613                             pushTo.push(createAliasFromItem(searchIndex[query_aliases[i]]));
 614                         }
 615                     }
 616                 });
 617             }
 618
 619             var sortFunc = function(aaa, bbb) {
 620                 if (aaa.path < bbb.path) {
 621                     return 1;
 622                 } else if (aaa.path === bbb.path) {
 623                     return 0;
 624                 }
 625                 return -1;
 626             };
 627             crateAliases.sort(sortFunc);
 628             aliases.sort(sortFunc);
 629
 630             var pushFunc = function(alias) {
 631                 alias.alias = query.raw;
 632                 var res = buildHrefAndPath(alias);
 633                 alias.displayPath = pathSplitter(res[0]);
 634                 alias.fullPath = alias.displayPath + alias.name;
 635                 alias.href = res[1];
 636
 637                 ret.others.unshift(alias);
 638                 if (ret.others.length > MAX_RESULTS) {
 639                     ret.others.pop();
 640                 }
 641             };
 642             onEach(aliases, pushFunc);
 643             onEach(crateAliases, pushFunc);
 644         }
 645
 646         /**
 647          * This function adds the given result into the provided `res` map if it matches the
 648          * following condition:
 649          *
 650          * * If it is a "literal search" (`isExact`), then `lev` must be 0.
 651          * * If it is not a "literal search", `lev` must be <= `MAX_LEV_DISTANCE`.
 652          *
 653          * The `res` map contains information which will be used to sort the search results:
 654          *
 655          * * `fullId` is a `string`` used as the key of the object we use for the `res` map.
 656          * * `id` is the index in both `searchWords` and `searchIndex` arrays for this element.
 657          * * `index` is an `integer`` used to sort by the position of the word in the item's name.
 658          * * `lev` is the main metric used to sort the search results.
 659          *
 660          * @param {boolean} isExact
 661          * @param {Object} res
 662          * @param {string} fullId
 663          * @param {integer} id
 664          * @param {integer} index
 665          * @param {integer} lev
 666          */
 667         function addIntoResults(isExact, res, fullId, id, index, lev) {
 668             if (lev === 0 || (!isExact && lev <= MAX_LEV_DISTANCE)) {
 669                 if (res[fullId] !== undefined) {
 670                     var result = res[fullId];
 671                     if (result.dontValidate || result.lev <= lev) {
 672                         return;
 673                     }
 674                 }
 675                 res[fullId] = {
 676                     id: id,
 677                     index: index,
 678                     dontValidate: isExact,
 679                     lev: lev,
 680                 };
 681             }
 682         }
 683
 684         // quoted values mean literal search
 685         var nSearchWords = searchWords.length;
 686         var i, it;
 687         var ty;
 688         var fullId;
 689         var returned;
 690         var in_args;
 691         var len;
 692         if ((val.charAt(0) === "\"" || val.charAt(0) === "'") &&
 693             val.charAt(val.length - 1) === val.charAt(0))
 694         {
 695             val = extractGenerics(val.substr(1, val.length - 2));
 696             for (i = 0; i < nSearchWords; ++i) {
 697                 if (filterCrates !== undefined && searchIndex[i].crate !== filterCrates) {
 698                     continue;
 699                 }
 700                 in_args = findArg(searchIndex[i], val, true, typeFilter);
 701                 returned = checkReturned(searchIndex[i], val, true, typeFilter);
 702                 ty = searchIndex[i];
 703                 fullId = ty.id;
 704
 705                 if (searchWords[i] === val.name
 706                     && typePassesFilter(typeFilter, searchIndex[i].ty)) {
 707                     addIntoResults(true, results, fullId, i, -1, 0);
 708                 }
 709                 addIntoResults(true, results_in_args, fullId, i, -1, in_args);
 710                 addIntoResults(true, results_returned, fullId, i, -1, returned);
 711             }
 712             query.inputs = [val];
 713             query.output = val;
 714             query.search = val;
 715         // searching by type
 716         } else if (val.search("->") > -1) {
 717             var trimmer = function(s) { return s.trim(); };
 718             var parts = val.split("->").map(trimmer);
 719             var input = parts[0];
 720             // sort inputs so that order does not matter
 721             var inputs = input.split(",").map(trimmer).sort();
 722             for (i = 0, len = inputs.length; i < len; ++i) {
 723                 inputs[i] = extractGenerics(inputs[i]);
 724             }
 725             var output = extractGenerics(parts[1]);
 726
 727             for (i = 0; i < nSearchWords; ++i) {
 728                 if (filterCrates !== undefined && searchIndex[i].crate !== filterCrates) {
 729                     continue;
 730                 }
 731                 var type = searchIndex[i].type;
 732                 ty = searchIndex[i];
 733                 if (!type) {
 734                     continue;
 735                 }
 736                 fullId = ty.id;
 737
 738                 returned = checkReturned(ty, output, true, NO_TYPE_FILTER);
 739                 if (output.name === "*" || returned === 0) {
 740                     in_args = false;
 741                     var is_module = false;
 742
 743                     if (input === "*") {
 744                         is_module = true;
 745                     } else {
 746                         var firstNonZeroDistance = 0;
 747                         for (it = 0, len = inputs.length; it < len; it++) {
 748                             var distance = checkType(type, inputs[it], true);
 749                             if (distance > 0) {
 750                                 firstNonZeroDistance = distance;
 751                                 break;
 752                             }
 753                         }
 754                         in_args = firstNonZeroDistance;
 755                     }
 756                     addIntoResults(true, results_in_args, fullId, i, -1, in_args);
 757                     addIntoResults(true, results_returned, fullId, i, -1, returned);
 758                     if (is_module) {
 759                         addIntoResults(true, results, fullId, i, -1, 0);
 760                     }
 761                 }
 762             }
 763             query.inputs = inputs.map(function(input) {
 764                 return input.name;
 765             });
 766             query.output = output.name;
 767         } else {
 768             query.inputs = [val];
 769             query.output = val;
 770             query.search = val;
 771             // gather matching search results up to a certain maximum
 772             val = val.replace(/_/g, "");
 773
 774             var valGenerics = extractGenerics(val);
 775
 776             var paths = valLower.split("::");
 777             removeEmptyStringsFromArray(paths);
 778             val = paths[paths.length - 1];
 779             var contains = paths.slice(0, paths.length > 1 ? paths.length - 1 : 1);
 780
 781             var lev, j;
 782             for (j = 0; j < nSearchWords; ++j) {
 783                 ty = searchIndex[j];
 784                 if (!ty || (filterCrates !== undefined && ty.crate !== filterCrates)) {
 785                     continue;
 786                 }
 787                 var lev_add = 0;
 788                 if (paths.length > 1) {
 789                     lev = checkPath(contains, paths[paths.length - 1], ty);
 790                     if (lev > MAX_LEV_DISTANCE) {
 791                         continue;
 792                     } else if (lev > 0) {
 793                         lev_add = lev / 10;
 794                     }
 795                 }
 796
 797                 returned = MAX_LEV_DISTANCE + 1;
 798                 in_args = MAX_LEV_DISTANCE + 1;
 799                 var index = -1;
 800                 // we want lev results to go lower than others
 801                 lev = MAX_LEV_DISTANCE + 1;
 802                 fullId = ty.id;
 803
 804                 if (searchWords[j].indexOf(split[i]) > -1 ||
 805                     searchWords[j].indexOf(val) > -1 ||
 806                     ty.normalizedName.indexOf(val) > -1)
 807                 {
 808                     // filter type: ... queries
 809                     if (typePassesFilter(typeFilter, ty.ty) && results[fullId] === undefined) {
 810                         index = ty.normalizedName.indexOf(val);
 811                     }
 812                 }
 813                 if ((lev = levenshtein(searchWords[j], val)) <= MAX_LEV_DISTANCE) {
 814                     if (typePassesFilter(typeFilter, ty.ty)) {
 815                         lev += 1;
 816                     } else {
 817                         lev = MAX_LEV_DISTANCE + 1;
 818                     }
 819                 }
 820                 in_args = findArg(ty, valGenerics, false, typeFilter);
 821                 returned = checkReturned(ty, valGenerics, false, typeFilter);
 822
 823                 lev += lev_add;
 824                 if (lev > 0 && val.length > 3 && searchWords[j].indexOf(val) > -1) {
 825                     if (val.length < 6) {
 826                         lev -= 1;
 827                     } else {
 828                         lev = 0;
 829                     }
 830                 }
 831                 addIntoResults(false, results_in_args, fullId, j, index, in_args);
 832                 addIntoResults(false, results_returned, fullId, j, index, returned);
 833                 if (typePassesFilter(typeFilter, ty.ty) &&
 834                         (index !== -1 || lev <= MAX_LEV_DISTANCE)) {
 835                     if (index !== -1 && paths.length < 2) {
 836                         lev = 0;
 837                     }
 838                     addIntoResults(false, results, fullId, j, index, lev);
 839                 }
 840             }
 841         }
 842
 843         var ret = {
 844             "in_args": sortResults(results_in_args, true),
 845             "returned": sortResults(results_returned, true),
 846             "others": sortResults(results, false),
 847         };
 848         handleAliases(ret, query, filterCrates);
 849         return ret;
 850     }
 851
 852     /**
 853      * Validate performs the following boolean logic. For example:
 854      * "File::open" will give IF A PARENT EXISTS => ("file" && "open")
 855      * exists in (name || path || parent) OR => ("file" && "open") exists in
 856      * (name || path )
 857      *
 858      * This could be written functionally, but I wanted to minimise
 859      * functions on stack.
 860      *
 861      * @param  {string} name   - The name of the result
 862      * @param  {string} path   - The path of the result
 863      * @param  {string} keys   - The keys to be used (["file", "open"])
 864      * @param  {Object} parent - The parent of the result
 865      * @return {boolean}       - Whether the result is valid or not
 866      */
 867     function validateResult(name, path, keys, parent) {
 868         for (var i = 0, len = keys.length; i < len; ++i) {
 869             // each check is for validation so we negate the conditions and invalidate
 870             if (!(
 871                 // check for an exact name match
 872                 name.indexOf(keys[i]) > -1 ||
 873                 // then an exact path match
 874                 path.indexOf(keys[i]) > -1 ||
 875                 // next if there is a parent, check for exact parent match
 876                 (parent !== undefined && parent.name !== undefined &&
 877                     parent.name.toLowerCase().indexOf(keys[i]) > -1) ||
 878                 // lastly check to see if the name was a levenshtein match
 879                 levenshtein(name, keys[i]) <= MAX_LEV_DISTANCE)) {
 880                 return false;
 881             }
 882         }
 883         return true;
 884     }
 885
 886     /**
 887      * Parse a string into a query object.
 888      *
 889      * @param {string} raw - The text that the user typed.
 890      * @returns {ParsedQuery}
 891      */
 892     function getQuery(raw) {
 893         var matches, type = "", query;
 894         query = raw;
 895
 896         matches = query.match(/^(fn|mod|struct|enum|trait|type|const|macro)\s*:\s*/i);
 897         if (matches) {
 898             type = matches[1].replace(/^const$/, "constant");
 899             query = query.substring(matches[0].length);
 900         }
 901
 902         return {
 903             raw: raw,
 904             query: query,
 905             type: type,
 906             id: query + type
 907         };
 908     }
 909
 910     function nextTab(direction) {
 911         var next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length;
 912         searchState.focusedByTab[searchState.currentTab] = document.activeElement;
 913         printTab(next);
 914         focusSearchResult();
 915     }
 916
 917     // Focus the first search result on the active tab, or the result that
 918     // was focused last time this tab was active.
 919     function focusSearchResult() {
 920         var target = searchState.focusedByTab[searchState.currentTab] ||
 921             document.querySelectorAll(".search-results.active a").item(0) ||
 922             document.querySelectorAll("#titles > button").item(searchState.currentTab);
 923         if (target) {
 924             target.focus();
 925         }
 926     }
 927
 928     function buildHrefAndPath(item) {
 929         var displayPath;
 930         var href;
 931         var type = itemTypes[item.ty];
 932         var name = item.name;
 933         var path = item.path;
 934
 935         if (type === "mod") {
 936             displayPath = path + "::";
 937             href = window.rootPath + path.replace(/::/g, "/") + "/" +
 938                    name + "/index.html";
 939         } else if (type === "primitive" || type === "keyword") {
 940             displayPath = "";
 941             href = window.rootPath + path.replace(/::/g, "/") +
 942                    "/" + type + "." + name + ".html";
 943         } else if (type === "externcrate") {
 944             displayPath = "";
 945             href = window.rootPath + name + "/index.html";
 946         } else if (item.parent !== undefined) {
 947             var myparent = item.parent;
 948             var anchor = "#" + type + "." + name;
 949             var parentType = itemTypes[myparent.ty];
 950             var pageType = parentType;
 951             var pageName = myparent.name;
 952
 953             if (parentType === "primitive") {
 954                 displayPath = myparent.name + "::";
 955             } else if (type === "structfield" && parentType === "variant") {
 956                 // Structfields belonging to variants are special: the
 957                 // final path element is the enum name.
 958                 var enumNameIdx = item.path.lastIndexOf("::");
 959                 var enumName = item.path.substr(enumNameIdx + 2);
 960                 path = item.path.substr(0, enumNameIdx);
 961                 displayPath = path + "::" + enumName + "::" + myparent.name + "::";
 962                 anchor = "#variant." + myparent.name + ".field." + name;
 963                 pageType = "enum";
 964                 pageName = enumName;
 965             } else {
 966                 displayPath = path + "::" + myparent.name + "::";
 967             }
 968             href = window.rootPath + path.replace(/::/g, "/") +
 969                    "/" + pageType +
 970                    "." + pageName +
 971                    ".html" + anchor;
 972         } else {
 973             displayPath = item.path + "::";
 974             href = window.rootPath + item.path.replace(/::/g, "/") +
 975                    "/" + type + "." + name + ".html";
 976         }
 977         return [displayPath, href];
 978     }
 979
 980     function escape(content) {
 981         var h1 = document.createElement("h1");
 982         h1.textContent = content;
 983         return h1.innerHTML;
 984     }
 985
 986     function pathSplitter(path) {
 987         var tmp = "<span>" + path.replace(/::/g, "::</span><span>");
 988         if (tmp.endsWith("<span>")) {
 989             return tmp.slice(0, tmp.length - 6);
 990         }
 991         return tmp;
 992     }
 993
 994     /**
 995      * Render a set of search results for a single tab.
 996      * @param {Array<?>}    array   - The search results for this tab
 997      * @param {ParsedQuery} query
 998      * @param {boolean}     display - True if this is the active tab
 999      */
1000     function addTab(array, query, display) {
1001         var extraClass = "";
1002         if (display === true) {
1003             extraClass = " active";
1004         }
1005
1006         var output = document.createElement("div");
1007         var length = 0;
1008         if (array.length > 0) {
1009             output.className = "search-results " + extraClass;
1010
1011             array.forEach(function(item) {
1012                 var name = item.name;
1013                 var type = itemTypes[item.ty];
1014
1015                 length += 1;
1016
1017                 var extra = "";
1018                 if (type === "primitive") {
1019                     extra = " <i>(primitive type)</i>";
1020                 } else if (type === "keyword") {
1021                     extra = " <i>(keyword)</i>";
1022                 }
1023
1024                 var link = document.createElement("a");
1025                 link.className = "result-" + type;
1026                 link.href = item.href;
1027
1028                 var wrapper = document.createElement("div");
1029                 var resultName = document.createElement("div");
1030                 resultName.className = "result-name";
1031
1032                 if (item.is_alias) {
1033                     var alias = document.createElement("span");
1034                     alias.className = "alias";
1035
1036                     var bold = document.createElement("b");
1037                     bold.innerText = item.alias;
1038                     alias.appendChild(bold);
1039
1040                     alias.insertAdjacentHTML(
1041                         "beforeend",
1042                         "<span class=\"grey\"><i>&nbsp;- see&nbsp;</i></span>");
1043
1044                     resultName.appendChild(alias);
1045                 }
1046                 resultName.insertAdjacentHTML(
1047                     "beforeend",
1048                     item.displayPath + "<span class=\"" + type + "\">" + name + extra + "</span>");
1049                 wrapper.appendChild(resultName);
1050
1051                 var description = document.createElement("div");
1052                 description.className = "desc";
1053                 var spanDesc = document.createElement("span");
1054                 spanDesc.insertAdjacentHTML("beforeend", item.desc);
1055
1056                 description.appendChild(spanDesc);
1057                 wrapper.appendChild(description);
1058                 link.appendChild(wrapper);
1059                 output.appendChild(link);
1060             });
1061         } else {
1062             output.className = "search-failed" + extraClass;
1063             output.innerHTML = "No results :(<br/>" +
1064                 "Try on <a href=\"https://duckduckgo.com/?q=" +
1065                 encodeURIComponent("rust " + query.query) +
1066                 "\">DuckDuckGo</a>?<br/><br/>" +
1067                 "Or try looking in one of these:<ul><li>The <a " +
1068                 "href=\"https://doc.rust-lang.org/reference/index.html\">Rust Reference</a> " +
1069                 " for technical details about the language.</li><li><a " +
1070                 "href=\"https://doc.rust-lang.org/rust-by-example/index.html\">Rust By " +
1071                 "Example</a> for expository code examples.</a></li><li>The <a " +
1072                 "href=\"https://doc.rust-lang.org/book/index.html\">Rust Book</a> for " +
1073                 "introductions to language features and the language itself.</li><li><a " +
1074                 "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" +
1075                 " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>";
1076         }
1077         return [output, length];
1078     }
1079
1080     function makeTabHeader(tabNb, text, nbElems) {
1081         if (searchState.currentTab === tabNb) {
1082             return "<button class=\"selected\">" + text +
1083                    " <div class=\"count\">(" + nbElems + ")</div></button>";
1084         }
1085         return "<button>" + text + " <div class=\"count\">(" + nbElems + ")</div></button>";
1086     }
1087
1088     function showResults(results, go_to_first, filterCrates) {
1089         var search = searchState.outputElement();
1090         if (go_to_first || (results.others.length === 1
1091             && getSettingValue("go-to-only-result") === "true"
1092             // By default, the search DOM element is "empty" (meaning it has no children not
1093             // text content). Once a search has been run, it won't be empty, even if you press
1094             // ESC or empty the search input (which also "cancels" the search).
1095             && (!search.firstChild || search.firstChild.innerText !== searchState.loadingText)))
1096         {
1097             var elem = document.createElement("a");
1098             elem.href = results.others[0].href;
1099             removeClass(elem, "active");
1100             // For firefox, we need the element to be in the DOM so it can be clicked.
1101             document.body.appendChild(elem);
1102             elem.click();
1103             return;
1104         }
1105         var query = getQuery(searchState.input.value);
1106
1107         currentResults = query.id;
1108
1109         var ret_others = addTab(results.others, query, true);
1110         var ret_in_args = addTab(results.in_args, query, false);
1111         var ret_returned = addTab(results.returned, query, false);
1112
1113         // Navigate to the relevant tab if the current tab is empty, like in case users search
1114         // for "-> String". If they had selected another tab previously, they have to click on
1115         // it again.
1116         var currentTab = searchState.currentTab;
1117         if ((currentTab === 0 && ret_others[1] === 0) ||
1118                 (currentTab === 1 && ret_in_args[1] === 0) ||
1119                 (currentTab === 2 && ret_returned[1] === 0)) {
1120             if (ret_others[1] !== 0) {
1121                 currentTab = 0;
1122             } else if (ret_in_args[1] !== 0) {
1123                 currentTab = 1;
1124             } else if (ret_returned[1] !== 0) {
1125                 currentTab = 2;
1126             }
1127         }
1128
1129         let crates = `<select id="crate-search"><option value="All crates">All crates</option>`;
1130         for (let c of window.ALL_CRATES) {
1131             crates += `<option value="${c}" ${c == filterCrates && "selected"}>${c}</option>`;
1132         }
1133         crates += `</select>`;
1134         var output = `<div id="search-settings">
1135             <h1 class="search-results-title">Results for ${escape(query.query)} ` +
1136             (query.type ? " (type: " + escape(query.type) + ")" : "") + "</h1>" +
1137             ` in ${crates} ` +
1138             `</div><div id="titles">` +
1139             makeTabHeader(0, "In Names", ret_others[1]) +
1140             makeTabHeader(1, "In Parameters", ret_in_args[1]) +
1141             makeTabHeader(2, "In Return Types", ret_returned[1]) +
1142             "</div>";
1143
1144         var resultsElem = document.createElement("div");
1145         resultsElem.id = "results";
1146         resultsElem.appendChild(ret_others[0]);
1147         resultsElem.appendChild(ret_in_args[0]);
1148         resultsElem.appendChild(ret_returned[0]);
1149
1150         search.innerHTML = output;
1151         document.getElementById("crate-search").addEventListener("input", updateCrate);
1152         search.appendChild(resultsElem);
1153         // Reset focused elements.
1154         searchState.focusedByTab = [null, null, null];
1155         searchState.showResults(search);
1156         var elems = document.getElementById("titles").childNodes;
1157         elems[0].onclick = function() { printTab(0); };
1158         elems[1].onclick = function() { printTab(1); };
1159         elems[2].onclick = function() { printTab(2); };
1160         printTab(currentTab);
1161     }
1162
1163     function execSearch(query, searchWords, filterCrates) {
1164         function getSmallest(arrays, positions, notDuplicates) {
1165             var start = null;
1166
1167             for (var it = 0, len = positions.length; it < len; ++it) {
1168                 if (arrays[it].length > positions[it] &&
1169                     (start === null || start > arrays[it][positions[it]].lev) &&
1170                     !notDuplicates[arrays[it][positions[it]].fullPath]) {
1171                     start = arrays[it][positions[it]].lev;
1172                 }
1173             }
1174             return start;
1175         }
1176
1177         function mergeArrays(arrays) {
1178             var ret = [];
1179             var positions = [];
1180             var notDuplicates = {};
1181
1182             for (var x = 0, arrays_len = arrays.length; x < arrays_len; ++x) {
1183                 positions.push(0);
1184             }
1185             while (ret.length < MAX_RESULTS) {
1186                 var smallest = getSmallest(arrays, positions, notDuplicates);
1187
1188                 if (smallest === null) {
1189                     break;
1190                 }
1191                 for (x = 0; x < arrays_len && ret.length < MAX_RESULTS; ++x) {
1192                     if (arrays[x].length > positions[x] &&
1193                             arrays[x][positions[x]].lev === smallest &&
1194                             !notDuplicates[arrays[x][positions[x]].fullPath]) {
1195                         ret.push(arrays[x][positions[x]]);
1196                         notDuplicates[arrays[x][positions[x]].fullPath] = true;
1197                         positions[x] += 1;
1198                     }
1199                 }
1200             }
1201             return ret;
1202         }
1203
1204         // Split search query by ",", while respecting angle bracket nesting.
1205         // Since "<" is an alias for the Ord family of traits, it also uses
1206         // lookahead to distinguish "<"-as-less-than from "<"-as-angle-bracket.
1207         //
1208         // tokenizeQuery("A<B, C>, D") == ["A<B, C>", "D"]
1209         // tokenizeQuery("A<B, C, D") == ["A<B", "C", "D"]
1210         function tokenizeQuery(raw) {
1211             var i, matched;
1212             var l = raw.length;
1213             var depth = 0;
1214             var nextAngle = /(<|>)/g;
1215             var ret = [];
1216             var start = 0;
1217             for (i = 0; i < l; ++i) {
1218                 switch (raw[i]) {
1219                     case "<":
1220                         nextAngle.lastIndex = i + 1;
1221                         matched = nextAngle.exec(raw);
1222                         if (matched && matched[1] === '>') {
1223                             depth += 1;
1224                         }
1225                         break;
1226                     case ">":
1227                         if (depth > 0) {
1228                             depth -= 1;
1229                         }
1230                         break;
1231                     case ",":
1232                         if (depth === 0) {
1233                             ret.push(raw.substring(start, i));
1234                             start = i + 1;
1235                         }
1236                         break;
1237                 }
1238             }
1239             if (start !== i) {
1240                 ret.push(raw.substring(start, i));
1241             }
1242             return ret;
1243         }
1244
1245         var queries = tokenizeQuery(query.raw);
1246         var results = {
1247             "in_args": [],
1248             "returned": [],
1249             "others": [],
1250         };
1251
1252         for (var i = 0, len = queries.length; i < len; ++i) {
1253             query = queries[i].trim();
1254             if (query.length !== 0) {
1255                 var tmp = execQuery(getQuery(query), searchWords, filterCrates);
1256
1257                 results.in_args.push(tmp.in_args);
1258                 results.returned.push(tmp.returned);
1259                 results.others.push(tmp.others);
1260             }
1261         }
1262         if (queries.length > 1) {
1263             return {
1264                 "in_args": mergeArrays(results.in_args),
1265                 "returned": mergeArrays(results.returned),
1266                 "others": mergeArrays(results.others),
1267             };
1268         }
1269         return {
1270             "in_args": results.in_args[0],
1271             "returned": results.returned[0],
1272             "others": results.others[0],
1273         };
1274     }
1275
1276     function getFilterCrates() {
1277         var elem = document.getElementById("crate-search");
1278
1279         if (elem && elem.value !== "All crates" &&
1280             hasOwnPropertyRustdoc(rawSearchIndex, elem.value))
1281         {
1282             return elem.value;
1283         }
1284         return undefined;
1285     }
1286
1287     /**
1288      * Perform a search based on the current state of the search input element
1289      * and display the results.
1290      * @param {Event}   [e]       - The event that triggered this search, if any
1291      * @param {boolean} [forced]
1292      */
1293     function search(e, forced) {
1294         var params = searchState.getQueryStringParams();
1295         var query = getQuery(searchState.input.value.trim());
1296
1297         if (e) {
1298             e.preventDefault();
1299         }
1300
1301         if (query.query.length === 0) {
1302             return;
1303         }
1304         if (!forced && query.id === currentResults) {
1305             if (query.query.length > 0) {
1306                 searchState.putBackSearch(searchState.input);
1307             }
1308             return;
1309         }
1310
1311         // Update document title to maintain a meaningful browser history
1312         searchState.title = "Results for " + query.query + " - Rust";
1313
1314         // Because searching is incremental by character, only the most
1315         // recent search query is added to the browser history.
1316         if (searchState.browserSupportsHistoryApi()) {
1317             var newURL = getNakedUrl() + "?search=" + encodeURIComponent(query.raw) +
1318                 window.location.hash;
1319             if (!history.state && !params.search) {
1320                 history.pushState(query, "", newURL);
1321             } else {
1322                 history.replaceState(query, "", newURL);
1323             }
1324         }
1325
1326         var filterCrates = getFilterCrates();
1327         showResults(execSearch(query, searchWords, filterCrates),
1328             params["go_to_first"], filterCrates);
1329     }
1330
1331     function buildIndex(rawSearchIndex) {
1332         searchIndex = [];
1333         /**
1334          * @type {Array<string>}
1335          */
1336         var searchWords = [];
1337         var i, word;
1338         var currentIndex = 0;
1339         var id = 0;
1340
1341         for (var crate in rawSearchIndex) {
1342             if (!hasOwnPropertyRustdoc(rawSearchIndex, crate)) {
1343                 continue;
1344             }
1345
1346             var crateSize = 0;
1347
1348             /**
1349              * The raw search data for a given crate. `n`, `t`, `d`, and `q`, `i`, and `f`
1350              * are arrays with the same length. n[i] contains the name of an item.
1351              * t[i] contains the type of that item (as a small integer that represents an
1352              * offset in `itemTypes`). d[i] contains the description of that item.
1353              *
1354              * q[i] contains the full path of the item, or an empty string indicating
1355              * "same as q[i-1]".
1356              *
1357              * i[i], f[i] are a mystery.
1358              *
1359              * `a` defines aliases with an Array of pairs: [name, offset], where `offset`
1360              * points into the n/t/d/q/i/f arrays.
1361              *
1362              * `doc` contains the description of the crate.
1363              *
1364              * `p` is a mystery and isn't the same length as n/t/d/q/i/f.
1365              *
1366              * @type {{
1367              *   doc: string,
1368              *   a: Object,
1369              *   n: Array<string>,
1370              *   t: Array<Number>,
1371              *   d: Array<string>,
1372              *   q: Array<string>,
1373              *   i: Array<Number>,
1374              *   f: Array<Array<?>>,
1375              *   p: Array<Object>,
1376              * }}
1377              */
1378             var crateCorpus = rawSearchIndex[crate];
1379
1380             searchWords.push(crate);
1381             // This object should have exactly the same set of fields as the "row"
1382             // object defined below. Your JavaScript runtime will thank you.
1383             // https://mathiasbynens.be/notes/shapes-ics
1384             var crateRow = {
1385                 crate: crate,
1386                 ty: 1, // == ExternCrate
1387                 name: crate,
1388                 path: "",
1389                 desc: crateCorpus.doc,
1390                 parent: undefined,
1391                 type: null,
1392                 id: id,
1393                 normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""),
1394             };
1395             id += 1;
1396             searchIndex.push(crateRow);
1397             currentIndex += 1;
1398
1399             // an array of (Number) item types
1400             var itemTypes = crateCorpus.t;
1401             // an array of (String) item names
1402             var itemNames = crateCorpus.n;
1403             // an array of (String) full paths (or empty string for previous path)
1404             var itemPaths = crateCorpus.q;
1405             // an array of (String) descriptions
1406             var itemDescs = crateCorpus.d;
1407             // an array of (Number) the parent path index + 1 to `paths`, or 0 if none
1408             var itemParentIdxs = crateCorpus.i;
1409             // an array of (Object | null) the type of the function, if any
1410             var itemFunctionSearchTypes = crateCorpus.f;
1411             // an array of [(Number) item type,
1412             //              (String) name]
1413             var paths = crateCorpus.p;
1414             // an array of [(String) alias name
1415             //             [Number] index to items]
1416             var aliases = crateCorpus.a;
1417
1418             // convert `rawPaths` entries into object form
1419             var len = paths.length;
1420             for (i = 0; i < len; ++i) {
1421                 paths[i] = {ty: paths[i][0], name: paths[i][1]};
1422             }
1423
1424             // convert `item*` into an object form, and construct word indices.
1425             //
1426             // before any analysis is performed lets gather the search terms to
1427             // search against apart from the rest of the data.  This is a quick
1428             // operation that is cached for the life of the page state so that
1429             // all other search operations have access to this cached data for
1430             // faster analysis operations
1431             len = itemTypes.length;
1432             var lastPath = "";
1433             for (i = 0; i < len; ++i) {
1434                 // This object should have exactly the same set of fields as the "crateRow"
1435                 // object defined above.
1436                 if (typeof itemNames[i] === "string") {
1437                     word = itemNames[i].toLowerCase();
1438                     searchWords.push(word);
1439                 } else {
1440                     word = "";
1441                     searchWords.push("");
1442                 }
1443                 var row = {
1444                     crate: crate,
1445                     ty: itemTypes[i],
1446                     name: itemNames[i],
1447                     path: itemPaths[i] ? itemPaths[i] : lastPath,
1448                     desc: itemDescs[i],
1449                     parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
1450                     type: itemFunctionSearchTypes[i],
1451                     id: id,
1452                     normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
1453                 };
1454                 id += 1;
1455                 searchIndex.push(row);
1456                 lastPath = row.path;
1457                 crateSize += 1;
1458             }
1459
1460             if (aliases) {
1461                 ALIASES[crate] = {};
1462                 var j, local_aliases;
1463                 for (var alias_name in aliases) {
1464                     if (!hasOwnPropertyRustdoc(aliases, alias_name)) {
1465                         continue;
1466                     }
1467
1468                     if (!hasOwnPropertyRustdoc(ALIASES[crate], alias_name)) {
1469                         ALIASES[crate][alias_name] = [];
1470                     }
1471                     local_aliases = aliases[alias_name];
1472                     for (j = 0, len = local_aliases.length; j < len; ++j) {
1473                         ALIASES[crate][alias_name].push(local_aliases[j] + currentIndex);
1474                     }
1475                 }
1476             }
1477             currentIndex += crateSize;
1478         }
1479         return searchWords;
1480     }
1481
1482     /**
1483      * Callback for when the search form is submitted.
1484      * @param {Event} [e] - The event that triggered this call, if any
1485      */
1486     function onSearchSubmit(e) {
1487         e.preventDefault();
1488         searchState.clearInputTimeout();
1489         search();
1490     }
1491
1492     function registerSearchEvents() {
1493         var searchAfter500ms = function() {
1494             searchState.clearInputTimeout();
1495             if (searchState.input.value.length === 0) {
1496                 if (searchState.browserSupportsHistoryApi()) {
1497                     history.replaceState("", window.currentCrate + " - Rust",
1498                         getNakedUrl() + window.location.hash);
1499                 }
1500                 searchState.hideResults();
1501             } else {
1502                 searchState.timeout = setTimeout(search, 500);
1503             }
1504         };
1505         searchState.input.onkeyup = searchAfter500ms;
1506         searchState.input.oninput = searchAfter500ms;
1507         document.getElementsByClassName("search-form")[0].onsubmit = onSearchSubmit;
1508         searchState.input.onchange = function(e) {
1509             if (e.target !== document.activeElement) {
1510                 // To prevent doing anything when it's from a blur event.
1511                 return;
1512             }
1513             // Do NOT e.preventDefault() here. It will prevent pasting.
1514             searchState.clearInputTimeout();
1515             // zero-timeout necessary here because at the time of event handler execution the
1516             // pasted content is not in the input field yet. Shouldn’t make any difference for
1517             // change, though.
1518             setTimeout(search, 0);
1519         };
1520         searchState.input.onpaste = searchState.input.onchange;
1521
1522         searchState.outputElement().addEventListener("keydown", function(e) {
1523             // We only handle unmodified keystrokes here. We don't want to interfere with,
1524             // for instance, alt-left and alt-right for history navigation.
1525             if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) {
1526                 return;
1527             }
1528             // up and down arrow select next/previous search result, or the
1529             // search box if we're already at the top.
1530             if (e.which === 38) { // up
1531                 var previous = document.activeElement.previousElementSibling;
1532                 if (previous) {
1533                     previous.focus();
1534                 } else {
1535                     searchState.focus();
1536                 }
1537                 e.preventDefault();
1538             } else if (e.which === 40) { // down
1539                 var next = document.activeElement.nextElementSibling;
1540                 if (next) {
1541                     next.focus();
1542                 }
1543                 var rect = document.activeElement.getBoundingClientRect();
1544                 if (window.innerHeight - rect.bottom < rect.height) {
1545                     window.scrollBy(0, rect.height);
1546                 }
1547                 e.preventDefault();
1548             } else if (e.which === 37) { // left
1549                 nextTab(-1);
1550                 e.preventDefault();
1551             } else if (e.which === 39) { // right
1552                 nextTab(1);
1553                 e.preventDefault();
1554             }
1555         });
1556
1557         searchState.input.addEventListener("keydown", function(e) {
1558             if (e.which === 40) { // down
1559                 focusSearchResult();
1560                 e.preventDefault();
1561             }
1562         });
1563
1564         // Push and pop states are used to add search results to the browser
1565         // history.
1566         if (searchState.browserSupportsHistoryApi()) {
1567             // Store the previous <title> so we can revert back to it later.
1568             var previousTitle = document.title;
1569
1570             window.addEventListener("popstate", function(e) {
1571                 var params = searchState.getQueryStringParams();
1572                 // Revert to the previous title manually since the History
1573                 // API ignores the title parameter.
1574                 document.title = previousTitle;
1575                 // When browsing forward to search results the previous
1576                 // search will be repeated, so the currentResults are
1577                 // cleared to ensure the search is successful.
1578                 currentResults = null;
1579                 // Synchronize search bar with query string state and
1580                 // perform the search. This will empty the bar if there's
1581                 // nothing there, which lets you really go back to a
1582                 // previous state with nothing in the bar.
1583                 if (params.search && params.search.length > 0) {
1584                     searchState.input.value = params.search;
1585                     // Some browsers fire "onpopstate" for every page load
1586                     // (Chrome), while others fire the event only when actually
1587                     // popping a state (Firefox), which is why search() is
1588                     // called both here and at the end of the startSearch()
1589                     // function.
1590                     search(e);
1591                 } else {
1592                     searchState.input.value = "";
1593                     // When browsing back from search results the main page
1594                     // visibility must be reset.
1595                     searchState.hideResults();
1596                 }
1597             });
1598         }
1599
1600         // This is required in firefox to avoid this problem: Navigating to a search result
1601         // with the keyboard, hitting enter, and then hitting back would take you back to
1602         // the doc page, rather than the search that should overlay it.
1603         // This was an interaction between the back-forward cache and our handlers
1604         // that try to sync state between the URL and the search input. To work around it,
1605         // do a small amount of re-init on page show.
1606         window.onpageshow = function(){
1607             var qSearch = searchState.getQueryStringParams().search;
1608             if (searchState.input.value === "" && qSearch) {
1609                 searchState.input.value = qSearch;
1610             }
1611             search();
1612         };
1613     }
1614
1615     function updateCrate(ev) {
1616         updateLocalStorage("rustdoc-saved-filter-crate", ev.target.value);
1617         // In case you "cut" the entry from the search input, then change the crate filter
1618         // before paste back the previous search, you get the old search results without
1619         // the filter. To prevent this, we need to remove the previous results.
1620         currentResults = null;
1621         search(undefined, true);
1622     }
1623
1624     searchWords = buildIndex(rawSearchIndex);
1625     registerSearchEvents();
1626     // If there's a search term in the URL, execute the search now.
1627     if (searchState.getQueryStringParams().search) {
1628         search();
1629     }
1630 };
1631
1632 if (window.searchIndex !== undefined) {
1633     initSearch(window.searchIndex);
1634 }
1635
1636 })();