src/librustdoc/html/static/search.js

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