path: root/browser/components/urlbar/UrlbarProviderAutofill.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 provider that provides an autofill result.
 */

import {
  UrlbarProvider,
  UrlbarUtils,
} from "resource:///modules/UrlbarUtils.sys.mjs";

const lazy = {};

ChromeUtils.defineESModuleGetters(lazy, {
  AboutPagesUtils: "resource://gre/modules/AboutPagesUtils.sys.mjs",
  PlacesUtils: "resource://gre/modules/PlacesUtils.sys.mjs",
  UrlbarPrefs: "resource:///modules/UrlbarPrefs.sys.mjs",
  UrlbarResult: "resource:///modules/UrlbarResult.sys.mjs",
  UrlbarTokenizer: "resource:///modules/UrlbarTokenizer.sys.mjs",
});

// AutoComplete query type constants.
// Describes the various types of queries that we can process rows for.
const QUERYTYPE = {
  AUTOFILL_ORIGIN: 1,
  AUTOFILL_URL: 2,
  AUTOFILL_ADAPTIVE: 3,
};

// Constants to support an alternative frecency algorithm.
const ORIGIN_USE_ALT_FRECENCY = Services.prefs.getBoolPref(
  "places.frecency.origins.alternative.featureGate",
  false
);
const ORIGIN_FRECENCY_FIELD = ORIGIN_USE_ALT_FRECENCY
  ? "alt_frecency"
  : "frecency";

// `WITH` clause for the autofill queries.  autofill_frecency_threshold.value is
// the mean of all moz_origins.frecency values + stddevMultiplier * one standard
// deviation.  This is inlined directly in the SQL (as opposed to being a custom
// Sqlite function for example) in order to be as efficient as possible.
// For alternative frecency, a NULL frecency will be normalized to 0.0, and when
// it will graduate, it will likely become 1 (official frecency is NOT NULL).
// Thus we set a minimum threshold of 2.0, otherwise if all the visits are older
// than the cutoff, we end up checking 0.0 (frecency) >= 0.0 (threshold) and
// autofill everything instead of nothing.
const SQL_AUTOFILL_WITH = ORIGIN_USE_ALT_FRECENCY
  ? `
    WITH
    autofill_frecency_threshold(value) AS (
      SELECT IFNULL(
        (SELECT value FROM moz_meta WHERE key = 'origin_alt_frecency_threshold'),
        2.0
      )
    )
    `
  : `
    WITH
    frecency_stats(count, sum, squares) AS (
      SELECT
        CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = 'origin_frecency_count') AS REAL),
        CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = 'origin_frecency_sum') AS REAL),
        CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = 'origin_frecency_sum_of_squares') AS REAL)
    ),
    autofill_frecency_threshold(value) AS (
      SELECT
        CASE count
        WHEN 0 THEN 0.0
        WHEN 1 THEN sum
        ELSE (sum / count) + (:stddevMultiplier * sqrt((squares - ((sum * sum) / count)) / count))
        END
      FROM frecency_stats
    )
  `;

const SQL_AUTOFILL_FRECENCY_THRESHOLD = `host_frecency >= (
    SELECT value FROM autofill_frecency_threshold
  )`;

