/* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /** * This module exports a component used to sort results in a UrlbarQueryContext. */ import { XPCOMUtils } from "resource://gre/modules/XPCOMUtils.sys.mjs"; import { UrlbarMuxer, UrlbarUtils, } from "resource:///modules/UrlbarUtils.sys.mjs"; const lazy = {}; ChromeUtils.defineESModuleGetters(lazy, { QuickSuggest: "resource:///modules/QuickSuggest.sys.mjs", UrlbarPrefs: "resource:///modules/UrlbarPrefs.sys.mjs", UrlbarProviderQuickSuggest: "resource:///modules/UrlbarProviderQuickSuggest.sys.mjs", UrlbarProviderTabToSearch: "resource:///modules/UrlbarProviderTabToSearch.sys.mjs", UrlbarSearchUtils: "resource:///modules/UrlbarSearchUtils.sys.mjs", }); XPCOMUtils.defineLazyGetter(lazy, "logger", () => UrlbarUtils.getLogger({ prefix: "MuxerUnifiedComplete" }) ); /** * Class used to create a muxer. * The muxer receives and sorts results in a UrlbarQueryContext. */ class MuxerUnifiedComplete extends UrlbarMuxer { constructor() { super(); } get name() { return "UnifiedComplete"; } /** * Sorts results in the given UrlbarQueryContext. * * @param {UrlbarQueryContext} context * The query context. */ sort(context) { // This method is called multiple times per keystroke, so it should be as // fast and efficient as possible. We do two passes through the results: // one to collect state for the second pass, and then a second to build the // sorted list of results. If you find yourself writing something like // context.results.find(), filter(), sort(), etc., modify one or both passes // instead. // Global state we'll use to make decisions during this sort. let state = { context, // RESULT_GROUP => array of results belonging to the group, excluding // group-relative suggestedIndex results resultsByGroup: new Map(), // RESULT_GROUP => array of group-relative suggestedIndex results // belonging to the group suggestedIndexResultsByGroup: new Map(), // This is analogous to `maxResults` except it's the total available // result span instead of the total available result count. We'll add // results until `usedResultSpan` would exceed `availableResultSpan`. availableResultSpan: context.maxResults, // The total span of results that have been added so far. usedResultSpan: 0, strippedUrlToTopPrefixAndTitle: new Map(), urlToTabResultType: new Map(), addedRemoteTabUrls: new Set(), addedSwitchTabUrls: new Set(), canShowPrivateSearch: context.results.length > 1, canShowTailSuggestions: true, // Form history and remote suggestions added so far. Used for deduping // suggestions. Also includes the heuristic query string if the heuristic // is a search result. All strings in the set are lowercased. suggestions: new Set(), canAddTabToSearch: true, hasUnitConversionResult: false, maxHeuristicResultSpan: 0, maxTabToSearchResultSpan: 0, // When you add state, update _copyState() as necessary. }; // Do the first pass over all results to build some state. for (let result of context.results) { // Add each result to the appropriate `resultsByGroup` map. let group = UrlbarUtils.getResultGroup(result); let resultsByGroup = result.hasSuggestedIndex && result.isSuggestedIndexRelativeToGroup ? state.suggestedIndexResultsByGroup : state.resultsByGroup; let results = resultsByGroup.get(group); if (!results) { results = []; resultsByGroup.set(group, results); } results.push(result); // Update pre-add state. this._updateStatePreAdd(result, state); } // Now that the first pass is done, adjust the available result span. if (state.maxTabToSearchResultSpan) { // Subtract the max tab-to-search span. state.availableResultSpan = Math.max( state.availableResultSpan - state.maxTabToSearchResultSpan, 0 ); } if (state.maxHeuristicResultSpan) { if (lazy.UrlbarPrefs.get("experimental.hideHeuristic")) { // The heuristic is hidden. The muxer will include it but the view will // hide it. Increase the available span to compensate so that the total // visible span accurately reflects `context.maxResults`. state.availableResultSpan += state.maxHeuristicResultSpan; } else if (context.maxResults > 0) { // `context.maxResults` is positive. Make sure there's room for the // heuristic even if it means exceeding `context.maxResults`. state.availableResultSpan = Math.max( state.availableResultSpan, state.maxHeuristicResultSpan ); } } // Determine the result groups to use for this sort. In search mode with // an engine, show search suggestions first. let rootGroup = context.searchMode?.engineName ? lazy.UrlbarPrefs.makeResultGroups({ showSearchSuggestionsFirst: true }) : lazy.UrlbarPrefs.get("resultGroups"); lazy.logger.debug(`Groups: ${rootGroup}`); // Fill the root group. let [sortedResults] = this._fillGroup( rootGroup, { availableSpan: state.availableResultSpan, maxResultCount: Infinity }, state ); // Add global suggestedIndex results unless the max result count is zero, // which isn't really supported but it's easy to honor here. We add them all // even if they exceed the max because we assume they're high-priority // results that should always be shown, and as long as the max is positive // it's not a problem to exceed it sometimes. In practice that will happen // only for small, non-default values of `maxRichResults`. if (context.maxResults > 0) { let suggestedIndexResults = state.resultsByGroup.get( UrlbarUtils.RESULT_GROUP.SUGGESTED_INDEX ); if (suggestedIndexResults) { this._addSuggestedIndexResults( suggestedIndexResults, sortedResults, state ); } } context.results = sortedResults; } /** * Returns a *deep* copy of state (except for `state.context`, which is * shallow copied). i.e., any Maps, Sets, and arrays in the state should be * recursively copied so that the original state is not modified when the copy * is modified. * * @param {object} state * The muxer state to copy. * @returns {object} * A deep copy of the state. */ _copyState(state) { let copy = Object.assign({}, state, { resultsByGroup: new Map(), suggestedIndexResultsByGroup: new Map(), strippedUrlToTopPrefixAndTitle: new Map( state.strippedUrlToTopPrefixAndTitle ), urlToTabResultType: new Map(state.urlToTabResultType), addedRemoteTabUrls: new Set(state.addedRemoteTabUrls), addedSwitchTabUrls: new Set(state.addedSwitchTabUrls), suggestions: new Set(state.suggestions), }); // Deep copy the `resultsByGroup` maps. for (let key of ["resultsByGroup", "suggestedIndexResultsByGroup"]) { for (let [group, results] of state[key]) { copy[key].set(group, [...results]); } } return copy; } /** * Recursively fills a result group and its children. * * There are two ways to limit the number of results in a group: * * (1) By max total result span using the `availableSpan` property. The group * will be filled so that the total span of its results does not exceed this * value. * * (2) By max total result count using the `maxResultCount` property. The * group will be filled so that the total number of its results does not * exceed this value. * * Both `availableSpan` and `maxResultCount` may be defined, and the group's * results will be capped to whichever limit is reached first. If either is * not defined, then the group inherits that limit from its parent group. * * In addition to limiting their total number of results, groups can also * control the composition of their child groups by using flex ratios. A group * can define a `flexChildren: true` property, and in that case each of its * children should have a `flex` property. Each child will be filled according * to the ratio of its flex value and the sum of the flex values of all the * children, similar to HTML flexbox. If some children do not fill up but * others do, the filled-up children will be allowed to grow to use up the * unfilled space. * * @param {object} group * The result group to fill. * @param {object} limits * An object with optional `availableSpan` and `maxResultCount` properties * as described above. They will be used as the limits for the group. * @param {object} state * The muxer state. * @returns {Array} * `[results, usedLimits, hasMoreResults]` -- see `_addResults`. */ _fillGroup(group, limits, state) { // Get the group's suggestedIndex results. Reminder: `group.group` is a // `RESULT_GROUP` constant. let suggestedIndexResults; if ("group" in group) { suggestedIndexResults = state.suggestedIndexResultsByGroup.get( group.group ); if (suggestedIndexResults) { // Subtract them from the group's limits so there will be room for them // later. Create a new `limits` object so we don't modify the caller's. let span = suggestedIndexResults.reduce((sum, result) => { sum += UrlbarUtils.getSpanForResult(result); return sum; }, 0); limits = { ...limits }; limits.availableSpan = Math.max(limits.availableSpan - span, 0); limits.maxResultCount = Math.max( limits.maxResultCount - suggestedIndexResults.length, 0 ); } } // Fill the group. If it has children, fill them recursively. Otherwise fill // the group directly. let [results, usedLimits, hasMoreResults] = group.children ? this._fillGroupChildren(group, limits, state) : this._addResults(group.group, limits, state); // Add the group's suggestedIndex results. if (suggestedIndexResults) { let suggestedIndexUsedLimits = this._addSuggestedIndexResults( suggestedIndexResults, results, state ); for (let [key, value] of Object.entries(suggestedIndexUsedLimits)) { usedLimits[key] += value; } } return [results, usedLimits, hasMoreResults]; } /** * Helper for `_fillGroup` that fills a group's children. * * @param {object} group * The result group to fill. It's assumed to have a `children` property. * @param {object} limits * An object with optional `availableSpan` and `maxResultCount` properties * as described in `_fillGroup`. * @param {object} state * The muxer state. * @param {Array} flexDataArray * See `_updateFlexData`. * @returns {Array} * `[results, usedLimits, hasMoreResults]` -- see `_addResults`. */ _fillGroupChildren(group, limits, state, flexDataArray = null) { // If the group has flexed children, update the data we use during flex // calculations. // // Handling flex is complicated so we discuss it briefly. We may do multiple // passes for a group with flexed children in order to try to optimally fill // them. If after one pass some children do not fill up but others do, we'll // do another pass that tries to overfill the filled-up children while still // respecting their flex ratios. We'll continue to do passes until all // children stop filling up or we reach the parent's limits. The way we // overfill children is by increasing their individual limits to make up for // the unused space in their underfilled siblings. Before starting a new // pass, we discard the results from the current pass so the new pass starts // with a clean slate. That means we need to copy the global sort state // (`state`) before modifying it in the current pass so we can use its // original value in the next pass [1]. // // [1] Instead of starting each pass with a clean slate in this way, we // could accumulate results with each pass since we only ever add results to // flexed children and never remove them. However, that would subvert muxer // logic related to the global state (deduping, `_canAddResult`) since we // generally assume the muxer adds results in the order they appear. let stateCopy; if (group.flexChildren) { stateCopy = this._copyState(state); flexDataArray = this._updateFlexData(group, limits, flexDataArray); } // Fill each child group, collecting all results in the `results` array. let results = []; let usedLimits = {}; for (let key of Object.keys(limits)) { usedLimits[key] = 0; } let anyChildUnderfilled = false; let anyChildHasMoreResults = false; for (let i = 0; i < group.children.length; i++) { let child = group.children[i]; let flexData = flexDataArray?.[i]; // Compute the child's limits. let childLimits = {}; for (let key of Object.keys(limits)) { childLimits[key] = flexData ? flexData.limits[key] : Math.min( typeof child[key] == "number" ? child[key] : Infinity, limits[key] - usedLimits[key] ); } // Recurse and fill the child. let [ childResults, childUsedLimits, childHasMoreResults, ] = this._fillGroup(child, childLimits, state); results = results.concat(childResults); for (let key of Object.keys(usedLimits)) { usedLimits[key] += childUsedLimits[key]; } anyChildHasMoreResults = anyChildHasMoreResults || childHasMoreResults; if (flexData?.hasMoreResults) { // The child is flexed and we possibly added more results to it. flexData.usedLimits = childUsedLimits; flexData.hasMoreResults = childHasMoreResults; anyChildUnderfilled = anyChildUnderfilled || (!childHasMoreResults && [...Object.entries(childLimits)].every( ([key, limit]) => flexData.usedLimits[key] < limit )); } } // If the children are flexed and some underfilled but others still have // more results, do another pass. if (anyChildUnderfilled && anyChildHasMoreResults) { [results, usedLimits, anyChildHasMoreResults] = this._fillGroupChildren( group, limits, stateCopy, flexDataArray ); // Update `state` in place so that it's also updated in the caller. for (let [key, value] of Object.entries(stateCopy)) { state[key] = value; } } return [results, usedLimits, anyChildHasMoreResults]; } /** * Updates flex-related state used while filling a group. * * @param {object} group * The result group being filled. * @param {object} limits * An object defining the group's limits as described in `_fillGroup`. * @param {Array} flexDataArray * An array parallel to `group.children`. The object at index i corresponds * to the child in `group.children` at index i. Each object maintains some * flex-related state for its child and is updated during each pass in * `_fillGroup` for `group`. When this method is called in the first pass, * this argument should be null, and the method will create and return a new * `flexDataArray` array that should be used in the remainder of the first * pass and all subsequent passes. * @returns {Array} * A new `flexDataArray` when called in the first pass, and `flexDataArray` * itself when called in subsequent passes. */ _updateFlexData(group, limits, flexDataArray) { flexDataArray = flexDataArray || group.children.map((child, index) => { let data = { // The index of the corresponding child in `group.children`. index, // The child's limits. limits: {}, // The fractional parts of the child's unrounded limits; see below. limitFractions: {}, // The used-up portions of the child's limits. usedLimits: {}, // True if `state.resultsByGroup` has more results of the child's // `RESULT_GROUP`. This is not related to the child's limits. hasMoreResults: true, // The child's flex value. flex: typeof child.flex == "number" ? child.flex : 0, }; for (let key of Object.keys(limits)) { data.limits[key] = 0; data.limitFractions[key] = 0; data.usedLimits[key] = 0; } return data; }); // The data objects for children with more results (i.e., that are still // fillable). let fillableDataArray = []; // The sum of the flex values of children with more results. let fillableFlexSum = 0; for (let data of flexDataArray) { if (data.hasMoreResults) { fillableFlexSum += data.flex; fillableDataArray.push(data); } } // Update each limit. for (let [key, limit] of Object.entries(limits)) { // Calculate the group's limit only including children with more results. let fillableLimit = limit; for (let data of flexDataArray) { if (!data.hasMoreResults) { fillableLimit -= data.usedLimits[key]; } } // Allow for the possibility that some children may have gone over limit. // `fillableLimit` will be negative in that case. fillableLimit = Math.max(fillableLimit, 0); // Next we'll compute the limits of children with more results. This value // is the sum of those limits. It may differ from `fillableLimit` due to // the fact that each individual child limit must be an integer. let summedFillableLimit = 0; // Compute the limits of children with more results. If there are also // children that don't have more results, then these new limits will be // larger than they were in the previous pass. for (let data of fillableDataArray) { let unroundedLimit = fillableLimit * (data.flex / fillableFlexSum); // `limitFraction` is the fractional part of the unrounded ideal limit. // e.g., for 5.234 it will be 0.234. We use this to minimize the // mathematical error when tweaking limits below. data.limitFractions[key] = unroundedLimit - Math.floor(unroundedLimit); data.limits[key] = Math.round(unroundedLimit); summedFillableLimit += data.limits[key]; } // As mentioned above, the sum of the individual child limits may not // equal the group's fillable limit. If the sum is smaller, the group will // end up with too few results. If it's larger, the group will have the // correct number of results (since we stop adding results once limits are // reached) but it may end up with a composition that does not reflect the // child flex ratios as accurately as possible. // // In either case, tweak the individual limits so that (1) their sum // equals the group's fillable limit, and (2) the composition respects the // flex ratios with as little mathematical error as possible. if (summedFillableLimit != fillableLimit) { // Collect the flex datas with a non-zero limit fractions. We'll round // them up or down depending on whether the sum is larger or smaller // than the group's fillable limit. let fractionalDataArray = fillableDataArray.filter( data => data.limitFractions[key] ); let diff; if (summedFillableLimit < fillableLimit) { // The sum is smaller. We'll increment individual limits until the sum // is equal, starting with the child whose limit fraction is closest // to 1 in order to minimize error. diff = 1; fractionalDataArray.sort((a, b) => { // Sort by fraction descending so larger fractions are first. let cmp = b.limitFractions[key] - a.limitFractions[key]; // Secondarily sort by index ascending so that children with the // same fraction are incremented in the order they appear, allowing // earlier children to have larger spans. return cmp || a.index - b.index; }); } else if (fillableLimit < summedFillableLimit) { // The sum is larger. We'll decrement individual limits until the sum // is equal, starting with the child whose limit fraction is closest // to 0 in order to minimize error. diff = -1; fractionalDataArray.sort((a, b) => { // Sort by fraction ascending so smaller fractions are first. let cmp = a.limitFractions[key] - b.limitFractions[key]; // Secondarily sort by index descending so that children with the // same fraction are decremented in reverse order, allowing earlier // children to retain larger spans. return cmp || b.index - a.index; }); } // Now increment or decrement individual limits until their sum is equal // to the group's fillable limit. while (summedFillableLimit != fillableLimit) { if (!fractionalDataArray.length) { // This shouldn't happen, but don't let it break us. lazy.logger.error("fractionalDataArray is empty!"); break; } let data = flexDataArray[fractionalDataArray.shift().index]; data.limits[key] += diff; summedFillableLimit += diff; } } } return flexDataArray; } /** * Adds results to a group using the results from its `RESULT_GROUP` in * `state.resultsByGroup`. * * @param {UrlbarUtils.RESULT_GROUP} groupConst * The group's `RESULT_GROUP`. * @param {object} limits * An object defining the group's limits as described in `_fillGroup`. * @param {object} state * Global state that we use to make decisions during this sort. * @returns {Array} * `[results, usedLimits, hasMoreResults]` where: * results: A flat array of results in the group, empty if no results * were added. * usedLimits: An object defining the amount of each limit that the * results use. For each possible limit property (see `_fillGroup`), * there will be a corresponding property in this object. For example, * if 3 results are added with a total span of 4, then this object will * be: { maxResultCount: 3, availableSpan: 4 } * hasMoreResults: True if `state.resultsByGroup` has more results of * the same `RESULT_GROUP`. This is not related to the group's limits. */ _addResults(groupConst, limits, state) { let usedLimits = {}; for (let key of Object.keys(limits)) { usedLimits[key] = 0; } // For form history, maxHistoricalSearchSuggestions == 0 implies the user // has opted out of form history completely, so we override the max result // count here in that case. Other values of maxHistoricalSearchSuggestions // are ignored and we use the flex defined on the form history group. if ( groupConst == UrlbarUtils.RESULT_GROUP.FORM_HISTORY && !lazy.UrlbarPrefs.get("maxHistoricalSearchSuggestions") ) { // Create a new `limits` object so we don't modify the caller's. limits = { ...limits }; limits.maxResultCount = 0; } let addedResults = []; let groupResults = state.resultsByGroup.get(groupConst); while ( groupResults?.length && state.usedResultSpan < state.availableResultSpan && [...Object.entries(limits)].every(([k, limit]) => usedLimits[k] < limit) ) { let result = groupResults[0]; if (this._canAddResult(result, state)) { let span = UrlbarUtils.getSpanForResult(result); let newUsedSpan = usedLimits.availableSpan + span; if (limits.availableSpan < newUsedSpan) { // Adding the result would exceed the group's available span, so stop // adding results to it. Skip the shift() below so the result can be // added to later groups. break; } addedResults.push(result); usedLimits.availableSpan = newUsedSpan; usedLimits.maxResultCount++; state.usedResultSpan += span; this._updateStatePostAdd(result, state); } // We either add or discard results in the order they appear in // `groupResults`, so shift() them off. That way later groups with the // same `RESULT_GROUP` won't include results that earlier groups have // added or discarded. groupResults.shift(); } return [addedResults, usedLimits, !!groupResults?.length]; } /** * Returns whether a result can be added to its group given the current sort * state. * * @param {UrlbarResult} result * The result. * @param {object} state * Global state that we use to make decisions during this sort. * @returns {boolean} * True if the result can be added and false if it should be discarded. */ // TODO (Bug 1741273): Refactor this method to avoid an eslint complexity // error or increase the complexity threshold. // eslint-disable-next-line complexity _canAddResult(result, state) { // QuickSuggest results are shown unless they are best matches // that duplicate heuristic results. if (result.providerName == lazy.UrlbarProviderQuickSuggest.name) { let heuristicUrl = state.context.heuristicResult?.payload.url; if ( heuristicUrl && !lazy.UrlbarPrefs.get("experimental.hideHeuristic") && result.isBestMatch ) { let opts = { stripHttp: true, stripHttps: true, stripWww: true, trimSlash: true, }; return ( UrlbarUtils.stripPrefixAndTrim(heuristicUrl, opts)[0] != UrlbarUtils.stripPrefixAndTrim(result.payload.url, opts)[0] ); } return true; } // We expect UrlbarProviderPlaces sent us the highest-ranked www. and non-www // origins, if any. Now, compare them to each other and to the heuristic // result. // // 1. If the heuristic result is lower ranked than both, discard the www // origin, unless it has a different page title than the non-www // origin. This is a guard against deduping when www.site.com and // site.com have different content. // 2. If the heuristic result is higher than either the www origin or // non-www origin: // 2a. If the heuristic is a www origin, discard the non-www origin. // 2b. If the heuristic is a non-www origin, discard the www origin. if ( !result.heuristic && result.type == UrlbarUtils.RESULT_TYPE.URL && result.payload.url ) { let [strippedUrl, prefix] = UrlbarUtils.stripPrefixAndTrim( result.payload.url, { stripHttp: true, stripHttps: true, stripWww: true, trimEmptyQuery: true, } ); let topPrefixData = state.strippedUrlToTopPrefixAndTitle.get(strippedUrl); // If the condition below is not met, we are deduping a result against // itself. if ( topPrefixData && (prefix != topPrefixData.prefix || result.providerName != topPrefixData.providerName) ) { let prefixRank = UrlbarUtils.getPrefixRank(prefix); if ( (prefixRank < topPrefixData.rank && (prefix.endsWith("www.") == topPrefixData.prefix.endsWith("www.") || result.payload?.title == topPrefixData.title)) || (prefix == topPrefixData.prefix && result.providerName != topPrefixData.providerName) ) { return false; } } } // Discard results that dupe autofill. if ( state.context.heuristicResult && state.context.heuristicResult.autofill && !result.autofill && state.context.heuristicResult.payload?.url == result.payload.url && state.context.heuristicResult.type == result.type && !lazy.UrlbarPrefs.get("experimental.hideHeuristic") ) { return false; } // HeuristicFallback may add non-heuristic results in some cases, but those // should be retained only if the heuristic result comes from it. if ( !result.heuristic && result.providerName == "HeuristicFallback" && state.context.heuristicResult?.providerName != "HeuristicFallback" ) { return false; } if (result.providerName == lazy.UrlbarProviderTabToSearch.name) { // Discard the result if a tab-to-search result was added already. if (!state.canAddTabToSearch) { return false; } // In cases where the heuristic result is not a URL and we have a // tab-to-search result, the tab-to-search provider determined that the // typed string is similar to an engine domain. We can let the // tab-to-search result through. if (state.context.heuristicResult?.type == UrlbarUtils.RESULT_TYPE.URL) { // Discard the result if the heuristic result is not autofill and we are // not making an exception for a fuzzy match. if ( !state.context.heuristicResult.autofill && !result.payload.satisfiesAutofillThreshold ) { return false; } let autofillHostname = new URL( state.context.heuristicResult.payload.url ).hostname; let [autofillDomain] = UrlbarUtils.stripPrefixAndTrim( autofillHostname, { stripWww: true, } ); // Strip the public suffix because we want to allow matching "domain.it" // with "domain.com". autofillDomain = UrlbarUtils.stripPublicSuffixFromHost(autofillDomain); if (!autofillDomain) { return false; } // For tab-to-search results, result.payload.url is the engine's domain // with the public suffix already stripped, for example "www.mozilla.". let [engineDomain] = UrlbarUtils.stripPrefixAndTrim( result.payload.url, { stripWww: true, } ); // Discard if the engine domain does not end with the autofilled one. if (!engineDomain.endsWith(autofillDomain)) { return false; } } } // Discard "Search in a Private Window" if appropriate. if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.inPrivateWindow && !state.canShowPrivateSearch ) { return false; } // Discard form history and remote suggestions that dupe previously added // suggestions or the heuristic. if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.lowerCaseSuggestion ) { let suggestion = result.payload.lowerCaseSuggestion.trim(); if (!suggestion || state.suggestions.has(suggestion)) { return false; } } // Discard tail suggestions if appropriate. if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.tail && !state.canShowTailSuggestions ) { return false; } // Discard remote tab results that dupes another remote tab or a // switch-to-tab result. if (result.type == UrlbarUtils.RESULT_TYPE.REMOTE_TAB) { if (state.addedRemoteTabUrls.has(result.payload.url)) { return false; } let maybeDupeType = state.urlToTabResultType.get(result.payload.url); if (maybeDupeType == UrlbarUtils.RESULT_TYPE.TAB_SWITCH) { return false; } } // Discard switch-to-tab results that dupes another switch-to-tab result. if ( result.type == UrlbarUtils.RESULT_TYPE.TAB_SWITCH && state.addedSwitchTabUrls.has(result.payload.url) ) { return false; } // Discard history results that dupe either remote or switch-to-tab results. if ( !result.heuristic && result.type == UrlbarUtils.RESULT_TYPE.URL && result.payload.url && state.urlToTabResultType.has(result.payload.url) ) { return false; } // Discard SERPs from browser history that dupe either the heuristic or // previously added suggestions. if ( result.source == UrlbarUtils.RESULT_SOURCE.HISTORY && result.type == UrlbarUtils.RESULT_TYPE.URL ) { let submission = Services.search.parseSubmissionURL(result.payload.url); if (submission) { let resultQuery = submission.terms.trim().toLocaleLowerCase(); if (state.suggestions.has(resultQuery)) { // If the result's URL is the same as a brand new SERP URL created // from the query string modulo certain URL params, then treat the // result as a dupe and discard it. let [newSerpURL] = UrlbarUtils.getSearchQueryUrl( submission.engine, submission.terms ); if ( lazy.UrlbarSearchUtils.serpsAreEquivalent( result.payload.url, newSerpURL ) ) { return false; } } } } // When in an engine search mode, discard URL results whose hostnames don't // include the root domain of the search mode engine. if (state.context.searchMode?.engineName && result.payload.url) { let engine = Services.search.getEngineByName( state.context.searchMode.engineName ); if (engine) { let searchModeRootDomain = lazy.UrlbarSearchUtils.getRootDomainFromEngine( engine ); let resultUrl = new URL(result.payload.url); // Add a trailing "." to increase the stringency of the check. This // check covers most general cases. Some edge cases are not covered, // like `resultUrl` being ebay.mydomain.com, which would escape this // check if `searchModeRootDomain` was "ebay". if (!resultUrl.hostname.includes(`${searchModeRootDomain}.`)) { return false; } } } // Discard history results that dupe the quick suggest result. if ( state.quickSuggestResult && !result.heuristic && result.type == UrlbarUtils.RESULT_TYPE.URL && lazy.QuickSuggest.isURLEquivalentToResultURL( result.payload.url, state.quickSuggestResult ) ) { return false; } // Discard history results whose URLs were originally sponsored. We use the // presence of a partner's URL search param to detect these. The param is // defined in the pref below, which is also used for the newtab page. if ( result.source == UrlbarUtils.RESULT_SOURCE.HISTORY && result.type == UrlbarUtils.RESULT_TYPE.URL ) { let param = Services.prefs.getCharPref( "browser.newtabpage.activity-stream.hideTopSitesWithSearchParam" ); if (param) { let [key, value] = param.split("="); let searchParams; try { ({ searchParams } = new URL(result.payload.url)); } catch (error) {} if ( (value === undefined && searchParams?.has(key)) || (value !== undefined && searchParams?.getAll(key).includes(value)) ) { return false; } } } // Heuristic results must always be the first result. If this result is a // heuristic but we've already added results, discard it. Normally this // should never happen because the standard result groups are set up so // that there's always at most one heuristic and it's always first, but // since result groups are stored in a pref and can therefore be modified // by the user, we perform this check. if (result.heuristic && state.usedResultSpan) { return false; } // Google search engine might suggest a result for unit conversion with // format that starts with "= ". If our UnitConversion can provide the // result, we discard the suggestion of Google in order to deduplicate. if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.engine == "Google" && result.payload.suggestion?.startsWith("= ") && state.hasUnitConversionResult ) { return false; } // Include the result. return true; } /** * Updates the global state that we use to make decisions during sort. This * should be called for results before we've decided whether to add or discard * them. * * @param {UrlbarResult} result * The result. * @param {object} state * Global state that we use to make decisions during this sort. */ _updateStatePreAdd(result, state) { // Keep track of the largest heuristic result span. if (result.heuristic && this._canAddResult(result, state)) { state.maxHeuristicResultSpan = Math.max( state.maxHeuristicResultSpan, UrlbarUtils.getSpanForResult(result) ); } // Subtract from `availableResultSpan` the span of global suggestedIndex // results so there will be room for them at the end of the sort. Except // when `maxRichResults` is zero and other special cases, we assume // suggestedIndex results will always be shown regardless of the total // available result span, `context.maxResults`, and `maxRichResults`. if ( result.hasSuggestedIndex && !result.isSuggestedIndexRelativeToGroup && this._canAddResult(result, state) ) { let span = UrlbarUtils.getSpanForResult(result); if (result.providerName == lazy.UrlbarProviderTabToSearch.name) { state.maxTabToSearchResultSpan = Math.max( state.maxTabToSearchResultSpan, span ); } else { state.availableResultSpan = Math.max( state.availableResultSpan - span, 0 ); } } // Save some state we'll use later to dedupe URL results. if ( (result.type == UrlbarUtils.RESULT_TYPE.URL || result.type == UrlbarUtils.RESULT_TYPE.KEYWORD) && result.payload.url && (!result.heuristic || !lazy.UrlbarPrefs.get("experimental.hideHeuristic")) ) { let [strippedUrl, prefix] = UrlbarUtils.stripPrefixAndTrim( result.payload.url, { stripHttp: true, stripHttps: true, stripWww: true, trimEmptyQuery: true, } ); let prefixRank = UrlbarUtils.getPrefixRank(prefix); let topPrefixData = state.strippedUrlToTopPrefixAndTitle.get(strippedUrl); let topPrefixRank = topPrefixData ? topPrefixData.rank : -1; if ( topPrefixRank < prefixRank || // If a quick suggest result has the same stripped URL and prefix rank // as another result, store the quick suggest as the top rank so we // discard the other during deduping. That happens after the user picks // the quick suggest: The URL is added to history and later both a // history result and the quick suggest may match a query. (topPrefixRank == prefixRank && result.providerName == lazy.UrlbarProviderQuickSuggest.name) ) { // strippedUrl => { prefix, title, rank, providerName } state.strippedUrlToTopPrefixAndTitle.set(strippedUrl, { prefix, title: result.payload.title, rank: prefixRank, providerName: result.providerName, }); } } // Save some state we'll use later to dedupe results from open/remote tabs. if ( result.payload.url && (result.type == UrlbarUtils.RESULT_TYPE.TAB_SWITCH || (result.type == UrlbarUtils.RESULT_TYPE.REMOTE_TAB && !state.urlToTabResultType.has(result.payload.url))) ) { // url => result type state.urlToTabResultType.set(result.payload.url, result.type); } // If we find results other than the heuristic, "Search in Private // Window," or tail suggestions, then we should hide tail suggestions // since they're a last resort. if ( state.canShowTailSuggestions && !result.heuristic && (result.type != UrlbarUtils.RESULT_TYPE.SEARCH || (!result.payload.inPrivateWindow && !result.payload.tail)) ) { state.canShowTailSuggestions = false; } if (result.providerName == lazy.UrlbarProviderQuickSuggest.name) { state.quickSuggestResult = result; } state.hasUnitConversionResult = state.hasUnitConversionResult || result.providerName == "UnitConversion"; } /** * Updates the global state that we use to make decisions during sort. This * should be called for results after they've been added. It should not be * called for discarded results. * * @param {UrlbarResult} result * The result. * @param {object} state * Global state that we use to make decisions during this sort. */ _updateStatePostAdd(result, state) { // Update heuristic state. if (result.heuristic) { state.context.heuristicResult = result; if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.query && !lazy.UrlbarPrefs.get("experimental.hideHeuristic") ) { let query = result.payload.query.trim().toLocaleLowerCase(); if (query) { state.suggestions.add(query); } } } // The "Search in a Private Window" result should only be shown when there // are other results and all of them are searches. It should not be shown // if the user typed an alias because that's an explicit engine choice. if ( !Services.search.separatePrivateDefaultUrlbarResultEnabled || (state.canShowPrivateSearch && (result.type != UrlbarUtils.RESULT_TYPE.SEARCH || result.payload.providesSearchMode || (result.heuristic && result.payload.keyword))) ) { state.canShowPrivateSearch = false; } // Update suggestions. if ( result.type == UrlbarUtils.RESULT_TYPE.SEARCH && result.payload.lowerCaseSuggestion ) { let suggestion = result.payload.lowerCaseSuggestion.trim(); if (suggestion) { state.suggestions.add(suggestion); } } // Avoid multiple tab-to-search results. // TODO (Bug 1670185): figure out better strategies to manage this case. if (result.providerName == lazy.UrlbarProviderTabToSearch.name) { state.canAddTabToSearch = false; // We want to record in urlbar.tips once per engagement per engine. Since // whether these results are shown is dependent on the Muxer, we must // add to `enginesShown` here. if (result.payload.dynamicType) { lazy.UrlbarProviderTabToSearch.enginesShown.onboarding.add( result.payload.engine ); } else { lazy.UrlbarProviderTabToSearch.enginesShown.regular.add( result.payload.engine ); } } // Sync will send us duplicate remote tabs if multiple copies of a tab are // open on a synced client. Keep track of which remote tabs we've added to // dedupe these. if (result.type == UrlbarUtils.RESULT_TYPE.REMOTE_TAB) { state.addedRemoteTabUrls.add(result.payload.url); } // Keep track of which switch tabs we've added to dedupe switch tabs. if (result.type == UrlbarUtils.RESULT_TYPE.TAB_SWITCH) { state.addedSwitchTabUrls.add(result.payload.url); } } /** * Inserts results with suggested indexes. This can be called for either * global or group-relative suggestedIndex results. It should be called after * `sortedResults` has been filled in. * * @param {Array} suggestedIndexResults * Results with a `suggestedIndex` property. * @param {Array} sortedResults * The sorted results. For global suggestedIndex results, this should be the * final list of all results before suggestedIndex results are inserted. For * group-relative suggestedIndex results, this should be the final list of * results in the group before group-relative suggestedIndex results are * inserted. * @param {object} state * Global state that we use to make decisions during this sort. * @returns {object} * A `usedLimits` object that describes the total span and count of all the * added results. See `_addResults`. */ _addSuggestedIndexResults(suggestedIndexResults, sortedResults, state) { let usedLimits = { availableSpan: 0, maxResultCount: 0, }; if (!suggestedIndexResults?.length) { // This is just a slight optimization; no need to continue. return usedLimits; } // Partition the results into positive- and negative-index arrays. Positive // indexes are relative to the start of the list and negative indexes are // relative to the end. let positive = []; let negative = []; for (let result of suggestedIndexResults) { let results = result.suggestedIndex < 0 ? negative : positive; results.push(result); } // Sort the positive results ascending so that results at the end of the // array don't end up offset by later insertions at the front. positive.sort((a, b) => { if (a.suggestedIndex !== b.suggestedIndex) { return a.suggestedIndex - b.suggestedIndex; } if (a.providerName === b.providerName) { return 0; } // If same suggestedIndex, change the displaying order along to following // provider priority. // TabToSearch > QuickSuggest > Other providers if (a.providerName === lazy.UrlbarProviderTabToSearch.name) { return 1; } if (b.providerName === lazy.UrlbarProviderTabToSearch.name) { return -1; } if (a.providerName === lazy.UrlbarProviderQuickSuggest.name) { return 1; } if (b.providerName === lazy.UrlbarProviderQuickSuggest.name) { return -1; } return 0; }); // Conversely, sort the negative results descending so that results at the // front of the array don't end up offset by later insertions at the end. negative.sort((a, b) => b.suggestedIndex - a.suggestedIndex); // Insert the results. We start with the positive results because we have // tests that assume they're inserted first. In practice it shouldn't matter // because there's no good reason we would ever have a negative result come // before a positive result in the same query. Even if we did, we have to // insert one before the other, and there's no right or wrong order. for (let results of [positive, negative]) { let prevResult; let prevIndex; for (let result of results) { if (this._canAddResult(result, state)) { let index; if ( prevResult && prevResult.suggestedIndex == result.suggestedIndex ) { index = prevIndex; } else { index = result.suggestedIndex >= 0 ? Math.min(result.suggestedIndex, sortedResults.length) : Math.max(result.suggestedIndex + sortedResults.length + 1, 0); } prevResult = result; prevIndex = index; sortedResults.splice(index, 0, result); usedLimits.availableSpan += UrlbarUtils.getSpanForResult(result); usedLimits.maxResultCount++; this._updateStatePostAdd(result, state); } } } return usedLimits; } } export var UrlbarMuxerUnifiedComplete = new MuxerUnifiedComplete();