path: root/browser/components/urlbar/UrlbarMuxerUnifiedComplete.jsm

/* 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/. */

"use strict";

/**
 * This module exports a component used to sort results in a UrlbarQueryContext.
 */

var EXPORTED_SYMBOLS = ["UrlbarMuxerUnifiedComplete"];

const { XPCOMUtils } = ChromeUtils.import(
  "resource://gre/modules/XPCOMUtils.jsm"
);
XPCOMUtils.defineLazyModuleGetters(this, {
  Services: "resource://gre/modules/Services.jsm",
  UrlbarPrefs: "resource:///modules/UrlbarPrefs.jsm",
  UrlbarProviderTabToSearch:
    "resource:///modules/UrlbarProviderTabToSearch.jsm",
  UrlbarMuxer: "resource:///modules/UrlbarUtils.jsm",
  UrlbarSearchUtils: "resource:///modules/UrlbarSearchUtils.jsm",
  UrlbarUtils: "resource:///modules/UrlbarUtils.jsm",
});

XPCOMUtils.defineLazyGetter(this, "logger", () =>
  UrlbarUtils.getLogger({ prefix: "MuxerUnifiedComplete" })
);

function groupFromResult(result) {
  if (result.heuristic) {
    return UrlbarUtils.RESULT_GROUP.HEURISTIC;
  }
  switch (result.type) {
    case UrlbarUtils.RESULT_TYPE.SEARCH:
      if (result.payload.suggestion) {
        return UrlbarUtils.RESULT_GROUP.SUGGESTION;
      }
      break;
    case UrlbarUtils.RESULT_TYPE.OMNIBOX:
      return UrlbarUtils.RESULT_GROUP.EXTENSION;
  }
  return UrlbarUtils.RESULT_GROUP.GENERAL;
}

// Breaks ties among heuristic results. Providers higher up the list are higher
// priority.
const HEURISTIC_ORDER = [
  // Test providers are handled in sort(),
  // Extension providers are handled in sort(),
  "UrlbarProviderSearchTips",
  "Omnibox",
  "UnifiedComplete",
  "Autofill",
  "TokenAliasEngines",
  "HeuristicFallback",
];