function originQuery(where) {
  // `frecency`, `bookmarked` and `visited` are partitioned by the fixed host,
  // without `www.`. `host_prefix` instead is partitioned by full host, because
  // we assume a prefix may not work regardless of `www.`.
  let selectVisited = where.includes("visited")
    ? `MAX(EXISTS(
      SELECT 1 FROM moz_places WHERE origin_id = o.id AND visit_count > 0
    )) OVER (PARTITION BY fixup_url(host)) > 0`
    : "0";
  let selectTitle;
  let joinBookmarks;
  if (where.includes("bookmarked")) {
    selectTitle = "ifnull(b.title, iif(h.frecency <> 0, h.title, NULL))";
    joinBookmarks = "LEFT JOIN moz_bookmarks b ON b.fk = h.id";
  } else {
    selectTitle = "iif(h.frecency <> 0, h.title, NULL)";
    joinBookmarks = "";
  }
  return `/* do not warn (bug no): cannot use an index to sort */
    ${SQL_AUTOFILL_WITH},
    origins(id, prefix, host_prefix, host, fixed, host_frecency, frecency, bookmarked, visited) AS (
      SELECT
      id,
      prefix,
      first_value(prefix) OVER (
        PARTITION BY host ORDER BY ${ORIGIN_FRECENCY_FIELD} DESC, prefix = "https://" DESC, id DESC
      ),
      host,
      fixup_url(host),
      IFNULL(total(${ORIGIN_FRECENCY_FIELD}) OVER (PARTITION BY fixup_url(host)), 0.0),
      ${ORIGIN_FRECENCY_FIELD},
      MAX(EXISTS(
        SELECT 1 FROM moz_places WHERE origin_id = o.id AND foreign_count > 0
      )) OVER (PARTITION BY fixup_url(host)),
      ${selectVisited}
      FROM moz_origins o
      WHERE prefix NOT IN ('about:', 'place:')
        AND ((host BETWEEN :searchString AND :searchString || X'FFFF')
          OR (host BETWEEN 'www.' || :searchString AND 'www.' || :searchString || X'FFFF'))
    ),
    matched_origin(host_fixed, url) AS (
      SELECT iif(instr(host, :searchString) = 1, host, fixed) || '/',
             ifnull(:prefix, host_prefix) || host || '/'
      FROM origins
      ${where}
      ORDER BY frecency DESC, prefix = "https://" DESC, id DESC
      LIMIT 1
    ),
    matched_place(host_fixed, url, id, title, frecency) AS (
      SELECT o.host_fixed, o.url, h.id, h.title, h.frecency
      FROM matched_origin o
      LEFT JOIN moz_places h ON h.url_hash IN (
        hash('https://' || o.host_fixed),
        hash('https://www.' || o.host_fixed),
        hash('http://' || o.host_fixed),
        hash('http://www.' || o.host_fixed)
      )
      ORDER BY
        h.title IS NOT NULL DESC,
        h.title || '/' <> o.host_fixed DESC,
        h.url = o.url DESC,
        h.frecency DESC,
        h.id DESC
      LIMIT 1
    )
    SELECT :query_type AS query_type,
           :searchString AS search_string,
           h.host_fixed AS host_fixed,
           h.url AS url,
           ${selectTitle} AS title
    FROM matched_place h
    ${joinBookmarks}
  `;
}

function urlQuery(where1, where2, isBookmarkContained) {
  // We limit the search to places that are either bookmarked or have a frecency
  // over some small, arbitrary threshold (20) in order to avoid scanning as few
  // rows as possible.  Keep in mind that we run this query every time the user
  // types a key when the urlbar value looks like a URL with a path.
  let selectTitle;
  let joinBookmarks;
  if (isBookmarkContained) {
    selectTitle = "ifnull(b.title, matched_url.title)";
    joinBookmarks = "LEFT JOIN moz_bookmarks b ON b.fk = matched_url.id";
  } else {
    selectTitle = "matched_url.title";
    joinBookmarks = "";
  }
  return `/* do not warn (bug no): cannot use an index to sort */
    WITH matched_url(url, title, frecency, bookmarked, visited, stripped_url, is_exact_match, id) AS (
      SELECT url,
             title,
             frecency,
             foreign_count > 0 AS bookmarked,
             visit_count > 0 AS visited,
             strip_prefix_and_userinfo(url) AS stripped_url,
             strip_prefix_and_userinfo(url) = strip_prefix_and_userinfo(:strippedURL) AS is_exact_match,
             id
      FROM moz_places
      WHERE rev_host = :revHost
            ${where1}
      UNION ALL
      SELECT url,
             title,
             frecency,
             foreign_count > 0 AS bookmarked,
             visit_count > 0 AS visited,
             strip_prefix_and_userinfo(url) AS stripped_url,
             strip_prefix_and_userinfo(url) = 'www.' || strip_prefix_and_userinfo(:strippedURL) AS is_exact_match,
             id
      FROM moz_places
      WHERE rev_host = :revHost || 'www.'
            ${where2}
      ORDER BY is_exact_match DESC, frecency DESC, id DESC
      LIMIT 1
    )
    SELECT :query_type AS query_type,
           :searchString AS search_string,
           :strippedURL AS stripped_url,
           matched_url.url AS url,
           ${selectTitle} AS title
    FROM matched_url
    ${joinBookmarks}
  `;
}

// Queries
const QUERY_ORIGIN_HISTORY_BOOKMARK = originQuery(
  `WHERE bookmarked OR ${SQL_AUTOFILL_FRECENCY_THRESHOLD}`
);

const QUERY_ORIGIN_PREFIX_HISTORY_BOOKMARK = originQuery(
  `WHERE prefix BETWEEN :prefix AND :prefix || X'FFFF'
     AND (bookmarked OR ${SQL_AUTOFILL_FRECENCY_THRESHOLD})`
);

const QUERY_ORIGIN_HISTORY = originQuery(
  `WHERE visited AND ${SQL_AUTOFILL_FRECENCY_THRESHOLD}`
);

