Google Git
Sign in
fuchsia/third_party/rust/5a2fceefd312ec027bdeaa89ebefbe4c33d94de1/./src/librustdoc/html/static/js/search.js
blob: d55208150b84315d2f834678c0eaf3f19fddfee9 [file]
// ignore-tidy-filelength
/* global addClass, getNakedUrl, getVar, nonnull, getSettingValue */
/* global onEachLazy, removeClass, searchState, browserSupportsHistoryApi */
"use strict";
/**
* @param {stringdex.Stringdex} Stringdex
* @param {typeof stringdex.RoaringBitmap} RoaringBitmap
* @param {stringdex.Hooks} hooks
*/
const initSearch = async function(Stringdex, RoaringBitmap, hooks) {
// polyfill
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/toSpliced
if (!Array.prototype.toSpliced) {
// Can't use arrow functions, because we want `this`
Array.prototype.toSpliced = function() {
const me = this.slice();
// @ts-expect-error
Array.prototype.splice.apply(me, arguments);
return me;
};
}
/**
*
* @template T
* @param {Iterable<T>} arr
* @param {function(T): Promise<any>} func
* @param {function(T): boolean} funcBtwn
*/
async function onEachBtwnAsync(arr, func, funcBtwn) {
let skipped = true;
for (const value of arr) {
if (!skipped) {
funcBtwn(value);
}
skipped = await func(value);
}
}
/**
* Allow the browser to redraw.
* @returns {Promise<void>}
*/
const yieldToBrowser = typeof window !== "undefined" && window.requestIdleCallback ?
function() {
return new Promise((resolve, _reject) => {
window.requestIdleCallback(resolve);
});
} :
function() {
return new Promise((resolve, _reject) => {
setTimeout(resolve, 0);
});
};
/**
* Promise-based timer wrapper.
* @param {number} ms
* @returns {Promise<void>}
*/
const timeout = function(ms) {
return new Promise((resolve, _reject) => {
setTimeout(resolve, ms);
});
};
if (!Promise.withResolvers) {
/**
* Polyfill
* @template T
* @returns {{
"promise": Promise<T>,
"resolve": (function(T): void),
"reject": (function(any): void)
}}
*/
Promise.withResolvers = () => {
let resolve, reject;
const promise = new Promise((res, rej) => {
resolve = res;
reject = rej;
});
// @ts-expect-error
return {promise, resolve, reject};
};
}
// ==================== Core search logic begin ====================
// This mapping table should match the discriminants of
// `rustdoc::formats::item_type::ItemType` type in Rust.
const itemTypes = [
"keyword",
"primitive",
"mod",
"externcrate",
"import",
"struct", // 5
"enum",
"fn",
"type",
"static",
"trait", // 10
"impl",
"tymethod",
"method",
"structfield",
"variant", // 15
"macro",
"associatedtype",
"constant",
"associatedconstant",
"union", // 20
"foreigntype",
"existential",
"attr",
"derive",
"traitalias", // 25
"generic",
];
// used for special search precedence
/** @type {rustdoc.ItemType} */
const TY_PRIMITIVE = 1;
/** @type {rustdoc.ItemType} */
const TY_GENERIC = 26;
/** @type {rustdoc.ItemType} */
const TY_IMPORT = 4;
/** @type {rustdoc.ItemType} */
const TY_TRAIT = 10;
/** @type {rustdoc.ItemType} */
const TY_FN = 7;
/** @type {rustdoc.ItemType} */
const TY_METHOD = 13;
/** @type {rustdoc.ItemType} */
const TY_TYMETHOD = 12;
/** @type {rustdoc.ItemType} */
const TY_ASSOCTYPE = 17;
const ROOT_PATH = typeof window !== "undefined" ? window.rootPath : "../";
// Hard limit on how deep to recurse into generics when doing type-driven search.
// This needs limited, partially because
// a search for `Ty` shouldn't match `WithInfcx<ParamEnvAnd<Vec<ConstTy<Interner<Ty=Ty>>>>>`,
// but mostly because this is the simplest and most principled way to limit the number
// of permutations we need to check.
const UNBOXING_LIMIT = 5;
// used for search query verification
const REGEX_IDENT = /\p{ID_Start}\p{ID_Continue}*|_\p{ID_Continue}+/uy;
const REGEX_INVALID_TYPE_FILTER = /[^a-z]/ui;
const MAX_RESULTS = 200;
const NO_TYPE_FILTER = -1;
/**
* The [edit distance] is a metric for measuring the difference between two strings.
*
* [edit distance]: https://en.wikipedia.org/wiki/Edit_distance
*/
/*
* 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 = {
/**
* @type {number[]}
*/
current: [],
/**
* @type {number[]}
*/
prev: [],
/**
* @type {number[]}
*/
prevPrev: [],
/**
* @param {string} a
* @param {string} b
* @param {number} limit
* @returns
*/
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);
},
};
/**
* @param {string} a
* @param {string} b
* @param {number} limit
* @returns
*/
function editDistance(a, b, limit) {
return editDistanceState.calculate(a, b, limit);
}
/**
* @param {string} c
* @returns {boolean}
*/
function isEndCharacter(c) {
return "=,>-])".indexOf(c) !== -1;
}
/**
* Same thing as ItemType::is_fn_like in item_type.rs
*
* @param {rustdoc.ItemType} ty
* @returns
*/
function isFnLikeTy(ty) {
return ty === TY_FN || ty === TY_METHOD || ty === TY_TYMETHOD;
}
/**
* Returns `true` if the given `c` character is a separator.
*
* @param {string} c
*
* @return {boolean}
*/
function isSeparatorCharacter(c) {
return c === "," || c === "=";
}
/**
* Returns `true` if the current parser position is starting with "->".
*
* @param {rustdoc.ParserState} parserState
*
* @return {boolean}
*/
function isReturnArrow(parserState) {
return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "->";
}
/**
* Increase current parser position until it doesn't find a whitespace anymore.
*
* @param {rustdoc.ParserState} parserState
*/
function skipWhitespace(parserState) {
while (parserState.pos < parserState.userQuery.length) {
const c = parserState.userQuery[parserState.pos];
if (c !== " ") {
break;
}
parserState.pos += 1;
}
}
/**
* Returns `true` if the previous character is `lookingFor`.
*
* @param {rustdoc.ParserState} parserState
* @param {String} lookingFor
*
* @return {boolean}
*/
function prevIs(parserState, lookingFor) {
let pos = parserState.pos;
while (pos > 0) {
const c = parserState.userQuery[pos - 1];
if (c === lookingFor) {
return true;
} else if (c !== " ") {
break;
}
pos -= 1;
}
return false;
}
/**
* Returns `true` if the last element in the `elems` argument has generics.
*
* @param {Array<rustdoc.ParserQueryElement>} elems
* @param {rustdoc.ParserState} parserState
*
* @return {boolean}
*/
function isLastElemGeneric(elems, parserState) {
return (elems.length > 0 && elems[elems.length - 1].generics.length > 0) ||
prevIs(parserState, ">");
}
/**
*
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
* @param {rustdoc.ParserQueryElement[]} elems
* @param {boolean} isInGenerics
*/
function getFilteredNextElem(query, parserState, elems, isInGenerics) {
const start = parserState.pos;
if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) {
throw ["Expected type filter before ", ":"];
}
getNextElem(query, parserState, elems, isInGenerics);
if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) {
if (parserState.typeFilter !== null) {
throw [
"Unexpected ",
":",
" (expected path after type filter ",
parserState.typeFilter + ":",
")",
];
}
if (elems.length === 0) {
throw ["Expected type filter before ", ":"];
} else if (query.literalSearch) {
throw ["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);
// typeFilterElem is not undefined. If it was, the elems.length check would have fired.
// @ts-expect-error
parserState.typeFilter = typeFilterElem.normalizedPathLast;
parserState.pos += 1;
parserState.totalElems -= 1;
query.literalSearch = false;
getNextElem(query, parserState, elems, isInGenerics);
}
}
/**
* This function parses the next query element until it finds `endChar`,
* calling `getNextElem` to collect each element.
*
* If there is no `endChar`, this function will implicitly stop at the end
* without raising an error.
*
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
* @param {Array<rustdoc.ParserQueryElement>} elems
* - This is where the new {QueryElement} will be added.
* @param {string} endChar - This function will stop when it'll encounter this
* character.
* @returns {{foundSeparator: boolean}}
*/
function getItemsBefore(query, parserState, elems, endChar) {
let foundStopChar = true;
let foundSeparator = false;
// If this is a generic, keep the outer item's type filter around.
const oldTypeFilter = parserState.typeFilter;
parserState.typeFilter = null;
const oldIsInBinding = parserState.isInBinding;
parserState.isInBinding = null;
// ML-style Higher Order Function notation
//
// a way to search for any closure or fn pointer regardless of
// which closure trait is used
//
// Looks like this:
//
// `option<t>, (t -> u) -> option<u>`
// ^^^^^^
//
// The Rust-style closure notation is implemented in getNextElem
let hofParameters = null;
let extra = "";
if (endChar === ">") {
extra = "<";
} else if (endChar === "]") {
extra = "[";
} else if (endChar === ")") {
extra = "(";
} else if (endChar === "") {
extra = "->";
} else {
extra = endChar;
}
while (parserState.pos < parserState.length) {
const c = parserState.userQuery[parserState.pos];
if (c === endChar) {
if (parserState.isInBinding) {
throw ["Unexpected ", endChar, " after ", "="];
}
break;
} else if (endChar !== "" && isReturnArrow(parserState)) {
// ML-style HOF notation only works when delimited in something,
// otherwise a function arrow starts the return type of the top
if (parserState.isInBinding) {
throw ["Unexpected ", "->", " after ", "="];
}
hofParameters = [...elems];
elems.length = 0;
parserState.pos += 2;
foundStopChar = true;
foundSeparator = false;
continue;
} else if (c === " ") {
parserState.pos += 1;
continue;
} else if (isSeparatorCharacter(c)) {
parserState.pos += 1;
foundStopChar = true;
foundSeparator = true;
continue;
} else if (c === ":" && isPathStart(parserState)) {
throw ["Unexpected ", "::", ": paths cannot start with ", "::"];
} else if (isEndCharacter(c)) {
throw ["Unexpected ", c, " after ", extra];
}
if (!foundStopChar) {
/** @type {string[]} */
let extra = [];
if (isLastElemGeneric(query.elems, parserState)) {
extra = [" after ", ">"];
} else if (prevIs(parserState, "\"")) {
throw ["Cannot have more than one element if you use quotes"];
}
if (endChar !== "") {
throw [
"Expected ",
",",
", ",
"=",
", or ",
endChar,
...extra,
", found ",
c,
];
}
throw [
"Expected ",
",",
" or ",
"=",
...extra,
", found ",
c,
];
}
const posBefore = parserState.pos;
getFilteredNextElem(query, parserState, elems, endChar !== "");
if (endChar !== "" && parserState.pos >= parserState.length) {
throw ["Unclosed ", extra];
}
// 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 the current position to continue the parsing.
if (posBefore === parserState.pos) {
parserState.pos += 1;
}
foundStopChar = false;
}
if (parserState.pos >= parserState.length && endChar !== "") {
throw ["Unclosed ", extra];
}
// We are either at the end of the string or on the `endChar` character, let's move
// forward in any case.
parserState.pos += 1;
if (hofParameters) {
// Commas in a HOF don't cause wrapping parens to become a tuple.
// If you want a one-tuple with a HOF in it, write `((a -> b),)`.
foundSeparator = false;
// HOFs can't have directly nested bindings.
if ([...elems, ...hofParameters].some(x => x.bindingName)
|| parserState.isInBinding) {
throw ["Unexpected ", "=", " within ", "->"];
}
// HOFs are represented the same way closures are.
// The arguments are wrapped in a tuple, and the output
// is a binding, even though the compiler doesn't technically
// represent fn pointers that way.
const hofElem = makePrimitiveElement("->", {
generics: hofParameters,
bindings: new Map([["output", [...elems]]]),
typeFilter: null,
});
elems.length = 0;
elems[0] = hofElem;
}
parserState.typeFilter = oldTypeFilter;
parserState.isInBinding = oldIsInBinding;
return { foundSeparator };
}
/**
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
* @param {Array<rustdoc.ParserQueryElement>} elems
* - This is where the new {QueryElement} will be added.
* @param {boolean} isInGenerics
*/
function getNextElem(query, parserState, elems, isInGenerics) {
/** @type {rustdoc.ParserQueryElement[]} */
const generics = [];
skipWhitespace(parserState);
let start = parserState.pos;
let end;
if ("[(".indexOf(parserState.userQuery[parserState.pos]) !== -1) {
let endChar = ")";
let name = "()";
let friendlyName = "tuple";
if (parserState.userQuery[parserState.pos] === "[") {
endChar = "]";
name = "[]";
friendlyName = "slice";
}
parserState.pos += 1;
const { foundSeparator } = getItemsBefore(query, parserState, generics, endChar);
const typeFilter = parserState.typeFilter;
const bindingName = parserState.isInBinding;
parserState.typeFilter = null;
parserState.isInBinding = null;
for (const gen of generics) {
if (gen.bindingName !== null) {
throw ["Type parameter ", "=", ` cannot be within ${friendlyName} `, name];
}
}
if (name === "()" && !foundSeparator && generics.length === 1
&& typeFilter === null) {
elems.push(generics[0]);
} else if (name === "()" && generics.length === 1 && generics[0].name === "->") {
// `primitive:(a -> b)` parser to `primitive:"->"<output=b, (a,)>`
// not `primitive:"()"<"->"<output=b, (a,)>>`
generics[0].typeFilter = typeFilter;
elems.push(generics[0]);
} else {
if (typeFilter !== null && typeFilter !== "primitive") {
throw [
"Invalid search type: primitive ",
name,
" and ",
typeFilter,
" both specified",
];
}
parserState.totalElems += 1;
if (isInGenerics) {
parserState.genericsElems += 1;
}
elems.push(makePrimitiveElement(name, { bindingName, generics }));
}
} else if (parserState.userQuery[parserState.pos] === "&") {
if (parserState.typeFilter !== null && parserState.typeFilter !== "primitive") {
throw [
"Invalid search type: primitive ",
"&",
" and ",
parserState.typeFilter,
" both specified",
];
}
parserState.typeFilter = null;
parserState.pos += 1;
let c = parserState.userQuery[parserState.pos];
while (c === " " && parserState.pos < parserState.length) {
parserState.pos += 1;
c = parserState.userQuery[parserState.pos];
}
const generics = [];
if (parserState.userQuery.slice(parserState.pos, parserState.pos + 3) === "mut") {
generics.push(makePrimitiveElement("mut", { typeFilter: "keyword" }));
parserState.pos += 3;
c = parserState.userQuery[parserState.pos];
}
while (c === " " && parserState.pos < parserState.length) {
parserState.pos += 1;
c = parserState.userQuery[parserState.pos];
}
if (!isEndCharacter(c) && parserState.pos < parserState.length) {
getFilteredNextElem(query, parserState, generics, isInGenerics);
}
elems.push(makePrimitiveElement("reference", { generics }));
} else {
const isStringElem = parserState.userQuery[start] === "\"";
// We handle the strings on their own mostly to make code easier to follow.
if (isStringElem) {
start += 1;
getStringElem(query, parserState, isInGenerics);
end = parserState.pos - 1;
} else {
end = getIdentEndPosition(parserState);
}
if (parserState.pos < parserState.length &&
parserState.userQuery[parserState.pos] === "<"
) {
if (start >= end) {
throw ["Found generics without a path"];
}
parserState.pos += 1;
getItemsBefore(query, parserState, generics, ">");
} else if (parserState.pos < parserState.length &&
parserState.userQuery[parserState.pos] === "("
) {
if (start >= end) {
throw ["Found generics without a path"];
}
if (parserState.isInBinding) {
throw ["Unexpected ", "(", " after ", "="];
}
parserState.pos += 1;
const typeFilter = parserState.typeFilter;
parserState.typeFilter = null;
getItemsBefore(query, parserState, generics, ")");
skipWhitespace(parserState);
if (isReturnArrow(parserState)) {
parserState.pos += 2;
skipWhitespace(parserState);
getFilteredNextElem(query, parserState, generics, isInGenerics);
generics[generics.length - 1].bindingName = makePrimitiveElement("output");
} else {
generics.push(makePrimitiveElement(null, {
bindingName: makePrimitiveElement("output"),
typeFilter: null,
}));
}
parserState.typeFilter = typeFilter;
}
if (isStringElem) {
skipWhitespace(parserState);
}
if (start >= end && generics.length === 0) {
return;
}
if (parserState.userQuery[parserState.pos] === "=") {
if (parserState.isInBinding) {
throw ["Cannot write ", "=", " twice in a binding"];
}
if (!isInGenerics) {
throw ["Type parameter ", "=", " must be within generics list"];
}
const name = parserState.userQuery.slice(start, end).trim();
if (name === "!") {
throw ["Type parameter ", "=", " key cannot be ", "!", " never type"];
}
if (name.includes("!")) {
throw ["Type parameter ", "=", " key cannot be ", "!", " macro"];
}
if (name.includes("::")) {
throw ["Type parameter ", "=", " key cannot contain ", "::", " path"];
}
if (name.includes(":")) {
throw ["Type parameter ", "=", " key cannot contain ", ":", " type"];
}
parserState.isInBinding = { name, generics };
} else {
elems.push(
createQueryElement(
query,
parserState,
parserState.userQuery.slice(start, end),
generics,
isInGenerics,
),
);
}
}
}
/**
* Checks that the type filter doesn't have unwanted characters like `<>` (which are ignored
* if empty).
*
* @param {number} start
* @param {rustdoc.ParserState} parserState
*/
function checkExtraTypeFilterCharacters(start, parserState) {
const query = parserState.userQuery.slice(start, parserState.pos).trim();
const match = query.match(REGEX_INVALID_TYPE_FILTER);
if (match) {
throw [
"Unexpected ",
match[0],
" in type filter (before ",
":",
")",
];
}
}
/**
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
* @param {string} name - Name of the query element.
* @param {Array<rustdoc.ParserQueryElement>} generics - List of generics of this query element.
* @param {boolean} isInGenerics
*
* @return {rustdoc.ParserQueryElement} - The newly created `QueryElement`.
*/
function createQueryElement(query, parserState, name, generics, isInGenerics) {
const path = name.trim();
if (path.length === 0 && generics.length === 0) {
throw ["Unexpected ", parserState.userQuery[parserState.pos]];
}
if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) {
throw ["Cannot have more than one element if you use quotes"];
}
const typeFilter = parserState.typeFilter;
parserState.typeFilter = null;
if (name.trim() === "!") {
if (typeFilter !== null && typeFilter !== "primitive") {
throw [
"Invalid search type: primitive never type ",
"!",
" and ",
typeFilter,
" both specified",
];
}
if (generics.length !== 0) {
throw [
"Never type ",
"!",
" does not accept generic parameters",
];
}
const bindingName = parserState.isInBinding;
parserState.isInBinding = null;
return makePrimitiveElement("never", { bindingName });
}
const quadcolon = /::\s*::/.exec(path);
if (path.startsWith("::")) {
throw ["Paths cannot start with ", "::"];
} else if (quadcolon !== null) {
throw ["Unexpected ", quadcolon[0]];
}
const pathSegments = path.split(/(?:::\s*)|(?:\s+(?:::\s*)?)/).map(x => x.toLowerCase());
// In case we only have something like `<p>`, there is no name.
if (pathSegments.length === 0
|| (pathSegments.length === 1 && pathSegments[0] === "")) {
if (generics.length > 0 || prevIs(parserState, ">")) {
throw ["Found generics without a path"];
} else {
throw ["Unexpected ", parserState.userQuery[parserState.pos]];
}
}
for (const [i, pathSegment] of pathSegments.entries()) {
if (pathSegment === "!") {
if (i !== 0) {
throw ["Never type ", "!", " is not associated item"];
}
pathSegments[i] = "never";
}
}
parserState.totalElems += 1;
if (isInGenerics) {
parserState.genericsElems += 1;
}
const bindingName = parserState.isInBinding;
parserState.isInBinding = null;
const bindings = new Map();
const pathLast = pathSegments[pathSegments.length - 1];
return {
name: name.trim(),
id: null,
fullPath: pathSegments,
pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1),
pathLast,
normalizedPathLast: pathLast.replace(/_/g, ""),
generics: generics.filter(gen => {
// Syntactically, bindings are parsed as generics,
// but the query engine treats them differently.
if (gen.bindingName !== null && gen.bindingName.name !== null) {
if (gen.name !== null) {
gen.bindingName.generics.unshift(gen);
}
bindings.set(
gen.bindingName.name.toLowerCase().replace(/_/g, ""),
gen.bindingName.generics,
);
return false;
}
return true;
}),
bindings,
typeFilter,
bindingName,
};
}
/**
*
* @param {string|null} name
* @param {rustdoc.ParserQueryElementFields=} extra
* @returns {rustdoc.ParserQueryElement}
*/
function makePrimitiveElement(name, extra) {
return Object.assign({
name,
id: null,
fullPath: [name],
pathWithoutLast: [],
pathLast: name,
normalizedPathLast: name,
generics: [],
bindings: new Map(),
typeFilter: "primitive",
bindingName: null,
}, extra);
}
/**
* If we encounter a `"`, then we try to extract the string
* from it until we find another `"`.
*
* This function will throw an error in the following cases:
* * There is already another string element.
* * We are parsing a generic argument.
* * There is more than one element.
* * There is no closing `"`.
*
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
* @param {boolean} isInGenerics
*/
function getStringElem(query, parserState, isInGenerics) {
if (isInGenerics) {
throw ["Unexpected ", "\"", " in generics"];
} else if (query.literalSearch) {
throw ["Cannot have more than one literal search element"];
} else if (parserState.totalElems - parserState.genericsElems > 0) {
throw ["Cannot use literal search when there is more than one element"];
}
parserState.pos += 1;
const start = parserState.pos;
const end = getIdentEndPosition(parserState);
if (parserState.pos >= parserState.length) {
throw ["Unclosed ", "\""];
} else if (parserState.userQuery[end] !== "\"") {
throw ["Unexpected ", parserState.userQuery[end], " in a string element"];
} else if (start === end) {
throw ["Cannot have empty string element"];
}
// To skip the quote at the end.
parserState.pos += 1;
query.literalSearch = true;
}
/**
* This function goes through all characters until it reaches an invalid ident
* character or the end of the query. It returns the position of the last
* character of the ident.
*
* @param {rustdoc.ParserState} parserState
*
* @return {number}
*/
function getIdentEndPosition(parserState) {
let afterIdent = consumeIdent(parserState);
let end = parserState.pos;
let macroExclamation = -1;
while (parserState.pos < parserState.length) {
const c = parserState.userQuery[parserState.pos];
if (c === "!") {
if (macroExclamation !== -1) {
throw ["Cannot have more than one ", "!", " in an ident"];
} else if (parserState.pos + 1 < parserState.length) {
const pos = parserState.pos;
parserState.pos++;
const beforeIdent = consumeIdent(parserState);
parserState.pos = pos;
if (beforeIdent) {
throw ["Unexpected ", "!", ": it can only be at the end of an ident"];
}
}
if (afterIdent) macroExclamation = parserState.pos;
} else if (isPathSeparator(c)) {
if (c === ":") {
if (!isPathStart(parserState)) {
break;
}
// Skip current ":".
parserState.pos += 1;
} else {
while (parserState.pos + 1 < parserState.length) {
const next_c = parserState.userQuery[parserState.pos + 1];
if (next_c !== " ") {
break;
}
parserState.pos += 1;
}
}
if (macroExclamation !== -1) {
throw ["Cannot have associated items in macros"];
}
} else if (
c === "[" ||
c === "(" ||
isEndCharacter(c) ||
isSpecialStartCharacter(c) ||
isSeparatorCharacter(c)
) {
break;
} else if (parserState.pos > 0) {
throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1],
" (not a valid identifier)"];
} else {
throw ["Unexpected ", c, " (not a valid identifier)"];
}
parserState.pos += 1;
afterIdent = consumeIdent(parserState);
end = parserState.pos;
}
if (macroExclamation !== -1) {
if (parserState.typeFilter === null) {
parserState.typeFilter = "macro";
} else if (parserState.typeFilter !== "macro") {
throw [
"Invalid search type: macro ",
"!",
" and ",
parserState.typeFilter,
" both specified",
];
}
end = macroExclamation;
}
return end;
}
/**
* @param {string} c
* @returns
*/
function isSpecialStartCharacter(c) {
return "<\"".indexOf(c) !== -1;
}
/**
* Returns `true` if the current parser position is starting with "::".
*
* @param {rustdoc.ParserState} parserState
*
* @return {boolean}
*/
function isPathStart(parserState) {
return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "::";
}
/**
* If the current parser position is at the beginning of an identifier,
* move the position to the end of it and return `true`. Otherwise, return `false`.
*
* @param {rustdoc.ParserState} parserState
*
* @return {boolean}
*/
function consumeIdent(parserState) {
REGEX_IDENT.lastIndex = parserState.pos;
const match = parserState.userQuery.match(REGEX_IDENT);
if (match) {
parserState.pos += match[0].length;
return true;
}
return false;
}
/**
* Returns `true` if the given `c` character is a path separator. For example
* `:` in `a::b` or a whitespace in `a b`.
*
* @param {string} c
*
* @return {boolean}
*/
function isPathSeparator(c) {
return c === ":" || c === " ";
}
/**
* @template T
*/
class VlqHexDecoder {
/**
* @param {string} string
* @param {function(rustdoc.VlqData): T} cons
*/
constructor(string, cons) {
this.string = string;
this.cons = cons;
this.offset = 0;
this.elemCount = 0;
/** @type {T[]} */
this.backrefQueue = [];
}
/**
* call after consuming `{`
* @returns {rustdoc.VlqData[]}
*/
decodeList() {
let c = this.string.charCodeAt(this.offset);
const ret = [];
while (c !== 125) { // 125 = "}"
ret.push(this.decode());
c = this.string.charCodeAt(this.offset);
}
this.offset += 1; // eat cb
return ret;
}
/**
* consumes and returns a list or integer
* @returns {rustdoc.VlqData}
*/
decode() {
let n = 0;
let c = this.string.charCodeAt(this.offset);
if (c === 123) { // 123 = "{"
this.offset += 1;
return this.decodeList();
}
while (c < 96) { // 96 = "`"
n = (n << 4) | (c & 0xF);
this.offset += 1;
c = this.string.charCodeAt(this.offset);
}
// last character >= la
n = (n << 4) | (c & 0xF);
const [sign, value] = [n & 1, n >> 1];
this.offset += 1;
this.elemCount += 1;
return sign ? -value : value;
}
/**
* @returns {T}
*/
next() {
const c = this.string.charCodeAt(this.offset);
// sixteen characters after "0" are backref
if (c >= 48 && c < 64) { // 48 = "0", 64 = "@"
this.offset += 1;
return this.backrefQueue[c - 48];
}
// special exception: 0 doesn't use backref encoding
// it's already one character, and it's always nullish
if (c === 96) { // 96 = "`"
this.offset += 1;
return this.cons(0);
}
const result = this.cons(this.decode());
this.backrefQueue.unshift(result);
if (this.backrefQueue.length > 16) {
this.backrefQueue.pop();
}
return result;
}
}
/** @type {Array<string>} */
const EMPTY_STRING_ARRAY = [];
/** @type {Array<rustdoc.FunctionType>} */
const EMPTY_GENERICS_ARRAY = [];
/** @type {Array<[number, rustdoc.FunctionType[]]>} */
const EMPTY_BINDINGS_ARRAY = [];
/** @type {Map<number, Array<any>>} */
const EMPTY_BINDINGS_MAP = new Map();
/**
* @param {string|null} typename
* @returns {number}
*/
function itemTypeFromName(typename) {
if (typename === null) {
return NO_TYPE_FILTER;
}
const index = itemTypes.findIndex(i => i === typename);
if (index < 0) {
throw ["Unknown type filter ", typename];
}
return index;
}
class DocSearch {
/**
* @param {string} rootPath
* @param {stringdex.Database} database
*/
constructor(rootPath, database) {
this.rootPath = rootPath;
this.database = database;
this.typeNameIdOfOutput = -1;
this.typeNameIdOfArray = -1;
this.typeNameIdOfSlice = -1;
this.typeNameIdOfArrayOrSlice = -1;
this.typeNameIdOfTuple = -1;
this.typeNameIdOfUnit = -1;
this.typeNameIdOfTupleOrUnit = -1;
this.typeNameIdOfReference = -1;
this.typeNameIdOfHof = -1;
this.utf8decoder = new TextDecoder();
/** @type {Map<number|null, rustdoc.FunctionType>} */
this.TYPES_POOL = new Map();
}
/**
* Load search index. If you do not call this function, `execQuery`
* will never fulfill.
*/
async buildIndex() {
const nn = this.database.getIndex("normalizedName");
if (!nn) {
return;
}
// Each of these identifiers are used specially by
// type-driven search.
const [
// output is the special associated type that goes
// after the arrow: the type checker desugars
// the path `Fn(a) -> b` into `Fn<Output=b, (a)>`
output,
// fn, fnmut, and fnonce all match `->`
fn,
fnMut,
fnOnce,
hof,
// array and slice both match `[]`
array,
slice,
arrayOrSlice,
// tuple and unit both match `()`
tuple,
unit,
tupleOrUnit,
// reference matches `&`
reference,
// never matches `!`
never,
] = await Promise.all([
nn.search("output"),
nn.search("fn"),
nn.search("fnmut"),
nn.search("fnonce"),
nn.search("->"),
nn.search("array"),
nn.search("slice"),
nn.search("[]"),
nn.search("tuple"),
nn.search("unit"),
nn.search("()"),
nn.search("reference"),
nn.search("never"),
]);
/**
* @param {stringdex.Trie|null|undefined} trie
* @param {rustdoc.ItemType} ty
* @param {string} modulePath
* @returns {Promise<number>}
* */
const first = async(trie, ty, modulePath) => {
if (trie) {
for (const id of trie.matches().entries()) {
const pathData = await this.getPathData(id);
if (pathData && pathData.ty === ty && pathData.modulePath === modulePath) {
return id;
}
}
}
return -1;
};
this.typeNameIdOfOutput = await first(output, TY_ASSOCTYPE, "");
this.typeNameIdOfFnPtr = await first(fn, TY_PRIMITIVE, "");
this.typeNameIdOfFn = await first(fn, TY_TRAIT, "core::ops");
this.typeNameIdOfFnMut = await first(fnMut, TY_TRAIT, "core::ops");
this.typeNameIdOfFnOnce = await first(fnOnce, TY_TRAIT, "core::ops");
this.typeNameIdOfArray = await first(array, TY_PRIMITIVE, "");
this.typeNameIdOfSlice = await first(slice, TY_PRIMITIVE, "");
this.typeNameIdOfArrayOrSlice = await first(arrayOrSlice, TY_PRIMITIVE, "");
this.typeNameIdOfTuple = await first(tuple, TY_PRIMITIVE, "");
this.typeNameIdOfUnit = await first(unit, TY_PRIMITIVE, "");
this.typeNameIdOfTupleOrUnit = await first(tupleOrUnit, TY_PRIMITIVE, "");
this.typeNameIdOfReference = await first(reference, TY_PRIMITIVE, "");
this.typeNameIdOfHof = await first(hof, TY_PRIMITIVE, "");
this.typeNameIdOfNever = await first(never, TY_PRIMITIVE, "");
}
/**
* Parses the query.
*
* The supported syntax by this parser is given in the rustdoc book chapter
* /src/doc/rustdoc/src/read-documentation/search.md
*
* When adding new things to the parser, add them there, too!
*
* @param {string} userQuery - The user query
*
* @return {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} - The parsed query
*/
static parseQuery(userQuery) {
/**
* Takes the user search input and returns an empty `ParsedQuery`.
*
* @param {string} userQuery
*
* @return {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>}
*/
function newParsedQuery(userQuery) {
return {
userQuery,
elems: [],
returned: [],
// Total number of "top" elements (does not include generics).
foundElems: 0,
// Total number of elements (includes generics).
totalElems: 0,
literalSearch: false,
hasReturnArrow: false,
error: null,
correction: null,
proposeCorrectionFrom: null,
proposeCorrectionTo: null,
// bloom filter build from type ids
typeFingerprint: new Uint32Array(4),
};
}
/**
* Parses the provided `query` input to fill `parserState`. If it encounters an error while
* parsing `query`, it'll throw an error.
*
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {rustdoc.ParserState} parserState
*/
function parseInput(query, parserState) {
let foundStopChar = true;
while (parserState.pos < parserState.length) {
const c = parserState.userQuery[parserState.pos];
if (isEndCharacter(c)) {
foundStopChar = true;
if (isSeparatorCharacter(c)) {
parserState.pos += 1;
continue;
} else if (c === "-" || c === ">") {
if (isReturnArrow(parserState)) {
query.hasReturnArrow = true;
break;
}
throw ["Unexpected ", c, " (did you mean ", "->", "?)"];
} else if (parserState.pos > 0) {
throw ["Unexpected ", c, " after ",
parserState.userQuery[parserState.pos - 1]];
}
throw ["Unexpected ", c];
} else if (c === " ") {
skipWhitespace(parserState);
continue;
}
if (!foundStopChar) {
let extra = EMPTY_STRING_ARRAY;
if (isLastElemGeneric(query.elems, parserState)) {
extra = [" after ", ">"];
} else if (prevIs(parserState, "\"")) {
throw ["Cannot have more than one element if you use quotes"];
}
if (parserState.typeFilter !== null) {
throw [
"Expected ",
",",
" or ",
"->",
...extra,
", found ",
c,
];
}
throw [
"Expected ",
",",
", ",
":",
" or ",
"->",
...extra,
", found ",
c,
];
}
const before = query.elems.length;
getFilteredNextElem(query, parserState, query.elems, false);
if (query.elems.length === before) {
// Nothing was added, weird... Let's increase the position to not remain stuck.
parserState.pos += 1;
}
foundStopChar = false;
}
if (parserState.typeFilter !== null) {
throw [
"Unexpected ",
":",
" (expected path after type filter ",
parserState.typeFilter + ":",
")",
];
}
while (parserState.pos < parserState.length) {
if (isReturnArrow(parserState)) {
parserState.pos += 2;
skipWhitespace(parserState);
// Get returned elements.
getItemsBefore(query, parserState, query.returned, "");
// Nothing can come afterward!
query.hasReturnArrow = true;
break;
} else {
parserState.pos += 1;
}
}
}
userQuery = userQuery.trim().replace(/\r|\n|\t/g, " ");
const parserState = {
length: userQuery.length,
pos: 0,
// Total number of elements (includes generics).
totalElems: 0,
genericsElems: 0,
typeFilter: null,
isInBinding: null,
userQuery,
};
let query = newParsedQuery(userQuery);
try {
parseInput(query, parserState);
// Scan for invalid type filters, so that we can report the error
// outside the search loop.
/** @param {rustdoc.ParserQueryElement} elem */
const checkTypeFilter = elem => {
const ty = itemTypeFromName(elem.typeFilter);
if (ty === TY_GENERIC && elem.generics.length !== 0) {
throw [
"Generic type parameter ",
elem.name,
" does not accept generic parameters",
];
}
for (const generic of elem.generics) {
checkTypeFilter(generic);
}
for (const constraints of elem.bindings.values()) {
for (const constraint of constraints) {
checkTypeFilter(constraint);
}
}
};
for (const elem of query.elems) {
checkTypeFilter(elem);
}
for (const elem of query.returned) {
checkTypeFilter(elem);
}
} catch (err) {
query = newParsedQuery(userQuery);
if (Array.isArray(err) && err.every(elem => typeof elem === "string")) {
query.error = err;
} else {
// rethrow the error if it isn't a string array
throw err;
}
return query;
}
if (!query.literalSearch) {
// If there is more than one element in the query, we switch to literalSearch in any
// case.
query.literalSearch = parserState.totalElems > 1;
}
query.foundElems = query.elems.length + query.returned.length;
query.totalElems = parserState.totalElems;
return query;
}
/**
* @param {number} id
* @returns {Promise<string|null>}
*/
async getName(id) {
const ni = this.database.getData("name");
if (!ni) {
return null;
}
const name = await ni.at(id);
return name === undefined || name === null ? null : this.utf8decoder.decode(name);
}
/**
* @param {number} id
* @returns {Promise<string|null>}
*/
async getDesc(id) {
const di = this.database.getData("desc");
if (!di) {
return null;
}
const desc = await di.at(id);
return desc === undefined || desc === null ? null : this.utf8decoder.decode(desc);
}
/**
* @param {number} id
* @returns {Promise<number|null>}
*/
async getAliasTarget(id) {
const ai = this.database.getData("alias");
if (!ai) {
return null;
}
const bytes = await ai.at(id);
if (bytes === undefined || bytes === null || bytes.length === 0) {
return null;
} else {
/** @type {string} */
const encoded = this.utf8decoder.decode(bytes);
/** @type {number|null} */
const decoded = JSON.parse(encoded);
return decoded;
}
}
/**
* @param {number} id
* @returns {Promise<rustdoc.EntryData|null>}
*/
async getEntryData(id) {
const ei = this.database.getData("entry");
if (!ei) {
return null;
}
const encoded = this.utf8decoder.decode(await ei.at(id));
if (encoded === "" || encoded === undefined || encoded === null) {
return null;
}
/**
* krate,
* ty,
* module_path,
* exact_module_path,
* parent,
* deprecated,
* associated_item_disambiguator
* @type {rustdoc.ArrayWithOptionals<[
* number,
* rustdoc.ItemType,
* number,
* number,
* number,
* number,
* ], [string]>}
*/
const raw = JSON.parse(encoded);
return {
krate: raw[0],
ty: raw[1],
modulePath: raw[2] === 0 ? null : raw[2] - 1,
exactModulePath: raw[3] === 0 ? null : raw[3] - 1,
parent: raw[4] === 0 ? null : raw[4] - 1,
deprecated: raw[5] === 1 ? true : false,
associatedItemDisambiguator: raw.length === 6 ? null : raw[6],
};
}
/**
* @param {number} id
* @returns {Promise<rustdoc.PathData|null>}
*/
async getPathData(id) {
const pi = this.database.getData("path");
if (!pi) {
return null;
}
const encoded = this.utf8decoder.decode(await pi.at(id));
if (encoded === "" || encoded === undefined || encoded === null) {
return null;
}
/**
* ty, module_path, exact_module_path, search_unbox, inverted_function_signature_index
* @type {rustdoc.ArrayWithOptionals<[rustdoc.ItemType, string], [string|0, 0|1, string]>}
*/
const raw = JSON.parse(encoded);
return {
ty: raw[0],
modulePath: raw[1],
exactModulePath: raw[2] === 0 || raw[2] === undefined ? raw[1] : raw[2],
};
}
/**
* @param {number} id
* @returns {Promise<rustdoc.FunctionData|null>}
*/
async getFunctionData(id) {
const fi = this.database.getData("function");
if (!fi) {
return null;
}
const encoded = this.utf8decoder.decode(await fi.at(id));
if (encoded === "" || encoded === undefined || encoded === null) {
return null;
}
/**
* function_signature, param_names
* @type {[string, string[]]}
*/
const raw = JSON.parse(encoded);
const parser = new VlqHexDecoder(raw[0], async functionSearchType => {
if (typeof functionSearchType === "number") {
return null;
}
const INPUTS_DATA = 0;
const OUTPUT_DATA = 1;
/** @type {Promise<rustdoc.FunctionType[]>} */
let inputs_;
/** @type {Promise<rustdoc.FunctionType[]>} */
let output_;
if (typeof functionSearchType[INPUTS_DATA] === "number") {
inputs_ = Promise.all([
this.buildItemSearchType(functionSearchType[INPUTS_DATA]),
]);
} else {
// @ts-ignore
inputs_ = this.buildItemSearchTypeAll(functionSearchType[INPUTS_DATA]);
}
if (functionSearchType.length > 1) {
if (typeof functionSearchType[OUTPUT_DATA] === "number") {
output_ = Promise.all([
this.buildItemSearchType(functionSearchType[OUTPUT_DATA]),
]);
} else {
// @ts-expect-error
output_ = this.buildItemSearchTypeAll(functionSearchType[OUTPUT_DATA]);
}
} else {
output_ = Promise.resolve(EMPTY_GENERICS_ARRAY);
}
/** @type {Promise<rustdoc.FunctionType[]>[]} */
const where_clause_ = [];
const l = functionSearchType.length;
for (let i = 2; i < l; ++i) {
where_clause_.push(typeof functionSearchType[i] === "number"
// @ts-expect-error
? Promise.all([this.buildItemSearchType(functionSearchType[i])])
// @ts-expect-error
: this.buildItemSearchTypeAll(functionSearchType[i]),
);
}
const [inputs, output, where_clause] = await Promise.all([
inputs_,
output_,
Promise.all(where_clause_),
]);
return {
inputs, output, where_clause,
};
});
return {
functionSignature: await parser.next(),
paramNames: raw[1],
elemCount: parser.elemCount,
};
}
/**
* @param {number} id
* @returns {Promise<rustdoc.TypeData|null>}
*/
async getTypeData(id) {
const ti = this.database.getData("type");
if (!ti) {
return null;
}
const encoded = this.utf8decoder.decode(await ti.at(id));
if (encoded === "" || encoded === undefined || encoded === null) {
return null;
}
/**
* function_signature, param_names
* @type {[string, number] | [number] | [string] | [] | null}
*/
const raw = JSON.parse(encoded);
if (!raw || raw.length === 0) {
return null;
}
let searchUnbox = false;
const invertedFunctionSignatureIndex = [];
if (typeof raw[0] === "string") {
if (raw[1]) {
searchUnbox = true;
}
// the inverted function signature index is a list of bitmaps,
// by number of types that appear in the function
let i = 0;
const pb = makeUint8ArrayFromBase64(raw[0]);
const l = pb.length;
while (i < l) {
if (pb[i] === 0) {
invertedFunctionSignatureIndex.push(RoaringBitmap.empty());
i += 1;
} else {
const bitmap = new RoaringBitmap(pb, i);
i += bitmap.consumed_len_bytes;
invertedFunctionSignatureIndex.push(bitmap);
}
}
} else if (raw[0]) {
searchUnbox = true;
}
return { searchUnbox, invertedFunctionSignatureIndex };
}
/**
* @returns {Promise<string[]>}
*/
async getCrateNameList() {
const crateNames = this.database.getData("crateNames");
if (!crateNames) {
return [];
}
const l = crateNames.length;
const names = [];
for (let i = 0; i < l; ++i) {
names.push(crateNames.at(i).then(name => {
if (name === undefined) {
return "";
}
return this.utf8decoder.decode(name);
}));
}
return Promise.all(names);
}
/**
* @param {number} id non-negative generic index
* @returns {Promise<stringdex.RoaringBitmap[]>}
*/
async getGenericInvertedIndex(id) {
const gii = this.database.getData("generic_inverted_index");
if (!gii) {
return [];
}
const pb = await gii.at(id);
if (pb === undefined || pb === null || pb.length === 0) {
return [];
}
const invertedFunctionSignatureIndex = [];
// the inverted function signature index is a list of bitmaps,
// by number of types that appear in the function
let i = 0;
const l = pb.length;
while (i < l) {
if (pb[i] === 0) {
invertedFunctionSignatureIndex.push(RoaringBitmap.empty());
i += 1;
} else {
const bitmap = new RoaringBitmap(pb, i);
i += bitmap.consumed_len_bytes;
invertedFunctionSignatureIndex.push(bitmap);
}
}
return invertedFunctionSignatureIndex;
}
/**
* @param {number} id
* @returns {Promise<rustdoc.Row?>}
*/
async getRow(id) {
const [name_, entry, path, type] = await Promise.all([
this.getName(id),
this.getEntryData(id),
this.getPathData(id),
this.getFunctionData(id),
]);
if (!entry && !path) {
return null;
}
const [
moduleName,
modulePathData,
exactModuleName,
exactModulePathData,
] = await Promise.all([
entry && entry.modulePath !== null ? this.getName(entry.modulePath) : null,
entry && entry.modulePath !== null ? this.getPathData(entry.modulePath) : null,
entry && entry.exactModulePath !== null ?
this.getName(entry.exactModulePath) :
null,
entry && entry.exactModulePath !== null ?
this.getPathData(entry.exactModulePath) :
null,
]);
const name = name_ === null ? "" : name_;
const normalizedName = (name.indexOf("_") === -1 ?
name :
name.replace(/_/g, "")).toLowerCase();
const modulePath = modulePathData === null || moduleName === null ? "" :
(modulePathData.modulePath === "" ?
moduleName :
`${modulePathData.modulePath}::${moduleName}`);
const [parentName, parentPath] = entry !== null && entry.parent !== null ?
await Promise.all([this.getName(entry.parent), this.getPathData(entry.parent)]) :
[null, null];
return {
id,
crate: entry ? nonnull(await this.getName(entry.krate)) : "",
ty: entry ? entry.ty : nonnull(path).ty,
name,
normalizedName,
modulePath,
exactModulePath: exactModulePathData === null || exactModuleName === null ? modulePath :
(exactModulePathData.exactModulePath === "" ?
exactModuleName :
`${exactModulePathData.exactModulePath}::${exactModuleName}`),
entry,
path,
type,
deprecated: entry ? entry.deprecated : false,
parent: parentName !== null && parentPath !== null ?
{ name: parentName, path: parentPath } :
null,
};
}
/**
* Convert a list of RawFunctionType / ID to object-based FunctionType.
*
* Crates often have lots of functions in them, and it's common to have a large number of
* functions that operate on a small set of data types, so the search index compresses them
* by encoding function parameter and return types as indexes into an array of names.
*
* Even when a general-purpose compression algorithm is used, this is still a win.
* I checked. https://github.com/rust-lang/rust/pull/98475#issue-1284395985
*
* The format for individual function types is encoded in
* librustdoc/html/render/mod.rs: impl Serialize for RenderType
*
* @param {null|Array<rustdoc.RawFunctionType>} types
*
* @return {Promise<Array<rustdoc.FunctionType>>}
*/
async buildItemSearchTypeAll(types) {
return types && types.length > 0 ?
await Promise.all(types.map(type => this.buildItemSearchType(type))) :
EMPTY_GENERICS_ARRAY;
}
/**
* Converts a single type.
*
* @param {rustdoc.RawFunctionType} type
* @return {Promise<rustdoc.FunctionType>}
*/
async buildItemSearchType(type) {
const PATH_INDEX_DATA = 0;
const GENERICS_DATA = 1;
const BINDINGS_DATA = 2;
let id, generics;
/**
* @type {Map<number, rustdoc.FunctionType[]>}
*/
let bindings;
if (typeof type === "number") {
id = type;
generics = EMPTY_GENERICS_ARRAY;
bindings = EMPTY_BINDINGS_MAP;
} else {
id = type[PATH_INDEX_DATA];
generics = await this.buildItemSearchTypeAll(type[GENERICS_DATA]);
if (type[BINDINGS_DATA] && type[BINDINGS_DATA].length > 0) {
bindings = new Map((await Promise.all(type[BINDINGS_DATA].map(
/**
* @param {[rustdoc.RawFunctionType, rustdoc.RawFunctionType[]]} binding
* @returns {Promise<[number, rustdoc.FunctionType[]][]>}
*/
async binding => {
const [assocType, constraints] = binding;
// Associated type constructors are represented sloppily in rustdoc's
// type search, to make the engine simpler.
//
// MyType<Output<T>=Result<T>> is equivalent to MyType<Output<Result<T>>=T>
// and both are, essentially
// MyType<Output=(T, Result<T>)>, except the tuple isn't actually there.
// It's more like the value of a type binding is naturally an array,
// which rustdoc calls "constraints".
//
// As a result, the key should never have generics on it.
const [k, v] = await Promise.all([
this.buildItemSearchType(assocType).then(t => t.id),
this.buildItemSearchTypeAll(constraints),
]);
return k === null ? EMPTY_BINDINGS_ARRAY : [[k, v]];
},
))).flat());
} else {
bindings = EMPTY_BINDINGS_MAP;
}
}
/**
* @type {rustdoc.FunctionType}
*/
let result;
if (id < 0) {
// types less than 0 are generic parameters
// the actual names of generic parameters aren't stored, since they aren't API
result = {
id,
name: "",
ty: TY_GENERIC,
path: null,
exactPath: null,
generics,
bindings,
unboxFlag: true,
};
} else if (id === 0) {
// `0` is used as a sentinel because it's fewer bytes than `null`
result = {
id: null,
name: "",
ty: TY_GENERIC,
path: null,
exactPath: null,
generics,
bindings,
unboxFlag: true,
};
} else {
const [name, path, type] = await Promise.all([
this.getName(id - 1),
this.getPathData(id - 1),
this.getTypeData(id - 1),
]);
if (path === undefined || path === null || type === undefined || type === null) {
return {
id: null,
name: "",
ty: TY_GENERIC,
path: null,
exactPath: null,
generics,
bindings,
unboxFlag: true,
};
}
result = {
id: id - 1,
name,
ty: path.ty,
path: path.modulePath,
exactPath: path.exactModulePath === null ? path.modulePath : path.exactModulePath,
generics,
bindings,
unboxFlag: type.searchUnbox,
};
}
const cr = this.TYPES_POOL.get(result.id);
if (cr) {
// Shallow equality check. Since this function is used
// to construct every type object, this should be mostly
// equivalent to a deep equality check, except if there's
// a conflict, we don't keep the old one around, so it's
// not a fully precise implementation of hashcons.
if (cr.generics.length === result.generics.length &&
cr.generics !== result.generics &&
cr.generics.every((x, i) => result.generics[i] === x)
) {
result.generics = cr.generics;
}
if (cr.bindings.size === result.bindings.size && cr.bindings !== result.bindings) {
let ok = true;
for (const [k, v] of cr.bindings.entries()) {
const v2 = result.bindings.get(k);
if (!v2) {
ok = false;
break;
}
if (v !== v2 && v.length === v2.length && v.every((x, i) => v2[i] === x)) {
result.bindings.set(k, v);
} else if (v !== v2) {
ok = false;
break;
}
}
if (ok) {
result.bindings = cr.bindings;
}
}
if (cr.ty === result.ty && cr.path === result.path
&& cr.bindings === result.bindings && cr.generics === result.generics
&& cr.ty === result.ty && cr.name === result.name
&& cr.unboxFlag === result.unboxFlag
) {
return cr;
}
}
this.TYPES_POOL.set(result.id, result);
return result;
}
/**
* Executes the parsed query and builds a {ResultsTable}.
*
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} parsedQuery
* - The parsed user query
* @param {Object} filterCrates - Crate to search in if defined
* @param {string} currentCrate - Current crate, to rank results from this crate higher
*
* @return {Promise<rustdoc.ResultsTable>}
*/
async execQuery(parsedQuery, filterCrates, currentCrate) {
const queryLen =
parsedQuery.elems.reduce((acc, next) => acc + next.pathLast.length, 0) +
parsedQuery.returned.reduce((acc, next) => acc + next.pathLast.length, 0);
const maxEditDistance = Math.floor(queryLen / 3);
/**
* @param {rustdoc.Row} item
* @returns {[string, string, string]}
*/
const buildHrefAndPath = item => {
let displayPath;
let href;
const type = itemTypes[item.ty];
const name = item.name;
let path = item.modulePath;
let exactPath = item.exactModulePath;
if (type === "mod") {
displayPath = path + "::";
href = this.rootPath + path.replace(/::/g, "/") + "/" +
name + "/index.html";
} else if (type === "import") {
displayPath = item.modulePath + "::";
href = this.rootPath + item.modulePath.replace(/::/g, "/") +
"/index.html#reexport." + name;
} else if (type === "primitive" || type === "keyword") {
displayPath = "";
exactPath = "";
href = this.rootPath + path.replace(/::/g, "/") +
"/" + type + "." + name + ".html";
} else if (type === "externcrate") {
displayPath = "";
href = this.rootPath + name + "/index.html";
} else if (item.parent) {
const myparent = item.parent;
let anchor = type + "." + name;
const parentType = itemTypes[myparent.path.ty];
let pageType = parentType;
let pageName = myparent.name;
exactPath = `${myparent.path.exactModulePath}::${myparent.name}`;
if (parentType === "primitive") {
displayPath = myparent.name + "::";
exactPath = myparent.name;
} else if (type === "structfield" && parentType === "variant") {
// Structfields belonging to variants are special: the
// final path element is the enum name.
const enumNameIdx = item.modulePath.lastIndexOf("::");
const enumName = item.modulePath.substr(enumNameIdx + 2);
path = item.modulePath.substr(0, enumNameIdx);
displayPath = path + "::" + enumName + "::" + myparent.name + "::";
anchor = "variant." + myparent.name + ".field." + name;
pageType = "enum";
pageName = enumName;
} else {
displayPath = path + "::" + myparent.name + "::";
}
if (item.entry && item.entry.associatedItemDisambiguator !== null) {
anchor = item.entry.associatedItemDisambiguator + "/" + anchor;
}
href = this.rootPath + path.replace(/::/g, "/") +
"/" + pageType +
"." + pageName +
".html#" + anchor;
} else {
displayPath = item.modulePath + "::";
href = this.rootPath + item.modulePath.replace(/::/g, "/") +
"/" + type + "." + name + ".html";
}
return [displayPath, href, `${exactPath}::${name}`];
};
/**
*
* @param {string} path
* @returns {string}
*/
function pathSplitter(path) {
const tmp = "<span>" + path.replace(/::/g, "::</span><span>");
if (tmp.endsWith("<span>")) {
return tmp.slice(0, tmp.length - 6);
}
return tmp;
}
/**
* Add extra data to result objects, and filter items that have been
* marked for removal.
*
* The output is formatted as an array of hunks, where odd numbered
* hunks are highlighted and even numbered ones are not.
*
* @param {rustdoc.ResultObject} obj
* @param {"sig"|"elems"|"returned"|null} typeInfo
* @param {rustdoc.QueryElement[]} elems
* @param {rustdoc.QueryElement[]} returned
* @returns {Promise<rustdoc.DisplayTypeSignature>}
*/
const formatDisplayTypeSignature = async(obj, typeInfo, elems, returned) => {
const objType = obj.type;
if (!objType) {
return {type: [], mappedNames: new Map(), whereClause: new Map()};
}
let fnInputs = null;
let fnOutput = null;
/** @type {Map<number, number> | null} */
let mgens = null;
if (typeInfo !== "elems" && typeInfo !== "returned") {
fnInputs = unifyFunctionTypes(
objType.inputs,
elems,
objType.where_clause,
null,
mgensScratch => {
fnOutput = unifyFunctionTypes(
objType.output,
returned,
objType.where_clause,
mgensScratch,
mgensOut => {
mgens = mgensOut;
return true;
},
0,
);
return !!fnOutput;
},
0,
);
} else {
const highlighted = unifyFunctionTypes(
typeInfo === "elems" ? objType.inputs : objType.output,
typeInfo === "elems" ? elems : returned,
objType.where_clause,
null,
mgensOut => {
mgens = mgensOut;
return true;
},
0,
);
if (typeInfo === "elems") {
fnInputs = highlighted;
} else {
fnOutput = highlighted;
}
}
if (!fnInputs) {
fnInputs = objType.inputs;
}
if (!fnOutput) {
fnOutput = objType.output;
}
const mappedNames = new Map();
const whereClause = new Map();
const fnParamNames = obj.paramNames || [];
/** @type {string[]} */
const queryParamNames = [];
/**
* Recursively writes a map of IDs to query generic names,
* which are later used to map query generic names to function generic names.
* For example, when the user writes `X -> Option<X>` and the function
* is actually written as `T -> Option<T>`, this function stores the
* mapping `(-1, "X")`, and the writeFn function looks up the entry
* for -1 to form the final, user-visible mapping of "X is T".
*
* @param {rustdoc.QueryElement} queryElem
*/
const remapQuery = queryElem => {
if (queryElem.id !== null && queryElem.id < 0) {
queryParamNames[-1 - queryElem.id] = queryElem.name;
}
if (queryElem.generics.length > 0) {
queryElem.generics.forEach(remapQuery);
}
if (queryElem.bindings.size > 0) {
[...queryElem.bindings.values()].flat().forEach(remapQuery);
}
};
elems.forEach(remapQuery);
returned.forEach(remapQuery);
/**
* Write text to a highlighting array.
* Index 0 is not highlighted, index 1 is highlighted,
* index 2 is not highlighted, etc.
*
* @param {{name: string|null, highlighted?: boolean}} fnType - input
* @param {string[]} result
*/
const pushText = (fnType, result) => {
// If !!(result.length % 2) == false, then pushing a new slot starts an even
// numbered slot. Even numbered slots are not highlighted.
//
// `highlighted` will not be defined if an entire subtree is not highlighted,
// so `!!` is used to coerce it to boolean. `result.length % 2` is used to
// check if the number is even, but it evaluates to a number, so it also
// needs coerced to a boolean.
if (!!(result.length % 2) === !!fnType.highlighted) {
result.push("");
} else if (result.length === 0 && !!fnType.highlighted) {
result.push("");
result.push("");
}
result[result.length - 1] += fnType.name;
};
/**
* Write a higher order function type: either a function pointer
* or a trait bound on Fn, FnMut, or FnOnce.
*
* @param {rustdoc.HighlightedFunctionType} fnType - input
* @param {string[]} result
* @returns {Promise<void>}
*/
const writeHof = async(fnType, result) => {
const hofOutput = fnType.bindings.get(this.typeNameIdOfOutput) || [];
const hofInputs = fnType.generics;
pushText(fnType, result);
pushText({name: " (", highlighted: false}, result);
let needsComma = false;
for (const fnType of hofInputs) {
if (needsComma) {
pushText({ name: ", ", highlighted: false }, result);
}
needsComma = true;
await writeFn(fnType, result);
}
pushText({
name: hofOutput.length === 0 ? ")" : ") -> ",
highlighted: false,
}, result);
if (hofOutput.length > 1) {
pushText({name: "(", highlighted: false}, result);
}
needsComma = false;
for (const fnType of hofOutput) {
if (needsComma) {
pushText({ name: ", ", highlighted: false }, result);
}
needsComma = true;
await writeFn(fnType, result);
}
if (hofOutput.length > 1) {
pushText({name: ")", highlighted: false}, result);
}
};
/**
* Write a primitive type with special syntax, like `!` or `[T]`.
* Returns `false` if the supplied type isn't special.
*
* @param {rustdoc.HighlightedFunctionType} fnType
* @param {string[]} result
* @returns {Promise<boolean>}
*/
const writeSpecialPrimitive = async(fnType, result) => {
if (fnType.id === this.typeNameIdOfArray || fnType.id === this.typeNameIdOfSlice ||
fnType.id === this.typeNameIdOfTuple || fnType.id === this.typeNameIdOfUnit) {
const [ob, sb] =
fnType.id === this.typeNameIdOfArray ||
fnType.id === this.typeNameIdOfSlice ?
["[", "]"] :
["(", ")"];
pushText({ name: ob, highlighted: fnType.highlighted }, result);
await onEachBtwnAsync(
fnType.generics,
nested => writeFn(nested, result),
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, result),
);
pushText({ name: sb, highlighted: fnType.highlighted }, result);
return true;
} else if (fnType.id === this.typeNameIdOfReference) {
pushText({ name: "&", highlighted: fnType.highlighted }, result);
let prevHighlighted = false;
await onEachBtwnAsync(
fnType.generics,
async value => {
prevHighlighted = !!value.highlighted;
await writeFn(value, result);
},
// @ts-expect-error
value => pushText({
name: " ",
highlighted: prevHighlighted && value.highlighted,
}, result),
);
return true;
} else if (
fnType.id === this.typeNameIdOfFn ||
fnType.id === this.typeNameIdOfFnMut ||
fnType.id === this.typeNameIdOfFnOnce ||
fnType.id === this.typeNameIdOfFnPtr
) {
await writeHof(fnType, result);
return true;
} else if (fnType.id === this.typeNameIdOfNever) {
pushText({ name: "!", highlighted: fnType.highlighted }, result);
return true;
}
return false;
};
/**
* Write a type. This function checks for special types,
* like slices, with their own formatting. It also handles
* updating the where clause and generic type param map.
*
* @param {rustdoc.HighlightedFunctionType} fnType
* @param {string[]} result
* @returns {Promise<void>}
*/
const writeFn = async(fnType, result) => {
if (fnType.id !== null && fnType.id < 0) {
if (fnParamNames[-1 - fnType.id] === "") {
// Normally, there's no need to shown an unhighlighted
// where clause, but if it's impl Trait, then we do.
const generics = fnType.generics.length > 0 ?
fnType.generics :
objType.where_clause[-1 - fnType.id];
for (const nested of generics) {
await writeFn(nested, result);
}
return;
} else if (mgens) {
for (const [queryId, fnId] of mgens) {
if (fnId === fnType.id) {
mappedNames.set(
queryParamNames[-1 - queryId],
fnParamNames[-1 - fnType.id],
);
}
}
}
pushText({
name: fnParamNames[-1 - fnType.id],
highlighted: !!fnType.highlighted,
}, result);
/** @type{string[]} */
const where = [];
await onEachBtwnAsync(
fnType.generics,
nested => writeFn(nested, where),
// @ts-expect-error
() => pushText({ name: " + ", highlighted: false }, where),
);
if (where.length > 0) {
whereClause.set(fnParamNames[-1 - fnType.id], where);
}
} else {
if (fnType.ty === TY_PRIMITIVE) {
if (await writeSpecialPrimitive(fnType, result)) {
return;
}
} else if (fnType.ty === TY_TRAIT && (
fnType.id === this.typeNameIdOfFn ||
fnType.id === this.typeNameIdOfFnMut ||
fnType.id === this.typeNameIdOfFnOnce ||
fnType.id === this.typeNameIdOfFnPtr
)) {
await writeHof(fnType, result);
return;
} else if (fnType.name === "" &&
fnType.bindings.size === 0 &&
fnType.generics.length !== 0
) {
pushText({ name: "impl ", highlighted: false }, result);
if (fnType.generics.length > 1) {
pushText({ name: "(", highlighted: false }, result);
}
await onEachBtwnAsync(
fnType.generics,
value => writeFn(value, result),
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, result),
);
if (fnType.generics.length > 1) {
pushText({ name: ")", highlighted: false }, result);
}
return;
}
pushText(fnType, result);
let hasBindings = false;
if (fnType.bindings.size > 0) {
await onEachBtwnAsync(
await Promise.all([...fnType.bindings.entries()].map(
/**
* @param {[number, rustdoc.HighlightedFunctionType[]]} param0
* @returns {Promise<[
* string|null,
* rustdoc.HighlightedFunctionType[],
* ]>}
*/
async([key, values]) => [await this.getName(key), values],
)),
async([name, values]) => {
// @ts-expect-error
if (values.length === 1 && values[0].id < 0 &&
// @ts-expect-error
`${fnType.name}::${name}` === fnParamNames[-1 - values[0].id]
) {
// the internal `Item=Iterator::Item` type variable should be
// shown in the where clause and name mapping output, but is
// redundant in this spot
for (const value of values) {
await writeFn(value, []);
}
return true;
}
if (!hasBindings) {
hasBindings = true;
pushText({ name: "<", highlighted: false }, result);
}
pushText({ name, highlighted: false }, result);
pushText({
name: values.length !== 1 ? "=(" : "=",
highlighted: false,
}, result);
await onEachBtwnAsync(
values || [],
value => writeFn(value, result),
// @ts-expect-error
() => pushText({ name: " + ", highlighted: false }, result),
);
if (values.length !== 1) {
pushText({ name: ")", highlighted: false }, result);
}
},
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, result),
);
}
if (fnType.generics.length > 0) {
pushText({ name: hasBindings ? ", " : "<", highlighted: false }, result);
}
await onEachBtwnAsync(
fnType.generics,
value => writeFn(value, result),
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, result),
);
if (hasBindings || fnType.generics.length > 0) {
pushText({ name: ">", highlighted: false }, result);
}
}
};
/** @type {string[]} */
const type = [];
await onEachBtwnAsync(
fnInputs,
fnType => writeFn(fnType, type),
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, type),
);
pushText({ name: " -> ", highlighted: false }, type);
await onEachBtwnAsync(
fnOutput,
fnType => writeFn(fnType, type),
// @ts-expect-error
() => pushText({ name: ", ", highlighted: false }, type),
);
return {type, mappedNames, whereClause};
};
/**
* Add extra data to result objects, and filter items that have been
* marked for removal.
*
* @param {[rustdoc.PlainResultObject, rustdoc.Row][]} results
* @param {"sig"|"elems"|"returned"|null} typeInfo
* @param {Set<string>} duplicates
* @returns {rustdoc.ResultObject[]}
*/
const transformResults = (results, typeInfo, duplicates) => {
const out = [];
for (const [result, item] of results) {
if (item.id !== -1) {
const res = buildHrefAndPath(item);
// many of these properties don't strictly need to be
// copied over, but copying them over satisfies tsc,
// and hopefully plays nice with the shape optimization
// of the browser engine.
/** @type {rustdoc.ResultObject} */
const obj = Object.assign({
parent: item.parent ? {
path: item.parent.path.modulePath,
exactPath: item.parent.path.exactModulePath ||
item.parent.path.modulePath,
name: item.parent.name,
ty: item.parent.path.ty,
} : undefined,
type: item.type && item.type.functionSignature ?
item.type.functionSignature :
undefined,
paramNames: item.type && item.type.paramNames ?
item.type.paramNames :
undefined,
dist: result.dist,
path_dist: result.path_dist,
index: result.index,
desc: this.getDesc(result.id),
item,
displayPath: pathSplitter(res[0]),
fullPath: "",
href: "",
displayTypeSignature: null,
}, result);
// To be sure than it some items aren't considered as duplicate.
obj.fullPath = res[2] + "|" + obj.item.ty;
if (duplicates.has(obj.fullPath)) {
continue;
}
// Exports are specifically not shown if the items they point at
// are already in the results.
if (obj.item.ty === TY_IMPORT && duplicates.has(res[2])) {
continue;
}
if (duplicates.has(res[2] + "|" + TY_IMPORT)) {
continue;
}
duplicates.add(obj.fullPath);
duplicates.add(res[2]);
if (typeInfo !== null) {
obj.displayTypeSignature = formatDisplayTypeSignature(
obj,
typeInfo,
result.elems,
result.returned,
);
}
obj.href = res[1];
out.push(obj);
if (out.length >= MAX_RESULTS) {
break;
}
}
}
return out;
};
const sortAndTransformResults =
/**
* @this {DocSearch}
* @param {Array<rustdoc.PlainResultObject|null>} results
* @param {"sig"|"elems"|"returned"|null} typeInfo
* @param {string} preferredCrate
* @param {Set<string>} duplicates
* @returns {AsyncGenerator<rustdoc.ResultObject, number>}
*/
async function*(results, typeInfo, preferredCrate, duplicates) {
const userQuery = parsedQuery.userQuery;
const normalizedUserQuery = parsedQuery.userQuery.toLowerCase();
const isMixedCase = normalizedUserQuery !== userQuery;
/**
* @type {[rustdoc.PlainResultObject, rustdoc.Row][]}
*/
const result_list = [];
for (const result of results.values()) {
if (!result) {
continue;
}
/**
* @type {rustdoc.Row?}
*/
const item = await this.getRow(result.id);
if (!item) {
continue;
}
if (filterCrates !== null && item.crate !== filterCrates) {
continue;
}
if (item) {
result_list.push([result, item]);
} else {
continue;
}
}
result_list.sort(([aaa, aai], [bbb, bbi]) => {
/** @type {number} */
let a;
/** @type {number} */
let b;
if (typeInfo === null) {
// in name based search...
// sort by exact case-sensitive match
if (isMixedCase) {
a = Number(aai.name !== userQuery);
b = Number(bbi.name !== userQuery);
if (a !== b) {
return a - b;
}
}
// sort by exact match with regard to the last word (mismatch goes later)
a = Number(aai.normalizedName !== normalizedUserQuery);
b = Number(bbi.normalizedName !== normalizedUserQuery);
if (a !== b) {
return a - b;
}
// sort by index of keyword in item name (no literal occurrence goes later)
a = Number(aaa.index < 0);
b = Number(bbb.index < 0);
if (a !== b) {
return a - b;
}
}
// Sort by distance in the path part, if specified
// (less changes required to match means higher rankings)
a = Number(aaa.path_dist);
b = Number(bbb.path_dist);
if (a !== b) {
return a - b;
}
// (later literal occurrence, if any, goes later)
a = Number(aaa.index);
b = Number(bbb.index);
if (a !== b) {
return a - b;
}
// Sort by distance in the name part, the last part of the path
// (less changes required to match means higher rankings)
a = Number(aaa.dist);
b = Number(bbb.dist);
if (a !== b) {
return a - b;
}
// sort aliases lower
a = Number(aaa.is_alias);
b = Number(bbb.is_alias);
if (a !== b) {
return a - b;
}
// sort deprecated items later
a = Number(aai.deprecated);
b = Number(bbi.deprecated);
if (a !== b) {
return a - b;
}
// sort by crate (current crate comes first)
a = Number(aai.crate !== preferredCrate);
b = Number(bbi.crate !== preferredCrate);
if (a !== b) {
return a - b;
}
// sort by item name length (longer goes later)
a = Number(aai.normalizedName.length);
b = Number(bbi.normalizedName.length);
if (a !== b) {
return a - b;
}
// sort by item name (lexicographically larger goes later)
let aw = aai.normalizedName;
let bw = bbi.normalizedName;
if (aw !== bw) {
return (aw > bw ? +1 : -1);
}
// sort by description (no description goes later)
const di = this.database.getData("desc");
if (di) {
a = Number(di.isEmpty(aaa.id));
b = Number(di.isEmpty(bbb.id));
if (a !== b) {
return a - b;
}
}
// sort by type (later occurrence in `itemTypes` goes later)
a = Number(aai.ty);
b = Number(bbi.ty);
if (a !== b) {
return a - b;
}
// sort by path (lexicographically larger goes later)
const ap = aai.modulePath;
const bp = bbi.modulePath;
aw = ap === undefined ? "" : ap;
bw = bp === undefined ? "" : bp;
if (aw !== bw) {
return (aw > bw ? +1 : -1);
}
// que sera, sera
return 0;
});
const transformed_result_list = transformResults(result_list, typeInfo, duplicates);
yield* transformed_result_list;
return transformed_result_list.length;
}
.bind(this);
/**
* This function checks if a list of search query `queryElems` can all be found in the
* search index (`fnTypes`).
*
* This function returns highlighted results on a match, or `null`. If `solutionCb` is
* supplied, it will call that function with mgens, and that callback can accept or
* reject the result by returning `true` or `false`. If the callback returns false,
* then this function will try with a different solution, or bail with null if it
* runs out of candidates.
*
* @param {rustdoc.FunctionType[]} fnTypesIn - The objects to check.
* @param {rustdoc.QueryElement[]} queryElems - The elements from the parsed query.
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgensIn
* - Map query generics to function generics (never modified).
* @param {function(Map<number,number>?): boolean} solutionCb
* - Called for each `mgens` solution.
* @param {number} unboxingDepth
* - Limit checks that Ty matches Vec<Ty>,
* but not Vec<ParamEnvAnd<WithInfcx<ConstTy<Interner<Ty=Ty>>>>>
*
* @return {rustdoc.HighlightedFunctionType[]|null}
* - Returns highlighted results if a match, null otherwise.
*/
function unifyFunctionTypes(
fnTypesIn,
queryElems,
whereClause,
mgensIn,
solutionCb,
unboxingDepth,
) {
if (unboxingDepth >= UNBOXING_LIMIT) {
return null;
}
/**
* @type {Map<number, number>|null}
*/
const mgens = mgensIn === null ? null : new Map(mgensIn);
if (queryElems.length === 0) {
return solutionCb(mgens) ? fnTypesIn : null;
}
if (!fnTypesIn || fnTypesIn.length === 0) {
return null;
}
const ql = queryElems.length;
const fl = fnTypesIn.length;
// One element fast path / base case
if (ql === 1 && queryElems[0].generics.length === 0
&& queryElems[0].bindings.size === 0) {
const queryElem = queryElems[0];
for (const [i, fnType] of fnTypesIn.entries()) {
if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgens)) {
continue;
}
if (fnType.id !== null &&
fnType.id < 0 &&
queryElem.id !== null &&
queryElem.id < 0
) {
if (mgens && mgens.has(queryElem.id) &&
mgens.get(queryElem.id) !== fnType.id) {
continue;
}
const mgensScratch = new Map(mgens);
mgensScratch.set(queryElem.id, fnType.id);
if (!solutionCb || solutionCb(mgensScratch)) {
const highlighted = [...fnTypesIn];
highlighted[i] = Object.assign({
highlighted: true,
}, fnType, {
generics: whereClause[-1 - fnType.id],
});
return highlighted;
}
} else if (solutionCb(mgens ? new Map(mgens) : null)) {
// unifyFunctionTypeIsMatchCandidate already checks that ids match
const highlighted = [...fnTypesIn];
highlighted[i] = Object.assign({
highlighted: true,
}, fnType, {
generics: unifyGenericTypes(
fnType.generics,
queryElem.generics,
whereClause,
mgens ? new Map(mgens) : null,
solutionCb,
unboxingDepth,
) || fnType.generics,
});
return highlighted;
}
}
for (const [i, fnType] of fnTypesIn.entries()) {
if (!unifyFunctionTypeIsUnboxCandidate(
fnType,
queryElem,
whereClause,
mgens,
unboxingDepth + 1,
)) {
continue;
}
// @ts-expect-error
if (fnType.id < 0) {
const highlightedGenerics = unifyFunctionTypes(
// @ts-expect-error
whereClause[(-fnType.id) - 1],
queryElems,
whereClause,
mgens,
solutionCb,
unboxingDepth + 1,
);
if (highlightedGenerics) {
const highlighted = [...fnTypesIn];
highlighted[i] = Object.assign({
highlighted: true,
}, fnType, {
generics: highlightedGenerics,
});
return highlighted;
}
} else {
const highlightedGenerics = unifyFunctionTypes(
[...Array.from(fnType.bindings.values()).flat(), ...fnType.generics],
queryElems,
whereClause,
mgens ? new Map(mgens) : null,
solutionCb,
unboxingDepth + 1,
);
if (highlightedGenerics) {
const highlighted = [...fnTypesIn];
highlighted[i] = Object.assign({}, fnType, {
generics: highlightedGenerics,
bindings: new Map([...fnType.bindings.entries()].map(([k, v]) => {
return [k, highlightedGenerics.splice(0, v.length)];
})),
});
return highlighted;
}
}
}
return null;
}
// Multiple element recursive case
/**
* @type {Array<rustdoc.FunctionType>}
*/
const fnTypes = fnTypesIn.slice();
/**
* Algorithm works by building up a solution set in the working arrays
* fnTypes gets mutated in place to make this work, while queryElems
* is left alone.
*
* It works backwards, because arrays can be cheaply truncated that way.
*
* vvvvvvv `queryElem`
* queryElems = [ unknown, unknown, good, good, good ]
* fnTypes = [ unknown, unknown, good, good, good ]
* ^^^^^^^^^^^^^^^^ loop over these elements to find candidates
*
* Everything in the current working solution is known to be a good
* match, but it might not be the match we wind up going with, because
* there might be more than one candidate match, and we need to try them all
* before giving up. So, to handle this, it backtracks on failure.
*/
const flast = fl - 1;
const qlast = ql - 1;
const queryElem = queryElems[qlast];
let queryElemsTmp = null;
for (let i = flast; i >= 0; i -= 1) {
const fnType = fnTypes[i];
if (!unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgens)) {
continue;
}
let mgensScratch;
if (fnType.id !== null && queryElem.id !== null && fnType.id < 0) {
mgensScratch = new Map(mgens);
if (mgensScratch.has(queryElem.id)
&& mgensScratch.get(queryElem.id) !== fnType.id) {
continue;
}
mgensScratch.set(queryElem.id, fnType.id);
} else {
mgensScratch = mgens;
}
// fnTypes[i] is a potential match
// fnTypes[flast] is the last item in the list
// swap them, and drop the potential match from the list
// check if the remaining function types also match
fnTypes[i] = fnTypes[flast];
fnTypes.length = flast;
if (!queryElemsTmp) {
queryElemsTmp = queryElems.slice(0, qlast);
}
/** @type {rustdoc.HighlightedFunctionType[]|null} */
let unifiedGenerics = [];
/** @type {null|Map<number, number>} */
let unifiedGenericsMgens = null;
/** @type {rustdoc.HighlightedFunctionType[]|null} */
const passesUnification = unifyFunctionTypes(
fnTypes,
queryElemsTmp,
whereClause,
mgensScratch,
mgensScratch => {
if (fnType.generics.length === 0 && queryElem.generics.length === 0
&& fnType.bindings.size === 0 && queryElem.bindings.size === 0) {
return solutionCb(mgensScratch);
}
const solution = unifyFunctionTypeCheckBindings(
fnType,
queryElem,
whereClause,
mgensScratch,
unboxingDepth,
);
if (!solution) {
return false;
}
const simplifiedGenerics = solution.simplifiedGenerics;
for (const simplifiedMgens of solution.mgens) {
unifiedGenerics = unifyGenericTypes(
simplifiedGenerics,
queryElem.generics,
whereClause,
simplifiedMgens,
solutionCb,
unboxingDepth,
);
if (unifiedGenerics !== null) {
unifiedGenericsMgens = simplifiedMgens;
return true;
}
}
return false;
},
unboxingDepth,
);
if (passesUnification) {
passesUnification.length = fl;
passesUnification[flast] = passesUnification[i];
passesUnification[i] = Object.assign({}, fnType, {
highlighted: true,
generics: unifiedGenerics,
bindings: new Map([...fnType.bindings.entries()].map(([k, v]) => {
return [k, queryElem.bindings.has(k) ? unifyFunctionTypes(
v,
// @ts-expect-error
queryElem.bindings.get(k),
whereClause,
unifiedGenericsMgens,
solutionCb,
unboxingDepth,
// @ts-expect-error
) : unifiedGenerics.splice(0, v.length)];
})),
});
return passesUnification;
}
// backtrack
fnTypes[flast] = fnTypes[i];
fnTypes[i] = fnType;
fnTypes.length = fl;
}
for (let i = flast; i >= 0; i -= 1) {
const fnType = fnTypes[i];
if (!unifyFunctionTypeIsUnboxCandidate(
fnType,
queryElem,
whereClause,
mgens,
unboxingDepth + 1,
)) {
continue;
}
const generics = fnType.id !== null && fnType.id < 0 ?
whereClause[(-fnType.id) - 1] :
fnType.generics;
const bindings = fnType.bindings ?
Array.from(fnType.bindings.values()).flat() :
[];
const passesUnification = unifyFunctionTypes(
fnTypes.toSpliced(i, 1, ...bindings, ...generics),
queryElems,
whereClause,
mgens,
solutionCb,
unboxingDepth + 1,
);
if (passesUnification) {
const highlightedGenerics = passesUnification.slice(
i,
i + generics.length + bindings.length,
);
const highlightedFnType = Object.assign({}, fnType, {
generics: highlightedGenerics,
bindings: new Map([...fnType.bindings.entries()].map(([k, v]) => {
return [k, highlightedGenerics.splice(0, v.length)];
})),
});
return passesUnification.toSpliced(
i,
generics.length + bindings.length,
highlightedFnType,
);
}
}
return null;
}
/**
* This function compares two lists of generics.
*
* This function behaves very similarly to `unifyFunctionTypes`, except that it
* doesn't skip or reorder anything. This is intended to match the behavior of
* the ordinary Rust type system, so that `Vec<Allocator>` only matches an actual
* `Vec` of `Allocators` and not the implicit `Allocator` parameter that every
* `Vec` has.
*
* @param {Array<rustdoc.FunctionType>} fnTypesIn - The objects to check.
* @param {Array<rustdoc.QueryElement>} queryElems - The elements from the parsed query.
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgensIn
* - Map functions generics to query generics (never modified).
* @param {function(Map<number,number>): boolean} solutionCb
* - Called for each `mgens` solution.
* @param {number} unboxingDepth
* - Limit checks that Ty matches Vec<Ty>,
* but not Vec<ParamEnvAnd<WithInfcx<ConstTy<Interner<Ty=Ty>>>>>
*
* @return {rustdoc.HighlightedFunctionType[]|null}
* - Returns highlighted results if a match, null otherwise.
*/
function unifyGenericTypes(
fnTypesIn,
queryElems,
whereClause,
mgensIn,
solutionCb,
unboxingDepth,
) {
if (unboxingDepth >= UNBOXING_LIMIT) {
return null;
}
/**
* @type {Map<number, number>|null}
*/
const mgens = mgensIn === null ? null : new Map(mgensIn);
if (queryElems.length === 0) {
// @ts-expect-error
return solutionCb(mgens) ? fnTypesIn : null;
}
if (!fnTypesIn || fnTypesIn.length === 0) {
return null;
}
const fnType = fnTypesIn[0];
const queryElem = queryElems[0];
if (unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgens)) {
if (fnType.id !== null &&
fnType.id < 0 &&
queryElem.id !== null &&
queryElem.id < 0
) {
if (!mgens || !mgens.has(queryElem.id) ||
mgens.get(queryElem.id) === fnType.id
) {
const mgensScratch = new Map(mgens);
mgensScratch.set(queryElem.id, fnType.id);
const fnTypesRemaining = unifyGenericTypes(
fnTypesIn.slice(1),
queryElems.slice(1),
whereClause,
mgensScratch,
solutionCb,
unboxingDepth,
);
if (fnTypesRemaining) {
const highlighted = [fnType, ...fnTypesRemaining];
highlighted[0] = Object.assign({
highlighted: true,
}, fnType, {
generics: whereClause[-1 - fnType.id],
});
return highlighted;
}
}
} else {
let unifiedGenerics;
const fnTypesRemaining = unifyGenericTypes(
fnTypesIn.slice(1),
queryElems.slice(1),
whereClause,
mgens,
// @ts-expect-error
mgensScratch => {
const solution = unifyFunctionTypeCheckBindings(
fnType,
queryElem,
whereClause,
mgensScratch,
unboxingDepth,
);
if (!solution) {
return false;
}
const simplifiedGenerics = solution.simplifiedGenerics;
for (const simplifiedMgens of solution.mgens) {
unifiedGenerics = unifyGenericTypes(
simplifiedGenerics,
queryElem.generics,
whereClause,
simplifiedMgens,
solutionCb,
unboxingDepth,
);
if (unifiedGenerics !== null) {
return true;
}
}
},
unboxingDepth,
);
if (fnTypesRemaining) {
const highlighted = [fnType, ...fnTypesRemaining];
highlighted[0] = Object.assign({
highlighted: true,
}, fnType, {
generics: unifiedGenerics || fnType.generics,
});
return highlighted;
}
}
}
if (unifyFunctionTypeIsUnboxCandidate(
fnType,
queryElem,
whereClause,
mgens,
unboxingDepth + 1,
)) {
let highlightedRemaining;
if (fnType.id !== null && fnType.id < 0) {
// Where clause corresponds to `F: A + B`
// ^^^^^
// The order of the constraints doesn't matter, so
// use order-agnostic matching for it.
const highlightedGenerics = unifyFunctionTypes(
whereClause[(-fnType.id) - 1],
[queryElem],
whereClause,
mgens,
// @ts-expect-error
mgensScratch => {
const hl = unifyGenericTypes(
fnTypesIn.slice(1),
queryElems.slice(1),
whereClause,
mgensScratch,
solutionCb,
unboxingDepth,
);
if (hl) {
highlightedRemaining = hl;
}
return hl;
},
unboxingDepth + 1,
);
if (highlightedGenerics) {
return [Object.assign({
highlighted: true,
}, fnType, {
generics: highlightedGenerics,
// @ts-expect-error
}), ...highlightedRemaining];
}
} else {
const highlightedGenerics = unifyGenericTypes(
[
...Array.from(fnType.bindings.values()).flat(),
...fnType.generics,
],
[queryElem],
whereClause,
mgens,
// @ts-expect-error
mgensScratch => {
const hl = unifyGenericTypes(
fnTypesIn.slice(1),
queryElems.slice(1),
whereClause,
mgensScratch,
solutionCb,
unboxingDepth,
);
if (hl) {
highlightedRemaining = hl;
}
return hl;
},
unboxingDepth + 1,
);
if (highlightedGenerics) {
return [Object.assign({}, fnType, {
generics: highlightedGenerics,
bindings: new Map([...fnType.bindings.entries()].map(([k, v]) => {
return [k, highlightedGenerics.splice(0, v.length)];
})),
// @ts-expect-error
}), ...highlightedRemaining];
}
}
}
return null;
}
/**
* Check if this function is a match candidate.
*
* This function is all the fast checks that don't require backtracking.
* It checks that two items are not named differently, and is load-bearing for that.
* It also checks that, if the query has generics, the function type must have generics
* or associated type bindings: that's not load-bearing, but it prevents unnecessary
* backtracking later.
*
* @param {rustdoc.FunctionType} fnType
* @param {rustdoc.QueryElement} queryElem
* @param {Map<number,number>|null} mgensIn - Map query generics to function generics.
* @returns {boolean}
*/
const unifyFunctionTypeIsMatchCandidate = (fnType, queryElem, mgensIn) => {
// type filters look like `trait:Read` or `enum:Result`
if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) {
return false;
}
// fnType.id < 0 means generic
// queryElem.id < 0 does too
// mgensIn[queryElem.id] = fnType.id
if (fnType.id !== null && fnType.id < 0 && queryElem.id !== null && queryElem.id < 0) {
if (
mgensIn && mgensIn.has(queryElem.id) &&
mgensIn.get(queryElem.id) !== fnType.id
) {
return false;
}
return true;
} else {
// For these special cases, matching code need added to the inverted index.
// search_index.rs -> convert_render_type does this
if (queryElem.id === this.typeNameIdOfArrayOrSlice &&
(fnType.id === this.typeNameIdOfSlice || fnType.id === this.typeNameIdOfArray)
) {
// [] matches primitive:array or primitive:slice
// if it matches, then we're fine, and this is an appropriate match candidate
} else if (queryElem.id === this.typeNameIdOfTupleOrUnit &&
(fnType.id === this.typeNameIdOfTuple || fnType.id === this.typeNameIdOfUnit)
) {
// () matches primitive:tuple or primitive:unit
// if it matches, then we're fine, and this is an appropriate match candidate
} else if (queryElem.id === this.typeNameIdOfHof && (
fnType.id === this.typeNameIdOfFn ||
fnType.id === this.typeNameIdOfFnMut ||
fnType.id === this.typeNameIdOfFnOnce ||
fnType.id === this.typeNameIdOfFnPtr
)) {
// -> matches fn, fnonce, and fnmut
// if it matches, then we're fine, and this is an appropriate match candidate
} else if (fnType.id !== queryElem.id || queryElem.id === null) {
return false;
}
// If the query elem has generics, and the function doesn't,
// it can't match.
if ((fnType.generics.length + fnType.bindings.size) === 0 &&
queryElem.generics.length !== 0
) {
return false;
}
if (fnType.bindings.size < queryElem.bindings.size) {
return false;
}
// If the query element is a path (it contains `::`), we need to check if this
// path is compatible with the target type.
const queryElemPathLength = queryElem.pathWithoutLast.length;
if (queryElemPathLength > 0) {
const fnTypePath = fnType.path !== undefined && fnType.path !== null ?
fnType.path.split("::") : [];
// If the path provided in the query element is longer than this type,
// no need to check it since it won't match in any case.
if (queryElemPathLength > fnTypePath.length) {
return false;
}
let i = 0;
for (const path of fnTypePath) {
if (path === queryElem.pathWithoutLast[i]) {
i += 1;
if (i >= queryElemPathLength) {
break;
}
}
}
if (i < queryElemPathLength) {
// If we didn't find all parts of the path of the query element inside
// the fn type, then it's not the right one.
return false;
}
}
return true;
}
};
/**
* This function checks the associated type bindings. Any that aren't matched get converted
* to generics, and this function returns an array of the function's generics with these
* simplified bindings added to them. That is, it takes a path like this:
*
* Iterator<Item=u32>
*
* ... if queryElem itself has an `Item=` in it, then this function returns an empty array.
* But if queryElem contains no Item=, then this function returns a one-item array with the
* ID of u32 in it, and the rest of the matching engine acts as if `Iterator<u32>` were
* the type instead.
*
* @param {rustdoc.FunctionType} fnType
* @param {rustdoc.QueryElement} queryElem
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgensIn - Map query generics to function generics.
* Never modified.
* @param {number} unboxingDepth
* @returns {false|{
* mgens: [Map<number,number>|null], simplifiedGenerics: rustdoc.FunctionType[]
* }}
*/
function unifyFunctionTypeCheckBindings(
fnType,
queryElem,
whereClause,
mgensIn,
unboxingDepth,
) {
if (fnType.bindings.size < queryElem.bindings.size) {
return false;
}
let simplifiedGenerics = fnType.generics || [];
if (fnType.bindings.size > 0) {
let mgensSolutionSet = [mgensIn];
for (const [name, constraints] of queryElem.bindings.entries()) {
if (mgensSolutionSet.length === 0) {
return false;
}
if (!fnType.bindings.has(name)) {
return false;
}
const fnTypeBindings = fnType.bindings.get(name);
mgensSolutionSet = mgensSolutionSet.flatMap(mgens => {
/** @type{Array<Map<number, number> | null>} */
const newSolutions = [];
unifyFunctionTypes(
// @ts-expect-error
fnTypeBindings,
constraints,
whereClause,
mgens,
newMgens => {
newSolutions.push(newMgens);
// return `false` makes unifyFunctionTypes return the full set of
// possible solutions
return false;
},
unboxingDepth,
);
return newSolutions;
});
}
if (mgensSolutionSet.length === 0) {
return false;
}
const binds = Array.from(fnType.bindings.entries()).flatMap(entry => {
const [name, constraints] = entry;
if (queryElem.bindings.has(name)) {
return [];
} else {
return constraints;
}
});
if (simplifiedGenerics.length > 0) {
simplifiedGenerics = [...binds, ...simplifiedGenerics];
} else {
simplifiedGenerics = binds;
}
// @ts-expect-error
return { simplifiedGenerics, mgens: mgensSolutionSet };
}
return { simplifiedGenerics, mgens: [mgensIn] };
}
/**
* @param {rustdoc.FunctionType} fnType
* @param {rustdoc.QueryElement} queryElem
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgens - Map query generics to function generics.
* @param {number} unboxingDepth
* @returns {boolean}
*/
function unifyFunctionTypeIsUnboxCandidate(
fnType,
queryElem,
whereClause,
mgens,
unboxingDepth,
) {
if (unboxingDepth >= UNBOXING_LIMIT) {
return false;
}
if (fnType.id !== null && fnType.id < 0) {
if (!whereClause) {
return false;
}
// This is only a potential unbox if the search query appears in the where clause
// for example, searching `Read -> usize` should find
// `fn read_all<R: Read>(R) -> Result<usize>`
// generic `R` is considered "unboxed"
return checkIfInList(
whereClause[(-fnType.id) - 1],
queryElem,
whereClause,
mgens,
unboxingDepth,
);
} else if (fnType.unboxFlag &&
(fnType.generics.length > 0 || fnType.bindings.size > 0)) {
const simplifiedGenerics = [
...fnType.generics,
...Array.from(fnType.bindings.values()).flat(),
];
return checkIfInList(
simplifiedGenerics,
queryElem,
whereClause,
mgens,
unboxingDepth,
);
}
return false;
}
/**
* This function checks if the given list contains any
* (non-generic) types mentioned in the query.
*
* @param {rustdoc.QueryElement[]} elems
* @param {rustdoc.FunctionType[]} list - A list of function types.
* @param {rustdoc.FunctionType[][]} where_clause - Trait bounds for generic items.
*/
function containsTypeFromQuery(elems, list, where_clause) {
if (!list) return false;
for (const ty of elems) {
if (ty.id !== null && ty.id < 0) {
continue;
}
if (checkIfInList(list, ty, where_clause, null, 0)) {
return true;
}
}
return false;
}
/**
* This function checks if the object (`row`) matches the given type (`elem`) and its
* generics (if any).
*
* @param {rustdoc.FunctionType[]} list
* @param {rustdoc.QueryElement} elem - The element from the parsed query.
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgens - Map functions generics to query generics.
* @param {number} unboxingDepth
*
* @return {boolean} - Returns true if found, false otherwise.
*/
function checkIfInList(list, elem, whereClause, mgens, unboxingDepth) {
for (const entry of list) {
if (checkType(entry, elem, whereClause, mgens, unboxingDepth)) {
return true;
}
}
return false;
}
/**
* This function checks if the object (`row`) matches the given type (`elem`) and its
* generics (if any).
*
* @param {rustdoc.FunctionType} row
* @param {rustdoc.QueryElement} elem - The element from the parsed query.
* @param {rustdoc.FunctionType[][]} whereClause - Trait bounds for generic items.
* @param {Map<number,number>|null} mgens - Map query generics to function generics.
*
* @return {boolean} - Returns true if the type matches, false otherwise.
*/
// @ts-expect-error
const checkType = (row, elem, whereClause, mgens, unboxingDepth) => {
if (unboxingDepth >= UNBOXING_LIMIT) {
return false;
}
if (row.id !== null && elem.id !== null &&
row.id > 0 && elem.id > 0 && elem.pathWithoutLast.length === 0 &&
row.generics.length === 0 && elem.generics.length === 0 &&
row.bindings.size === 0 && elem.bindings.size === 0 &&
// special case
elem.id !== this.typeNameIdOfArrayOrSlice &&
elem.id !== this.typeNameIdOfHof &&
elem.id !== this.typeNameIdOfTupleOrUnit
) {
return row.id === elem.id && typePassesFilter(elem.typeFilter, row.ty);
} else {
// @ts-expect-error
return unifyFunctionTypes(
[row],
[elem],
whereClause,
mgens,
() => true,
unboxingDepth,
);
}
};
/**
* Check a query solution for conflicting generics.
*/
// @ts-expect-error
const checkTypeMgensForConflict = mgens => {
if (!mgens) {
return true;
}
const fnTypes = new Set();
for (const [_qid, fid] of mgens) {
if (fnTypes.has(fid)) {
return false;
}
fnTypes.add(fid);
}
return true;
};
/**
* Compute an "edit distance" that ignores missing path elements.
* @param {string[]} contains search query path
* @param {string[]} path indexed page path
* @returns {null|number} edit distance
*/
function checkPath(contains, path) {
if (contains.length === 0) {
return 0;
}
const maxPathEditDistance = Math.floor(
contains.reduce((acc, next) => acc + next.length, 0) / 3,
);
let ret_dist = maxPathEditDistance + 1;
const length = path.length;
const clength = contains.length;
pathiter: for (let i = length - clength; i >= 0; i -= 1) {
let dist_total = 0;
for (let x = 0; x < clength; ++x) {
const [p, c] = [path[i + x], contains[x]];
if (Math.floor((p.length - c.length) / 3) <= maxPathEditDistance &&
p.indexOf(c) !== -1
) {
// discount distance on substring match
dist_total += Math.floor((p.length - c.length) / 3);
} else {
const dist = editDistance(p, c, maxPathEditDistance);
if (dist > maxPathEditDistance) {
continue pathiter;
}
dist_total += dist;
}
}
ret_dist = Math.min(ret_dist, Math.round(dist_total / clength));
}
return ret_dist > maxPathEditDistance ? null : ret_dist;
}
/**
* Compute an "edit distance" that ignores missing path elements.
* @param {string[]} contains search query path
* @param {rustdoc.Row} row indexed item
* @returns {null|number} edit distance
*/
function checkRowPath(contains, row) {
if (contains.length === 0) {
return 0;
}
const path = row.modulePath.split("::");
if (row.parent && row.parent.name) {
path.push(row.parent.name.toLowerCase());
}
return checkPath(contains, path);
}
/**
*
* @param {number} filter
* @param {rustdoc.ItemType} type
* @returns
*/
function typePassesFilter(filter, type) {
// No filter or Exact mach
if (filter <= NO_TYPE_FILTER || filter === type) return true;
// Match related items
const name = itemTypes[type];
switch (itemTypes[filter]) {
case "constant":
return name === "associatedconstant";
case "fn":
return name === "method" || name === "tymethod";
case "type":
return name === "primitive" || name === "associatedtype";
case "trait":
return name === "traitalias";
}
// No match
return false;
}
const innerRunNameQuery =
/**
* @this {DocSearch}
* @param {string} currentCrate
* @returns {AsyncGenerator<rustdoc.ResultObject>}
*/
async function*(currentCrate) {
const index = this.database.getIndex("normalizedName");
if (!index) {
return;
}
const idDuplicates = new Set();
const pathDuplicates = new Set();
let count = 0;
const prefixResults = [];
const normalizedUserQuery = parsedQuery.userQuery
.replace(/[_"]/g, "")
.toLowerCase();
/**
* @param {string} name
* @param {number} alias
* @param {number} dist
* @param {number} index
* @returns {Promise<rustdoc.PlainResultObject?>}
*/
const handleAlias = async(name, alias, dist, index) => {
return {
id: alias,
dist,
path_dist: 0,
index,
alias: name,
is_alias: true,
elems: [], // only used in type-based queries
returned: [], // only used in type-based queries
original: await this.getRow(alias),
};
};
/**
* @param {Promise<rustdoc.PlainResultObject|null>[]} data
* @returns {AsyncGenerator<rustdoc.ResultObject, boolean>}
*/
const flush = async function* (data) {
const satr = sortAndTransformResults(
await Promise.all(data),
null,
currentCrate,
pathDuplicates,
);
data.length = 0;
for await (const processed of satr) {
yield processed;
count += 1;
if ((count & 0x7F) === 0) {
await yieldToBrowser();
}
if (count >= MAX_RESULTS) {
return true;
}
}
return false;
};
const aliasResults = await index.search(normalizedUserQuery);
if (aliasResults) {
for (const id of aliasResults.matches().entries()) {
const [name, alias] = await Promise.all([
this.getName(id),
this.getAliasTarget(id),
]);
if (name !== null &&
alias !== null &&
!idDuplicates.has(id) &&
name.replace(/[_"]/g, "").toLowerCase() === normalizedUserQuery
) {
prefixResults.push(handleAlias(name, alias, 0, 0));
idDuplicates.add(id);
}
}
}
if (parsedQuery.error !== null || parsedQuery.elems.length === 0) {
yield* flush(prefixResults);
return;
}
const elem = parsedQuery.elems[0];
const typeFilter = itemTypeFromName(elem.typeFilter);
/**
* @param {number} id
* @returns {Promise<rustdoc.PlainResultObject?>}
*/
const handleNameSearch = async id => {
const row = await this.getRow(id);
if (!row || !row.entry) {
return null;
}
if (!typePassesFilter(typeFilter, row.ty) ||
(filterCrates !== null && row.crate !== filterCrates)) {
return null;
}
/** @type {number|null} */
let pathDist = 0;
if (elem.fullPath.length > 1) {
pathDist = checkRowPath(elem.pathWithoutLast, row);
if (pathDist === null) {
return null;
}
}
if (parsedQuery.literalSearch) {
return row.name.toLowerCase() === elem.pathLast ? {
id,
dist: 0,
path_dist: 0,
index: 0,
elems: [], // only used in type-based queries
returned: [], // only used in type-based queries
is_alias: false,
} : null;
} else {
return {
id,
dist: editDistance(
row.normalizedName,
elem.normalizedPathLast,
maxEditDistance,
),
path_dist: pathDist,
index: row.normalizedName.indexOf(elem.normalizedPathLast),
elems: [], // only used in type-based queries
returned: [], // only used in type-based queries
is_alias: false,
};
}
};
if (elem.normalizedPathLast === "") {
// faster full-table scan for this specific case.
const nameData = this.database.getData("name");
const l = nameData ? nameData.length : 0;
for (let id = 0; id < l; ++id) {
if (!idDuplicates.has(id)) {
idDuplicates.add(id);
prefixResults.push(handleNameSearch(id));
}
if (yield* flush(prefixResults)) {
return;
}
}
return;
}
const results = await index.search(elem.normalizedPathLast);
if (results) {
for await (const result of results.prefixMatches()) {
for (const id of result.entries()) {
if (!idDuplicates.has(id)) {
idDuplicates.add(id);
prefixResults.push(handleNameSearch(id));
const [name, alias] = await Promise.all([
this.getName(id),
this.getAliasTarget(id),
]);
if (name !== null && alias !== null) {
prefixResults.push(handleAlias(name, alias, 0, 0));
}
}
}
if (yield* flush(prefixResults)) {
return;
}
}
if (yield* flush(prefixResults)) {
return;
}
}
const levSearchResults = index.searchLev(elem.normalizedPathLast);
const levResults = [];
for await (const levResult of levSearchResults) {
for (const id of levResult.matches().entries()) {
if (!idDuplicates.has(id)) {
idDuplicates.add(id);
levResults.push(handleNameSearch(id));
const [name, alias] = await Promise.all([
this.getName(id),
this.getAliasTarget(id),
]);
if (name !== null && alias !== null) {
levResults.push(handleAlias(
name,
alias,
editDistance(elem.normalizedPathLast, name, maxEditDistance),
name.indexOf(elem.normalizedPathLast),
));
}
}
}
}
yield* flush(levResults);
if (results) {
const substringResults = [];
for await (const result of results.substringMatches()) {
for (const id of result.entries()) {
if (!idDuplicates.has(id)) {
idDuplicates.add(id);
substringResults.push(handleNameSearch(id));
const [name, alias] = await Promise.all([
this.getName(id),
this.getAliasTarget(id),
]);
if (name !== null && alias !== null) {
levResults.push(handleAlias(
name,
alias,
editDistance(
elem.normalizedPathLast,
name,
maxEditDistance,
),
name.indexOf(elem.normalizedPathLast),
));
}
}
}
if (yield* flush(substringResults)) {
return;
}
}
}
}
.bind(this);
const innerRunTypeQuery =
/**
* @this {DocSearch}
* @param {rustdoc.ParserQueryElement[]} inputs
* @param {rustdoc.ParserQueryElement[]} output
* @param {"sig"|"elems"|"returned"|null} typeInfo
* @param {string} currentCrate
* @returns {AsyncGenerator<rustdoc.ResultObject>}
*/
async function*(inputs, output, typeInfo, currentCrate) {
const index = this.database.getIndex("normalizedName");
if (!index) {
return;
}
/** @type {Map<string, number>} */
const genericMap = new Map();
/**
* @template Q
* @typedef {{
* invertedIndex: stringdex.RoaringBitmap[],
* queryElem: Q,
* }} PostingsList
*/
/** @type {stringdex.RoaringBitmap[]} */
const empty_inverted_index = [];
/** @type {PostingsList<any>[]} */
const empty_postings_list = [];
/** @type {stringdex.RoaringBitmap[]} */
const everything_inverted_index = [];
for (let i = 0; i < 64; ++i) {
everything_inverted_index.push(RoaringBitmap.everything());
}
/**
* @type {PostingsList<rustdoc.QueryElement[]>}
*/
const everything_postings_list = {
invertedIndex: everything_inverted_index,
queryElem: [],
};
/**
* @type {PostingsList<rustdoc.QueryElement[]>[]}
*/
const nested_everything_postings_list = [everything_postings_list];
/**
* @param {...stringdex.RoaringBitmap[]} idx
* @returns {stringdex.RoaringBitmap[]}
*/
const intersectInvertedIndexes = (...idx) => {
let i = 0;
const l = idx.length;
while (i < l - 1 && idx[i] === everything_inverted_index) {
i += 1;
}
const result = [...idx[i]];
for (; i < l; ++i) {
if (idx[i] === everything_inverted_index) {
continue;
}
if (idx[i].length < result.length) {
result.length = idx[i].length;
}
for (let j = 0; j < result.length; ++j) {
result[j] = result[j].intersection(idx[i][j]);
}
}
return result;
};
/**
* Fetch a bitmap of potentially-matching functions,
* plus a list of query elements annotated with the correct IDs.
*
* More than one ID can exist because, for example, q=`Iter` can match
* `std::vec::Iter`, or `std::btree_set::Iter`, or anything else, and those
* items different IDs. What's worse, q=`Iter<Iter>` has N**2 possible
* matches, because it could be `vec::Iter<btree_set::Iter>`,
* `btree_set::Iter<vec::Iter>`, `vec::Iter<vec::Iter>`,
* `btree_set::Iter<btree_set::Iter>`,
* or anything else. This function returns all possible permutations.
*
* @param {rustdoc.ParserQueryElement|null} elem
* @returns {Promise<PostingsList<rustdoc.QueryElement>[]>}
*/
const unpackPostingsList = async elem => {
if (!elem) {
return empty_postings_list;
}
const typeFilter = itemTypeFromName(elem.typeFilter);
const searchResults = await index.search(elem.normalizedPathLast);
/**
* @type {Promise<[
* number,
* string|null,
* rustdoc.TypeData|null,
* rustdoc.PathData|null,
* ]>[]}
* */
const typePromises = [];
if (typeFilter !== TY_GENERIC && searchResults) {
for (const id of searchResults.matches().entries()) {
typePromises.push(Promise.all([
this.getName(id),
this.getTypeData(id),
this.getPathData(id),
]).then(([name, typeData, pathData]) =>
[id, name, typeData, pathData]));
}
}
const types = (await Promise.all(typePromises))
.filter(([_id, name, ty, path]) =>
name !== null && name.toLowerCase() === elem.pathLast &&
ty && !ty.invertedFunctionSignatureIndex.every(bitmap => {
return bitmap.isEmpty();
}) &&
path && path.ty !== TY_ASSOCTYPE &&
(elem.pathWithoutLast.length === 0 ||
checkPath(
elem.pathWithoutLast,
path.modulePath.split("::"),
) === 0),
);
if (types.length === 0) {
const areGenericsAllowed = typeFilter === TY_GENERIC || (
typeFilter === -1 &&
(parsedQuery.totalElems > 1 || parsedQuery.hasReturnArrow) &&
elem.pathWithoutLast.length === 0 &&
elem.generics.length === 0 &&
elem.bindings.size === 0
);
if (typeFilter !== TY_GENERIC &&
(elem.name.length >= 3 || !areGenericsAllowed)
) {
/** @type {string|null} */
let chosenName = null;
/** @type {rustdoc.TypeData[]} */
let chosenType = [];
/** @type {rustdoc.PathData[]} */
let chosenPath = [];
/** @type {number[]} */
let chosenId = [];
let chosenDist = Number.MAX_SAFE_INTEGER;
const levResults = index.searchLev(elem.normalizedPathLast);
for await (const searchResults of levResults) {
for (const id of searchResults.matches().entries()) {
const [name, ty, path] = await Promise.all([
this.getName(id),
this.getTypeData(id),
this.getPathData(id),
]);
if (name !== null && ty !== null && path !== null &&
!ty.invertedFunctionSignatureIndex.every(bitmap => {
return bitmap.isEmpty();
}) &&
path.ty !== TY_ASSOCTYPE
) {
let dist = editDistance(
name,
elem.pathLast,
maxEditDistance,
);
if (elem.pathWithoutLast.length !== 0) {
const pathDist = checkPath(
elem.pathWithoutLast,
path.modulePath.split("::"),
);
// guaranteed to be higher than the path limit
dist += pathDist === null ?
Number.MAX_SAFE_INTEGER :
pathDist;
}
if (name === chosenName) {
chosenId.push(id);
chosenType.push(ty);
chosenPath.push(path);
} else if (dist < chosenDist) {
chosenName = name;
chosenId = [id];
chosenType = [ty];
chosenPath = [path];
chosenDist = dist;
}
}
}
if (chosenId.length !== 0) {
// searchLev returns results in order
// if we have working matches, we're done
break;
}
}
if (areGenericsAllowed) {
parsedQuery.proposeCorrectionFrom = elem.name;
parsedQuery.proposeCorrectionTo = chosenName;
} else {
parsedQuery.correction = chosenName;
for (let i = 0; i < chosenType.length; ++i) {
types.push([
chosenId[i],
chosenName,
chosenType[i],
chosenPath[i],
]);
}
}
}
if (areGenericsAllowed) {
let genericId = genericMap.get(elem.normalizedPathLast);
if (genericId === undefined) {
genericId = genericMap.size;
genericMap.set(elem.normalizedPathLast, genericId);
}
return [{
invertedIndex: await this.getGenericInvertedIndex(genericId),
queryElem: {
name: elem.name,
id: (-genericId) - 1,
typeFilter: TY_GENERIC,
generics: [],
bindings: EMPTY_BINDINGS_MAP,
fullPath: elem.fullPath,
pathLast: elem.pathLast,
normalizedPathLast: elem.normalizedPathLast,
pathWithoutLast: elem.pathWithoutLast,
},
}];
}
}
types.sort(([_i, name1, _t, pathData1], [_i2, name2, _t2, pathData2]) => {
const p1 = !pathData1 ? "" : pathData1.modulePath;
const p2 = !pathData2 ? "" : pathData2.modulePath;
const n1 = name1 === null ? "" : name1;
const n2 = name2 === null ? "" : name2;
if (p1.length !== p2.length) {
return p1.length > p2.length ? +1 : -1;
}
if (n1.length !== n2.length) {
return n1.length > n2.length ? +1 : -1;
}
if (n1 !== n2) {
return n1 > n2 ? +1 : -1;
}
if (p1 !== p2) {
return p1 > p2 ? +1 : -1;
}
return 0;
});
/** @type {PostingsList<rustdoc.QueryElement>[]} */
const results = [];
for (const [id, _name, typeData] of types) {
if (!typeData || typeData.invertedFunctionSignatureIndex.every(bitmap => {
return bitmap.isEmpty();
})) {
continue;
}
const upla = await unpackPostingsListAll(elem.generics);
const uplb = await unpackPostingsListBindings(elem.bindings);
for (const {invertedIndex: genericsIdx, queryElem: generics} of upla) {
for (const {invertedIndex: bindingsIdx, queryElem: bindings} of uplb) {
results.push({
invertedIndex: intersectInvertedIndexes(
typeData.invertedFunctionSignatureIndex,
genericsIdx,
bindingsIdx,
),
queryElem: {
name: elem.name,
id,
typeFilter,
generics,
bindings,
fullPath: elem.fullPath,
pathLast: elem.pathLast,
normalizedPathLast: elem.normalizedPathLast,
pathWithoutLast: elem.pathWithoutLast,
},
});
if ((results.length & 0x7F) === 0) {
await yieldToBrowser();
}
}
}
}
return results;
};
/**
* Fetch all possible matching permutations of a list of query elements.
*
* The empty list returns an "identity postings list", with a bitmap that
* matches everything and an empty list of elems. This allows you to safely
* take the intersection of this bitmap.
*
* @param {(rustdoc.ParserQueryElement|null)[]|null} elems
* @returns {Promise<PostingsList<rustdoc.QueryElement[]>[]>}
*/
const unpackPostingsListAll = async elems => {
if (!elems || elems.length === 0) {
return nested_everything_postings_list;
}
const [firstPostingsList, remainingAll] = await Promise.all([
unpackPostingsList(elems[0]),
unpackPostingsListAll(elems.slice(1)),
]);
/** @type {PostingsList<rustdoc.QueryElement[]>[]} */
const results = [];
for (const {
invertedIndex: firstIdx,
queryElem: firstElem,
} of firstPostingsList) {
for (const {
invertedIndex: remainingIdx,
queryElem: remainingElems,
} of remainingAll) {
results.push({
invertedIndex: intersectInvertedIndexes(firstIdx, remainingIdx),
queryElem: [firstElem, ...remainingElems],
});
if ((results.length & 0x7F) === 0) {
await yieldToBrowser();
}
}
}
return results;
};
/**
* Fetch all possible matching permutations of a map query element bindings.
*
* The empty list returns an "identity postings list", with a bitmap that
* matches everything and an empty list of elems. This allows you to safely
* take the intersection of this bitmap.
*
* Heads up! This function mutates the Map that you provide.
* Before passing an actual parser item to it, make sure to clone the map.
*
* @param {Map<string, rustdoc.ParserQueryElement[]>} elems
* @returns {Promise<PostingsList<
* Map<number, rustdoc.QueryElement[]>,
* >[]>}
*/
const unpackPostingsListBindings = async elems => {
if (!elems) {
return [{
invertedIndex: everything_inverted_index,
queryElem: new Map(),
}];
}
const firstKey = elems.keys().next().value;
if (firstKey === undefined) {
return [{
invertedIndex: everything_inverted_index,
queryElem: new Map(),
}];
}
const firstList = elems.get(firstKey);
if (firstList === undefined) {
return [{
invertedIndex: everything_inverted_index,
queryElem: new Map(),
}];
}
const firstKeyIds = await index.search(firstKey);
if (!firstKeyIds) {
// User specified a non-existent key.
return [{
invertedIndex: empty_inverted_index,
queryElem: new Map(),
}];
}
elems.delete(firstKey);
const [firstPostingsList, remainingAll] = await Promise.all([
unpackPostingsListAll(firstList),
unpackPostingsListBindings(elems),
]);
/** @type {PostingsList<Map<number, rustdoc.QueryElement[]>>[]} */
const results = [];
for (const keyId of firstKeyIds.matches().entries()) {
for (const {
invertedIndex: firstIdx,
queryElem: firstElem,
} of firstPostingsList) {
for (const {
invertedIndex: remainingIdx,
queryElem: remainingElems,
} of remainingAll) {
const elems = new Map(remainingElems);
elems.set(keyId, firstElem);
results.push({
invertedIndex: intersectInvertedIndexes(firstIdx, remainingIdx),
queryElem: elems,
});
if ((results.length & 0x7F) === 0) {
await yieldToBrowser();
}
}
}
}
elems.set(firstKey, firstList);
if (results.length === 0) {
// User specified a non-existent key.
return [{
invertedIndex: empty_inverted_index,
queryElem: new Map(),
}];
}
return results;
};
// finally, we can do the actual unification loop
const [allInputs, allOutput] = await Promise.all([
unpackPostingsListAll(inputs),
unpackPostingsListAll(output),
]);
let checkCounter = 0;
/**
* Finally, we can perform an incremental search, sorted by the number of
* entries that match a given query.
*
* The outer list gives the number of elements. The inner one is separate
* for each distinct name resolution.
*
* @type {{
* bitmap: stringdex.RoaringBitmap,
* inputs: rustdoc.QueryElement[],
* output: rustdoc.QueryElement[],
* }[][]}
*/
const queryPlan = [];
for (const {invertedIndex: inputsIdx, queryElem: inputs} of allInputs) {
for (const {invertedIndex: outputIdx, queryElem: output} of allOutput) {
const invertedIndex = intersectInvertedIndexes(inputsIdx, outputIdx);
for (const [size, bitmap] of invertedIndex.entries()) {
checkCounter += 1;
if ((checkCounter & 0x7F) === 0) {
await yieldToBrowser();
}
if (!queryPlan[size]) {
queryPlan[size] = [];
}
queryPlan[size].push({
bitmap, inputs, output,
});
}
}
}
const resultPromises = [];
const dedup = new Set();
let resultCounter = 0;
const isReturnTypeQuery = inputs.length === 0;
/** @type {rustdoc.PlainResultObject[]} */
const pushToBottom = [];
plan: for (const queryStep of queryPlan) {
for (const {bitmap, inputs, output} of queryStep) {
for (const id of bitmap.entries()) {
checkCounter += 1;
if ((checkCounter & 0x7F) === 0) {
await yieldToBrowser();
}
resultPromises.push(this.getFunctionData(id).then(async fnData => {
if (!fnData || !fnData.functionSignature) {
return null;
}
checkCounter += 1;
if ((checkCounter & 0x7F) === 0) {
await yieldToBrowser();
}
const functionSignature = fnData.functionSignature;
if (!unifyFunctionTypes(
functionSignature.inputs,
inputs,
functionSignature.where_clause,
null,
mgens => {
return !!unifyFunctionTypes(
functionSignature.output,
output,
functionSignature.where_clause,
mgens,
checkTypeMgensForConflict,
0, // unboxing depth
);
},
0, // unboxing depth
)) {
return null;
}
const result = {
id,
dist: fnData.elemCount,
path_dist: 0,
index: -1,
elems: inputs,
returned: output,
is_alias: false,
};
const entry = await this.getEntryData(id);
if ((entry && !isFnLikeTy(entry.ty)) ||
(isReturnTypeQuery &&
functionSignature &&
containsTypeFromQuery(
output,
functionSignature.inputs,
functionSignature.where_clause,
)
)
) {
pushToBottom.push(result);
return null;
}
return result;
}));
}
}
for await (const result of sortAndTransformResults(
await Promise.all(resultPromises),
typeInfo,
currentCrate,
dedup,
)) {
if (resultCounter >= MAX_RESULTS) {
break plan;
}
yield result;
resultCounter += 1;
}
resultPromises.length = 0;
}
if (resultCounter >= MAX_RESULTS) {
return;
}
for await (const result of sortAndTransformResults(
await Promise.all(pushToBottom),
typeInfo,
currentCrate,
dedup,
)) {
if (resultCounter >= MAX_RESULTS) {
break;
}
yield result;
resultCounter += 1;
}
}
.bind(this);
if (parsedQuery.foundElems === 1 && !parsedQuery.hasReturnArrow) {
// We never want the main tab to delay behind the other two tabs.
// This is a bit of a hack (because JS's scheduler doesn't have much of an API),
// along with making innerRunTypeQuery yield to the UI thread.
const {
promise: donePromise,
resolve: doneResolve,
reject: doneReject,
} = Promise.withResolvers();
const doneTimeout = timeout(250);
return {
"in_args": (async function*() {
await Promise.race([donePromise, doneTimeout]);
yield* innerRunTypeQuery(parsedQuery.elems, [], "elems", currentCrate);
})(),
"returned": (async function*() {
await Promise.race([donePromise, doneTimeout]);
yield* innerRunTypeQuery([], parsedQuery.elems, "returned", currentCrate);
})(),
"others": (async function*() {
try {
yield* innerRunNameQuery(currentCrate);
doneResolve(null);
} catch (e) {
doneReject(e);
throw e;
}
})(),
"query": parsedQuery,
};
} else if (parsedQuery.error !== null) {
return {
"in_args": (async function*() {})(),
"returned": (async function*() {})(),
"others": innerRunNameQuery(currentCrate),
"query": parsedQuery,
};
} else {
const typeInfo = parsedQuery.elems.length === 0 ?
"returned" : (
parsedQuery.returned.length === 0 ? "elems" : "sig"
);
return {
"in_args": (async function*() {})(),
"returned": (async function*() {})(),
"others": parsedQuery.foundElems === 0 ?
(async function*() {})() :
innerRunTypeQuery(
parsedQuery.elems,
parsedQuery.returned,
typeInfo,
currentCrate,
),
"query": parsedQuery,
};
}
}
}
// ==================== Core search logic end ====================
/** @type {DocSearch} */
let docSearch;
const longItemTypes = [
"keyword",
"primitive type",
"module",
"extern crate",
"re-export",
"struct",
"enum",
"function",
"type alias",
"static",
"trait",
"",
"trait method",
"method",
"struct field",
"enum variant",
"macro",
"assoc type",
"constant",
"assoc const",
"union",
"foreign type",
"existential type",
"attribute macro",
"derive macro",
"trait alias",
];
// @ts-expect-error
let currentResults;
// In the search display, allows to switch between tabs.
// @ts-expect-error
function printTab(nb) {
let iter = 0;
let foundCurrentTab = false;
let foundCurrentResultSet = false;
// @ts-expect-error
onEachLazy(document.getElementById("search-tabs").childNodes, elem => {
if (nb === iter) {
addClass(elem, "selected");
foundCurrentTab = true;
} else {
removeClass(elem, "selected");
}
iter += 1;
});
const isTypeSearch = (nb > 0 || iter === 1);
iter = 0;
// @ts-expect-error
onEachLazy(document.getElementById("results").childNodes, elem => {
if (nb === iter) {
addClass(elem, "active");
foundCurrentResultSet = true;
} else {
removeClass(elem, "active");
}
iter += 1;
});
if (foundCurrentTab && foundCurrentResultSet) {
searchState.currentTab = nb;
// Corrections only kick in on type-based searches.
const correctionsElem = document.getElementsByClassName("search-corrections");
if (isTypeSearch) {
removeClass(correctionsElem[0], "hidden");
} else {
addClass(correctionsElem[0], "hidden");
}
} else if (nb !== 0) {
printTab(0);
}
}
/**
* Build an URL with search parameters.
*
* @param {string} search - The current search being performed.
* @param {string|null} filterCrates - The current filtering crate (if any).
*
* @return {string}
*/
function buildUrl(search, filterCrates) {
let extra = "?search=" + encodeURIComponent(search);
if (filterCrates !== null) {
extra += "&filter-crate=" + encodeURIComponent(filterCrates);
}
return getNakedUrl() + extra + window.location.hash;
}
/**
* Return the filtering crate or `null` if there is none.
*
* @return {string|null}
*/
function getFilterCrates() {
const elem = document.getElementById("crate-search");
// @ts-expect-error
if (elem && elem.value !== "all crates") {
// @ts-expect-error
return elem.value;
}
return null;
}
// @ts-expect-error
function nextTab(direction) {
const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length;
window.searchState.focusedByTab[searchState.currentTab] = document.activeElement;
printTab(next);
focusSearchResult();
}
// Focus the first search result on the active tab, or the result that
// was focused last time this tab was active.
function focusSearchResult() {
const target = searchState.focusedByTab[searchState.currentTab] ||
document.querySelectorAll(".search-results.active a").item(0) ||
document.querySelectorAll("#search-tabs button").item(searchState.currentTab);
searchState.focusedByTab[searchState.currentTab] = null;
if (target && target instanceof HTMLElement) {
target.focus();
}
}
/**
* Render a set of search results for a single tab.
* @param {AsyncGenerator<rustdoc.ResultObject>} results - The search results for this tab
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {boolean} display - True if this is the active tab
* @param {function(number, HTMLElement): any} finishedCallback
* @param {boolean} isTypeSearch
* @returns {Promise<HTMLElement>}
*/
async function addTab(results, query, display, finishedCallback, isTypeSearch) {
const extraClass = display ? " active" : "";
/** @type {HTMLElement} */
let output = document.createElement("ul");
output.className = "search-results " + extraClass;
let count = 0;
/** @type {Promise<string|null>[]} */
const descList = [];
/** @param {rustdoc.ResultObject} obj */
const addNextResultToOutput = async obj => {
count += 1;
const name = obj.item.name;
const type = itemTypes[obj.item.ty];
const longType = longItemTypes[obj.item.ty];
const typeName = longType.length !== 0 ? `${longType}` : "?";
const link = document.createElement("a");
link.className = "result-" + type;
link.href = obj.href;
const resultName = document.createElement("span");
resultName.className = "result-name";
resultName.insertAdjacentHTML(
"beforeend",
`<span class="typename">${typeName}</span>`);
link.appendChild(resultName);
let alias = " ";
if (obj.alias !== undefined) {
alias = ` <div class="alias">\
<b>${obj.alias}</b><i class="grey">&nbsp;- see&nbsp;</i>\
</div>`;
}
resultName.insertAdjacentHTML(
"beforeend",
`<div class="path">${alias}\
${obj.displayPath}<span class="${type}">${name}</span>\
</div>`);
const description = document.createElement("div");
description.className = "desc";
obj.desc.then(desc => {
if (desc !== null) {
description.insertAdjacentHTML("beforeend", desc);
}
});
descList.push(obj.desc);
if (obj.displayTypeSignature) {
const {type, mappedNames, whereClause} = await obj.displayTypeSignature;
const displayType = document.createElement("div");
type.forEach((value, index) => {
if (index % 2 !== 0) {
const highlight = document.createElement("strong");
highlight.appendChild(document.createTextNode(value));
displayType.appendChild(highlight);
} else {
displayType.appendChild(document.createTextNode(value));
}
});
if (mappedNames.size > 0 || whereClause.size > 0) {
let addWhereLineFn = () => {
const line = document.createElement("div");
line.className = "where";
line.appendChild(document.createTextNode("where"));
displayType.appendChild(line);
addWhereLineFn = () => {};
};
for (const [qname, name] of mappedNames) {
// don't care unless the generic name is different
if (name === qname) {
continue;
}
addWhereLineFn();
const line = document.createElement("div");
line.className = "where";
line.appendChild(document.createTextNode(` ${qname} matches `));
const lineStrong = document.createElement("strong");
lineStrong.appendChild(document.createTextNode(name));
line.appendChild(lineStrong);
displayType.appendChild(line);
}
for (const [name, innerType] of whereClause) {
// don't care unless there's at least one highlighted entry
if (innerType.length <= 1) {
continue;
}
addWhereLineFn();
const line = document.createElement("div");
line.className = "where";
line.appendChild(document.createTextNode(` ${name}: `));
innerType.forEach((value, index) => {
if (index % 2 !== 0) {
const highlight = document.createElement("strong");
highlight.appendChild(document.createTextNode(value));
line.appendChild(highlight);
} else {
line.appendChild(document.createTextNode(value));
}
});
displayType.appendChild(line);
}
}
displayType.className = "type-signature";
link.appendChild(displayType);
}
link.appendChild(description);
output.appendChild(link);
results.next().then(async nextResult => {
if (nextResult.value) {
addNextResultToOutput(nextResult.value);
} else {
await Promise.all(descList);
// need to make sure the element is shown before
// running this callback
yieldToBrowser().then(() => finishedCallback(count, output));
}
});
};
const firstResult = await results.next();
let correctionOutput = "";
if (query.correction !== null && isTypeSearch) {
const orig = query.returned.length > 0
? query.returned[0].name
: query.elems[0].name;
correctionOutput = "<h3 class=\"search-corrections\">" +
`Type "${orig}" not found. ` +
"Showing results for closest type name " +
`"${query.correction}" instead.</h3>`;
}
if (query.proposeCorrectionFrom !== null && isTypeSearch) {
const orig = query.proposeCorrectionFrom;
const targ = query.proposeCorrectionTo;
correctionOutput = "<h3 class=\"search-corrections\">" +
`Type "${orig}" not found and used as generic parameter. ` +
`Consider searching for "${targ}" instead.</h3>`;
}
if (firstResult.value) {
if (correctionOutput !== "") {
const h3 = document.createElement("h3");
h3.innerHTML = correctionOutput;
output.appendChild(h3);
}
await addNextResultToOutput(firstResult.value);
} else {
output = document.createElement("div");
if (correctionOutput !== "") {
const h3 = document.createElement("h3");
h3.innerHTML = correctionOutput;
output.appendChild(h3);
}
output.className = "search-failed" + extraClass;
const dlroChannel = `https://doc.rust-lang.org/${getVar("channel")}`;
if (query.userQuery !== "") {
output.innerHTML += "No results :(<br/>" +
"Try on <a href=\"https://duckduckgo.com/?q=" +
encodeURIComponent("rust " + query.userQuery) +
"\">DuckDuckGo</a>?<br/><br/>" +
"Or try looking in one of these:<ul><li>The <a " +
`href="${dlroChannel}/reference/index.html">Rust Reference</a> ` +
" for technical details about the language.</li><li><a " +
`href="${dlroChannel}/rust-by-example/index.html">Rust By ` +
"Example</a> for expository code examples.</a></li><li>The <a " +
`href="${dlroChannel}/book/index.html">Rust Book</a> for ` +
"introductions to language features and the language itself.</li><li><a " +
"href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" +
" <a href=\"https://crates.io/\">crates.io</a>.</li></ul>";
}
output.innerHTML += "Example searches:<ul>" +
"<li><a href=\"" + getNakedUrl() + "?search=std::vec\">std::vec</a></li>" +
"<li><a href=\"" + getNakedUrl() + "?search=u32+->+bool\">u32 -> bool</a></li>" +
"<li><a href=\"" + getNakedUrl() + "?search=Option<T>,+(T+->+U)+->+Option<U>\">" +
"Option&lt;T>, (T -> U) -> Option&lt;U></a></li>" +
"</ul>";
// need to make sure the element is shown before
// running this callback
yieldToBrowser().then(() => finishedCallback(0, output));
}
return output;
}
/**
* returns [tab, output]
* @param {number} tabNb
* @param {string} text
* @param {AsyncGenerator<rustdoc.ResultObject>} results
* @param {rustdoc.ParsedQuery<rustdoc.ParserQueryElement>} query
* @param {boolean} isTypeSearch
* @param {boolean} goToFirst
* @returns {[HTMLElement, Promise<HTMLElement>]}
*/
function makeTab(tabNb, text, results, query, isTypeSearch, goToFirst) {
const isCurrentTab = window.searchState.currentTab === tabNb;
const tabButton = document.createElement("button");
tabButton.appendChild(document.createTextNode(text));
tabButton.className = isCurrentTab ? "selected" : "";
const tabCount = document.createElement("span");
tabCount.className = "count loading";
tabCount.innerHTML = "\u{2007}(\u{2007})\u{2007}\u{2007}";
tabButton.appendChild(tabCount);
return [
tabButton,
addTab(results, query, isCurrentTab, (count, output) => {
const search = window.searchState.outputElement();
const error = query.error;
if (count === 0 && error !== null && search) {
error.forEach((value, index) => {
value = value.split("<").join("&lt;").split(">").join("&gt;");
if (index % 2 !== 0) {
error[index] = `<code>${value.replaceAll(" ", "&nbsp;")}</code>`;
} else {
error[index] = value;
}
});
const errorReport = document.createElement("h3");
errorReport.className = "error";
errorReport.innerHTML = `Query parser error: "${error.join("")}".`;
search.insertBefore(errorReport, search.firstElementChild);
} else if (goToFirst ||
(count === 1 && getSettingValue("go-to-only-result") === "true")
) {
// Needed to force re-execution of JS when coming back to a page. Let's take this
// scenario as example:
//
// 1. You have the "Directly go to item in search if there is only one result"
// option enabled.
// 2. You make a search which results only one result, leading you automatically to
// this result.
// 3. You go back to previous page.
//
// Now, without the call below, the JS will not be re-executed and the previous
// state will be used, starting search again since the search input is not empty,
// leading you back to the previous page again.
window.onunload = () => { };
window.searchState.removeQueryParameters();
const a = output.querySelector("a");
if (a) {
a.click();
return;
}
}
// https://blog.horizon-eda.org/misc/2020/02/19/ui.html
//
// CSS runs with `font-variant-numeric: tabular-nums` to ensure all
// digits are the same width. \u{2007} is a Unicode space character
// that is defined to be the same width as a digit.
const fmtNbElems =
count < 10 ? `\u{2007}(${count})\u{2007}\u{2007}` :
count < 100 ? `\u{2007}(${count})\u{2007}` : `\u{2007}(${count})`;
tabCount.innerHTML = fmtNbElems;
tabCount.className = "count";
}, isTypeSearch),
];
}
/**
* @param {DocSearch} docSearch
* @param {rustdoc.ResultsTable} results
* @param {boolean} goToFirst
* @param {string} filterCrates
*/
async function showResults(docSearch, results, goToFirst, filterCrates) {
const search = window.searchState.outputElement();
if (!search) {
return;
}
let crates = "";
const crateNames = await docSearch.getCrateNameList();
if (crateNames.length > 1) {
crates = "&nbsp;in&nbsp;<div id=\"crate-search-div\">" +
"<select id=\"crate-search\"><option value=\"all crates\">all crates</option>";
const l = crateNames.length;
for (let i = 0; i < l; i += 1) {
const c = crateNames[i];
crates += `<option value="${c}" ${c === filterCrates && "selected"}>${c}</option>`;
}
crates += "</select></div>";
}
nonnull(document.querySelector(".search-switcher")).innerHTML = `Search results${crates}`;
/** @type {[HTMLElement, Promise<HTMLElement>][]} */
const tabs = [];
searchState.currentTab = 0;
if (results.query.error !== null) {
tabs.push(makeTab(0, "In Names", results.others, results.query, false, goToFirst));
} else if (
results.query.foundElems <= 1 &&
results.query.returned.length === 0 &&
!results.query.hasReturnArrow
) {
tabs.push(makeTab(0, "In Names", results.others, results.query, false, goToFirst));
tabs.push(makeTab(1, "In Parameters", results.in_args, results.query, true, false));
tabs.push(makeTab(2, "In Return Types", results.returned, results.query, true, false));
} else {
const signatureTabTitle =
results.query.elems.length === 0 ? "In Function Return Types" :
results.query.returned.length === 0 ? "In Function Parameters" :
"In Function Signatures";
tabs.push(makeTab(0, signatureTabTitle, results.others, results.query, true, goToFirst));
}
const tabsElem = document.createElement("div");
tabsElem.id = "search-tabs";
const resultsElem = document.createElement("div");
resultsElem.id = "results";
search.innerHTML = "";
for (const [tab, output] of tabs) {
tabsElem.appendChild(tab);
const placeholder = document.createElement("div");
output.then(output => {
if (placeholder.parentElement) {
placeholder.parentElement.replaceChild(output, placeholder);
}
});
resultsElem.appendChild(placeholder);
}
if (window.searchState.rustdocToolbar) {
nonnull(
nonnull(window.searchState.containerElement())
.querySelector(".main-heading"),
).appendChild(window.searchState.rustdocToolbar);
}
const crateSearch = document.getElementById("crate-search");
if (crateSearch) {
crateSearch.addEventListener("input", updateCrate);
}
search.appendChild(tabsElem);
search.appendChild(resultsElem);
// Reset focused elements.
window.searchState.showResults();
window.searchState.focusedByTab = [null, null, null];
let i = 0;
for (const elem of tabsElem.childNodes) {
const j = i;
// @ts-expect-error
elem.onclick = () => printTab(j);
window.searchState.focusedByTab[i] = null;
i += 1;
}
printTab(0);
}
// @ts-expect-error
function updateSearchHistory(url) {
const btn = document.querySelector("#search-button a");
if (btn instanceof HTMLAnchorElement) {
btn.href = url;
}
if (!browserSupportsHistoryApi()) {
return;
}
const params = searchState.getQueryStringParams();
if (!history.state && params.search === undefined) {
history.pushState(null, "", url);
} else {
history.replaceState(null, "", url);
}
}
/**
* Perform a search based on the current state of the search input element
* and display the results.
* @param {boolean} [forced]
*/
async function search(forced) {
const query = DocSearch.parseQuery(nonnull(window.searchState.inputElement()).value.trim());
let filterCrates = getFilterCrates();
// @ts-expect-error
if (!forced && query.userQuery === currentResults) {
if (query.userQuery.length > 0) {
putBackSearch();
}
return;
}
currentResults = query.userQuery;
searchState.setLoadingSearch();
const params = searchState.getQueryStringParams();
// In case we have no information about the saved crate and there is a URL query parameter,
// we override it with the URL query parameter.
if (filterCrates === null && params["filter-crate"] !== undefined) {
filterCrates = params["filter-crate"];
}
if (filterCrates !== null &&
(await docSearch.getCrateNameList()).indexOf(filterCrates) === -1
) {
filterCrates = null;
}
// Update document title to maintain a meaningful browser history
searchState.title = "\"" + query.userQuery + "\" Search - Rust";
// Because searching is incremental by character, only the most
// recent search query is added to the browser history.
updateSearchHistory(buildUrl(query.userQuery, filterCrates));
await showResults(
docSearch,
// @ts-expect-error
await docSearch.execQuery(query, filterCrates, window.currentCrate),
params.go_to_first,
// @ts-expect-error
filterCrates);
}
/**
* Callback for when the search form is submitted.
* @param {Event} [e] - The event that triggered this call, if any
*/
function onSearchSubmit(e) {
// @ts-expect-error
e.preventDefault();
searchState.clearInputTimeout();
search();
}
function putBackSearch() {
const search_input = window.searchState.inputElement();
if (!search_input) {
return;
}
if (search_input.value !== "" && !searchState.isDisplayed()) {
searchState.showResults();
if (browserSupportsHistoryApi()) {
history.replaceState(null, "",
buildUrl(search_input.value, getFilterCrates()));
}
document.title = searchState.title;
}
}
function registerSearchEvents() {
const params = searchState.getQueryStringParams();
// Populate search bar with query string search term when provided,
// but only if the input bar is empty. This avoid the obnoxious issue
// where you start trying to do a search, and the index loads, and
// suddenly your search is gone!
const inputElement = nonnull(window.searchState.inputElement());
if (inputElement.value === "") {
inputElement.value = params.search || "";
}
const searchAfter500ms = () => {
searchState.clearInputTimeout();
window.searchState.timeout = setTimeout(search, 500);
};
inputElement.onkeyup = searchAfter500ms;
inputElement.oninput = searchAfter500ms;
if (inputElement.form) {
inputElement.form.onsubmit = onSearchSubmit;
}
inputElement.onchange = e => {
if (e.target !== document.activeElement) {
// To prevent doing anything when it's from a blur event.
return;
}
// Do NOT e.preventDefault() here. It will prevent pasting.
searchState.clearInputTimeout();
// zero-timeout necessary here because at the time of event handler execution the
// pasted content is not in the input field yet. Shouldn’t make any difference for
// change, though.
setTimeout(search, 0);
};
inputElement.onpaste = inputElement.onchange;
// @ts-expect-error
searchState.outputElement().addEventListener("keydown", e => {
if (!(e instanceof KeyboardEvent)) {
return;
}
// We only handle unmodified keystrokes here. We don't want to interfere with,
// for instance, alt-left and alt-right for history navigation.
if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) {
return;
}
// up and down arrow select next/previous search result, or the
// search box if we're already at the top.
if (e.which === 38) { // up
// @ts-expect-error
const previous = document.activeElement.previousElementSibling;
if (previous) {
// @ts-expect-error
previous.focus();
} else {
searchState.focus();
}
e.preventDefault();
} else if (e.which === 40) { // down
// @ts-expect-error
const next = document.activeElement.nextElementSibling;
if (next) {
// @ts-expect-error
next.focus();
}
// @ts-expect-error
const rect = document.activeElement.getBoundingClientRect();
if (window.innerHeight - rect.bottom < rect.height) {
window.scrollBy(0, rect.height);
}
e.preventDefault();
} else if (e.which === 37) { // left
nextTab(-1);
e.preventDefault();
} else if (e.which === 39) { // right
nextTab(1);
e.preventDefault();
}
});
inputElement.addEventListener("keydown", e => {
if (e.which === 40) { // down
focusSearchResult();
e.preventDefault();
}
});
inputElement.addEventListener("focus", () => {
putBackSearch();
});
}
// @ts-expect-error
function updateCrate(ev) {
if (ev.target.value === "all crates") {
// If we don't remove it from the URL, it'll be picked up again by the search.
const query = nonnull(window.searchState.inputElement()).value.trim();
updateSearchHistory(buildUrl(query, null));
}
// In case you "cut" the entry from the search input, then change the crate filter
// before paste back the previous search, you get the old search results without
// the filter. To prevent this, we need to remove the previous results.
currentResults = null;
search(true);
}
// eslint-disable-next-line max-len
// polyfill https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Uint8Array/fromBase64
/**
* @type {function(string): Uint8Array} base64
*/
//@ts-expect-error
const makeUint8ArrayFromBase64 = Uint8Array.fromBase64 ? Uint8Array.fromBase64 : (string => {
const bytes_as_string = atob(string);
const l = bytes_as_string.length;
const bytes = new Uint8Array(l);
for (let i = 0; i < l; ++i) {
bytes[i] = bytes_as_string.charCodeAt(i);
}
return bytes;
});
if (ROOT_PATH === null) {
return;
}
const database = await Stringdex.loadDatabase(hooks);
if (typeof window !== "undefined") {
docSearch = new DocSearch(ROOT_PATH, database);
await docSearch.buildIndex();
onEachLazy(document.querySelectorAll(
".search-form.loading",
), form => {
removeClass(form, "loading");
});
registerSearchEvents();
// If there's a search term in the URL, execute the search now.
if (window.searchState.getQueryStringParams().search !== undefined) {
search();
}
} else if (typeof exports !== "undefined") {
docSearch = new DocSearch(ROOT_PATH, database);
await docSearch.buildIndex();
return { docSearch, DocSearch };
}
};
if (typeof window !== "undefined") {
const ROOT_PATH = window.rootPath;
/** @type {stringdex.Callbacks|null} */
let databaseCallbacks = null;
initSearch(window.Stringdex, window.RoaringBitmap, {
loadRoot: callbacks => {
for (const key in callbacks) {
if (Object.hasOwn(callbacks, key)) {
// @ts-ignore
window[key] = callbacks[key];
}
}
databaseCallbacks = callbacks;
// search.index/root is loaded by main.js, so
// this script doesn't need to launch it, but
// must pick it up
// @ts-ignore
if (window.searchIndex) {
// @ts-ignore
window.rr_(window.searchIndex);
}
},
loadTreeByHash: hashHex => {
const script = document.createElement("script");
script.src = `${ROOT_PATH}/search.index/${hashHex}.js`;
script.onerror = e => {
if (databaseCallbacks) {
databaseCallbacks.err_rn_(hashHex, e);
}
};
document.documentElement.appendChild(script);
},
loadDataByNameAndHash: (name, hashHex) => {
const script = document.createElement("script");
script.src = `${ROOT_PATH}/search.index/${name}/${hashHex}.js`;
script.onerror = e => {
if (databaseCallbacks) {
databaseCallbacks.err_rd_(hashHex, e);
}
};
document.documentElement.appendChild(script);
},
});
} else if (typeof exports !== "undefined") {
// eslint-disable-next-line no-undef
exports.initSearch = initSearch;
}