/**
 * 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,
      resultsByGroup: new Map(),
      totalResultCount: 0,
      topHeuristicRank: Infinity,
      strippedUrlToTopPrefixAndTitle: new Map(),
      canShowPrivateSearch: context.results.length > 1,
      canShowTailSuggestions: true,
      formHistorySuggestions: new Set(),
      canAddTabToSearch: true,
    };

    let resultsWithSuggestedIndex = [];

    // Do the first pass over all results to build some state.
    for (let result of context.results) {
      // Save results that have a suggested index for later.
      if (result.suggestedIndex >= 0) {
        resultsWithSuggestedIndex.push(result);
        continue;
      }

      // Add all other results to the resultsByGroup map:
      // group => array of results belonging to the group
      let group = groupFromResult(result);
      let results = state.resultsByGroup.get(group);
      if (!results) {
        results = [];
        state.resultsByGroup.set(group, results);
      }
      results.push(result);

      // Update pre-add state.
      this._updateStatePreAdd(result, state);
    }

    if (
      context.heuristicResult?.type == UrlbarUtils.RESULT_TYPE.SEARCH &&
      context.heuristicResult?.payload.query
    ) {
      state.heuristicResultQuery = context.heuristicResult.payload.query.toLocaleLowerCase();
    }

    // If the heuristic result is a search result, use search buckets, otherwise
    // use normal buckets.
    let buckets =
      context.heuristicResult?.type == UrlbarUtils.RESULT_TYPE.SEARCH
        ? UrlbarPrefs.get("matchBucketsSearch")
        : UrlbarPrefs.get("matchBuckets");
    logger.debug(`Buckets: ${buckets}`);

    // Do the second pass to fill each bucket.  We'll build a list where each
    // item at index i is the array of results in the bucket at index i.
    let resultsByBucketIndex = [];
    for (let [group, maxResultCount] of buckets) {
      let results = this._addResults(group, maxResultCount, state);
      resultsByBucketIndex.push(results);
    }

    // In search mode for an engine, search suggestions should always appear
    // before general results. Transplanting them allows us to keep history
    // results up to the limit set in matchBuckets, while filling the space
    // above them with suggestions.
    if (context.searchMode?.engineName) {
      let suggestionsIndex = resultsByBucketIndex.findIndex(
        results =>
          results[0] &&
          !results[0].heuristic &&
          results[0].type == UrlbarUtils.RESULT_TYPE.SEARCH
      );
      if (suggestionsIndex > 1) {
        logger.debug(`Transplanting suggestions before general results.`);
        let removed = resultsByBucketIndex.splice(suggestionsIndex, 1);
        resultsByBucketIndex.splice(1, 0, ...removed);
      }
    }

    // Build the sorted results list by concatenating each bucket's results.
    let sortedResults = [];
    let remainingCount = context.maxResults;
    for (let i = 0; i < resultsByBucketIndex.length && remainingCount; i++) {
      let results = resultsByBucketIndex[i];
      let count = Math.min(remainingCount, results.length);
      sortedResults.push(...results.slice(0, count));
      remainingCount -= count;
    }

    // Finally, insert results that have a suggested index.  Sort them by index
    // in descending order so that earlier insertions don't disrupt later ones.
    resultsWithSuggestedIndex.sort(
      (a, b) => a.suggestedIndex - b.suggestedIndex
    );
    // Do a first pass to update sort state for each result.
    for (let result of resultsWithSuggestedIndex) {
      this._updateStatePreAdd(result, state);
    }
    // Now insert them.
    for (let result of resultsWithSuggestedIndex) {
      if (this._canAddResult(result, state)) {
        let index =
          result.suggestedIndex <= sortedResults.length
            ? result.suggestedIndex
            : sortedResults.length;
        sortedResults.splice(index, 0, result);
        this._updateStatePostAdd(result, state);
      }
    }

    context.results = sortedResults;
  }

  /**
   * Adds results to a bucket using results from the bucket's group in
   * `state.resultsByGroup`.
   *
   * @param {string} group
   *   The bucket's group.
   * @param {number} maxResultCount
   *   The maximum number of results to add to the bucket.
   * @param {object} state
   *   Global state that we use to make decisions during this sort.
   * @returns {array}
   *   The added results, empty if no results were added.
   */
  _addResults(group, maxResultCount, state) {
    let addedResults = [];
    let groupResults = state.resultsByGroup.get(group);
    while (
      groupResults?.length &&
      addedResults.length < maxResultCount &&
      state.totalResultCount < state.context.maxResults
    ) {
      // We either add or discard results in the order they appear in the
      // groupResults array, so shift() them off.  That way later buckets with
      // the same group won't include results that earlier buckets have added or
      // discarded.
      let result = groupResults.shift();
      if (this._canAddResult(result, state)) {
        addedResults.push(result);
        state.totalResultCount++;
        this._updateStatePostAdd(result, state);
      }
    }
    return addedResults;
  }

  /**
   * Returns whether a result can be added to its bucket 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.
   */
  _canAddResult(result, state) {
    // Exclude low-ranked heuristic results.
    if (result.heuristic && result != state.context.heuristicResult) {
      return false;
    }

    // We expect UnifiedComplete 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);
      // We don't expect completely identical URLs in the results at this point,
      // so if the prefixes are the same, then we're deduping a result against
      // itself.
      if (topPrefixData && prefix != topPrefixData.prefix) {
        let prefixRank = UrlbarUtils.getPrefixRank(prefix);
        if (
          prefixRank < topPrefixData.rank &&
          (prefix.endsWith("www.") == topPrefixData.prefix.endsWith("www.") ||
            result.payload?.title == topPrefixData.title)
        ) {
          return false;
        }
      }
    }

    // Discard results that dupe autofill.
    if (
      state.context.heuristicResult &&
      state.context.heuristicResult.providerName == "Autofill" &&
      result.providerName != "Autofill" &&
      state.context.heuristicResult.payload?.url == result.payload.url &&
      state.context.heuristicResult.type == result.type
    ) {
      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 == "TabToSearch") {
      // Discard the result if a tab-to-search result was added already.
      if (!state.canAddTabToSearch) {
        return false;
      }

      if (!result.payload.satisfiesAutofillThreshold) {
        // Discard the result if the heuristic result is not autofill.
        if (
          state.context.heuristicResult.type != UrlbarUtils.RESULT_TYPE.URL ||
          !state.context.heuristicResult.autofill
        ) {
          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 that dupes the heuristic or previous added form
    // history (for restyleSearch).
    if (
      result.type == UrlbarUtils.RESULT_TYPE.SEARCH &&
      result.source == UrlbarUtils.RESULT_SOURCE.HISTORY &&
      (result.payload.lowerCaseSuggestion === state.heuristicResultQuery ||
        state.formHistorySuggestions.has(result.payload.lowerCaseSuggestion))
    ) {
      return false;
    }

    // Discard remote search suggestions that dupe the heuristic.
    if (
      result.type == UrlbarUtils.RESULT_TYPE.SEARCH &&
      result.source == UrlbarUtils.RESULT_SOURCE.SEARCH &&
      result.payload.lowerCaseSuggestion &&
      result.payload.lowerCaseSuggestion === state.heuristicResultQuery
    ) {
      return false;
    }

    // Discard tail suggestions if appropriate.
    if (
      result.type == UrlbarUtils.RESULT_TYPE.SEARCH &&
      result.payload.tail &&
      !state.canShowTailSuggestions
    ) {
      return false;
    }

    // Discard SERPs from browser history that dupe either the heuristic or
    // previously added form history.
    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.toLocaleLowerCase();
        if (
          state.heuristicResultQuery === resultQuery ||
          state.formHistorySuggestions.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,
            resultQuery
          );
          if (
            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 = 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;
        }
      }
    }

    // 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) {
    // Determine the highest-ranking heuristic result.
    if (result.heuristic) {
      // + 2 to reserve the highest-priority slots for test and extension
      // providers.
      let heuristicRank = HEURISTIC_ORDER.indexOf(result.providerName) + 2;
      // Extension and test provider names vary widely and aren't suitable
      // for a static safelist like HEURISTIC_ORDER.
      if (result.providerType == UrlbarUtils.PROVIDER_TYPE.EXTENSION) {
        heuristicRank = 1;
      } else if (result.providerName.startsWith("TestProvider")) {
        heuristicRank = 0;
      } else if (heuristicRank - 2 == -1) {
        throw new Error(
          `Heuristic result returned by unexpected provider: ${result.providerName}`
        );
      }
      // Replace in case of ties, which would occur if a provider sent two
      // heuristic results.
      if (heuristicRank <= state.topHeuristicRank) {
        state.topHeuristicRank = heuristicRank;
        state.context.heuristicResult = result;
      }
    }

    // Save some state we'll use later to dedupe URL results.
    if (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 prefixRank = UrlbarUtils.getPrefixRank(prefix);
      let topPrefixData = state.strippedUrlToTopPrefixAndTitle.get(strippedUrl);
      let topPrefixRank = topPrefixData ? topPrefixData.rank : -1;
      if (topPrefixRank < prefixRank) {
        // strippedUrl => { prefix, title, rank }
        state.strippedUrlToTopPrefixAndTitle.set(strippedUrl, {
          prefix,
          title: result.payload.title,
          rank: prefixRank,
        });
      }
    }

    // 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;
    }
  }

  /**
   * 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) {
    // 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 (
      state.canShowPrivateSearch &&
      (result.type != UrlbarUtils.RESULT_TYPE.SEARCH ||
        result.payload.providesSearchMode ||
        (result.heuristic && result.payload.keyword))
    ) {
      state.canShowPrivateSearch = false;
    }

    // Update form history suggestions.
    if (
      result.type == UrlbarUtils.RESULT_TYPE.SEARCH &&
      result.source == UrlbarUtils.RESULT_SOURCE.HISTORY
    ) {
      state.formHistorySuggestions.add(result.payload.lowerCaseSuggestion);
    }

    // Avoid multiple tab-to-search results.
    // TODO (Bug 1670185): figure out better strategies to manage this case.
    if (result.providerName == "TabToSearch") {
      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 `onboardingEnginesShown` here.
      if (result.payload.dynamicType) {
        UrlbarProviderTabToSearch.onboardingEnginesShown.add(
          result.payload.engine
        );
      }
    }
  }
}

var UrlbarMuxerUnifiedComplete = new MuxerUnifiedComplete();