const QUERY_ORIGIN_PREFIX_HISTORY = originQuery(
  `WHERE prefix BETWEEN :prefix AND :prefix || X'FFFF'
     AND visited AND ${SQL_AUTOFILL_FRECENCY_THRESHOLD}`
);

const QUERY_ORIGIN_BOOKMARK = originQuery(`WHERE bookmarked`);

const QUERY_ORIGIN_PREFIX_BOOKMARK = originQuery(
  `WHERE prefix BETWEEN :prefix AND :prefix || X'FFFF' AND bookmarked`
);

const QUERY_URL_HISTORY_BOOKMARK = urlQuery(
  `AND (bookmarked OR frecency > 20)
     AND stripped_url COLLATE NOCASE
       BETWEEN :strippedURL AND :strippedURL || X'FFFF'`,
  `AND (bookmarked OR frecency > 20)
     AND stripped_url COLLATE NOCASE
       BETWEEN 'www.' || :strippedURL AND 'www.' || :strippedURL || X'FFFF'`,
  true
);

const QUERY_URL_PREFIX_HISTORY_BOOKMARK = urlQuery(
  `AND (bookmarked OR frecency > 20)
     AND url COLLATE NOCASE
       BETWEEN :prefix || :strippedURL AND :prefix || :strippedURL || X'FFFF'`,
  `AND (bookmarked OR frecency > 20)
     AND url COLLATE NOCASE
       BETWEEN :prefix || 'www.' || :strippedURL AND :prefix || 'www.' || :strippedURL || X'FFFF'`,
  true
);

const QUERY_URL_HISTORY = urlQuery(
  `AND (visited OR NOT bookmarked)
     AND frecency > 20
     AND stripped_url COLLATE NOCASE
       BETWEEN :strippedURL AND :strippedURL || X'FFFF'`,
  `AND (visited OR NOT bookmarked)
     AND frecency > 20
     AND stripped_url COLLATE NOCASE
       BETWEEN 'www.' || :strippedURL AND 'www.' || :strippedURL || X'FFFF'`,
  false
);

const QUERY_URL_PREFIX_HISTORY = urlQuery(
  `AND (visited OR NOT bookmarked)
     AND frecency > 20
     AND url COLLATE NOCASE
       BETWEEN :prefix || :strippedURL AND :prefix || :strippedURL || X'FFFF'`,
  `AND (visited OR NOT bookmarked)
     AND frecency > 20
     AND url COLLATE NOCASE
       BETWEEN :prefix || 'www.' || :strippedURL AND :prefix || 'www.' || :strippedURL || X'FFFF'`,
  false
);

const QUERY_URL_BOOKMARK = urlQuery(
  `AND bookmarked
     AND stripped_url COLLATE NOCASE
       BETWEEN :strippedURL AND :strippedURL || X'FFFF'`,
  `AND bookmarked
     AND stripped_url COLLATE NOCASE
       BETWEEN 'www.' || :strippedURL AND 'www.' || :strippedURL || X'FFFF'`,
  true
);

const QUERY_URL_PREFIX_BOOKMARK = urlQuery(
  `AND bookmarked
     AND url COLLATE NOCASE
       BETWEEN :prefix || :strippedURL AND :prefix || :strippedURL || X'FFFF'`,
  `AND bookmarked
     AND url COLLATE NOCASE
       BETWEEN :prefix || 'www.' || :strippedURL AND :prefix || 'www.' || :strippedURL || X'FFFF'`,
  true
);

/**
 * Class used to create the provider.
 */
class ProviderAutofill extends UrlbarProvider {
  constructor() {
    super();
  }

  /**
   * Returns the name of this provider.
   *
   * @returns {string} the name of this provider.
   */
  get name() {
    return "Autofill";
  }

  /**
   * Returns the type of this provider.
   *
   * @returns {integer} one of the types from UrlbarUtils.PROVIDER_TYPE.*
   */
  get type() {
    return UrlbarUtils.PROVIDER_TYPE.HEURISTIC;
  }

  /**
   * Whether this provider should be invoked for the given context.
   * If this method returns false, the providers manager won't start a query
   * with this provider, to save on resources.
   *
   * @param {UrlbarQueryContext} queryContext The query context object
   * @returns {boolean} Whether this provider should be invoked for the search.
   */
  async isActive(queryContext) {
    let instance = this.queryInstance;

    // This is usually reset on canceling or completing the query, but since we
    // query in isActive, it may not have been canceled by the previous call.
    // It is an object with values { result: UrlbarResult, instance: Query }.
    // See the documentation for _getAutofillData for more information.
    this._autofillData = null;

    // First of all, check for the autoFill pref.
    if (!lazy.UrlbarPrefs.get("autoFill")) {
      return false;
    }

    if (!queryContext.allowAutofill) {
      return false;
    }

    if (queryContext.tokens.length != 1) {
      return false;
    }

    // Trying to autofill an extremely long string would be expensive, and
    // not particularly useful since the filled part falls out of screen anyway.
    if (queryContext.searchString.length > UrlbarUtils.MAX_TEXT_LENGTH) {
      return false;
    }

    // autoFill can only cope with history, bookmarks, and about: entries.
    if (
      !queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY) &&
      !queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      return false;
    }

