path: root/browser/components/urlbar/UrlbarMuxerUnifiedComplete.sys.mjs

/* 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();