From 631cd5845e8de329d0e227aaa707d7ea228b8f8f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:20:29 +0200 Subject: Merging upstream version 1.70.0+dfsg1. Signed-off-by: Daniel Baumann --- src/librustdoc/html/static/js/search.js | 716 ++++++++++++++++++++------------ 1 file changed, 457 insertions(+), 259 deletions(-) (limited to 'src/librustdoc/html/static/js/search.js') diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js index b98bced41..929dae81c 100644 --- a/src/librustdoc/html/static/js/search.js +++ b/src/librustdoc/html/static/js/search.js @@ -76,39 +76,111 @@ function printTab(nb) { } /** - * A function to compute the Levenshtein distance between two strings - * Licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported - * Full License can be found at http://creativecommons.org/licenses/by-sa/3.0/legalcode - * This code is an unmodified version of the code written by Marco de Wit - * and was found at https://stackoverflow.com/a/18514751/745719 + * The [edit distance] is a metric for measuring the difference between two strings. + * + * [edit distance]: https://en.wikipedia.org/wiki/Edit_distance */ -const levenshtein_row2 = []; -function levenshtein(s1, s2) { - if (s1 === s2) { - return 0; - } - const s1_len = s1.length, s2_len = s2.length; - if (s1_len && s2_len) { - let i1 = 0, i2 = 0, a, b, c, c2; - const row = levenshtein_row2; - while (i1 < s1_len) { - row[i1] = ++i1; - } - while (i2 < s2_len) { - c2 = s2.charCodeAt(i2); - a = i2; - ++i2; - b = i2; - for (i1 = 0; i1 < s1_len; ++i1) { - c = a + (s1.charCodeAt(i1) !== c2 ? 1 : 0); - a = row[i1]; - b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); - row[i1] = b; - } - } - return b; - } - return s1_len + s2_len; + +/* + * This function was translated, mostly line-for-line, from + * https://github.com/rust-lang/rust/blob/ff4b772f805ec1e/compiler/rustc_span/src/edit_distance.rs + * + * The current implementation is the restricted Damerau-Levenshtein algorithm. It is restricted + * because it does not permit modifying characters that have already been transposed. The specific + * algorithm should not matter to the caller of the methods, which is why it is not noted in the + * documentation. + */ +const editDistanceState = { + current: [], + prev: [], + prevPrev: [], + calculate: function calculate(a, b, limit) { + // Ensure that `b` is the shorter string, minimizing memory use. + if (a.length < b.length) { + const aTmp = a; + a = b; + b = aTmp; + } + + const minDist = a.length - b.length; + // If we know the limit will be exceeded, we can return early. + if (minDist > limit) { + return limit + 1; + } + + // Strip common prefix. + // We know that `b` is the shorter string, so we don't need to check + // `a.length`. + while (b.length > 0 && b[0] === a[0]) { + a = a.substring(1); + b = b.substring(1); + } + // Strip common suffix. + while (b.length > 0 && b[b.length - 1] === a[a.length - 1]) { + a = a.substring(0, a.length - 1); + b = b.substring(0, b.length - 1); + } + + // If either string is empty, the distance is the length of the other. + // We know that `b` is the shorter string, so we don't need to check `a`. + if (b.length === 0) { + return minDist; + } + + const aLength = a.length; + const bLength = b.length; + + for (let i = 0; i <= bLength; ++i) { + this.current[i] = 0; + this.prev[i] = i; + this.prevPrev[i] = Number.MAX_VALUE; + } + + // row by row + for (let i = 1; i <= aLength; ++i) { + this.current[0] = i; + const aIdx = i - 1; + + // column by column + for (let j = 1; j <= bLength; ++j) { + const bIdx = j - 1; + + // There is no cost to substitute a character with itself. + const substitutionCost = a[aIdx] === b[bIdx] ? 0 : 1; + + this.current[j] = Math.min( + // deletion + this.prev[j] + 1, + // insertion + this.current[j - 1] + 1, + // substitution + this.prev[j - 1] + substitutionCost + ); + + if ((i > 1) && (j > 1) && (a[aIdx] === b[bIdx - 1]) && (a[aIdx - 1] === b[bIdx])) { + // transposition + this.current[j] = Math.min( + this.current[j], + this.prevPrev[j - 2] + 1 + ); + } + } + + // Rotate the buffers, reusing the memory + const prevPrevTmp = this.prevPrev; + this.prevPrev = this.prev; + this.prev = this.current; + this.current = prevPrevTmp; + } + + // `prev` because we already rotated the buffers. + const distance = this.prev[bLength]; + return distance <= limit ? distance : (limit + 1); + }, +}; + +function editDistance(a, b, limit) { + return editDistanceState.calculate(a, b, limit); } function initSearch(rawSearchIndex) { @@ -119,7 +191,7 @@ function initSearch(rawSearchIndex) { */ let searchIndex; let currentResults; - const ALIASES = Object.create(null); + const ALIASES = new Map(); function isWhitespace(c) { return " \t\n\r".indexOf(c) !== -1; @@ -282,12 +354,15 @@ function initSearch(rawSearchIndex) { if (isInGenerics) { parserState.genericsElems += 1; } + const typeFilter = parserState.typeFilter; + parserState.typeFilter = null; return { name: name, fullPath: pathSegments, pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1), pathLast: pathSegments[pathSegments.length - 1], generics: generics, + typeFilter, }; } @@ -386,9 +461,7 @@ function initSearch(rawSearchIndex) { if (parserState.pos < parserState.length && parserState.userQuery[parserState.pos] === "<" ) { - if (isInGenerics) { - throw ["Unexpected ", "<", " after ", "<"]; - } else if (start >= end) { + if (start >= end) { throw ["Found generics without a path"]; } parserState.pos += 1; @@ -423,6 +496,11 @@ function initSearch(rawSearchIndex) { */ function getItemsBefore(query, parserState, elems, endChar) { let foundStopChar = true; + let start = parserState.pos; + + // If this is a generic, keep the outer item's type filter around. + const oldTypeFilter = parserState.typeFilter; + parserState.typeFilter = null; while (parserState.pos < parserState.length) { const c = parserState.userQuery[parserState.pos]; @@ -434,7 +512,25 @@ function initSearch(rawSearchIndex) { continue; } else if (c === ":" && isPathStart(parserState)) { throw ["Unexpected ", "::", ": paths cannot start with ", "::"]; - } else if (c === ":" || isEndCharacter(c)) { + } else if (c === ":") { + if (parserState.typeFilter !== null) { + throw ["Unexpected ", ":"]; + } + if (elems.length === 0) { + throw ["Expected type filter before ", ":"]; + } else if (query.literalSearch) { + throw ["You cannot use quotes on type filter"]; + } + // The type filter doesn't count as an element since it's a modifier. + const typeFilterElem = elems.pop(); + checkExtraTypeFilterCharacters(start, parserState); + parserState.typeFilter = typeFilterElem.name; + parserState.pos += 1; + parserState.totalElems -= 1; + query.literalSearch = false; + foundStopChar = true; + continue; + } else if (isEndCharacter(c)) { let extra = ""; if (endChar === ">") { extra = "<"; @@ -468,15 +564,10 @@ function initSearch(rawSearchIndex) { ]; } const posBefore = parserState.pos; + start = parserState.pos; getNextElem(query, parserState, elems, endChar === ">"); - if (endChar !== "") { - if (parserState.pos >= parserState.length) { - throw ["Unclosed ", "<"]; - } - const c2 = parserState.userQuery[parserState.pos]; - if (!isSeparatorCharacter(c2) && c2 !== endChar) { - throw ["Expected ", endChar, ", found ", c2]; - } + if (endChar !== "" && parserState.pos >= parserState.length) { + throw ["Unclosed ", "<"]; } // This case can be encountered if `getNextElem` encountered a "stop character" right // from the start. For example if you have `,,` or `<>`. In this case, we simply move up @@ -492,6 +583,8 @@ function initSearch(rawSearchIndex) { // We are either at the end of the string or on the `endChar` character, let's move forward // in any case. parserState.pos += 1; + + parserState.typeFilter = oldTypeFilter; } /** @@ -500,10 +593,10 @@ function initSearch(rawSearchIndex) { * * @param {ParserState} parserState */ - function checkExtraTypeFilterCharacters(parserState) { + function checkExtraTypeFilterCharacters(start, parserState) { const query = parserState.userQuery; - for (let pos = 0; pos < parserState.pos; ++pos) { + for (let pos = start; pos < parserState.pos; ++pos) { if (!isIdentCharacter(query[pos]) && !isWhitespaceCharacter(query[pos])) { throw ["Unexpected ", query[pos], " in type filter"]; } @@ -519,6 +612,7 @@ function initSearch(rawSearchIndex) { */ function parseInput(query, parserState) { let foundStopChar = true; + let start = parserState.pos; while (parserState.pos < parserState.length) { const c = parserState.userQuery[parserState.pos]; @@ -540,16 +634,15 @@ function initSearch(rawSearchIndex) { } if (query.elems.length === 0) { throw ["Expected type filter before ", ":"]; - } else if (query.elems.length !== 1 || parserState.totalElems !== 1) { - throw ["Unexpected ", ":"]; } else if (query.literalSearch) { throw ["You cannot use quotes on type filter"]; } - checkExtraTypeFilterCharacters(parserState); // The type filter doesn't count as an element since it's a modifier. - parserState.typeFilter = query.elems.pop().name; + const typeFilterElem = query.elems.pop(); + checkExtraTypeFilterCharacters(start, parserState); + parserState.typeFilter = typeFilterElem.name; parserState.pos += 1; - parserState.totalElems = 0; + parserState.totalElems -= 1; query.literalSearch = false; foundStopChar = true; continue; @@ -581,6 +674,7 @@ function initSearch(rawSearchIndex) { ]; } const before = query.elems.length; + start = parserState.pos; getNextElem(query, parserState, query.elems, false); if (query.elems.length === before) { // Nothing was added, weird... Let's increase the position to not remain stuck. @@ -588,6 +682,9 @@ function initSearch(rawSearchIndex) { } foundStopChar = false; } + if (parserState.typeFilter !== null) { + throw ["Unexpected ", ":", " (expected path after type filter)"]; + } while (parserState.pos < parserState.length) { if (isReturnArrow(parserState)) { parserState.pos += 2; @@ -615,7 +712,6 @@ function initSearch(rawSearchIndex) { return { original: userQuery, userQuery: userQuery.toLowerCase(), - typeFilter: NO_TYPE_FILTER, elems: [], returned: [], // Total number of "top" elements (does not include generics). @@ -666,18 +762,15 @@ function initSearch(rawSearchIndex) { * * ident = *(ALPHA / DIGIT / "_") * path = ident *(DOUBLE-COLON ident) [!] - * arg = path [generics] - * arg-without-generic = path + * arg = [type-filter *WS COLON *WS] path [generics] * type-sep = COMMA/WS *(COMMA/WS) * nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep) - * nonempty-arg-list-without-generics = *(type-sep) arg-without-generic - * *(type-sep arg-without-generic) *(type-sep) - * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list-without-generics ] *(type-sep) - * CLOSE-ANGLE-BRACKET/EOF + * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list ] *(type-sep) + * CLOSE-ANGLE-BRACKET * return-args = RETURN-ARROW *(type-sep) nonempty-arg-list * * exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ] - * type-search = [type-filter *WS COLON] [ nonempty-arg-list ] [ return-args ] + * type-search = [ nonempty-arg-list ] [ return-args ] * * query = *WS (exact-search / type-search) *WS * @@ -726,6 +819,20 @@ function initSearch(rawSearchIndex) { * @return {ParsedQuery} - The parsed query */ function parseQuery(userQuery) { + function convertTypeFilterOnElem(elem) { + if (elem.typeFilter !== null) { + let typeFilter = elem.typeFilter; + if (typeFilter === "const") { + typeFilter = "constant"; + } + elem.typeFilter = itemTypeFromName(typeFilter); + } else { + elem.typeFilter = NO_TYPE_FILTER; + } + for (const elem2 of elem.generics) { + convertTypeFilterOnElem(elem2); + } + } userQuery = userQuery.trim(); const parserState = { length: userQuery.length, @@ -740,17 +847,15 @@ function initSearch(rawSearchIndex) { try { parseInput(query, parserState); - if (parserState.typeFilter !== null) { - let typeFilter = parserState.typeFilter; - if (typeFilter === "const") { - typeFilter = "constant"; - } - query.typeFilter = itemTypeFromName(typeFilter); + for (const elem of query.elems) { + convertTypeFilterOnElem(elem); + } + for (const elem of query.returned) { + convertTypeFilterOnElem(elem); } } catch (err) { query = newParsedQuery(userQuery); query.error = err; - query.typeFilter = -1; return query; } @@ -793,26 +898,34 @@ function initSearch(rawSearchIndex) { * @return {ResultsTable} */ function execQuery(parsedQuery, searchWords, filterCrates, currentCrate) { - const results_others = {}, results_in_args = {}, results_returned = {}; + const results_others = new Map(), results_in_args = new Map(), + results_returned = new Map(); + /** + * Add extra data to result objects, and filter items that have been + * marked for removal. + * + * @param {[ResultObject]} results + * @returns {[ResultObject]} + */ function transformResults(results) { - const duplicates = {}; + const duplicates = new Set(); const out = []; for (const result of results) { if (result.id > -1) { const obj = searchIndex[result.id]; - obj.lev = result.lev; + obj.dist = result.dist; const res = buildHrefAndPath(obj); obj.displayPath = pathSplitter(res[0]); obj.fullPath = obj.displayPath + obj.name; // To be sure than it some items aren't considered as duplicate. obj.fullPath += "|" + obj.ty; - if (duplicates[obj.fullPath]) { + if (duplicates.has(obj.fullPath)) { continue; } - duplicates[obj.fullPath] = true; + duplicates.add(obj.fullPath); obj.href = res[1]; out.push(obj); @@ -824,24 +937,30 @@ function initSearch(rawSearchIndex) { return out; } + /** + * This function takes a result map, and sorts it by various criteria, including edit + * distance, substring match, and the crate it comes from. + * + * @param {Results} results + * @param {boolean} isType + * @param {string} preferredCrate + * @returns {[ResultObject]} + */ function sortResults(results, isType, preferredCrate) { - const userQuery = parsedQuery.userQuery; - const ar = []; - for (const entry in results) { - if (hasOwnPropertyRustdoc(results, entry)) { - const result = results[entry]; - result.word = searchWords[result.id]; - result.item = searchIndex[result.id] || {}; - ar.push(result); - } - } - results = ar; // if there are no results then return to default and fail - if (results.length === 0) { + if (results.size === 0) { return []; } - results.sort((aaa, bbb) => { + const userQuery = parsedQuery.userQuery; + const result_list = []; + for (const result of results.values()) { + result.word = searchWords[result.id]; + result.item = searchIndex[result.id] || {}; + result_list.push(result); + } + + result_list.sort((aaa, bbb) => { let a, b; // sort by exact match with regard to the last word (mismatch goes later) @@ -860,8 +979,8 @@ function initSearch(rawSearchIndex) { // Sort by distance in the path part, if specified // (less changes required to match means higher rankings) - a = aaa.path_lev; - b = bbb.path_lev; + a = aaa.path_dist; + b = bbb.path_dist; if (a !== b) { return a - b; } @@ -875,8 +994,15 @@ function initSearch(rawSearchIndex) { // Sort by distance in the name part, the last part of the path // (less changes required to match means higher rankings) - a = (aaa.lev); - b = (bbb.lev); + a = (aaa.dist); + b = (bbb.dist); + if (a !== b) { + return a - b; + } + + // sort deprecated items later + a = aaa.item.deprecated; + b = bbb.item.deprecated; if (a !== b) { return a - b; } @@ -943,7 +1069,7 @@ function initSearch(rawSearchIndex) { nameSplit = hasPath ? null : parsedQuery.elems[0].path; } - for (const result of results) { + for (const result of result_list) { // this validation does not make sense when searching by types if (result.dontValidate) { continue; @@ -956,72 +1082,87 @@ function initSearch(rawSearchIndex) { result.id = -1; } } - return transformResults(results); + return transformResults(result_list); } /** * This function checks if the object (`row`) generics match the given type (`elem`) - * generics. If there are no generics on `row`, `defaultLev` is returned. + * generics. If there are no generics on `row`, `defaultDistance` is returned. * - * @param {Row} row - The object to check. - * @param {QueryElement} elem - The element from the parsed query. - * @param {integer} defaultLev - This is the value to return in case there are no generics. + * @param {Row} row - The object to check. + * @param {QueryElement} elem - The element from the parsed query. + * @param {integer} defaultDistance - This is the value to return in case there are no + * generics. * - * @return {integer} - Returns the best match (if any) or `maxLevDistance + 1`. + * @return {integer} - Returns the best match (if any) or `maxEditDistance + 1`. */ - function checkGenerics(row, elem, defaultLev, maxLevDistance) { + function checkGenerics(row, elem, defaultDistance, maxEditDistance) { if (row.generics.length === 0) { - return elem.generics.length === 0 ? defaultLev : maxLevDistance + 1; + return elem.generics.length === 0 ? defaultDistance : maxEditDistance + 1; } else if (row.generics.length > 0 && row.generics[0].name === null) { - return checkGenerics(row.generics[0], elem, defaultLev, maxLevDistance); + return checkGenerics(row.generics[0], elem, defaultDistance, maxEditDistance); } // The names match, but we need to be sure that all generics kinda // match as well. - let elem_name; if (elem.generics.length > 0 && row.generics.length >= elem.generics.length) { - const elems = Object.create(null); + const elems = new Map(); for (const entry of row.generics) { - elem_name = entry.name; - if (elem_name === "") { + if (entry.name === "") { // Pure generic, needs to check into it. - if (checkGenerics(entry, elem, maxLevDistance + 1, maxLevDistance) !== 0) { - return maxLevDistance + 1; + if (checkGenerics(entry, elem, maxEditDistance + 1, maxEditDistance) + !== 0) { + return maxEditDistance + 1; } continue; } - if (elems[elem_name] === undefined) { - elems[elem_name] = 0; + let currentEntryElems; + if (elems.has(entry.name)) { + currentEntryElems = elems.get(entry.name); + } else { + currentEntryElems = []; + elems.set(entry.name, currentEntryElems); } - elems[elem_name] += 1; + currentEntryElems.push(entry); } // We need to find the type that matches the most to remove it in order // to move forward. - for (const generic of elem.generics) { - let match = null; - if (elems[generic.name]) { - match = generic.name; - } else { - for (elem_name in elems) { - if (!hasOwnPropertyRustdoc(elems, elem_name)) { - continue; - } - if (elem_name === generic) { - match = elem_name; - break; - } + const handleGeneric = generic => { + if (!elems.has(generic.name)) { + return false; + } + const matchElems = elems.get(generic.name); + const matchIdx = matchElems.findIndex(tmp_elem => { + if (checkGenerics(tmp_elem, generic, 0, maxEditDistance) !== 0) { + return false; } + return typePassesFilter(generic.typeFilter, tmp_elem.ty); + }); + if (matchIdx === -1) { + return false; + } + matchElems.splice(matchIdx, 1); + if (matchElems.length === 0) { + elems.delete(generic.name); } - if (match === null) { - return maxLevDistance + 1; + return true; + }; + // To do the right thing with type filters, we first process generics + // that have them, removing matching ones from the "bag," then do the + // ones with no type filter, which can match any entry regardless of its + // own type. + for (const generic of elem.generics) { + if (generic.typeFilter !== -1 && !handleGeneric(generic)) { + return maxEditDistance + 1; } - elems[match] -= 1; - if (elems[match] === 0) { - delete elems[match]; + } + for (const generic of elem.generics) { + if (generic.typeFilter === -1 && !handleGeneric(generic)) { + return maxEditDistance + 1; } } return 0; } - return maxLevDistance + 1; + return maxEditDistance + 1; } /** @@ -1031,17 +1172,17 @@ function initSearch(rawSearchIndex) { * @param {Row} row * @param {QueryElement} elem - The element from the parsed query. * - * @return {integer} - Returns a Levenshtein distance to the best match. + * @return {integer} - Returns an edit distance to the best match. */ - function checkIfInGenerics(row, elem, maxLevDistance) { - let lev = maxLevDistance + 1; + function checkIfInGenerics(row, elem, maxEditDistance) { + let dist = maxEditDistance + 1; for (const entry of row.generics) { - lev = Math.min(checkType(entry, elem, true, maxLevDistance), lev); - if (lev === 0) { + dist = Math.min(checkType(entry, elem, true, maxEditDistance), dist); + if (dist === 0) { break; } } - return lev; + return dist; } /** @@ -1052,67 +1193,73 @@ function initSearch(rawSearchIndex) { * @param {QueryElement} elem - The element from the parsed query. * @param {boolean} literalSearch * - * @return {integer} - Returns a Levenshtein distance to the best match. If there is - * no match, returns `maxLevDistance + 1`. + * @return {integer} - Returns an edit distance to the best match. If there is + * no match, returns `maxEditDistance + 1`. */ - function checkType(row, elem, literalSearch, maxLevDistance) { + function checkType(row, elem, literalSearch, maxEditDistance) { if (row.name === null) { // This is a pure "generic" search, no need to run other checks. if (row.generics.length > 0) { - return checkIfInGenerics(row, elem, maxLevDistance); + return checkIfInGenerics(row, elem, maxEditDistance); } - return maxLevDistance + 1; + return maxEditDistance + 1; } - let lev = levenshtein(row.name, elem.name); + let dist; + if (typePassesFilter(elem.typeFilter, row.ty)) { + dist = editDistance(row.name, elem.name, maxEditDistance); + } else { + dist = maxEditDistance + 1; + } if (literalSearch) { - if (lev !== 0) { + if (dist !== 0) { // The name didn't match, let's try to check if the generics do. if (elem.generics.length === 0) { const checkGeneric = row.generics.length > 0; if (checkGeneric && row.generics - .findIndex(tmp_elem => tmp_elem.name === elem.name) !== -1) { + .findIndex(tmp_elem => tmp_elem.name === elem.name && + typePassesFilter(elem.typeFilter, tmp_elem.ty)) !== -1) { return 0; } } - return maxLevDistance + 1; + return maxEditDistance + 1; } else if (elem.generics.length > 0) { - return checkGenerics(row, elem, maxLevDistance + 1, maxLevDistance); + return checkGenerics(row, elem, maxEditDistance + 1, maxEditDistance); } return 0; } else if (row.generics.length > 0) { if (elem.generics.length === 0) { - if (lev === 0) { + if (dist === 0) { return 0; } // The name didn't match so we now check if the type we're looking for is inside // the generics! - lev = Math.min(lev, checkIfInGenerics(row, elem, maxLevDistance)); - return lev; - } else if (lev > maxLevDistance) { + dist = Math.min(dist, checkIfInGenerics(row, elem, maxEditDistance)); + return dist; + } else if (dist > maxEditDistance) { // So our item's name doesn't match at all and has generics. // // Maybe it's present in a sub generic? For example "f>>()", if we're // looking for "B", we'll need to go down. - return checkIfInGenerics(row, elem, maxLevDistance); + return checkIfInGenerics(row, elem, maxEditDistance); } else { // At this point, the name kinda match and we have generics to check, so // let's go! - const tmp_lev = checkGenerics(row, elem, lev, maxLevDistance); - if (tmp_lev > maxLevDistance) { - return maxLevDistance + 1; + const tmp_dist = checkGenerics(row, elem, dist, maxEditDistance); + if (tmp_dist > maxEditDistance) { + return maxEditDistance + 1; } // We compute the median value of both checks and return it. - return (tmp_lev + lev) / 2; + return (tmp_dist + dist) / 2; } } else if (elem.generics.length > 0) { // In this case, we were expecting generics but there isn't so we simply reject this // one. - return maxLevDistance + 1; + return maxEditDistance + 1; } // No generics on our query or on the target type so we can return without doing // anything else. - return lev; + return dist; } /** @@ -1120,29 +1267,42 @@ function initSearch(rawSearchIndex) { * * @param {Row} row * @param {QueryElement} elem - The element from the parsed query. - * @param {integer} typeFilter + * @param {integer} maxEditDistance + * @param {Array} skipPositions - Do not return one of these positions. * - * @return {integer} - Returns a Levenshtein distance to the best match. If there is no - * match, returns `maxLevDistance + 1`. + * @return {dist: integer, position: integer} - Returns an edit distance to the best match. + * If there is no match, returns + * `maxEditDistance + 1` and position: -1. */ - function findArg(row, elem, typeFilter, maxLevDistance) { - let lev = maxLevDistance + 1; + function findArg(row, elem, maxEditDistance, skipPositions) { + let dist = maxEditDistance + 1; + let position = -1; if (row && row.type && row.type.inputs && row.type.inputs.length > 0) { + let i = 0; for (const input of row.type.inputs) { - if (!typePassesFilter(typeFilter, input.ty)) { + if (skipPositions.indexOf(i) !== -1) { + i += 1; continue; } - lev = Math.min( - lev, - checkType(input, elem, parsedQuery.literalSearch, maxLevDistance) + const typeDist = checkType( + input, + elem, + parsedQuery.literalSearch, + maxEditDistance ); - if (lev === 0) { - return 0; + if (typeDist === 0) { + return {dist: 0, position: i}; } + if (typeDist < dist) { + dist = typeDist; + position = i; + } + i += 1; } } - return parsedQuery.literalSearch ? maxLevDistance + 1 : lev; + dist = parsedQuery.literalSearch ? maxEditDistance + 1 : dist; + return {dist, position}; } /** @@ -1150,37 +1310,50 @@ function initSearch(rawSearchIndex) { * * @param {Row} row * @param {QueryElement} elem - The element from the parsed query. - * @param {integer} typeFilter + * @param {integer} maxEditDistance + * @param {Array} skipPositions - Do not return one of these positions. * - * @return {integer} - Returns a Levenshtein distance to the best match. If there is no - * match, returns `maxLevDistance + 1`. + * @return {dist: integer, position: integer} - Returns an edit distance to the best match. + * If there is no match, returns + * `maxEditDistance + 1` and position: -1. */ - function checkReturned(row, elem, typeFilter, maxLevDistance) { - let lev = maxLevDistance + 1; + function checkReturned(row, elem, maxEditDistance, skipPositions) { + let dist = maxEditDistance + 1; + let position = -1; if (row && row.type && row.type.output.length > 0) { const ret = row.type.output; + let i = 0; for (const ret_ty of ret) { - if (!typePassesFilter(typeFilter, ret_ty.ty)) { + if (skipPositions.indexOf(i) !== -1) { + i += 1; continue; } - lev = Math.min( - lev, - checkType(ret_ty, elem, parsedQuery.literalSearch, maxLevDistance) + const typeDist = checkType( + ret_ty, + elem, + parsedQuery.literalSearch, + maxEditDistance ); - if (lev === 0) { - return 0; + if (typeDist === 0) { + return {dist: 0, position: i}; } + if (typeDist < dist) { + dist = typeDist; + position = i; + } + i += 1; } } - return parsedQuery.literalSearch ? maxLevDistance + 1 : lev; + dist = parsedQuery.literalSearch ? maxEditDistance + 1 : dist; + return {dist, position}; } - function checkPath(contains, ty, maxLevDistance) { + function checkPath(contains, ty, maxEditDistance) { if (contains.length === 0) { return 0; } - let ret_lev = maxLevDistance + 1; + let ret_dist = maxEditDistance + 1; const path = ty.path.split("::"); if (ty.parent && ty.parent.name) { @@ -1190,27 +1363,27 @@ function initSearch(rawSearchIndex) { const length = path.length; const clength = contains.length; if (clength > length) { - return maxLevDistance + 1; + return maxEditDistance + 1; } for (let i = 0; i < length; ++i) { if (i + clength > length) { break; } - let lev_total = 0; + let dist_total = 0; let aborted = false; for (let x = 0; x < clength; ++x) { - const lev = levenshtein(path[i + x], contains[x]); - if (lev > maxLevDistance) { + const dist = editDistance(path[i + x], contains[x], maxEditDistance); + if (dist > maxEditDistance) { aborted = true; break; } - lev_total += lev; + dist_total += dist; } if (!aborted) { - ret_lev = Math.min(ret_lev, Math.round(lev_total / clength)); + ret_dist = Math.min(ret_dist, Math.round(dist_total / clength)); } } - return ret_lev; + return ret_dist; } function typePassesFilter(filter, type) { @@ -1244,6 +1417,7 @@ function initSearch(rawSearchIndex) { parent: item.parent, type: item.type, is_alias: true, + deprecated: item.deprecated, }; } @@ -1254,22 +1428,22 @@ function initSearch(rawSearchIndex) { const aliases = []; const crateAliases = []; if (filterCrates !== null) { - if (ALIASES[filterCrates] && ALIASES[filterCrates][lowerQuery]) { - const query_aliases = ALIASES[filterCrates][lowerQuery]; + if (ALIASES.has(filterCrates) && ALIASES.get(filterCrates).has(lowerQuery)) { + const query_aliases = ALIASES.get(filterCrates).get(lowerQuery); for (const alias of query_aliases) { aliases.push(createAliasFromItem(searchIndex[alias])); } } } else { - Object.keys(ALIASES).forEach(crate => { - if (ALIASES[crate][lowerQuery]) { + for (const [crate, crateAliasesIndex] of ALIASES) { + if (crateAliasesIndex.has(lowerQuery)) { const pushTo = crate === currentCrate ? crateAliases : aliases; - const query_aliases = ALIASES[crate][lowerQuery]; + const query_aliases = crateAliasesIndex.get(lowerQuery); for (const alias of query_aliases) { pushTo.push(createAliasFromItem(searchIndex[alias])); } } - }); + } } const sortFunc = (aaa, bbb) => { @@ -1304,41 +1478,41 @@ function initSearch(rawSearchIndex) { * This function adds the given result into the provided `results` map if it matches the * following condition: * - * * If it is a "literal search" (`parsedQuery.literalSearch`), then `lev` must be 0. - * * If it is not a "literal search", `lev` must be <= `maxLevDistance`. + * * If it is a "literal search" (`parsedQuery.literalSearch`), then `dist` must be 0. + * * If it is not a "literal search", `dist` must be <= `maxEditDistance`. * * The `results` map contains information which will be used to sort the search results: * * * `fullId` is a `string`` used as the key of the object we use for the `results` map. * * `id` is the index in both `searchWords` and `searchIndex` arrays for this element. * * `index` is an `integer`` used to sort by the position of the word in the item's name. - * * `lev` is the main metric used to sort the search results. - * * `path_lev` is zero if a single-component search query is used, otherwise it's the + * * `dist` is the main metric used to sort the search results. + * * `path_dist` is zero if a single-component search query is used, otherwise it's the * distance computed for everything other than the last path component. * * @param {Results} results * @param {string} fullId * @param {integer} id * @param {integer} index - * @param {integer} lev - * @param {integer} path_lev + * @param {integer} dist + * @param {integer} path_dist */ - function addIntoResults(results, fullId, id, index, lev, path_lev, maxLevDistance) { - const inBounds = lev <= maxLevDistance || index !== -1; - if (lev === 0 || (!parsedQuery.literalSearch && inBounds)) { - if (results[fullId] !== undefined) { - const result = results[fullId]; - if (result.dontValidate || result.lev <= lev) { + function addIntoResults(results, fullId, id, index, dist, path_dist, maxEditDistance) { + const inBounds = dist <= maxEditDistance || index !== -1; + if (dist === 0 || (!parsedQuery.literalSearch && inBounds)) { + if (results.has(fullId)) { + const result = results.get(fullId); + if (result.dontValidate || result.dist <= dist) { return; } } - results[fullId] = { + results.set(fullId, { id: id, index: index, dontValidate: parsedQuery.literalSearch, - lev: lev, - path_lev: path_lev, - }; + dist: dist, + path_dist: path_dist, + }); } } @@ -1346,7 +1520,7 @@ function initSearch(rawSearchIndex) { * This function is called in case the query is only one element (with or without generics). * This element will be compared to arguments' and returned values' items and also to items. * - * Other important thing to note: since there is only one element, we use levenshtein + * Other important thing to note: since there is only one element, we use edit * distance for name comparisons. * * @param {Row} row @@ -1364,24 +1538,24 @@ function initSearch(rawSearchIndex) { results_others, results_in_args, results_returned, - maxLevDistance + maxEditDistance ) { if (!row || (filterCrates !== null && row.crate !== filterCrates)) { return; } - let lev, index = -1, path_lev = 0; + let dist, index = -1, path_dist = 0; const fullId = row.id; const searchWord = searchWords[pos]; - const in_args = findArg(row, elem, parsedQuery.typeFilter, maxLevDistance); - const returned = checkReturned(row, elem, parsedQuery.typeFilter, maxLevDistance); + const in_args = findArg(row, elem, maxEditDistance, []); + const returned = checkReturned(row, elem, maxEditDistance, []); - // path_lev is 0 because no parent path information is currently stored + // path_dist is 0 because no parent path information is currently stored // in the search index - addIntoResults(results_in_args, fullId, pos, -1, in_args, 0, maxLevDistance); - addIntoResults(results_returned, fullId, pos, -1, returned, 0, maxLevDistance); + addIntoResults(results_in_args, fullId, pos, -1, in_args.dist, 0, maxEditDistance); + addIntoResults(results_returned, fullId, pos, -1, returned.dist, 0, maxEditDistance); - if (!typePassesFilter(parsedQuery.typeFilter, row.ty)) { + if (!typePassesFilter(elem.typeFilter, row.ty)) { return; } @@ -1403,34 +1577,34 @@ function initSearch(rawSearchIndex) { // No need to check anything else if it's a "pure" generics search. if (elem.name.length === 0) { if (row.type !== null) { - lev = checkGenerics(row.type, elem, maxLevDistance + 1, maxLevDistance); - // path_lev is 0 because we know it's empty - addIntoResults(results_others, fullId, pos, index, lev, 0, maxLevDistance); + dist = checkGenerics(row.type, elem, maxEditDistance + 1, maxEditDistance); + // path_dist is 0 because we know it's empty + addIntoResults(results_others, fullId, pos, index, dist, 0, maxEditDistance); } return; } if (elem.fullPath.length > 1) { - path_lev = checkPath(elem.pathWithoutLast, row, maxLevDistance); - if (path_lev > maxLevDistance) { + path_dist = checkPath(elem.pathWithoutLast, row, maxEditDistance); + if (path_dist > maxEditDistance) { return; } } if (parsedQuery.literalSearch) { if (searchWord === elem.name) { - addIntoResults(results_others, fullId, pos, index, 0, path_lev); + addIntoResults(results_others, fullId, pos, index, 0, path_dist); } return; } - lev = levenshtein(searchWord, elem.pathLast); + dist = editDistance(searchWord, elem.pathLast, maxEditDistance); - if (index === -1 && lev + path_lev > maxLevDistance) { + if (index === -1 && dist + path_dist > maxEditDistance) { return; } - addIntoResults(results_others, fullId, pos, index, lev, path_lev, maxLevDistance); + addIntoResults(results_others, fullId, pos, index, dist, path_dist, maxEditDistance); } /** @@ -1442,22 +1616,29 @@ function initSearch(rawSearchIndex) { * @param {integer} pos - Position in the `searchIndex`. * @param {Object} results */ - function handleArgs(row, pos, results, maxLevDistance) { + function handleArgs(row, pos, results, maxEditDistance) { if (!row || (filterCrates !== null && row.crate !== filterCrates)) { return; } - let totalLev = 0; - let nbLev = 0; + let totalDist = 0; + let nbDist = 0; // If the result is too "bad", we return false and it ends this search. function checkArgs(elems, callback) { + const skipPositions = []; for (const elem of elems) { // There is more than one parameter to the query so all checks should be "exact" - const lev = callback(row, elem, NO_TYPE_FILTER, maxLevDistance); - if (lev <= 1) { - nbLev += 1; - totalLev += lev; + const { dist, position } = callback( + row, + elem, + maxEditDistance, + skipPositions + ); + if (dist <= 1) { + nbDist += 1; + totalDist += dist; + skipPositions.push(position); } else { return false; } @@ -1471,11 +1652,11 @@ function initSearch(rawSearchIndex) { return; } - if (nbLev === 0) { + if (nbDist === 0) { return; } - const lev = Math.round(totalLev / nbLev); - addIntoResults(results, row.id, pos, 0, lev, 0, maxLevDistance); + const dist = Math.round(totalDist / nbDist); + addIntoResults(results, row.id, pos, 0, dist, 0, maxEditDistance); } function innerRunQuery() { @@ -1488,7 +1669,7 @@ function initSearch(rawSearchIndex) { for (const elem of parsedQuery.returned) { queryLen += elem.name.length; } - const maxLevDistance = Math.floor(queryLen / 3); + const maxEditDistance = Math.floor(queryLen / 3); if (parsedQuery.foundElems === 1) { if (parsedQuery.elems.length === 1) { @@ -1503,7 +1684,7 @@ function initSearch(rawSearchIndex) { results_others, results_in_args, results_returned, - maxLevDistance + maxEditDistance ); } } else if (parsedQuery.returned.length === 1) { @@ -1514,15 +1695,22 @@ function initSearch(rawSearchIndex) { in_returned = checkReturned( row, elem, - parsedQuery.typeFilter, - maxLevDistance + maxEditDistance, + [] + ); + addIntoResults( + results_others, + row.id, + i, + -1, + in_returned.dist, + maxEditDistance ); - addIntoResults(results_others, row.id, i, -1, in_returned, maxLevDistance); } } } else if (parsedQuery.foundElems > 0) { for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) { - handleArgs(searchIndex[i], i, results_others, maxLevDistance); + handleArgs(searchIndex[i], i, results_others, maxEditDistance); } } } @@ -1560,7 +1748,7 @@ function initSearch(rawSearchIndex) { * * @return {boolean} - Whether the result is valid or not */ - function validateResult(name, path, keys, parent, maxLevDistance) { + function validateResult(name, path, keys, parent, maxEditDistance) { if (!keys || !keys.length) { return true; } @@ -1574,8 +1762,8 @@ function initSearch(rawSearchIndex) { // next if there is a parent, check for exact parent match (parent !== undefined && parent.name !== undefined && parent.name.toLowerCase().indexOf(key) > -1) || - // lastly check to see if the name was a levenshtein match - levenshtein(name, key) <= maxLevDistance)) { + // lastly check to see if the name was an editDistance match + editDistance(name, key, maxEditDistance) <= maxEditDistance)) { return false; } } @@ -1762,11 +1950,7 @@ function initSearch(rawSearchIndex) { function showResults(results, go_to_first, filterCrates) { const search = searchState.outputElement(); if (go_to_first || (results.others.length === 1 - && getSettingValue("go-to-only-result") === "true" - // By default, the search DOM element is "empty" (meaning it has no children not - // text content). Once a search has been run, it won't be empty, even if you press - // ESC or empty the search input (which also "cancels" the search). - && (!search.firstChild || search.firstChild.innerText !== searchState.loadingText)) + && getSettingValue("go-to-only-result") === "true") ) { const elem = document.createElement("a"); elem.href = results.others[0].href; @@ -2064,10 +2248,11 @@ function initSearch(rawSearchIndex) { * n: Array, * t: String, * d: Array, - * q: Array, + * q: Array<[Number, string]>, * i: Array, * f: Array, * p: Array, + * c: Array * }} */ const crateCorpus = rawSearchIndex[crate]; @@ -2086,6 +2271,7 @@ function initSearch(rawSearchIndex) { type: null, id: id, normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""), + deprecated: null, }; id += 1; searchIndex.push(crateRow); @@ -2095,14 +2281,20 @@ function initSearch(rawSearchIndex) { const itemTypes = crateCorpus.t; // an array of (String) item names const itemNames = crateCorpus.n; - // an array of (String) full paths (or empty string for previous path) - const itemPaths = crateCorpus.q; + // an array of [(Number) item index, + // (String) full path] + // an item whose index is not present will fall back to the previous present path + // i.e. if indices 4 and 11 are present, but 5-10 and 12-13 are not present, + // 5-10 will fall back to the path for 4 and 12-13 will fall back to the path for 11 + const itemPaths = new Map(crateCorpus.q); // an array of (String) descriptions const itemDescs = crateCorpus.d; // an array of (Number) the parent path index + 1 to `paths`, or 0 if none const itemParentIdxs = crateCorpus.i; // an array of (Object | null) the type of the function, if any const itemFunctionSearchTypes = crateCorpus.f; + // an array of (Number) indices for the deprecated items + const deprecatedItems = new Set(crateCorpus.c); // an array of [(Number) item type, // (String) name] const paths = crateCorpus.p; @@ -2142,12 +2334,13 @@ function initSearch(rawSearchIndex) { crate: crate, ty: itemTypes.charCodeAt(i) - charA, name: itemNames[i], - path: itemPaths[i] ? itemPaths[i] : lastPath, + path: itemPaths.has(i) ? itemPaths.get(i) : lastPath, desc: itemDescs[i], parent: itemParentIdxs[i] > 0 ? paths[itemParentIdxs[i] - 1] : undefined, type: buildFunctionSearchType(itemFunctionSearchTypes[i], lowercasePaths), id: id, normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""), + deprecated: deprecatedItems.has(i), }; id += 1; searchIndex.push(row); @@ -2156,17 +2349,22 @@ function initSearch(rawSearchIndex) { } if (aliases) { - ALIASES[crate] = Object.create(null); + const currentCrateAliases = new Map(); + ALIASES.set(crate, currentCrateAliases); for (const alias_name in aliases) { if (!hasOwnPropertyRustdoc(aliases, alias_name)) { continue; } - if (!hasOwnPropertyRustdoc(ALIASES[crate], alias_name)) { - ALIASES[crate][alias_name] = []; + let currentNameAliases; + if (currentCrateAliases.has(alias_name)) { + currentNameAliases = currentCrateAliases.get(alias_name); + } else { + currentNameAliases = []; + currentCrateAliases.set(alias_name, currentNameAliases); } for (const local_alias of aliases[alias_name]) { - ALIASES[crate][alias_name].push(local_alias + currentIndex); + currentNameAliases.push(local_alias + currentIndex); } } } -- cgit v1.2.3