1 /* global addClass, getNakedUrl, getSettingValue */
2 /* global onEachLazy, removeClass, searchState, browserSupportsHistoryApi, exports */
7 // This mapping table should match the discriminants of
8 // `rustdoc::formats::item_type::ItemType` type in Rust.
38 // used for special search precedence
39 const TY_PRIMITIVE = itemTypes.indexOf("primitive");
40 const TY_KEYWORD = itemTypes.indexOf("keyword");
41 const ROOT_PATH = typeof window !== "undefined" ? window.rootPath : "../";
43 function hasOwnPropertyRustdoc(obj, property) {
44 return Object.prototype.hasOwnProperty.call(obj, property);
47 // In the search display, allows to switch between tabs.
48 function printTab(nb) {
50 let foundCurrentTab = false;
51 let foundCurrentResultSet = false;
52 onEachLazy(document.getElementById("search-tabs").childNodes, elem => {
54 addClass(elem, "selected");
55 foundCurrentTab = true;
57 removeClass(elem, "selected");
62 onEachLazy(document.getElementById("results").childNodes, elem => {
64 addClass(elem, "active");
65 foundCurrentResultSet = true;
67 removeClass(elem, "active");
71 if (foundCurrentTab && foundCurrentResultSet) {
72 searchState.currentTab = nb;
73 } else if (nb !== 0) {
79 * A function to compute the Levenshtein distance between two strings
80 * Licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported
81 * Full License can be found at http://creativecommons.org/licenses/by-sa/3.0/legalcode
82 * This code is an unmodified version of the code written by Marco de Wit
83 * and was found at https://stackoverflow.com/a/18514751/745719
85 const levenshtein_row2 = [];
86 function levenshtein(s1, s2) {
90 const s1_len = s1.length, s2_len = s2.length;
91 if (s1_len && s2_len) {
92 let i1 = 0, i2 = 0, a, b, c, c2;
93 const row = levenshtein_row2;
98 c2 = s2.charCodeAt(i2);
102 for (i1 = 0; i1 < s1_len; ++i1) {
103 c = a + (s1.charCodeAt(i1) !== c2 ? 1 : 0);
105 b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
111 return s1_len + s2_len;
114 function initSearch(rawSearchIndex) {
115 const MAX_RESULTS = 200;
116 const NO_TYPE_FILTER = -1;
122 const ALIASES = Object.create(null);
124 function isWhitespace(c) {
125 return " \t\n\r".indexOf(c) !== -1;
128 function isSpecialStartCharacter(c) {
129 return "<\"".indexOf(c) !== -1;
132 function isEndCharacter(c) {
133 return ",>-".indexOf(c) !== -1;
136 function isStopCharacter(c) {
137 return isWhitespace(c) || isEndCharacter(c);
140 function isErrorCharacter(c) {
141 return "()".indexOf(c) !== -1;
144 function itemTypeFromName(typename) {
145 for (let i = 0, len = itemTypes.length; i < len; ++i) {
146 if (itemTypes[i] === typename) {
151 throw new Error("Unknown type filter `" + typename + "`");
155 * If we encounter a `"`, then we try to extract the string from it until we find another `"`.
157 * This function will throw an error in the following cases:
158 * * There is already another string element.
159 * * We are parsing a generic argument.
160 * * There is more than one element.
161 * * There is no closing `"`.
163 * @param {ParsedQuery} query
164 * @param {ParserState} parserState
165 * @param {boolean} isInGenerics
167 function getStringElem(query, parserState, isInGenerics) {
169 throw new Error("`\"` cannot be used in generics");
170 } else if (query.literalSearch) {
171 throw new Error("Cannot have more than one literal search element");
172 } else if (parserState.totalElems - parserState.genericsElems > 0) {
173 throw new Error("Cannot use literal search when there is more than one element");
175 parserState.pos += 1;
176 const start = parserState.pos;
177 const end = getIdentEndPosition(parserState);
178 if (parserState.pos >= parserState.length) {
179 throw new Error("Unclosed `\"`");
180 } else if (parserState.userQuery[end] !== "\"") {
181 throw new Error(`Unexpected \`${parserState.userQuery[end]}\` in a string element`);
182 } else if (start === end) {
183 throw new Error("Cannot have empty string element");
185 // To skip the quote at the end.
186 parserState.pos += 1;
187 query.literalSearch = true;
191 * Returns `true` if the current parser position is starting with "::".
193 * @param {ParserState} parserState
197 function isPathStart(parserState) {
198 return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "::";
202 * Returns `true` if the current parser position is starting with "->".
204 * @param {ParserState} parserState
208 function isReturnArrow(parserState) {
209 return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "->";
213 * Returns `true` if the given `c` character is valid for an ident.
219 function isIdentCharacter(c) {
222 (c >= "0" && c <= "9") ||
223 (c >= "a" && c <= "z") ||
224 (c >= "A" && c <= "Z"));
228 * Returns `true` if the given `c` character is a separator.
234 function isSeparatorCharacter(c) {
235 return c === "," || isWhitespaceCharacter(c);
239 * Returns `true` if the given `c` character is a whitespace.
245 function isWhitespaceCharacter(c) {
246 return c === " " || c === "\t";
250 * @param {ParsedQuery} query
251 * @param {ParserState} parserState
252 * @param {string} name - Name of the query element.
253 * @param {Array<QueryElement>} generics - List of generics of this query element.
255 * @return {QueryElement} - The newly created `QueryElement`.
257 function createQueryElement(query, parserState, name, generics, isInGenerics) {
258 if (name === "*" || (name.length === 0 && generics.length === 0)) {
261 if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) {
262 throw new Error("You cannot have more than one element if you use quotes");
264 const pathSegments = name.split("::");
265 if (pathSegments.length > 1) {
266 for (let i = 0, len = pathSegments.length; i < len; ++i) {
267 const pathSegment = pathSegments[i];
269 if (pathSegment.length === 0) {
271 throw new Error("Paths cannot start with `::`");
272 } else if (i + 1 === len) {
273 throw new Error("Paths cannot end with `::`");
275 throw new Error("Unexpected `::::`");
279 // In case we only have something like `<p>`, there is no name.
280 if (pathSegments.length === 0 || (pathSegments.length === 1 && pathSegments[0] === "")) {
281 throw new Error("Found generics without a path");
283 parserState.totalElems += 1;
285 parserState.genericsElems += 1;
289 fullPath: pathSegments,
290 pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1),
291 pathLast: pathSegments[pathSegments.length - 1],
297 * This function goes through all characters until it reaches an invalid ident character or the
298 * end of the query. It returns the position of the last character of the ident.
300 * @param {ParserState} parserState
304 function getIdentEndPosition(parserState) {
305 let end = parserState.pos;
306 let foundExclamation = false;
307 while (parserState.pos < parserState.length) {
308 const c = parserState.userQuery[parserState.pos];
309 if (!isIdentCharacter(c)) {
311 if (foundExclamation) {
312 throw new Error("Cannot have more than one `!` in an ident");
313 } else if (parserState.pos + 1 < parserState.length &&
314 isIdentCharacter(parserState.userQuery[parserState.pos + 1])
316 throw new Error("`!` can only be at the end of an ident");
318 foundExclamation = true;
319 } else if (isErrorCharacter(c)) {
320 throw new Error(`Unexpected \`${c}\``);
322 isStopCharacter(c) ||
323 isSpecialStartCharacter(c) ||
324 isSeparatorCharacter(c)
327 } else if (c === ":") { // If we allow paths ("str::string" for example).
328 if (!isPathStart(parserState)) {
332 parserState.pos += 1;
333 foundExclamation = false;
335 throw new Error(`Unexpected \`${c}\``);
338 parserState.pos += 1;
339 end = parserState.pos;
345 * @param {ParsedQuery} query
346 * @param {ParserState} parserState
347 * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added.
348 * @param {boolean} isInGenerics
350 function getNextElem(query, parserState, elems, isInGenerics) {
353 let start = parserState.pos;
355 // We handle the strings on their own mostly to make code easier to follow.
356 if (parserState.userQuery[parserState.pos] === "\"") {
358 getStringElem(query, parserState, isInGenerics);
359 end = parserState.pos - 1;
361 end = getIdentEndPosition(parserState);
363 if (parserState.pos < parserState.length &&
364 parserState.userQuery[parserState.pos] === "<"
367 throw new Error("Unexpected `<` after `<`");
368 } else if (start >= end) {
369 throw new Error("Found generics without a path");
371 parserState.pos += 1;
372 getItemsBefore(query, parserState, generics, ">");
374 if (start >= end && generics.length === 0) {
381 parserState.userQuery.slice(start, end),
389 * This function parses the next query element until it finds `endChar`, calling `getNextElem`
390 * to collect each element.
392 * If there is no `endChar`, this function will implicitly stop at the end without raising an
395 * @param {ParsedQuery} query
396 * @param {ParserState} parserState
397 * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added.
398 * @param {string} endChar - This function will stop when it'll encounter this
401 function getItemsBefore(query, parserState, elems, endChar) {
402 let foundStopChar = true;
404 while (parserState.pos < parserState.length) {
405 const c = parserState.userQuery[parserState.pos];
408 } else if (isSeparatorCharacter(c)) {
409 parserState.pos += 1;
410 foundStopChar = true;
412 } else if (c === ":" && isPathStart(parserState)) {
413 throw new Error("Unexpected `::`: paths cannot start with `::`");
414 } else if (c === ":" || isEndCharacter(c)) {
416 if (endChar === ">") {
418 } else if (endChar === "") {
421 throw new Error("Unexpected `" + c + "` after " + extra);
423 if (!foundStopChar) {
424 if (endChar !== "") {
425 throw new Error(`Expected \`,\`, \` \` or \`${endChar}\`, found \`${c}\``);
427 throw new Error(`Expected \`,\` or \` \`, found \`${c}\``);
429 const posBefore = parserState.pos;
430 getNextElem(query, parserState, elems, endChar === ">");
431 // This case can be encountered if `getNextElem` encountered a "stop character" right
432 // from the start. For example if you have `,,` or `<>`. In this case, we simply move up
433 // the current position to continue the parsing.
434 if (posBefore === parserState.pos) {
435 parserState.pos += 1;
437 foundStopChar = false;
439 // We are either at the end of the string or on the `endChar`` character, let's move forward
441 parserState.pos += 1;
445 * Checks that the type filter doesn't have unwanted characters like `<>` (which are ignored
448 * @param {ParserState} parserState
450 function checkExtraTypeFilterCharacters(parserState) {
451 const query = parserState.userQuery;
453 for (let pos = 0; pos < parserState.pos; ++pos) {
454 if (!isIdentCharacter(query[pos]) && !isWhitespaceCharacter(query[pos])) {
455 throw new Error(`Unexpected \`${query[pos]}\` in type filter`);
461 * Parses the provided `query` input to fill `parserState`. If it encounters an error while
462 * parsing `query`, it'll throw an error.
464 * @param {ParsedQuery} query
465 * @param {ParserState} parserState
467 function parseInput(query, parserState) {
469 let foundStopChar = true;
471 while (parserState.pos < parserState.length) {
472 c = parserState.userQuery[parserState.pos];
473 if (isStopCharacter(c)) {
474 foundStopChar = true;
475 if (isSeparatorCharacter(c)) {
476 parserState.pos += 1;
478 } else if (c === "-" || c === ">") {
479 if (isReturnArrow(parserState)) {
482 throw new Error(`Unexpected \`${c}\` (did you mean \`->\`?)`);
484 throw new Error(`Unexpected \`${c}\``);
485 } else if (c === ":" && !isPathStart(parserState)) {
486 if (parserState.typeFilter !== null) {
487 throw new Error("Unexpected `:`");
489 if (query.elems.length === 0) {
490 throw new Error("Expected type filter before `:`");
491 } else if (query.elems.length !== 1 || parserState.totalElems !== 1) {
492 throw new Error("Unexpected `:`");
493 } else if (query.literalSearch) {
494 throw new Error("You cannot use quotes on type filter");
496 checkExtraTypeFilterCharacters(parserState);
497 // The type filter doesn't count as an element since it's a modifier.
498 parserState.typeFilter = query.elems.pop().name;
499 parserState.pos += 1;
500 parserState.totalElems = 0;
501 query.literalSearch = false;
502 foundStopChar = true;
505 if (!foundStopChar) {
506 if (parserState.typeFilter !== null) {
507 throw new Error(`Expected \`,\`, \` \` or \`->\`, found \`${c}\``);
509 throw new Error(`Expected \`,\`, \` \`, \`:\` or \`->\`, found \`${c}\``);
511 before = query.elems.length;
512 getNextElem(query, parserState, query.elems, false);
513 if (query.elems.length === before) {
514 // Nothing was added, weird... Let's increase the position to not remain stuck.
515 parserState.pos += 1;
517 foundStopChar = false;
519 while (parserState.pos < parserState.length) {
520 c = parserState.userQuery[parserState.pos];
521 if (isReturnArrow(parserState)) {
522 parserState.pos += 2;
523 // Get returned elements.
524 getItemsBefore(query, parserState, query.returned, "");
525 // Nothing can come afterward!
526 if (query.returned.length === 0) {
527 throw new Error("Expected at least one item after `->`");
531 parserState.pos += 1;
537 * Takes the user search input and returns an empty `ParsedQuery`.
539 * @param {string} userQuery
541 * @return {ParsedQuery}
543 function newParsedQuery(userQuery) {
546 userQuery: userQuery.toLowerCase(),
547 typeFilter: NO_TYPE_FILTER,
550 // Total number of "top" elements (does not include generics).
552 literalSearch: false,
558 * Build an URL with search parameters.
560 * @param {string} search - The current search being performed.
561 * @param {string|null} filterCrates - The current filtering crate (if any).
565 function buildUrl(search, filterCrates) {
566 let extra = "?search=" + encodeURIComponent(search);
568 if (filterCrates !== null) {
569 extra += "&filter-crate=" + encodeURIComponent(filterCrates);
571 return getNakedUrl() + extra + window.location.hash;
575 * Return the filtering crate or `null` if there is none.
577 * @return {string|null}
579 function getFilterCrates() {
580 const elem = document.getElementById("crate-search");
583 elem.value !== "all crates" &&
584 hasOwnPropertyRustdoc(rawSearchIndex, elem.value)
594 * The supported syntax by this parser is as follow:
596 * ident = *(ALPHA / DIGIT / "_") [!]
597 * path = ident *(DOUBLE-COLON ident)
598 * arg = path [generics]
599 * arg-without-generic = path
600 * type-sep = COMMA/WS *(COMMA/WS)
601 * nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep)
602 * nonempty-arg-list-without-generics = *(type-sep) arg-without-generic
603 * *(type-sep arg-without-generic) *(type-sep)
604 * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list-without-generics ] *(type-sep)
605 * CLOSE-ANGLE-BRACKET/EOF
606 * return-args = RETURN-ARROW *(type-sep) nonempty-arg-list
608 * exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ]
609 * type-search = [type-filter *WS COLON] [ nonempty-arg-list ] [ return-args ]
611 * query = *WS (exact-search / type-search) *WS
632 * "associatedconstant" /
641 * OPEN-ANGLE-BRACKET = "<"
642 * CLOSE-ANGLE-BRACKET = ">"
644 * DOUBLE-COLON = "::"
647 * RETURN-ARROW = "->"
649 * ALPHA = %x41-5A / %x61-7A ; A-Z / a-z
653 * @param {string} val - The user query
655 * @return {ParsedQuery} - The parsed query
657 function parseQuery(userQuery) {
658 userQuery = userQuery.trim();
659 const parserState = {
660 length: userQuery.length,
662 // Total number of elements (includes generics).
666 userQuery: userQuery.toLowerCase(),
668 let query = newParsedQuery(userQuery);
671 parseInput(query, parserState);
672 if (parserState.typeFilter !== null) {
673 let typeFilter = parserState.typeFilter;
674 if (typeFilter === "const") {
675 typeFilter = "constant";
677 query.typeFilter = itemTypeFromName(typeFilter);
680 query = newParsedQuery(userQuery);
681 query.error = err.message;
682 query.typeFilter = -1;
686 if (!query.literalSearch) {
687 // If there is more than one element in the query, we switch to literalSearch in any
689 query.literalSearch = parserState.totalElems > 1;
691 query.foundElems = query.elems.length + query.returned.length;
696 * Creates the query results.
698 * @param {Array<Result>} results_in_args
699 * @param {Array<Result>} results_returned
700 * @param {Array<Result>} results_in_args
701 * @param {ParsedQuery} parsedQuery
703 * @return {ResultsTable}
705 function createQueryResults(results_in_args, results_returned, results_others, parsedQuery) {
707 "in_args": results_in_args,
708 "returned": results_returned,
709 "others": results_others,
710 "query": parsedQuery,
715 * Executes the parsed query and builds a {ResultsTable}.
717 * @param {ParsedQuery} parsedQuery - The parsed user query
718 * @param {Object} searchWords - The list of search words to query against
719 * @param {Object} [filterCrates] - Crate to search in if defined
720 * @param {Object} [currentCrate] - Current crate, to rank results from this crate higher
722 * @return {ResultsTable}
724 function execQuery(parsedQuery, searchWords, filterCrates, currentCrate) {
725 const results_others = {}, results_in_args = {}, results_returned = {};
727 function transformResults(results) {
728 const duplicates = {};
731 for (const result of results) {
732 if (result.id > -1) {
733 const obj = searchIndex[result.id];
734 obj.lev = result.lev;
735 const res = buildHrefAndPath(obj);
736 obj.displayPath = pathSplitter(res[0]);
737 obj.fullPath = obj.displayPath + obj.name;
738 // To be sure than it some items aren't considered as duplicate.
739 obj.fullPath += "|" + obj.ty;
741 if (duplicates[obj.fullPath]) {
744 duplicates[obj.fullPath] = true;
748 if (out.length >= MAX_RESULTS) {
756 function sortResults(results, isType, preferredCrate) {
757 const userQuery = parsedQuery.userQuery;
759 for (const entry in results) {
760 if (hasOwnPropertyRustdoc(results, entry)) {
761 const result = results[entry];
762 result.word = searchWords[result.id];
763 result.item = searchIndex[result.id] || {};
768 // if there are no results then return to default and fail
769 if (results.length === 0) {
773 results.sort((aaa, bbb) => {
776 // sort by exact match with regard to the last word (mismatch goes later)
777 a = (aaa.word !== userQuery);
778 b = (bbb.word !== userQuery);
783 // sort by index of keyword in item name (no literal occurrence goes later)
790 // Sort by distance in the path part, if specified
791 // (less changes required to match means higher rankings)
798 // (later literal occurrence, if any, goes later)
805 // Sort by distance in the name part, the last part of the path
806 // (less changes required to match means higher rankings)
813 // sort by crate (current crate comes first)
814 a = (aaa.item.crate !== preferredCrate);
815 b = (bbb.item.crate !== preferredCrate);
820 // sort by item name length (longer goes later)
827 // sort by item name (lexicographically larger goes later)
831 return (a > b ? +1 : -1);
834 // special precedence for primitive and keyword pages
835 if ((aaa.item.ty === TY_PRIMITIVE && bbb.item.ty !== TY_KEYWORD) ||
836 (aaa.item.ty === TY_KEYWORD && bbb.item.ty !== TY_PRIMITIVE)) {
839 if ((bbb.item.ty === TY_PRIMITIVE && aaa.item.ty !== TY_PRIMITIVE) ||
840 (bbb.item.ty === TY_KEYWORD && aaa.item.ty !== TY_KEYWORD)) {
844 // sort by description (no description goes later)
845 a = (aaa.item.desc === "");
846 b = (bbb.item.desc === "");
851 // sort by type (later occurrence in `itemTypes` goes later)
858 // sort by path (lexicographically larger goes later)
862 return (a > b ? +1 : -1);
869 let nameSplit = null;
870 if (parsedQuery.elems.length === 1) {
871 const hasPath = typeof parsedQuery.elems[0].path === "undefined";
872 nameSplit = hasPath ? null : parsedQuery.elems[0].path;
875 for (const result of results) {
876 // this validation does not make sense when searching by types
877 if (result.dontValidate) {
880 const name = result.item.name.toLowerCase(),
881 path = result.item.path.toLowerCase(),
882 parent = result.item.parent;
884 if (!isType && !validateResult(name, path, nameSplit, parent)) {
888 return transformResults(results);
892 * This function checks if the object (`row`) generics match the given type (`elem`)
893 * generics. If there are no generics on `row`, `defaultLev` is returned.
895 * @param {Row} row - The object to check.
896 * @param {QueryElement} elem - The element from the parsed query.
897 * @param {integer} defaultLev - This is the value to return in case there are no generics.
899 * @return {integer} - Returns the best match (if any) or `maxLevDistance + 1`.
901 function checkGenerics(row, elem, defaultLev, maxLevDistance) {
902 if (row.generics.length === 0) {
903 return elem.generics.length === 0 ? defaultLev : maxLevDistance + 1;
904 } else if (row.generics.length > 0 && row.generics[0].name === null) {
905 return checkGenerics(row.generics[0], elem, defaultLev, maxLevDistance);
907 // The names match, but we need to be sure that all generics kinda
910 if (elem.generics.length > 0 && row.generics.length >= elem.generics.length) {
911 const elems = Object.create(null);
912 for (const entry of row.generics) {
913 elem_name = entry.name;
914 if (elem_name === "") {
915 // Pure generic, needs to check into it.
916 if (checkGenerics(entry, elem, maxLevDistance + 1, maxLevDistance) !== 0) {
917 return maxLevDistance + 1;
921 if (elems[elem_name] === undefined) {
922 elems[elem_name] = 0;
924 elems[elem_name] += 1;
926 // We need to find the type that matches the most to remove it in order
928 for (const generic of elem.generics) {
930 if (elems[generic.name]) {
931 match = generic.name;
933 for (elem_name in elems) {
934 if (!hasOwnPropertyRustdoc(elems, elem_name)) {
937 if (elem_name === generic) {
943 if (match === null) {
944 return maxLevDistance + 1;
947 if (elems[match] === 0) {
953 return maxLevDistance + 1;
957 * This function checks if the object (`row`) matches the given type (`elem`) and its
961 * @param {QueryElement} elem - The element from the parsed query.
963 * @return {integer} - Returns a Levenshtein distance to the best match.
965 function checkIfInGenerics(row, elem, maxLevDistance) {
966 let lev = maxLevDistance + 1;
967 for (const entry of row.generics) {
968 lev = Math.min(checkType(entry, elem, true, maxLevDistance), lev);
977 * This function checks if the object (`row`) matches the given type (`elem`) and its
981 * @param {QueryElement} elem - The element from the parsed query.
982 * @param {boolean} literalSearch
984 * @return {integer} - Returns a Levenshtein distance to the best match. If there is
985 * no match, returns `maxLevDistance + 1`.
987 function checkType(row, elem, literalSearch, maxLevDistance) {
988 if (row.name === null) {
989 // This is a pure "generic" search, no need to run other checks.
990 if (row.generics.length > 0) {
991 return checkIfInGenerics(row, elem, maxLevDistance);
993 return maxLevDistance + 1;
996 let lev = levenshtein(row.name, elem.name);
999 // The name didn't match, let's try to check if the generics do.
1000 if (elem.generics.length === 0) {
1001 const checkGeneric = row.generics.length > 0;
1002 if (checkGeneric && row.generics
1003 .findIndex(tmp_elem => tmp_elem.name === elem.name) !== -1) {
1007 return maxLevDistance + 1;
1008 } else if (elem.generics.length > 0) {
1009 return checkGenerics(row, elem, maxLevDistance + 1, maxLevDistance);
1012 } else if (row.generics.length > 0) {
1013 if (elem.generics.length === 0) {
1017 // The name didn't match so we now check if the type we're looking for is inside
1019 lev = Math.min(lev, checkIfInGenerics(row, elem, maxLevDistance));
1021 } else if (lev > maxLevDistance) {
1022 // So our item's name doesn't match at all and has generics.
1024 // Maybe it's present in a sub generic? For example "f<A<B<C>>>()", if we're
1025 // looking for "B<C>", we'll need to go down.
1026 return checkIfInGenerics(row, elem, maxLevDistance);
1028 // At this point, the name kinda match and we have generics to check, so
1030 const tmp_lev = checkGenerics(row, elem, lev, maxLevDistance);
1031 if (tmp_lev > maxLevDistance) {
1032 return maxLevDistance + 1;
1034 // We compute the median value of both checks and return it.
1035 return (tmp_lev + lev) / 2;
1037 } else if (elem.generics.length > 0) {
1038 // In this case, we were expecting generics but there isn't so we simply reject this
1040 return maxLevDistance + 1;
1042 // No generics on our query or on the target type so we can return without doing
1048 * This function checks if the object (`row`) has an argument with the given type (`elem`).
1051 * @param {QueryElement} elem - The element from the parsed query.
1052 * @param {integer} typeFilter
1054 * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
1055 * match, returns `maxLevDistance + 1`.
1057 function findArg(row, elem, typeFilter, maxLevDistance) {
1058 let lev = maxLevDistance + 1;
1060 if (row && row.type && row.type.inputs && row.type.inputs.length > 0) {
1061 for (const input of row.type.inputs) {
1062 if (!typePassesFilter(typeFilter, input.ty)) {
1067 checkType(input, elem, parsedQuery.literalSearch, maxLevDistance)
1074 return parsedQuery.literalSearch ? maxLevDistance + 1 : lev;
1078 * This function checks if the object (`row`) returns the given type (`elem`).
1081 * @param {QueryElement} elem - The element from the parsed query.
1082 * @param {integer} typeFilter
1084 * @return {integer} - Returns a Levenshtein distance to the best match. If there is no
1085 * match, returns `maxLevDistance + 1`.
1087 function checkReturned(row, elem, typeFilter, maxLevDistance) {
1088 let lev = maxLevDistance + 1;
1090 if (row && row.type && row.type.output.length > 0) {
1091 const ret = row.type.output;
1092 for (const ret_ty of ret) {
1093 if (!typePassesFilter(typeFilter, ret_ty.ty)) {
1098 checkType(ret_ty, elem, parsedQuery.literalSearch, maxLevDistance)
1105 return parsedQuery.literalSearch ? maxLevDistance + 1 : lev;
1108 function checkPath(contains, ty, maxLevDistance) {
1109 if (contains.length === 0) {
1112 let ret_lev = maxLevDistance + 1;
1113 const path = ty.path.split("::");
1115 if (ty.parent && ty.parent.name) {
1116 path.push(ty.parent.name.toLowerCase());
1119 const length = path.length;
1120 const clength = contains.length;
1121 if (clength > length) {
1122 return maxLevDistance + 1;
1124 for (let i = 0; i < length; ++i) {
1125 if (i + clength > length) {
1129 let aborted = false;
1130 for (let x = 0; x < clength; ++x) {
1131 const lev = levenshtein(path[i + x], contains[x]);
1132 if (lev > maxLevDistance) {
1139 ret_lev = Math.min(ret_lev, Math.round(lev_total / clength));
1145 function typePassesFilter(filter, type) {
1146 // No filter or Exact mach
1147 if (filter <= NO_TYPE_FILTER || filter === type) return true;
1149 // Match related items
1150 const name = itemTypes[type];
1151 switch (itemTypes[filter]) {
1153 return name === "associatedconstant";
1155 return name === "method" || name === "tymethod";
1157 return name === "primitive" || name === "associatedtype";
1159 return name === "traitalias";
1166 function createAliasFromItem(item) {
1173 parent: item.parent,
1179 function handleAliases(ret, query, filterCrates, currentCrate) {
1180 const lowerQuery = query.toLowerCase();
1181 // We separate aliases and crate aliases because we want to have current crate
1182 // aliases to be before the others in the displayed results.
1184 const crateAliases = [];
1185 if (filterCrates !== null) {
1186 if (ALIASES[filterCrates] && ALIASES[filterCrates][lowerQuery]) {
1187 const query_aliases = ALIASES[filterCrates][lowerQuery];
1188 for (const alias of query_aliases) {
1189 aliases.push(createAliasFromItem(searchIndex[alias]));
1193 Object.keys(ALIASES).forEach(crate => {
1194 if (ALIASES[crate][lowerQuery]) {
1195 const pushTo = crate === currentCrate ? crateAliases : aliases;
1196 const query_aliases = ALIASES[crate][lowerQuery];
1197 for (const alias of query_aliases) {
1198 pushTo.push(createAliasFromItem(searchIndex[alias]));
1204 const sortFunc = (aaa, bbb) => {
1205 if (aaa.path < bbb.path) {
1207 } else if (aaa.path === bbb.path) {
1212 crateAliases.sort(sortFunc);
1213 aliases.sort(sortFunc);
1215 const pushFunc = alias => {
1216 alias.alias = query;
1217 const res = buildHrefAndPath(alias);
1218 alias.displayPath = pathSplitter(res[0]);
1219 alias.fullPath = alias.displayPath + alias.name;
1220 alias.href = res[1];
1222 ret.others.unshift(alias);
1223 if (ret.others.length > MAX_RESULTS) {
1228 aliases.forEach(pushFunc);
1229 crateAliases.forEach(pushFunc);
1233 * This function adds the given result into the provided `results` map if it matches the
1234 * following condition:
1236 * * If it is a "literal search" (`parsedQuery.literalSearch`), then `lev` must be 0.
1237 * * If it is not a "literal search", `lev` must be <= `maxLevDistance`.
1239 * The `results` map contains information which will be used to sort the search results:
1241 * * `fullId` is a `string`` used as the key of the object we use for the `results` map.
1242 * * `id` is the index in both `searchWords` and `searchIndex` arrays for this element.
1243 * * `index` is an `integer`` used to sort by the position of the word in the item's name.
1244 * * `lev` is the main metric used to sort the search results.
1245 * * `path_lev` is zero if a single-component search query is used, otherwise it's the
1246 * distance computed for everything other than the last path component.
1248 * @param {Results} results
1249 * @param {string} fullId
1250 * @param {integer} id
1251 * @param {integer} index
1252 * @param {integer} lev
1253 * @param {integer} path_lev
1255 function addIntoResults(results, fullId, id, index, lev, path_lev, maxLevDistance) {
1256 const inBounds = lev <= maxLevDistance || index !== -1;
1257 if (lev === 0 || (!parsedQuery.literalSearch && inBounds)) {
1258 if (results[fullId] !== undefined) {
1259 const result = results[fullId];
1260 if (result.dontValidate || result.lev <= lev) {
1267 dontValidate: parsedQuery.literalSearch,
1275 * This function is called in case the query is only one element (with or without generics).
1276 * This element will be compared to arguments' and returned values' items and also to items.
1278 * Other important thing to note: since there is only one element, we use levenshtein
1279 * distance for name comparisons.
1282 * @param {integer} pos - Position in the `searchIndex`.
1283 * @param {QueryElement} elem - The element from the parsed query.
1284 * @param {Results} results_others - Unqualified results (not in arguments nor in
1286 * @param {Results} results_in_args - Matching arguments results.
1287 * @param {Results} results_returned - Matching returned arguments results.
1289 function handleSingleArg(
1298 if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
1301 let lev, index = -1, path_lev = 0;
1302 const fullId = row.id;
1303 const searchWord = searchWords[pos];
1305 const in_args = findArg(row, elem, parsedQuery.typeFilter, maxLevDistance);
1306 const returned = checkReturned(row, elem, parsedQuery.typeFilter, maxLevDistance);
1308 // path_lev is 0 because no parent path information is currently stored
1309 // in the search index
1310 addIntoResults(results_in_args, fullId, pos, -1, in_args, 0, maxLevDistance);
1311 addIntoResults(results_returned, fullId, pos, -1, returned, 0, maxLevDistance);
1313 if (!typePassesFilter(parsedQuery.typeFilter, row.ty)) {
1317 const row_index = row.normalizedName.indexOf(elem.pathLast);
1318 const word_index = searchWord.indexOf(elem.pathLast);
1320 // lower indexes are "better" matches
1321 // rank based on the "best" match
1322 if (row_index === -1) {
1324 } else if (word_index === -1) {
1326 } else if (word_index < row_index) {
1332 // No need to check anything else if it's a "pure" generics search.
1333 if (elem.name.length === 0) {
1334 if (row.type !== null) {
1335 lev = checkGenerics(row.type, elem, maxLevDistance + 1, maxLevDistance);
1336 // path_lev is 0 because we know it's empty
1337 addIntoResults(results_others, fullId, pos, index, lev, 0, maxLevDistance);
1342 if (elem.fullPath.length > 1) {
1343 path_lev = checkPath(elem.pathWithoutLast, row, maxLevDistance);
1344 if (path_lev > maxLevDistance) {
1349 if (parsedQuery.literalSearch) {
1350 if (searchWord === elem.name) {
1351 addIntoResults(results_others, fullId, pos, index, 0, path_lev);
1356 lev = levenshtein(searchWord, elem.pathLast);
1358 if (index === -1 && lev + path_lev > maxLevDistance) {
1362 addIntoResults(results_others, fullId, pos, index, lev, path_lev, maxLevDistance);
1366 * This function is called in case the query has more than one element. In this case, it'll
1367 * try to match the items which validates all the elements. For `aa -> bb` will look for
1368 * functions which have a parameter `aa` and has `bb` in its returned values.
1371 * @param {integer} pos - Position in the `searchIndex`.
1372 * @param {Object} results
1374 function handleArgs(row, pos, results, maxLevDistance) {
1375 if (!row || (filterCrates !== null && row.crate !== filterCrates)) {
1382 // If the result is too "bad", we return false and it ends this search.
1383 function checkArgs(elems, callback) {
1384 for (const elem of elems) {
1385 // There is more than one parameter to the query so all checks should be "exact"
1386 const lev = callback(row, elem, NO_TYPE_FILTER, maxLevDistance);
1396 if (!checkArgs(parsedQuery.elems, findArg)) {
1399 if (!checkArgs(parsedQuery.returned, checkReturned)) {
1406 const lev = Math.round(totalLev / nbLev);
1407 addIntoResults(results, row.id, pos, 0, lev, 0, maxLevDistance);
1410 function innerRunQuery() {
1411 let elem, i, nSearchWords, in_returned, row;
1414 for (const elem of parsedQuery.elems) {
1415 queryLen += elem.name.length;
1417 for (const elem of parsedQuery.returned) {
1418 queryLen += elem.name.length;
1420 const maxLevDistance = Math.floor(queryLen / 3);
1422 if (parsedQuery.foundElems === 1) {
1423 if (parsedQuery.elems.length === 1) {
1424 elem = parsedQuery.elems[0];
1425 for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1426 // It means we want to check for this element everywhere (in names, args and
1438 } else if (parsedQuery.returned.length === 1) {
1439 // We received one returned argument to check, so looking into returned values.
1440 elem = parsedQuery.returned[0];
1441 for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1442 row = searchIndex[i];
1443 in_returned = checkReturned(
1446 parsedQuery.typeFilter,
1449 addIntoResults(results_others, row.id, i, -1, in_returned, maxLevDistance);
1452 } else if (parsedQuery.foundElems > 0) {
1453 for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) {
1454 handleArgs(searchIndex[i], i, results_others, maxLevDistance);
1459 if (parsedQuery.error === null) {
1463 const ret = createQueryResults(
1464 sortResults(results_in_args, true, currentCrate),
1465 sortResults(results_returned, true, currentCrate),
1466 sortResults(results_others, false, currentCrate),
1468 handleAliases(ret, parsedQuery.original.replace(/"/g, ""), filterCrates, currentCrate);
1469 if (parsedQuery.error !== null && ret.others.length !== 0) {
1470 // It means some doc aliases were found so let's "remove" the error!
1471 ret.query.error = null;
1477 * Validate performs the following boolean logic. For example:
1478 * "File::open" will give IF A PARENT EXISTS => ("file" && "open")
1479 * exists in (name || path || parent) OR => ("file" && "open") exists in
1482 * This could be written functionally, but I wanted to minimise
1483 * functions on stack.
1485 * @param {string} name - The name of the result
1486 * @param {string} path - The path of the result
1487 * @param {string} keys - The keys to be used (["file", "open"])
1488 * @param {Object} parent - The parent of the result
1490 * @return {boolean} - Whether the result is valid or not
1492 function validateResult(name, path, keys, parent, maxLevDistance) {
1493 if (!keys || !keys.length) {
1496 for (const key of keys) {
1497 // each check is for validation so we negate the conditions and invalidate
1499 // check for an exact name match
1500 name.indexOf(key) > -1 ||
1501 // then an exact path match
1502 path.indexOf(key) > -1 ||
1503 // next if there is a parent, check for exact parent match
1504 (parent !== undefined && parent.name !== undefined &&
1505 parent.name.toLowerCase().indexOf(key) > -1) ||
1506 // lastly check to see if the name was a levenshtein match
1507 levenshtein(name, key) <= maxLevDistance)) {
1514 function nextTab(direction) {
1515 const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length;
1516 searchState.focusedByTab[searchState.currentTab] = document.activeElement;
1518 focusSearchResult();
1521 // Focus the first search result on the active tab, or the result that
1522 // was focused last time this tab was active.
1523 function focusSearchResult() {
1524 const target = searchState.focusedByTab[searchState.currentTab] ||
1525 document.querySelectorAll(".search-results.active a").item(0) ||
1526 document.querySelectorAll("#search-tabs button").item(searchState.currentTab);
1527 searchState.focusedByTab[searchState.currentTab] = null;
1533 function buildHrefAndPath(item) {
1536 const type = itemTypes[item.ty];
1537 const name = item.name;
1538 let path = item.path;
1540 if (type === "mod") {
1541 displayPath = path + "::";
1542 href = ROOT_PATH + path.replace(/::/g, "/") + "/" +
1543 name + "/index.html";
1544 } else if (type === "import") {
1545 displayPath = item.path + "::";
1546 href = ROOT_PATH + item.path.replace(/::/g, "/") + "/index.html#reexport." + name;
1547 } else if (type === "primitive" || type === "keyword") {
1549 href = ROOT_PATH + path.replace(/::/g, "/") +
1550 "/" + type + "." + name + ".html";
1551 } else if (type === "externcrate") {
1553 href = ROOT_PATH + name + "/index.html";
1554 } else if (item.parent !== undefined) {
1555 const myparent = item.parent;
1556 let anchor = "#" + type + "." + name;
1557 const parentType = itemTypes[myparent.ty];
1558 let pageType = parentType;
1559 let pageName = myparent.name;
1561 if (parentType === "primitive") {
1562 displayPath = myparent.name + "::";
1563 } else if (type === "structfield" && parentType === "variant") {
1564 // Structfields belonging to variants are special: the
1565 // final path element is the enum name.
1566 const enumNameIdx = item.path.lastIndexOf("::");
1567 const enumName = item.path.substr(enumNameIdx + 2);
1568 path = item.path.substr(0, enumNameIdx);
1569 displayPath = path + "::" + enumName + "::" + myparent.name + "::";
1570 anchor = "#variant." + myparent.name + ".field." + name;
1572 pageName = enumName;
1574 displayPath = path + "::" + myparent.name + "::";
1576 href = ROOT_PATH + path.replace(/::/g, "/") +
1581 displayPath = item.path + "::";
1582 href = ROOT_PATH + item.path.replace(/::/g, "/") +
1583 "/" + type + "." + name + ".html";
1585 return [displayPath, href];
1588 function pathSplitter(path) {
1589 const tmp = "<span>" + path.replace(/::/g, "::</span><span>");
1590 if (tmp.endsWith("<span>")) {
1591 return tmp.slice(0, tmp.length - 6);
1597 * Render a set of search results for a single tab.
1598 * @param {Array<?>} array - The search results for this tab
1599 * @param {ParsedQuery} query
1600 * @param {boolean} display - True if this is the active tab
1602 function addTab(array, query, display) {
1603 let extraClass = "";
1604 if (display === true) {
1605 extraClass = " active";
1608 const output = document.createElement("div");
1610 if (array.length > 0) {
1611 output.className = "search-results " + extraClass;
1613 array.forEach(item => {
1614 const name = item.name;
1615 const type = itemTypes[item.ty];
1620 if (type === "primitive") {
1621 extra = " <i>(primitive type)</i>";
1622 } else if (type === "keyword") {
1623 extra = " <i>(keyword)</i>";
1626 const link = document.createElement("a");
1627 link.className = "result-" + type;
1628 link.href = item.href;
1630 const resultName = document.createElement("div");
1631 resultName.className = "result-name";
1633 if (item.is_alias) {
1634 const alias = document.createElement("span");
1635 alias.className = "alias";
1637 const bold = document.createElement("b");
1638 bold.innerText = item.alias;
1639 alias.appendChild(bold);
1641 alias.insertAdjacentHTML(
1643 "<span class=\"grey\"><i> - see </i></span>");
1645 resultName.appendChild(alias);
1647 resultName.insertAdjacentHTML(
1649 item.displayPath + "<span class=\"" + type + "\">" + name + extra + "</span>");
1650 link.appendChild(resultName);
1652 const description = document.createElement("div");
1653 description.className = "desc";
1654 description.insertAdjacentHTML("beforeend", item.desc);
1656 link.appendChild(description);
1657 output.appendChild(link);
1659 } else if (query.error === null) {
1660 output.className = "search-failed" + extraClass;
1661 output.innerHTML = "No results :(<br/>" +
1662 "Try on <a href=\"https://duckduckgo.com/?q=" +
1663 encodeURIComponent("rust " + query.userQuery) +
1664 "\">DuckDuckGo</a>?<br/><br/>" +
1665 "Or try looking in one of these:<ul><li>The <a " +
1666 "href=\"https://doc.rust-lang.org/reference/index.html\">Rust Reference</a> " +
1667 " for technical details about the language.</li><li><a " +
1668 "href=\"https://doc.rust-lang.org/rust-by-example/index.html\">Rust By " +
1669 "Example</a> for expository code examples.</a></li><li>The <a " +
1670 "href=\"https://doc.rust-lang.org/book/index.html\">Rust Book</a> for " +
1671 "introductions to language features and the language itself.</li><li><a " +
1672 "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" +
1673 " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>";
1675 return [output, length];
1678 function makeTabHeader(tabNb, text, nbElems) {
1679 if (searchState.currentTab === tabNb) {
1680 return "<button class=\"selected\">" + text +
1681 " <span class=\"count\">(" + nbElems + ")</span></button>";
1683 return "<button>" + text + " <span class=\"count\">(" + nbElems + ")</span></button>";
1687 * @param {ResultsTable} results
1688 * @param {boolean} go_to_first
1689 * @param {string} filterCrates
1691 function showResults(results, go_to_first, filterCrates) {
1692 const search = searchState.outputElement();
1693 if (go_to_first || (results.others.length === 1
1694 && getSettingValue("go-to-only-result") === "true"
1695 // By default, the search DOM element is "empty" (meaning it has no children not
1696 // text content). Once a search has been run, it won't be empty, even if you press
1697 // ESC or empty the search input (which also "cancels" the search).
1698 && (!search.firstChild || search.firstChild.innerText !== searchState.loadingText))
1700 const elem = document.createElement("a");
1701 elem.href = results.others[0].href;
1702 removeClass(elem, "active");
1703 // For firefox, we need the element to be in the DOM so it can be clicked.
1704 document.body.appendChild(elem);
1708 if (results.query === undefined) {
1709 results.query = parseQuery(searchState.input.value);
1712 currentResults = results.query.userQuery;
1714 const ret_others = addTab(results.others, results.query, true);
1715 const ret_in_args = addTab(results.in_args, results.query, false);
1716 const ret_returned = addTab(results.returned, results.query, false);
1718 // Navigate to the relevant tab if the current tab is empty, like in case users search
1719 // for "-> String". If they had selected another tab previously, they have to click on
1721 let currentTab = searchState.currentTab;
1722 if ((currentTab === 0 && ret_others[1] === 0) ||
1723 (currentTab === 1 && ret_in_args[1] === 0) ||
1724 (currentTab === 2 && ret_returned[1] === 0)) {
1725 if (ret_others[1] !== 0) {
1727 } else if (ret_in_args[1] !== 0) {
1729 } else if (ret_returned[1] !== 0) {
1735 const crates_list = Object.keys(rawSearchIndex);
1736 if (crates_list.length > 1) {
1737 crates = " in <div id=\"crate-search-div\"><select id=\"crate-search\">" +
1738 "<option value=\"all crates\">all crates</option>";
1739 for (const c of crates_list) {
1740 crates += `<option value="${c}" ${c === filterCrates && "selected"}>${c}</option>`;
1742 crates += "</select></div>";
1745 let output = `<h1 class="search-results-title">Results${crates}</h1>`;
1746 if (results.query.error !== null) {
1747 output += `<h3>Query parser error: "${results.query.error}".</h3>`;
1748 output += "<div id=\"search-tabs\">" +
1749 makeTabHeader(0, "In Names", ret_others[1]) +
1752 } else if (results.query.foundElems <= 1 && results.query.returned.length === 0) {
1753 output += "<div id=\"search-tabs\">" +
1754 makeTabHeader(0, "In Names", ret_others[1]) +
1755 makeTabHeader(1, "In Parameters", ret_in_args[1]) +
1756 makeTabHeader(2, "In Return Types", ret_returned[1]) +
1759 const signatureTabTitle =
1760 results.query.elems.length === 0 ? "In Function Return Types" :
1761 results.query.returned.length === 0 ? "In Function Parameters" :
1762 "In Function Signatures";
1763 output += "<div id=\"search-tabs\">" +
1764 makeTabHeader(0, signatureTabTitle, ret_others[1]) +
1769 const resultsElem = document.createElement("div");
1770 resultsElem.id = "results";
1771 resultsElem.appendChild(ret_others[0]);
1772 resultsElem.appendChild(ret_in_args[0]);
1773 resultsElem.appendChild(ret_returned[0]);
1775 search.innerHTML = output;
1776 const crateSearch = document.getElementById("crate-search");
1778 crateSearch.addEventListener("input", updateCrate);
1780 search.appendChild(resultsElem);
1781 // Reset focused elements.
1782 searchState.showResults(search);
1783 const elems = document.getElementById("search-tabs").childNodes;
1784 searchState.focusedByTab = [];
1786 for (const elem of elems) {
1788 elem.onclick = () => printTab(j);
1789 searchState.focusedByTab.push(null);
1792 printTab(currentTab);
1796 * Perform a search based on the current state of the search input element
1797 * and display the results.
1798 * @param {Event} [e] - The event that triggered this search, if any
1799 * @param {boolean} [forced]
1801 function search(e, forced) {
1806 const query = parseQuery(searchState.input.value.trim());
1807 let filterCrates = getFilterCrates();
1809 if (!forced && query.userQuery === currentResults) {
1810 if (query.userQuery.length > 0) {
1816 searchState.setLoadingSearch();
1818 const params = searchState.getQueryStringParams();
1820 // In case we have no information about the saved crate and there is a URL query parameter,
1821 // we override it with the URL query parameter.
1822 if (filterCrates === null && params["filter-crate"] !== undefined) {
1823 filterCrates = params["filter-crate"];
1826 // Update document title to maintain a meaningful browser history
1827 searchState.title = "Results for " + query.original + " - Rust";
1829 // Because searching is incremental by character, only the most
1830 // recent search query is added to the browser history.
1831 if (browserSupportsHistoryApi()) {
1832 const newURL = buildUrl(query.original, filterCrates);
1834 if (!history.state && !params.search) {
1835 history.pushState(null, "", newURL);
1837 history.replaceState(null, "", newURL);
1842 execQuery(query, searchWords, filterCrates, window.currentCrate),
1848 * Convert a list of RawFunctionType / ID to object-based FunctionType.
1850 * Crates often have lots of functions in them, and it's common to have a large number of
1851 * functions that operate on a small set of data types, so the search index compresses them
1852 * by encoding function parameter and return types as indexes into an array of names.
1854 * Even when a general-purpose compression algorithm is used, this is still a win. I checked.
1855 * https://github.com/rust-lang/rust/pull/98475#issue-1284395985
1857 * The format for individual function types is encoded in
1858 * librustdoc/html/render/mod.rs: impl Serialize for RenderType
1860 * @param {null|Array<RawFunctionType>} types
1861 * @param {Array<{name: string, ty: number}>} lowercasePaths
1863 * @return {Array<FunctionSearchType>}
1865 function buildItemSearchTypeAll(types, lowercasePaths) {
1866 const PATH_INDEX_DATA = 0;
1867 const GENERICS_DATA = 1;
1868 return types.map(type => {
1869 let pathIndex, generics;
1870 if (typeof type === "number") {
1874 pathIndex = type[PATH_INDEX_DATA];
1875 generics = buildItemSearchTypeAll(type[GENERICS_DATA], lowercasePaths);
1878 // `0` is used as a sentinel because it's fewer bytes than `null`
1879 name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
1880 ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
1887 * Convert from RawFunctionSearchType to FunctionSearchType.
1889 * Crates often have lots of functions in them, and function signatures are sometimes complex,
1890 * so rustdoc uses a pretty tight encoding for them. This function converts it to a simpler,
1891 * object-based encoding so that the actual search code is more readable and easier to debug.
1893 * The raw function search type format is generated using serde in
1894 * librustdoc/html/render/mod.rs: impl Serialize for IndexItemFunctionType
1896 * @param {RawFunctionSearchType} functionSearchType
1897 * @param {Array<{name: string, ty: number}>} lowercasePaths
1899 * @return {null|FunctionSearchType}
1901 function buildFunctionSearchType(functionSearchType, lowercasePaths) {
1902 const INPUTS_DATA = 0;
1903 const OUTPUT_DATA = 1;
1904 // `0` is used as a sentinel because it's fewer bytes than `null`
1905 if (functionSearchType === 0) {
1909 if (typeof functionSearchType[INPUTS_DATA] === "number") {
1910 const pathIndex = functionSearchType[INPUTS_DATA];
1912 name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
1913 ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
1917 inputs = buildItemSearchTypeAll(functionSearchType[INPUTS_DATA], lowercasePaths);
1919 if (functionSearchType.length > 1) {
1920 if (typeof functionSearchType[OUTPUT_DATA] === "number") {
1921 const pathIndex = functionSearchType[OUTPUT_DATA];
1923 name: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].name,
1924 ty: pathIndex === 0 ? null : lowercasePaths[pathIndex - 1].ty,
1928 output = buildItemSearchTypeAll(functionSearchType[OUTPUT_DATA], lowercasePaths);
1938 function buildIndex(rawSearchIndex) {
1941 * @type {Array<string>}
1943 const searchWords = [];
1945 let currentIndex = 0;
1948 for (const crate in rawSearchIndex) {
1949 if (!hasOwnPropertyRustdoc(rawSearchIndex, crate)) {
1956 * The raw search data for a given crate. `n`, `t`, `d`, and `q`, `i`, and `f`
1957 * are arrays with the same length. n[i] contains the name of an item.
1958 * t[i] contains the type of that item (as a small integer that represents an
1959 * offset in `itemTypes`). d[i] contains the description of that item.
1961 * q[i] contains the full path of the item, or an empty string indicating
1964 * i[i] contains an item's parent, usually a module. For compactness,
1965 * it is a set of indexes into the `p` array.
1967 * f[i] contains function signatures, or `0` if the item isn't a function.
1968 * Functions are themselves encoded as arrays. The first item is a list of
1969 * types representing the function's inputs, and the second list item is a list
1970 * of types representing the function's output. Tuples are flattened.
1971 * Types are also represented as arrays; the first item is an index into the `p`
1972 * array, while the second is a list of types representing any generic parameters.
1974 * `a` defines aliases with an Array of pairs: [name, offset], where `offset`
1975 * points into the n/t/d/q/i/f arrays.
1977 * `doc` contains the description of the crate.
1979 * `p` is a list of path/type pairs. It is used for parents and function parameters.
1989 * f: Array<RawFunctionSearchType>,
1993 const crateCorpus = rawSearchIndex[crate];
1995 searchWords.push(crate);
1996 // This object should have exactly the same set of fields as the "row"
1997 // object defined below. Your JavaScript runtime will thank you.
1998 // https://mathiasbynens.be/notes/shapes-ics
2001 ty: 1, // == ExternCrate
2004 desc: crateCorpus.doc,
2008 normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""),
2011 searchIndex.push(crateRow);
2014 // an array of (Number) item types
2015 const itemTypes = crateCorpus.t;
2016 // an array of (String) item names
2017 const itemNames = crateCorpus.n;
2018 // an array of (String) full paths (or empty string for previous path)
2019 const itemPaths = crateCorpus.q;
2020 // an array of (String) descriptions
2021 const itemDescs = crateCorpus.d;
2022 // an array of (Number) the parent path index + 1 to `paths`, or 0 if none
2023 const itemParentIdxs = crateCorpus.i;
2024 // an array of (Object | null) the type of the function, if any
2025 const itemFunctionSearchTypes = crateCorpus.f;
2026 // an array of [(Number) item type,
2028 const paths = crateCorpus.p;
2029 // an array of [(String) alias name
2030 // [Number] index to items]
2031 const aliases = crateCorpus.a;
2033 // an array of [{name: String, ty: Number}]
2034 const lowercasePaths = [];
2036 // convert `rawPaths` entries into object form
2037 // generate normalizedPaths for function search mode
2038 let len = paths.length;
2039 for (i = 0; i < len; ++i) {
2040 lowercasePaths.push({ty: paths[i][0], name: paths[i][1].toLowerCase()});
2041 paths[i] = {ty: paths[i][0], name: paths[i][1]};
2044 // convert `item*` into an object form, and construct word indices.
2046 // before any analysis is performed lets gather the search terms to
2047 // search against apart from the rest of the data. This is a quick
2048 // operation that is cached for the life of the page state so that
2049 // all other search operations have access to this cached data for
2050 // faster analysis operations
2051 len = itemTypes.length;
2053 for (i = 0; i < len; ++i) {
2054 // This object should have exactly the same set of fields as the "crateRow"
2055 // object defined above.
2056 if (typeof itemNames[i] === "string") {
2057 word = itemNames[i].toLowerCase();
2058 searchWords.push(word);
2061 searchWords.push("");
2067 path: itemPaths[i] ? itemPaths[i] : lastPath,
2069 parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined,
2070 type: buildFunctionSearchType(itemFunctionSearchTypes[i], lowercasePaths),
2072 normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""),
2075 searchIndex.push(row);
2076 lastPath = row.path;
2081 ALIASES[crate] = Object.create(null);
2082 for (const alias_name in aliases) {
2083 if (!hasOwnPropertyRustdoc(aliases, alias_name)) {
2087 if (!hasOwnPropertyRustdoc(ALIASES[crate], alias_name)) {
2088 ALIASES[crate][alias_name] = [];
2090 for (const local_alias of aliases[alias_name]) {
2091 ALIASES[crate][alias_name].push(local_alias + currentIndex);
2095 currentIndex += crateSize;
2101 * Callback for when the search form is submitted.
2102 * @param {Event} [e] - The event that triggered this call, if any
2104 function onSearchSubmit(e) {
2106 searchState.clearInputTimeout();
2110 function putBackSearch() {
2111 const search_input = searchState.input;
2112 if (!searchState.input) {
2115 if (search_input.value !== "" && !searchState.isDisplayed()) {
2116 searchState.showResults();
2117 if (browserSupportsHistoryApi()) {
2118 history.replaceState(null, "",
2119 buildUrl(search_input.value, getFilterCrates()));
2121 document.title = searchState.title;
2125 function registerSearchEvents() {
2126 const params = searchState.getQueryStringParams();
2128 // Populate search bar with query string search term when provided,
2129 // but only if the input bar is empty. This avoid the obnoxious issue
2130 // where you start trying to do a search, and the index loads, and
2131 // suddenly your search is gone!
2132 if (searchState.input.value === "") {
2133 searchState.input.value = params.search || "";
2136 const searchAfter500ms = () => {
2137 searchState.clearInputTimeout();
2138 if (searchState.input.value.length === 0) {
2139 if (browserSupportsHistoryApi()) {
2140 history.replaceState(null, window.currentCrate + " - Rust",
2141 getNakedUrl() + window.location.hash);
2143 searchState.hideResults();
2145 searchState.timeout = setTimeout(search, 500);
2148 searchState.input.onkeyup = searchAfter500ms;
2149 searchState.input.oninput = searchAfter500ms;
2150 document.getElementsByClassName("search-form")[0].onsubmit = onSearchSubmit;
2151 searchState.input.onchange = e => {
2152 if (e.target !== document.activeElement) {
2153 // To prevent doing anything when it's from a blur event.
2156 // Do NOT e.preventDefault() here. It will prevent pasting.
2157 searchState.clearInputTimeout();
2158 // zero-timeout necessary here because at the time of event handler execution the
2159 // pasted content is not in the input field yet. Shouldn’t make any difference for
2161 setTimeout(search, 0);
2163 searchState.input.onpaste = searchState.input.onchange;
2165 searchState.outputElement().addEventListener("keydown", e => {
2166 // We only handle unmodified keystrokes here. We don't want to interfere with,
2167 // for instance, alt-left and alt-right for history navigation.
2168 if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) {
2171 // up and down arrow select next/previous search result, or the
2172 // search box if we're already at the top.
2173 if (e.which === 38) { // up
2174 const previous = document.activeElement.previousElementSibling;
2178 searchState.focus();
2181 } else if (e.which === 40) { // down
2182 const next = document.activeElement.nextElementSibling;
2186 const rect = document.activeElement.getBoundingClientRect();
2187 if (window.innerHeight - rect.bottom < rect.height) {
2188 window.scrollBy(0, rect.height);
2191 } else if (e.which === 37) { // left
2194 } else if (e.which === 39) { // right
2200 searchState.input.addEventListener("keydown", e => {
2201 if (e.which === 40) { // down
2202 focusSearchResult();
2207 searchState.input.addEventListener("focus", () => {
2211 searchState.input.addEventListener("blur", () => {
2212 searchState.input.placeholder = searchState.input.origPlaceholder;
2215 // Push and pop states are used to add search results to the browser
2217 if (browserSupportsHistoryApi()) {
2218 // Store the previous <title> so we can revert back to it later.
2219 const previousTitle = document.title;
2221 window.addEventListener("popstate", e => {
2222 const params = searchState.getQueryStringParams();
2223 // Revert to the previous title manually since the History
2224 // API ignores the title parameter.
2225 document.title = previousTitle;
2226 // When browsing forward to search results the previous
2227 // search will be repeated, so the currentResults are
2228 // cleared to ensure the search is successful.
2229 currentResults = null;
2230 // Synchronize search bar with query string state and
2231 // perform the search. This will empty the bar if there's
2232 // nothing there, which lets you really go back to a
2233 // previous state with nothing in the bar.
2234 if (params.search && params.search.length > 0) {
2235 searchState.input.value = params.search;
2236 // Some browsers fire "onpopstate" for every page load
2237 // (Chrome), while others fire the event only when actually
2238 // popping a state (Firefox), which is why search() is
2239 // called both here and at the end of the startSearch()
2243 searchState.input.value = "";
2244 // When browsing back from search results the main page
2245 // visibility must be reset.
2246 searchState.hideResults();
2251 // This is required in firefox to avoid this problem: Navigating to a search result
2252 // with the keyboard, hitting enter, and then hitting back would take you back to
2253 // the doc page, rather than the search that should overlay it.
2254 // This was an interaction between the back-forward cache and our handlers
2255 // that try to sync state between the URL and the search input. To work around it,
2256 // do a small amount of re-init on page show.
2257 window.onpageshow = () => {
2258 const qSearch = searchState.getQueryStringParams().search;
2259 if (searchState.input.value === "" && qSearch) {
2260 searchState.input.value = qSearch;
2266 function updateCrate(ev) {
2267 if (ev.target.value === "all crates") {
2268 // If we don't remove it from the URL, it'll be picked up again by the search.
2269 const params = searchState.getQueryStringParams();
2270 const query = searchState.input.value.trim();
2271 if (!history.state && !params.search) {
2272 history.pushState(null, "", buildUrl(query, null));
2274 history.replaceState(null, "", buildUrl(query, null));
2277 // In case you "cut" the entry from the search input, then change the crate filter
2278 // before paste back the previous search, you get the old search results without
2279 // the filter. To prevent this, we need to remove the previous results.
2280 currentResults = null;
2281 search(undefined, true);
2285 * @type {Array<string>}
2287 const searchWords = buildIndex(rawSearchIndex);
2288 if (typeof window !== "undefined") {
2289 registerSearchEvents();
2290 // If there's a search term in the URL, execute the search now.
2291 if (window.searchState.getQueryStringParams().search) {
2296 if (typeof exports !== "undefined") {
2297 exports.initSearch = initSearch;
2298 exports.execQuery = execQuery;
2299 exports.parseQuery = parseQuery;
2304 if (typeof window !== "undefined") {
2305 window.initSearch = initSearch;
2306 if (window.searchIndex !== undefined) {
2307 initSearch(window.searchIndex);
2310 // Running in Node, not a browser. Run initSearch just to produce the