    // Autofill doesn't search tags or titles
    if (
      queryContext.tokens.some(
        t =>
          t.type == lazy.UrlbarTokenizer.TYPE.RESTRICT_TAG ||
          t.type == lazy.UrlbarTokenizer.TYPE.RESTRICT_TITLE
      )
    ) {
      return false;
    }

    [this._strippedPrefix, this._searchString] = UrlbarUtils.stripURLPrefix(
      queryContext.searchString
    );
    this._strippedPrefix = this._strippedPrefix.toLowerCase();

    // Don't try to autofill if the search term includes any whitespace.
    // This may confuse completeDefaultIndex cause the AUTOCOMPLETE_MATCH
    // tokenizer ends up trimming the search string and returning a value
    // that doesn't match it, or is even shorter.
    if (lazy.UrlbarTokenizer.REGEXP_SPACES.test(queryContext.searchString)) {
      return false;
    }

    // Fetch autofill result now, rather than in startQuery. We do this so the
    // muxer doesn't have to wait on autofill for every query, since startQuery
    // will be guaranteed to return a result very quickly using this approach.
    // Bug 1651101 is filed to improve this behaviour.
    let result = await this._getAutofillResult(queryContext);
    if (!result || instance != this.queryInstance) {
      return false;
    }
    this._autofillData = { result, instance };
    return true;
  }

  /**
   * Gets the provider's priority.
   *
   * @param {UrlbarQueryContext} queryContext The query context object
   * @returns {number} The provider's priority for the given query.
   */
  getPriority(queryContext) {
    return 0;
  }

  /**
   * Starts querying.
   *
   * @param {object} queryContext The query context object
   * @param {Function} addCallback Callback invoked by the provider to add a new
   *        result.
   * @returns {Promise} resolved when the query stops.
   */
  async startQuery(queryContext, addCallback) {
    // Check if the query was cancelled while the autofill result was being
    // fetched. We don't expect this to be true since we also check the instance
    // in isActive and clear _autofillData in cancelQuery, but we sanity check it.
    if (
      !this._autofillData ||
      this._autofillData.instance != this.queryInstance
    ) {
      this.logger.error("startQuery invoked with an invalid _autofillData");
      return;
    }

    this._autofillData.result.heuristic = true;
    addCallback(this, this._autofillData.result);
    this._autofillData = null;
  }

  /**
   * Cancels a running query.
   *
   * @param {object} queryContext The query context object
   */
  cancelQuery(queryContext) {
    if (this._autofillData?.instance == this.queryInstance) {
      this._autofillData = null;
    }
  }

  /**
   * Filters hosts by retaining only the ones over the autofill threshold, then
   * sorts them by their frecency, and extracts the one with the highest value.
   *
   * @param {UrlbarQueryContext} queryContext The current queryContext.
   * @param {Array} hosts Array of host names to examine.
   * @returns {Promise<string?>}
   *   Resolved when the filtering is complete. Resolves with the top matching
   *   host, or null if not found.
   */
  async getTopHostOverThreshold(queryContext, hosts) {
    let db = await lazy.PlacesUtils.promiseLargeCacheDBConnection();
    let conditions = [];
    // Pay attention to the order of params, since they are not named.
    let params = [...hosts];
    if (!ORIGIN_USE_ALT_FRECENCY) {
      params.unshift(lazy.UrlbarPrefs.get("autoFill.stddevMultiplier"));
    }
    let sources = queryContext.sources;
    if (
      sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY) &&
      sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      conditions.push(`(bookmarked OR ${SQL_AUTOFILL_FRECENCY_THRESHOLD})`);
    } else if (sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY)) {
      conditions.push(`visited AND ${SQL_AUTOFILL_FRECENCY_THRESHOLD}`);
    } else if (sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)) {
      conditions.push("bookmarked");
    }

    let rows = await db.executeCached(
      `
        ${SQL_AUTOFILL_WITH},
        origins(id, prefix, host_prefix, host, fixed, host_frecency, frecency, bookmarked, visited) AS (
          SELECT
          id,
          prefix,
          first_value(prefix) OVER (
            PARTITION BY host ORDER BY ${ORIGIN_FRECENCY_FIELD} DESC, prefix = "https://" DESC, id DESC
          ),
          host,
          fixup_url(host),
          IFNULL(total(${ORIGIN_FRECENCY_FIELD}) OVER (PARTITION BY fixup_url(host)), 0.0),
          ${ORIGIN_FRECENCY_FIELD},
          MAX(EXISTS(
            SELECT 1 FROM moz_places WHERE origin_id = o.id AND foreign_count > 0
          )) OVER (PARTITION BY fixup_url(host)),
          MAX(EXISTS(
            SELECT 1 FROM moz_places WHERE origin_id = o.id AND visit_count > 0
          )) OVER (PARTITION BY fixup_url(host))
          FROM moz_origins o
          WHERE o.host IN (${new Array(hosts.length).fill("?").join(",")})
        )
        SELECT host
        FROM origins
        ${conditions.length ? "WHERE " + conditions.join(" AND ") : ""}
        ORDER BY frecency DESC, prefix = "https://" DESC, id DESC
        LIMIT 1
      `,
      params
    );
    if (!rows.length) {
      return null;
    }
    return rows[0].getResultByName("host");
  }

  /**
   * Obtains the query to search for autofill origin results.
   *
   * @param {UrlbarQueryContext} queryContext
   *   The current queryContext.
   * @returns {Array} consisting of the correctly optimized query to search the
   *         database with and an object containing the params to bound.
   */
  _getOriginQuery(queryContext) {
    // At this point, searchString is not a URL with a path; it does not
    // contain a slash, except for possibly at the very end.  If there is
    // trailing slash, remove it when searching here to match the rest of the
    // string because it may be an origin.
    let searchStr = this._searchString.endsWith("/")
      ? this._searchString.slice(0, -1)
      : this._searchString;

    let opts = {
      query_type: QUERYTYPE.AUTOFILL_ORIGIN,
      searchString: searchStr.toLowerCase(),
    };
    if (!ORIGIN_USE_ALT_FRECENCY) {
      opts.stddevMultiplier = lazy.UrlbarPrefs.get("autoFill.stddevMultiplier");
    }
    if (this._strippedPrefix) {
      opts.prefix = this._strippedPrefix;
    }

    if (
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY) &&
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      return [
        this._strippedPrefix
          ? QUERY_ORIGIN_PREFIX_HISTORY_BOOKMARK
          : QUERY_ORIGIN_HISTORY_BOOKMARK,
        opts,
      ];
    }
    if (queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY)) {
      return [
        this._strippedPrefix
          ? QUERY_ORIGIN_PREFIX_HISTORY
          : QUERY_ORIGIN_HISTORY,
        opts,
      ];
    }
    if (queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)) {
      return [
        this._strippedPrefix
          ? QUERY_ORIGIN_PREFIX_BOOKMARK
          : QUERY_ORIGIN_BOOKMARK,
        opts,
      ];
    }
    throw new Error("Either history or bookmark behavior expected");
  }

  /**
   * Obtains the query to search for autoFill url results.
   *
   * @param {UrlbarQueryContext} queryContext
   *   The current queryContext.
   * @returns {Array} consisting of the correctly optimized query to search the
   *         database with and an object containing the params to bound.
   */
  _getUrlQuery(queryContext) {
    // Try to get the host from the search string.  The host is the part of the
    // URL up to either the path slash, port colon, or query "?".  If the search
    // string doesn't look like it begins with a host, then return; it doesn't
    // make sense to do a URL query with it.
    const urlQueryHostRegexp = /^[^/:?]+/;
    let hostMatch = urlQueryHostRegexp.exec(this._searchString);
    if (!hostMatch) {
      return [null, null];
    }

    let host = hostMatch[0].toLowerCase();
    let revHost = host.split("").reverse().join("") + ".";

    // Build a string that's the URL stripped of its prefix, i.e., the host plus
    // everything after.  Use queryContext.trimmedSearchString instead of
    // this._searchString because this._searchString has had unEscapeURIForUI()
    // called on it.  It's therefore not necessarily the literal URL.
    let strippedURL = queryContext.trimmedSearchString;
    if (this._strippedPrefix) {
      strippedURL = strippedURL.substr(this._strippedPrefix.length);
    }
    strippedURL = host + strippedURL.substr(host.length);

    let opts = {
      query_type: QUERYTYPE.AUTOFILL_URL,
      searchString: this._searchString,
      revHost,
      strippedURL,
    };
    if (this._strippedPrefix) {
      opts.prefix = this._strippedPrefix;
    }

    if (
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY) &&
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      return [
        this._strippedPrefix
          ? QUERY_URL_PREFIX_HISTORY_BOOKMARK
          : QUERY_URL_HISTORY_BOOKMARK,
        opts,
      ];
    }
    if (queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY)) {
      return [
        this._strippedPrefix ? QUERY_URL_PREFIX_HISTORY : QUERY_URL_HISTORY,
        opts,
      ];
    }
    if (queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)) {
      return [
        this._strippedPrefix ? QUERY_URL_PREFIX_BOOKMARK : QUERY_URL_BOOKMARK,
        opts,
      ];
    }
    throw new Error("Either history or bookmark behavior expected");
  }

  _getAdaptiveHistoryQuery(queryContext) {
    let sourceCondition;
    if (
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY) &&
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      sourceCondition = "(h.foreign_count > 0 OR h.frecency > 20)";
    } else if (
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.HISTORY)
    ) {
      sourceCondition =
        "((h.visit_count > 0 OR h.foreign_count = 0) AND h.frecency > 20)";
    } else if (
      queryContext.sources.includes(UrlbarUtils.RESULT_SOURCE.BOOKMARKS)
    ) {
      sourceCondition = "h.foreign_count > 0";
    } else {
      return [];
    }

    let selectTitle;
    let joinBookmarks;
    if (UrlbarUtils.RESULT_SOURCE.BOOKMARKS) {
      selectTitle = "ifnull(b.title, matched.title)";
      joinBookmarks = "LEFT JOIN moz_bookmarks b ON b.fk = matched.id";
    } else {
      selectTitle = "matched.title";
      joinBookmarks = "";
    }

    const params = {
      queryType: QUERYTYPE.AUTOFILL_ADAPTIVE,
      // `fullSearchString` is the value the user typed including a prefix if
      // they typed one. `searchString` has been stripped of the prefix.
      fullSearchString: queryContext.searchString.toLowerCase(),
      searchString: this._searchString,
      strippedPrefix: this._strippedPrefix,
      useCountThreshold: lazy.UrlbarPrefs.get(
        "autoFillAdaptiveHistoryUseCountThreshold"
      ),
    };

    const query = `
      WITH matched(input, url, title, stripped_url, is_exact_match, starts_with, id) AS (
        SELECT
          i.input AS input,
          h.url AS url,
          h.title AS title,
          strip_prefix_and_userinfo(h.url) AS stripped_url,
          strip_prefix_and_userinfo(h.url) = :searchString AS is_exact_match,
          (strip_prefix_and_userinfo(h.url) COLLATE NOCASE BETWEEN :searchString AND :searchString || X'FFFF') AS starts_with,
          h.id AS id
        FROM moz_places h
        JOIN moz_inputhistory i ON i.place_id = h.id
        WHERE LENGTH(i.input) != 0
          AND :fullSearchString BETWEEN i.input AND i.input || X'FFFF'
          AND ${sourceCondition}
          AND i.use_count >= :useCountThreshold
          AND (:strippedPrefix = '' OR get_prefix(h.url) = :strippedPrefix)
          AND (
            starts_with OR
            (stripped_url COLLATE NOCASE BETWEEN 'www.' || :searchString AND 'www.' || :searchString || X'FFFF')
          )
        ORDER BY is_exact_match DESC, i.use_count DESC, h.frecency DESC, h.id DESC
        LIMIT 1
      )
      SELECT
        :queryType AS query_type,
        :searchString AS search_string,
        input,
        url,
        iif(starts_with, stripped_url, fixup_url(stripped_url)) AS url_fixed,
        ${selectTitle} AS title,
        stripped_url
      FROM matched
      ${joinBookmarks}
    `;

    return [query, params];
  }

  /**
   * Processes a matched row in the Places database.
   *
   * @param {object} row
   *   The matched row.
   * @param {UrlbarQueryContext} queryContext
   *   The query context.
   * @returns {UrlbarResult} a result generated from the matches row.
   */
  _processRow(row, queryContext) {
    let queryType = row.getResultByName("query_type");
    let title = row.getResultByName("title");

    // `searchString` is `this._searchString` or derived from it. It is
    // stripped, meaning the prefix (the URL protocol) has been removed.
    let searchString = row.getResultByName("search_string");

    // `fixedURL` is the part of the matching stripped URL that starts with the
    // stripped search string. The important point here is "www" handling. If a
    // stripped URL starts with "www", we allow the user to omit the "www" and
    // still match it. So if the matching stripped URL starts with "www" but the
    // stripped search string does not, `fixedURL` will also omit the "www".
    // Otherwise `fixedURL` will be equivalent to the matching stripped URL.
    //
    // Example 1:
    //   stripped URL: www.example.com/
    //   searchString: exam
    //   fixedURL: example.com/
    // Example 2:
    //   stripped URL: www.example.com/
    //   searchString: www.exam
    //   fixedURL: www.example.com/
    // Example 3:
    //   stripped URL: example.com/
    //   searchString: exam
    //   fixedURL: example.com/
    let fixedURL;

    // `finalCompleteValue` will be the UrlbarResult's URL. If the matching
    // stripped URL starts with "www" but the user omitted it,
    // `finalCompleteValue` will include it to properly reflect the real URL.
    let finalCompleteValue;

    let autofilledType;
    let adaptiveHistoryInput;

    switch (queryType) {
      case QUERYTYPE.AUTOFILL_ORIGIN: {
        fixedURL = row.getResultByName("host_fixed");
        finalCompleteValue = row.getResultByName("url");
        autofilledType = "origin";
        break;
      }
      case QUERYTYPE.AUTOFILL_URL: {
        let url = row.getResultByName("url");
        let strippedURL = row.getResultByName("stripped_url");

        if (!UrlbarUtils.canAutofillURL(url, strippedURL, true)) {
          return null;
        }

        // We autofill urls to-the-next-slash.
        // http://mozilla.org/foo/bar/baz will be autofilled to:
        //  - http://mozilla.org/f[oo/]
        //  - http://mozilla.org/foo/b[ar/]
        //  - http://mozilla.org/foo/bar/b[az]
        // And, toLowerCase() is preferred over toLocaleLowerCase() here
        // because "COLLATE NOCASE" in the SQL only handles ASCII characters.
        let strippedURLIndex = url
          .toLowerCase()
          .indexOf(strippedURL.toLowerCase());
        let strippedPrefix = url.substr(0, strippedURLIndex);
        let nextSlashIndex = url.indexOf(
          "/",
          strippedURLIndex + strippedURL.length - 1
        );
        fixedURL =
          nextSlashIndex < 0
            ? url.substr(strippedURLIndex)
            : url.substring(strippedURLIndex, nextSlashIndex + 1);
        finalCompleteValue = strippedPrefix + fixedURL;
        if (finalCompleteValue !== url) {
          title = null;
        }
        autofilledType = "url";
        break;
      }
      case QUERYTYPE.AUTOFILL_ADAPTIVE: {
        adaptiveHistoryInput = row.getResultByName("input");
        fixedURL = row.getResultByName("url_fixed");
        finalCompleteValue = row.getResultByName("url");
        autofilledType = "adaptive";
        break;
      }
    }

    // Compute `autofilledValue`, the full value that will be placed in the
    // input. It includes two parts: the part the user already typed in the
    // character case they typed it (`queryContext.searchString`), and the
    // autofilled part, which is the portion of the fixed URL starting after the
    // stripped search string.
    let autofilledValue =
      queryContext.searchString + fixedURL.substring(searchString.length);

    // If more than an origin was autofilled and the user typed the full
    // autofilled value, override the final URL by using the exact value the
    // user typed. This allows the user to visit a URL that differs from the
    // autofilled URL only in character case (for example "wikipedia.org/RAID"
    // vs. "wikipedia.org/Raid") by typing the full desired URL.
    if (
      queryType != QUERYTYPE.AUTOFILL_ORIGIN &&
      queryContext.searchString.length == autofilledValue.length
    ) {
      // Use `new URL().href` to lowercase the domain in the final completed
      // URL. This isn't necessary since domains are case insensitive, but it
      // looks nicer because it means the domain will remain lowercased in the
      // input, and it also reflects the fact that Firefox will visit the
      // lowercased name.
      const originalCompleteValue = new URL(finalCompleteValue).href;
      let strippedAutofilledValue = autofilledValue.substring(
        this._strippedPrefix.length
      );
      finalCompleteValue = new URL(
        finalCompleteValue.substring(
          0,
          finalCompleteValue.length - strippedAutofilledValue.length
        ) + strippedAutofilledValue
      ).href;

      // If the character case of except origin part of the original
      // finalCompleteValue differs from finalCompleteValue that includes user's
      // input, we set title null because it expresses different web page.
      if (finalCompleteValue !== originalCompleteValue) {
        title = null;
      }
    }

    let payload = {
      url: [finalCompleteValue, UrlbarUtils.HIGHLIGHT.TYPED],
      icon: UrlbarUtils.getIconForUrl(finalCompleteValue),
    };

    if (title) {
      payload.title = [title, UrlbarUtils.HIGHLIGHT.TYPED];
    } else {
      let trimHttps = lazy.UrlbarPrefs.get("trimHttps");
      let displaySpec = UrlbarUtils.prepareUrlForDisplay(finalCompleteValue, {
        trimURL: false,
      });
      let [fallbackTitle] = UrlbarUtils.stripPrefixAndTrim(displaySpec, {
        stripHttp: !trimHttps,
        stripHttps: trimHttps,
        trimEmptyQuery: true,
        trimSlash: !this._searchString.includes("/"),
      });
      payload.fallbackTitle = [fallbackTitle, UrlbarUtils.HIGHLIGHT.TYPED];
    }

    let result = new lazy.UrlbarResult(
      UrlbarUtils.RESULT_TYPE.URL,
      UrlbarUtils.RESULT_SOURCE.HISTORY,
      ...lazy.UrlbarResult.payloadAndSimpleHighlights(
        queryContext.tokens,
        payload
      )
    );

    result.autofill = {
      adaptiveHistoryInput,
      value: autofilledValue,
      selectionStart: queryContext.searchString.length,
      selectionEnd: autofilledValue.length,
      type: autofilledType,
    };
    return result;
  }

  async _getAutofillResult(queryContext) {
    // We may be autofilling an about: link.
    let result = this._matchAboutPageForAutofill(queryContext);
    if (result) {
      return result;
    }

    // It may also look like a URL we know from the database.
    result = await this._matchKnownUrl(queryContext);
    if (result) {
      return result;
    }

    return null;
  }

  _matchAboutPageForAutofill(queryContext) {
    // Check that the typed query is at least one character longer than the
    // about: prefix.
    if (this._strippedPrefix != "about:" || !this._searchString) {
      return null;
    }

    for (const aboutUrl of lazy.AboutPagesUtils.visibleAboutUrls) {
      if (aboutUrl.startsWith(`about:${this._searchString.toLowerCase()}`)) {
        let [trimmedUrl] = UrlbarUtils.stripPrefixAndTrim(aboutUrl, {
          stripHttp: true,
          trimEmptyQuery: true,
          trimSlash: !this._searchString.includes("/"),
        });
        let result = new lazy.UrlbarResult(
          UrlbarUtils.RESULT_TYPE.URL,
          UrlbarUtils.RESULT_SOURCE.HISTORY,
          ...lazy.UrlbarResult.payloadAndSimpleHighlights(queryContext.tokens, {
            title: [trimmedUrl, UrlbarUtils.HIGHLIGHT.TYPED],
            url: [aboutUrl, UrlbarUtils.HIGHLIGHT.TYPED],
            icon: UrlbarUtils.getIconForUrl(aboutUrl),
          })
        );
        let autofilledValue =
          queryContext.searchString +
          aboutUrl.substring(queryContext.searchString.length);
        result.autofill = {
          type: "about",
          value: autofilledValue,
          selectionStart: queryContext.searchString.length,
          selectionEnd: autofilledValue.length,
        };
        return result;
      }
    }
    return null;
  }

  async _matchKnownUrl(queryContext) {
    let conn = await lazy.PlacesUtils.promiseLargeCacheDBConnection();
    if (!conn) {
      return null;
    }

    // We try to autofill with adaptive history first.
    if (
      lazy.UrlbarPrefs.get("autoFillAdaptiveHistoryEnabled") &&
      lazy.UrlbarPrefs.get("autoFillAdaptiveHistoryMinCharsThreshold") <=
        queryContext.searchString.length
    ) {
      const [query, params] = this._getAdaptiveHistoryQuery(queryContext);
      if (query) {
        const resultSet = await conn.executeCached(query, params);
        if (resultSet.length) {
          return this._processRow(resultSet[0], queryContext);
        }
      }
    }

    // The adaptive history query is passed queryContext.searchString (the full
    // search string), but the origin and URL queries are passed the prefix
    // (this._strippedPrefix) and the rest of the search string
    // (this._searchString) separately. The user must specify a non-prefix part
    // to trigger origin and URL autofill.
    if (!this._searchString.length) {
      return null;
    }

    // If search string looks like an origin, try to autofill against origins.
    // Otherwise treat it as a possible URL.  When the string has only one slash
    // at the end, we still treat it as an URL.
    let query, params;
    if (
      lazy.UrlbarTokenizer.looksLikeOrigin(this._searchString, {
        ignoreKnownDomains: true,
      })
    ) {
      [query, params] = this._getOriginQuery(queryContext);
    } else {
      [query, params] = this._getUrlQuery(queryContext);
    }

    // _getUrlQuery doesn't always return a query.
    if (query) {
      let rows = await conn.executeCached(query, params);
      if (rows.length) {
        return this._processRow(rows[0], queryContext);
      }
    }
    return null;
  }
}

export var UrlbarProviderAutofill = new ProviderAutofill();