Bug 1239708: Improve awesomebar autofill. Part 0: Core changes. r?mak draft
authorDrew Willcoxon <adw@mozilla.com>
Mon, 14 May 2018 11:19:04 -0700
changeset 794912 c4b05f3d83a0581e3518b88bc778a119f8b1f7b9
parent 794866 c96b4323d7b8149d7737723e1a4937447cb46c18
child 794913 131e2bad2f6b0480be96e0548a04ad8ba7e84992
push id109819
push userbmo:adw@mozilla.com
push dateMon, 14 May 2018 20:01:28 +0000
reviewersmak
bugs1239708
milestone62.0a1
Bug 1239708: Improve awesomebar autofill. Part 0: Core changes. r?mak MozReview-Commit-ID: DmPVD6Z3Vj8
toolkit/components/places/UnifiedComplete.js
toolkit/components/places/nsPlacesIndexes.h
toolkit/components/places/nsPlacesTables.h
toolkit/components/places/nsPlacesTriggers.h
--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -27,17 +27,16 @@ const INSERTMETHOD = {
   MERGE: 2 // Always merge previous and current results
 };
 
 // Prefs are defined as [pref name, default value].
 const PREF_URLBAR_BRANCH = "browser.urlbar.";
 const PREF_URLBAR_DEFAULTS = new Map([
   ["autocomplete.enabled", true],
   ["autoFill", true],
-  ["autoFill.typed", true],
   ["autoFill.searchEngines", false],
   ["restyleSearches", false],
   ["delay", 50],
   ["matchBehavior", MATCH_BOUNDARY_ANYWHERE],
   ["filter.javascript", true],
   ["maxRichResults", 10],
   ["suggest.history", true],
   ["suggest.bookmark", true],
@@ -54,17 +53,17 @@ const PREF_URLBAR_DEFAULTS = new Map([
 ]);
 const PREF_OTHER_DEFAULTS = new Map([
   ["keyword.enabled", true],
 ]);
 
 // AutoComplete query type constants.
 // Describes the various types of queries that we can process rows for.
 const QUERYTYPE_FILTERED            = 0;
-const QUERYTYPE_AUTOFILL_HOST       = 1;
+const QUERYTYPE_AUTOFILL_ORIGIN     = 1;
 const QUERYTYPE_AUTOFILL_URL        = 2;
 
 // This separator is used as an RTL-friendly way to split the title and tags.
 // It can also be used by an nsIAutoCompleteResult consumer to re-split the
 // "comment" back into the title and the tag.
 const TITLE_TAGS_SEPARATOR = " \u2013 ";
 
 // Telemetry probes.
@@ -88,16 +87,19 @@ const MAXIMUM_ALLOWED_EXTENSION_TIME_MS 
 const REGEXP_SINGLEWORD_HOST = new RegExp("^[a-z0-9-]+$", "i");
 
 // Regex used to match userContextId.
 const REGEXP_USER_CONTEXT_ID = /(?:^| )user-context-id:(\d+)/;
 
 // Regex used to match one or more whitespace.
 const REGEXP_SPACES = /\s+/;
 
+// Regex used to strip prefixes from URLs.  See stripPrefix().
+const REGEXP_STRIP_PREFIX = /^[a-zA-Z]+:(?:\/\/)?/;
+
 // The result is notified on a delay, to avoid rebuilding the panel at every match.
 const NOTIFYRESULT_DELAY_MS = 16;
 
 // Sqlite result row index constants.
 const QUERYINDEX_QUERYTYPE     = 0;
 const QUERYINDEX_URL           = 1;
 const QUERYINDEX_TITLE         = 2;
 const QUERYINDEX_BOOKMARKED    = 3;
@@ -236,79 +238,121 @@ const SQL_ADAPTIVE_QUERY =
          AND t.userContextId = :userContextId
    WHERE AUTOCOMPLETE_MATCH(NULL, h.url,
                             IFNULL(btitle, h.title), tags,
                             h.visit_count, h.typed, bookmarked,
                             t.open_count,
                             :matchBehavior, :searchBehavior)
    ORDER BY rank DESC, h.frecency DESC`;
 
+// Result row indexes for originQuery()
+const QUERYINDEX_ORIGIN_AUTOFILLED_VALUE = 1;
+const QUERYINDEX_ORIGIN_URL = 2;
+const QUERYINDEX_ORIGIN_FRECENCY = 3;
 
-function hostQuery(conditions = "") {
-  let query =
-    `/* do not warn (bug NA): not worth to index on (typed, frecency) */
-     SELECT :query_type, host || '/', IFNULL(prefix, 'http://') || host || '/',
-            NULL, NULL, NULL, NULL, NULL, NULL, NULL, frecency
-     FROM moz_hosts
-     WHERE host BETWEEN :searchString AND :searchString || X'FFFF'
-     AND frecency <> 0
-     ${conditions}
-     ORDER BY frecency DESC
-     LIMIT 1`;
-  return query;
+function originQuery(conditions = "", bookmarkedFragment = "NULL") {
+  return `SELECT :query_type,
+                 host || '/',
+                 prefix || host || '/',
+                 frecency,
+                 ${bookmarkedFragment} AS bookmarked,
+                 id
+          FROM moz_origins
+          WHERE host BETWEEN :searchString AND :searchString || X'FFFF'
+                AND frecency <> 0
+                ${conditions}
+          UNION ALL
+          SELECT :query_type,
+                 fixup_url(host) || '/',
+                 prefix || host || '/',
+                 frecency,
+                 ${bookmarkedFragment} AS bookmarked,
+                 id
+          FROM moz_origins
+          WHERE host BETWEEN 'www.' || :searchString AND 'www.' || :searchString || X'FFFF'
+                AND frecency <> 0
+                ${conditions}
+          ORDER BY frecency DESC, id DESC
+          LIMIT 1 `;
 }
 
-const SQL_HOST_QUERY = hostQuery();
+const SQL_ORIGIN_QUERY = originQuery();
+
+const SQL_ORIGIN_PREFIX_QUERY = originQuery(
+  `AND prefix BETWEEN :prefix AND :prefix || X'FFFF'`
+);
+
+const SQL_ORIGIN_BOOKMARKED_QUERY = originQuery(
+  `AND bookmarked`,
+  `(SELECT foreign_count > 0 FROM moz_places
+    WHERE moz_places.origin_id = moz_origins.id)`
+);
 
-const SQL_TYPED_HOST_QUERY = hostQuery("AND typed = 1");
+const SQL_ORIGIN_PREFIX_BOOKMARKED_QUERY = originQuery(
+  `AND bookmarked
+   AND prefix BETWEEN :prefix AND :prefix || X'FFFF'`,
+  `(SELECT foreign_count > 0 FROM moz_places
+    WHERE moz_places.origin_id = moz_origins.id)`
+);
+
+// Result row indexes for urlQuery()
+const QUERYINDEX_URL_URL = 1;
+const QUERYINDEX_URL_STRIPPED_URL = 2;
+const QUERYINDEX_URL_FRECENCY = 3;
 
-function bookmarkedHostQuery(conditions = "") {
-  let query =
-    `/* do not warn (bug NA): not worth to index on (typed, frecency) */
-     SELECT :query_type, host || '/', IFNULL(prefix, 'http://') || host || '/',
-            ( SELECT foreign_count > 0 FROM moz_places
-              WHERE rev_host = get_unreversed_host(host || '.') || '.'
-                 OR rev_host = get_unreversed_host(host || '.') || '.www.'
-            ) AS bookmarked, NULL, NULL, NULL, NULL, NULL, NULL, frecency
-     FROM moz_hosts
-     WHERE host BETWEEN :searchString AND :searchString || X'FFFF'
-     AND bookmarked
-     AND frecency <> 0
-     ${conditions}
-     ORDER BY frecency DESC
-     LIMIT 1`;
-  return query;
+function urlQuery(conditions1, conditions2) {
+  return `/* do not warn (bug no): cannot use an index to sort */
+          SELECT :query_type,
+                 url,
+                 :strippedURL,
+                 frecency,
+                 foreign_count > 0 AS bookmarked,
+                 id
+          FROM moz_places
+          WHERE rev_host = :revHost
+                AND frecency <> 0
+                ${conditions1}
+          UNION ALL
+          SELECT :query_type,
+                 url,
+                 :strippedURL,
+                 frecency,
+                 foreign_count > 0 AS bookmarked,
+                 id
+          FROM moz_places
+          WHERE rev_host = :revHost || 'www.'
+                AND frecency <> 0
+                ${conditions2}
+          ORDER BY frecency DESC, id DESC
+          LIMIT 1 `;
 }
 
-const SQL_BOOKMARKED_HOST_QUERY = bookmarkedHostQuery();
+const SQL_URL_QUERY = urlQuery(
+  `AND strip_prefix_and_userinfo(url) BETWEEN :strippedURL AND :strippedURL || X'FFFF'`,
+  `AND strip_prefix_and_userinfo(url) BETWEEN 'www.' || :strippedURL AND 'www.' || :strippedURL || X'FFFF'`
+);
 
-const SQL_BOOKMARKED_TYPED_HOST_QUERY = bookmarkedHostQuery("AND typed = 1");
+const SQL_URL_PREFIX_QUERY = urlQuery(
+  `AND url BETWEEN :prefix || :strippedURL AND :prefix || :strippedURL || X'FFFF'`,
+  `AND url BETWEEN :prefix || 'www.' || :strippedURL AND :prefix || 'www.' || :strippedURL || X'FFFF'`
+);
 
-function urlQuery(conditions = "") {
-  return `/* do not warn (bug no): cannot use an index to sort */
-          SELECT :query_type, h.url, NULL,
-            foreign_count > 0 AS bookmarked,
-            NULL, NULL, NULL, NULL, NULL, NULL, h.frecency
-          FROM moz_places h
-          WHERE (rev_host = :revHost OR rev_host = :revHost || "www.")
-          AND h.frecency <> 0
-          AND fixup_url(h.url) BETWEEN :searchString AND :searchString || X'FFFF'
-          ${conditions}
-          ORDER BY h.frecency DESC, h.id DESC
-          LIMIT 1`;
-}
+const SQL_URL_BOOKMARKED_QUERY = urlQuery(
+  `AND bookmarked
+   AND strip_prefix_and_userinfo(url) BETWEEN :strippedURL AND :strippedURL || X'FFFF'`,
+  `AND bookmarked
+   AND strip_prefix_and_userinfo(url) BETWEEN 'www.' || :strippedURL AND 'www.' || :strippedURL || X'FFFF'`
+);
 
-const SQL_URL_QUERY = urlQuery();
-
-const SQL_TYPED_URL_QUERY = urlQuery("AND h.typed = 1");
-
-// TODO (bug 1045924): use foreign_count once available.
-const SQL_BOOKMARKED_URL_QUERY = urlQuery("AND bookmarked");
-
-const SQL_BOOKMARKED_TYPED_URL_QUERY = urlQuery("AND bookmarked AND h.typed = 1");
+const SQL_URL_PREFIX_BOOKMARKED_QUERY = urlQuery(
+  `AND bookmarked
+   AND url BETWEEN :prefix || :strippedURL AND :prefix || :strippedURL || X'FFFF'`,
+  `AND bookmarked
+   AND url BETWEEN :prefix || 'www.' || :strippedURL AND :prefix || 'www.' || :strippedURL || X'FFFF'`
+);
 
 // Getters
 
 ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm");
 ChromeUtils.import("resource://gre/modules/Services.jsm");
 
 Cu.importGlobalProperties(["fetch"]);
 
@@ -629,16 +673,17 @@ XPCOMUtils.defineLazyGetter(this, "Prelo
   sites: [],
 
   add(url, title) {
     let site = new PreloadedSite(url, title);
     this.sites.push(site);
   },
 
   populate(sites) {
+    this.sites = [];
     for (let site of sites) {
       this.add(site[0], site[1]);
     }
   },
 }));
 
 XPCOMUtils.defineLazyGetter(this, "ProfileAgeCreatedPromise", () => {
   return (new ProfileAge(null, null)).created;
@@ -656,37 +701,35 @@ XPCOMUtils.defineLazyGetter(this, "Profi
  *       empty string.  We don't want that, as it'll break our logic, so return
  *       an empty array then.
  */
 function getUnfilteredSearchTokens(searchString) {
   return searchString.length ? searchString.split(REGEXP_SPACES) : [];
 }
 
 /**
- * Strip prefixes from the URI that we don't care about for searching.
+ * Strips the prefix from a URL and returns the prefix and the remainder of the
+ * URL.  "Prefix" is defined to be the scheme and colon, plus, if present, two
+ * slashes.  If the given string is not actually a URL, then an empty prefix and
+ * the string itself is returned.
  *
- * @param spec
- *        The text to modify.
- * @return the modified spec.
+ * @param  str
+ *         The possible URL to strip.
+ * @return If `str` is a URL, then [prefix, remainder].  Otherwise, ["", str].
  */
-function stripPrefix(spec) {
-  ["http://", "https://", "ftp://"].some(scheme => {
-    // Strip protocol if not directly followed by a space
-    if (spec.startsWith(scheme) && spec[scheme.length] != " ") {
-      spec = spec.slice(scheme.length);
-      return true;
-    }
-    return false;
-  });
-
-  // Strip www. if not directly followed by a space
-  if (spec.startsWith("www.") && spec[4] != " ") {
-    spec = spec.slice(4);
+function stripPrefix(str) {
+  let match = REGEXP_STRIP_PREFIX.exec(str);
+  if (!match) {
+    return ["", str];
   }
-  return spec;
+  let prefix = match[0];
+  if (prefix.length < str.length && str[prefix.length] == " ") {
+    return ["", str];
+  }
+  return [prefix, str.substr(prefix.length)];
 }
 
 /**
  * Strip http and trailing separators from a spec.
  *
  * @param spec
  *        The text to modify.
  * @param trimSlash
@@ -733,16 +776,35 @@ function makeKeyForURL(match) {
 function looksLikeUrl(str, ignoreAlphanumericHosts = false) {
   // Single word not including special chars.
   return !REGEXP_SPACES.test(str) &&
          (["/", "@", ":", "["].some(c => str.includes(c)) ||
           (ignoreAlphanumericHosts ? /(.*\..*){3,}/.test(str) : str.includes(".")));
 }
 
 /**
+ * Returns:
+ *
+ *   * `str` if `str` doesn't have any slashes
+ *   * `str` trimmed of its trailing slash if it's the only slash
+ *   * null if `str` has a slash that's not trailing
+ */
+function trimTrailingSlashIfOnlySlash(str) {
+  let slashIndex = str.indexOf("/");
+  if (slashIndex >= 0) {
+    if (slashIndex < str.length - 1) {
+      return null;
+    }
+    // Trim the trailing slash.
+    str = str.slice(0, -1);
+  }
+  return str;
+}
+
+/**
  * Manages a single instance of an autocomplete search.
  *
  * The first three parameters all originate from the similarly named parameters
  * of nsIAutoCompleteSearch.startSearch().
  *
  * @param searchString
  *        The search string.
  * @param searchParam
@@ -766,26 +828,19 @@ function looksLikeUrl(str, ignoreAlphanu
  * @param [optional] previousResult
  *        The result object from the previous search. if available.
  */
 function Search(searchString, searchParam, autocompleteListener,
                 autocompleteSearch, prohibitSearchSuggestions, previousResult) {
   // We want to store the original string for case sensitive searches.
   this._originalSearchString = searchString;
   this._trimmedOriginalSearchString = searchString.trim();
-  let strippedOriginalSearchString =
-    stripPrefix(this._trimmedOriginalSearchString.toLowerCase());
-  this._searchString =
-    Services.textToSubURI.unEscapeURIForUI("UTF-8", strippedOriginalSearchString);
-
-  // The protocol and the host are lowercased by nsIURI, so it's fine to
-  // lowercase the typed prefix, to add it back to the results later.
-  this._strippedPrefix = this._trimmedOriginalSearchString.slice(
-    0, this._trimmedOriginalSearchString.length - strippedOriginalSearchString.length
-  ).toLowerCase();
+  let [prefix, suffix] = stripPrefix(this._trimmedOriginalSearchString);
+  this._searchString = Services.textToSubURI.unEscapeURIForUI("UTF-8", suffix);
+  this._strippedPrefix = prefix.toLowerCase();
 
   this._matchBehavior = Prefs.get("matchBehavior");
   // Set the default behavior for this search.
   this._behavior = this._searchString ? Prefs.get("defaultBehavior")
                                       : Prefs.get("emptySearchDefaultBehavior");
 
   let params = new Set(searchParam.split(" "));
   this._enableActions = params.has("enable-actions");
@@ -847,24 +902,16 @@ function Search(searchString, searchPara
 
   // These are used to avoid adding duplicate entries to the results.
   this._usedURLs = [];
   this._usedPlaceIds = new Set();
 
   // Counters for the number of matches per MATCHTYPE.
   this._counts = Object.values(MATCHTYPE)
                        .reduce((o, p) => { o[p] = 0; return o; }, {});
-
-  this._searchStringHasWWW = this._strippedPrefix.endsWith("www.");
-  this._searchStringWWW = this._searchStringHasWWW ? "www." : "";
-  this._searchStringFromWWW = this._searchStringWWW + this._searchString;
-
-  this._searchStringSchemeFound = this._strippedPrefix.match(/^(\w+):/i);
-  this._searchStringScheme = this._searchStringSchemeFound ?
-                             this._searchStringSchemeFound[1].toLowerCase() : "";
 }
 
 Search.prototype = {
   /**
    * Enables the desired AutoComplete behavior.
    *
    * @param type
    *        The behavior type to set.
@@ -1012,17 +1059,17 @@ Search.prototype = {
     // wait for the initialization of PlacesSearchAutocompleteProvider first.
     await PlacesSearchAutocompleteProvider.ensureInitialized();
     if (!this.pending)
       return;
 
     // For any given search, we run many queries/heuristics:
     // 1) by alias (as defined in SearchService)
     // 2) inline completion from search engine resultDomains
-    // 3) inline completion for hosts (this._hostQuery) or urls (this._urlQuery)
+    // 3) inline completion for origins (this._originQuery) or urls (this._urlQuery)
     // 4) directly typed in url (ie, can be navigated to as-is)
     // 5) submission for the current search engine
     // 6) Places keywords
     // 7) adaptive learning (this._adaptiveQuery)
     // 8) open pages not supported by history (this._switchToTabQuery)
     // 9) query based on match behavior
     //
     // (6) only gets ran if we get any filtered tokens, since if there are no
@@ -1160,117 +1207,68 @@ Search.prototype = {
       return;
     let profileCreationDate = await ProfileAgeCreatedPromise;
     let daysSinceProfileCreation = (Date.now() - profileCreationDate) / MS_PER_DAY;
     if (daysSinceProfileCreation > Prefs.get("usepreloadedtopurls.expire_days"))
       Services.prefs.setBoolPref("browser.urlbar.usepreloadedtopurls.enabled", false);
   },
 
   _matchPreloadedSites() {
-    if (!Prefs.get("usepreloadedtopurls.enabled"))
+    if (!Prefs.get("usepreloadedtopurls.enabled")) {
       return;
-
-    // In case user typed just "https://" or "www." or "https://www."
-    // - we do not put out the whole lot of sites
-    if (!this._searchString)
-      return;
+    }
 
-    if (!(this._searchStringScheme === "" ||
-          this._searchStringScheme === "https" ||
-          this._searchStringScheme === "http"))
+    if (!this._searchString) {
+      // The user hasn't typed anything, or they've only typed a scheme.
       return;
-
-    let strictMatches = [];
-    let looseMatches = [];
+    }
 
     for (let site of PreloadedSiteStorage.sites) {
-      if (this._searchStringScheme && this._searchStringScheme !== site.uri.scheme)
-        continue;
-      let match = {
-        value: site.uri.spec,
-        comment: site.title,
-        style: "preloaded-top-site",
-        frecency: FRECENCY_DEFAULT - 1,
-      };
-      if (site.uri.host.includes(this._searchStringFromWWW) ||
-          site._matchTitle.includes(this._searchStringFromWWW)) {
-        strictMatches.push(match);
-      } else if (site.uri.host.includes(this._searchString) ||
-                 site._matchTitle.includes(this._searchString)) {
-        looseMatches.push(match);
+      let url = site.uri.spec;
+      if ((!this._strippedPrefix || url.startsWith(this._strippedPrefix)) &&
+          (site.uri.host.includes(this._searchString) ||
+           site._matchTitle.includes(this._searchString))) {
+        this._addMatch({
+          value: url,
+          comment: site.title,
+          style: "preloaded-top-site",
+          frecency: FRECENCY_DEFAULT - 1,
+        });
       }
     }
-    for (let match of [...strictMatches, ...looseMatches]) {
-      this._addMatch(match);
-    }
   },
 
   _matchPreloadedSiteForAutofill() {
-    if (!Prefs.get("usepreloadedtopurls.enabled"))
+    if (!Prefs.get("usepreloadedtopurls.enabled")) {
       return false;
-
-    if (!(this._searchStringScheme === "" ||
-          this._searchStringScheme === "https" ||
-          this._searchStringScheme === "http"))
-      return false;
+    }
 
-    let searchStringSchemePrefix = this._searchStringScheme
-                                   ? (this._searchStringScheme + "://")
-                                   : "";
-
-    // If search string has scheme - we'll match it strictly
-    function matchScheme(site, search) {
-      return !search._searchStringScheme ||
-             search._searchStringScheme === site.uri.scheme;
+    let matchedSite = PreloadedSiteStorage.sites.find(site => {
+      return (!this._strippedPrefix ||
+              site.uri.spec.startsWith(this._strippedPrefix)) &&
+             (site.uri.host.startsWith(this._searchString) ||
+              site.uri.host.startsWith("www." + this._searchString));
+    });
+    if (!matchedSite) {
+      return false;
     }
 
-    // First we try to strict-match
-    // If search string has "www."- we try to strict-match it along with "www."
-    function matchStrict(site) {
-      return site.uri.host.startsWith(this._searchStringFromWWW)
-             && matchScheme(site, this);
-    }
-    let site = PreloadedSiteStorage.sites.find(matchStrict, this);
-    if (site) {
-      let match = {
-        // We keep showing prefix that user typed, then what we match on
-        value: searchStringSchemePrefix + site.uri.host + "/",
-        style: "autofill preloaded-top-site",
-        finalCompleteValue: site.uri.spec,
-        frecency: Infinity
-      };
-      this._result.setDefaultIndex(0);
-      this._addMatch(match);
-      return true;
-    }
+    this._result.setDefaultIndex(0);
+
+    let url = matchedSite.uri.spec;
+    let value = stripPrefix(url)[1];
+    value = value.substr(value.indexOf(this._searchString));
 
-    // If no strict result found - we try loose match
-    // regardless of "www." in Preloaded-sites or search string
-    function matchLoose(site) {
-      return site._hostWithoutWWW.startsWith(this._searchString)
-             && matchScheme(site, this);
-    }
-    site = PreloadedSiteStorage.sites.find(matchLoose, this);
-    if (site) {
-      let match = {
-        // We keep showing prefix that user typed, then what we match on
-        value: searchStringSchemePrefix + this._searchStringWWW +
-               site._hostWithoutWWW + "/",
-        style: "autofill preloaded-top-site",
-        // On loose match, result should always have "www."
-        finalCompleteValue: site.uri.scheme + "://www." +
-                            site._hostWithoutWWW + "/",
-        frecency: Infinity
-      };
-      this._result.setDefaultIndex(0);
-      this._addMatch(match);
-      return true;
-    }
-
-    return false;
+    this._addAutofillMatch(
+      value,
+      url,
+      Infinity,
+      ["preloaded-top-site"]
+    );
+    return true;
   },
 
   async _matchFirstHeuristicResult(conn) {
     // We always try to make the first result a special "heuristic" result.  The
     // heuristics below determine what type of result it will be, if any.
 
     let hasSearchTerms = this._searchTokens.length > 0;
 
@@ -1303,18 +1301,18 @@ Search.prototype = {
       // It may also look like a URL we know from the database.
       let matched = await this._matchKnownUrl(conn);
       if (matched) {
         return true;
       }
     }
 
     if (this.pending && shouldAutofill) {
-      // Or it may look like a URL we know about from search engines.
-      let matched = await this._matchSearchEngineUrl();
+      // Or it may look like a search engine domain.
+      let matched = await this._matchSearchEngineDomain();
       if (matched) {
         return true;
       }
     }
 
     if (this.pending && shouldAutofill) {
       let matched = this._matchPreloadedSiteForAutofill();
       if (matched) {
@@ -1415,44 +1413,36 @@ Search.prototype = {
     }
 
     // Disallow fetching search suggestions for strings looking like URLs, to
     // avoid disclosing information about networks or passwords.
     return this._searchTokens.some(looksLikeUrl);
   },
 
   async _matchKnownUrl(conn) {
-    // Hosts have no "/" in them.
-    let lastSlashIndex = this._searchString.lastIndexOf("/");
-    // Search only URLs if there's a slash in the search string...
-    if (lastSlashIndex != -1) {
-      // ...but not if it's exactly at the end of the search string.
-      if (lastSlashIndex < this._searchString.length - 1) {
-        // We don't want to execute this query right away because it needs to
-        // search the entire DB without an index, but we need to know if we have
-        // a result as it will influence other heuristics. So we guess by
-        // assuming that if we get a result from a *host* query and it *looks*
-        // like a URL, then we'll probably have a result.
-        let gotResult = false;
-        let [ query, params ] = this._urlQuery;
-        await conn.executeCached(query, params, (row, cancel) => {
-          gotResult = true;
-          this._onResultRow(row, cancel);
-        });
-        return gotResult;
-      }
-      return false;
+    let gotResult = false;
+
+    // If search string has a slash in it, then treat it as a possible URL and
+    // try to autofill against URLs.  Otherwise treat it as a possible origin
+    // and try to autofill against origins.  One exception:  When the string has
+    // only one slash and it's at the end, treat it as a possible origin, not a
+    // URL.
+    let query, params;
+    if (trimTrailingSlashIfOnlySlash(this._searchString)) {
+      [query, params] = this._originQuery;
+    } else {
+      [query, params] = this._urlQuery;
     }
 
-    let gotResult = false;
-    let [ query, params ] = this._hostQuery;
-    await conn.executeCached(query, params, (row, cancel) => {
-      gotResult = true;
-      this._onResultRow(row, cancel);
-    });
+    if (query) {
+      await conn.executeCached(query, params, (row, cancel) => {
+        gotResult = true;
+        this._onResultRow(row, cancel);
+      });
+    }
     return gotResult;
   },
 
   _matchExtensionHeuristicResult() {
     if (ExtensionSearchHandler.isKeywordRegistered(this._searchTokens[0]) &&
         this._originalSearchString.length > this._searchTokens[0].length) {
       let description = ExtensionSearchHandler.getDescription(this._searchTokens[0]);
       this._addExtensionMatch(this._originalSearchString, description);
@@ -1501,63 +1491,62 @@ Search.prototype = {
       // but the string does, it may cause pointless icon flicker on typing.
       icon: "page-icon:" + entry.url.href,
       style,
       frecency: Infinity
     });
     return true;
   },
 
-  async _matchSearchEngineUrl() {
-    if (!Prefs.get("autoFill.searchEngines"))
+  async _matchSearchEngineDomain() {
+    if (!Prefs.get("autoFill.searchEngines")) {
       return false;
-
-    let match = await PlacesSearchAutocompleteProvider.findMatchByToken(
-                                                           this._searchString);
-    if (!match)
+    }
+    if (!this._searchString) {
       return false;
+    }
 
-    // The match doesn't contain a 'scheme://www.' prefix, but since we have
-    // stripped it from the search string, here we could still be matching
-    // 'https://www.g' to 'google.com'.
-    // There are a couple cases where we don't want to match though:
-    //
-    //  * If the protocol differs we should not match. For example if the user
-    //    searched https we should not return http.
-    try {
-      let prefixURI = Services.io.newURI(this._strippedPrefix + match.token);
-      let finalURI = Services.io.newURI(match.url);
-      if (prefixURI.scheme != finalURI.scheme)
-        return false;
-    } catch (e) {}
-
-    //  * If the user typed "www." but the final url doesn't have it, we
-    //    should not match as well, the two urls may point to different pages.
-    if (this._strippedPrefix.endsWith("www.") &&
-        !stripHttpAndTrim(match.url).startsWith("www."))
-      return false;
-
-    let value = this._strippedPrefix + match.token;
-
-    // In any case, we should never arrive here with a value that doesn't
-    // match the search string.  If this happens there is some case we
-    // are not handling properly yet.
-    if (!value.startsWith(this._originalSearchString)) {
-      Cu.reportError(`Trying to inline complete in-the-middle
-                      ${this._originalSearchString} to ${value}`);
+    // PlacesSearchAutocompleteProvider only matches against engine domains.  If
+    // the search string (without the prefix) contains multiple slashes, or a
+    // single slash that's not at the end, don't try to match.
+    let searchStr = trimTrailingSlashIfOnlySlash(this._searchString);
+    if (!searchStr) {
       return false;
     }
 
+    let match =
+      await PlacesSearchAutocompleteProvider.findMatchByToken(searchStr);
+    if (!match ||
+        (this._strippedPrefix && !match.url.startsWith(this._strippedPrefix))) {
+      return false;
+    }
+
+    // The value that's autofilled in the input is the prefix the user typed, if
+    // any, plus the portion of the engine domain that the user typed.  Append a
+    // trailing slash too, as is usual with autofill.
+    let value =
+      this._strippedPrefix +
+      match.token.substr(match.token.indexOf(searchStr)) +
+      "/";
+
+    let finalCompleteValue = match.url;
+    try {
+      let fixupInfo = Services.uriFixup.getFixupURIInfo(match.url, 0);
+      if (fixupInfo.fixedURI) {
+        finalCompleteValue = fixupInfo.fixedURI.spec;
+      }
+    } catch (ex) {}
+
     this._result.setDefaultIndex(0);
     this._addMatch({
       value,
+      finalCompleteValue,
       comment: match.engineName,
       icon: match.iconUrl,
       style: "priority-search",
-      finalCompleteValue: match.url,
       frecency: Infinity
     });
     return true;
   },
 
   async _matchSearchEngineAlias() {
     if (this._searchTokens.length < 1)
       return false;
@@ -1760,36 +1749,35 @@ Search.prototype = {
     }
 
     this._addMatch(match);
     return true;
   },
 
   _onResultRow(row, cancel) {
     let queryType = row.getResultByIndex(QUERYINDEX_QUERYTYPE);
-    let match;
     switch (queryType) {
-      case QUERYTYPE_AUTOFILL_HOST:
+      case QUERYTYPE_AUTOFILL_ORIGIN:
         this._result.setDefaultIndex(0);
-        match = this._processHostRow(row);
+        this._addOriginAutofillMatch(row);
         break;
       case QUERYTYPE_AUTOFILL_URL:
         this._result.setDefaultIndex(0);
-        match = this._processUrlRow(row);
+        this._addURLAutofillMatch(row);
         break;
       case QUERYTYPE_FILTERED:
-        match = this._processRow(row);
+        this._addFilteredQueryMatch(row);
         break;
     }
-    this._addMatch(match);
     // If the search has been canceled by the user or by _addMatch, or we
     // fetched enough results, we can stop the underlying Sqlite query.
     let count = this._counts[MATCHTYPE.GENERAL] + this._counts[MATCHTYPE.HEURISTIC];
-    if (!this.pending || count >= Prefs.get("maxRichResults"))
+    if (!this.pending || count >= Prefs.get("maxRichResults")) {
       cancel();
+    }
   },
 
   _maybeRestyleSearchMatch(match) {
     // Return if the URL does not represent a search result.
     let parseResult =
       PlacesSearchAutocompleteProvider.parseSubmissionURL(match.value);
     if (!parseResult) {
       return;
@@ -1825,30 +1813,16 @@ Search.prototype = {
     else if (typeof match.type != "string")
       match.type = MATCHTYPE.GENERAL;
 
     // A search could be canceled between a query start and its completion,
     // in such a case ensure we won't notify any result for it.
     if (!this.pending)
       return;
 
-    // For autofill entries, the comment field must be a stripped version
-    // of the final destination url, so that the user will definitely know
-    // where he is going to end up. For example, if the user is visiting a
-    // secure page, we'll leave the https on it, to let him know that.
-    // This must happen before generating the dedupe key.
-    if (match.hasOwnProperty("style") && match.style.includes("autofill")) {
-      // We fallback to match.value, as that's what autocomplete does if
-      // finalCompleteValue is null.
-      // Trim only if the value looks like a domain, we want to retain the
-      // trailing slash if we're completing a url to the next slash.
-      match.comment = stripHttpAndTrim(match.finalCompleteValue || match.value,
-                                       !this._searchString.includes("/"));
-    }
-
     match.style = match.style || "favicon";
 
     // Restyle past searches, unless they are bookmarks or special results.
     if (Prefs.get("restyleSearches") && match.style == "favicon") {
       this._maybeRestyleSearchMatch(match);
     }
 
     if (this._addingHeuristicFirstMatch) {
@@ -2003,17 +1977,18 @@ Search.prototype = {
     if (this._previousSearchMatchTypes.length == 0 || !this.pending)
       return;
 
     let index = 0;
     let changed = false;
     if (!this._buckets) {
       // No match arrived yet, so any match of the given type should be removed
       // from the top.
-      while (this._previousSearchMatchTypes[0] == type) {
+      while (this._previousSearchMatchTypes.length &&
+             this._previousSearchMatchTypes[0] == type) {
         this._previousSearchMatchTypes.shift();
         this._result.removeMatchAt(0);
         changed = true;
       }
     } else {
       for (let bucket of this._buckets) {
         if (bucket.type != type) {
           index += bucket.count;
@@ -2042,79 +2017,54 @@ Search.prototype = {
         if (this._counts[type] == 0) {
           // Don't notify, since we are about to notify completion.
           this._cleanUpNonCurrentMatches(type, false);
         }
       }
     }
   },
 
-  _processHostRow(row) {
-    let match = {};
-    let strippedHost = row.getResultByIndex(QUERYINDEX_URL);
-    let url = row.getResultByIndex(QUERYINDEX_TITLE);
-    let unstrippedHost = stripHttpAndTrim(url, false);
-    let frecency = row.getResultByIndex(QUERYINDEX_FRECENCY);
+  _addOriginAutofillMatch(row) {
+    this._addAutofillMatch(
+      row.getResultByIndex(QUERYINDEX_ORIGIN_AUTOFILLED_VALUE),
+      row.getResultByIndex(QUERYINDEX_ORIGIN_URL),
+      row.getResultByIndex(QUERYINDEX_ORIGIN_FRECENCY)
+    );
+  },
 
-    // If the unfixup value doesn't preserve the user's input just
-    // ignore it and complete to the found host.
-    if (!unstrippedHost.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
-      unstrippedHost = null;
-    }
-
-    match.value = this._strippedPrefix + strippedHost;
-    match.finalCompleteValue = unstrippedHost;
-
-    match.icon = "page-icon:" + url;
-
-    // Although this has a frecency, this query is executed before any other
-    // queries that would result in frecency matches.
-    match.frecency = frecency;
-    match.style = "autofill";
-    return match;
+  _addURLAutofillMatch(row) {
+    let url = row.getResultByIndex(QUERYINDEX_URL_URL);
+    let strippedURL = row.getResultByIndex(QUERYINDEX_URL_STRIPPED_URL);
+    this._addAutofillMatch(
+      url.substr(url.indexOf(strippedURL)),
+      url,
+      row.getResultByIndex(QUERYINDEX_URL_FRECENCY)
+    );
   },
 
-  _processUrlRow(row) {
-    let url = row.getResultByIndex(QUERYINDEX_URL);
-    let strippedUrl = stripPrefix(url);
-    let prefix = url.substr(0, url.length - strippedUrl.length);
-    let frecency = row.getResultByIndex(QUERYINDEX_FRECENCY);
-
-    // We must complete the URL up to the next separator (which is /, ? or #).
-    let searchString = stripPrefix(this._trimmedOriginalSearchString);
-    let separatorIndex = strippedUrl.slice(searchString.length)
-                                    .search(/[\/\?\#]/);
-    if (separatorIndex != -1) {
-      separatorIndex += searchString.length;
-      if (strippedUrl[separatorIndex] == "/") {
-        separatorIndex++; // Include the "/" separator
-      }
-      strippedUrl = strippedUrl.slice(0, separatorIndex);
-    }
+  _addAutofillMatch(autofilledValue, finalCompleteValue, frecency, extraStyles = []) {
+    // The match's comment is only for display.  Set it to finalCompleteValue,
+    // the actual URL that will be visited when the user chooses the match, so
+    // that the user knows exactly where the match will take them.  To make it
+    // look a little nicer, remove "http://", and if the user typed a host
+    // without a trailing slash, remove any trailing slash, too.
+    let comment = stripHttpAndTrim(finalCompleteValue,
+                                   !this._searchString.includes("/"));
 
-    let match = {
-      value: this._strippedPrefix + strippedUrl,
-      // Although this has a frecency, this query is executed before any other
-      // queries that would result in frecency matches.
+    this._addMatch({
+      value: this._strippedPrefix + autofilledValue,
+      finalCompleteValue,
+      comment,
       frecency,
-      style: "autofill"
-    };
-
-    // Complete to the found url only if its untrimmed value preserves the
-    // user's input.
-    if (url.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
-      match.finalCompleteValue = prefix + strippedUrl;
-    }
-
-    match.icon = "page-icon:" + (match.finalCompleteValue || match.value);
-
-    return match;
+      style: ["autofill"].concat(extraStyles).join(" "),
+      icon: "page-icon:" + finalCompleteValue,
+    });
   },
 
-  _processRow(row) {
+  _addFilteredQueryMatch(row) {
     let match = {};
     match.placeId = row.getResultByIndex(QUERYINDEX_PLACEID);
     let escapedURL = row.getResultByIndex(QUERYINDEX_URL);
     let openPageCount = row.getResultByIndex(QUERYINDEX_SWITCHTAB) || 0;
     let historyTitle = row.getResultByIndex(QUERYINDEX_TITLE) || "";
     let bookmarked = row.getResultByIndex(QUERYINDEX_BOOKMARKED);
     let bookmarkTitle = bookmarked ?
       row.getResultByIndex(QUERYINDEX_BOOKMARKTITLE) : null;
@@ -2170,17 +2120,17 @@ Search.prototype = {
     if (action)
       match.style = "action " + action;
 
     match.value = url;
     match.comment = title;
     match.icon = "page-icon:" + escapedURL;
     match.frecency = frecency;
 
-    return match;
+    this._addMatch(match);
   },
 
   /**
    * @return a string consisting of the search query to be used based on the
    * previously set urlbar suggestion preferences.
    */
   get _suggestionPrefQuery() {
     if (!this.hasBehavior("restrict") && this.hasBehavior("history") &&
@@ -2311,82 +2261,104 @@ Search.prototype = {
 
     if (this._prohibitAutoFill)
       return false;
 
     return true;
   },
 
   /**
-   * Obtains the query to search for autoFill host results.
+   * Obtains the query to search for autofill origin results.
    *
    * @return an array consisting of the correctly optimized query to search the
    *         database with and an object containing the params to bound.
    */
-  get _hostQuery() {
-    let typed = Prefs.get("autoFill.typed") || this.hasBehavior("typed");
-    let bookmarked = this.hasBehavior("bookmark") && !this.hasBehavior("history");
+  get _originQuery() {
+    // 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 query = [];
+    let opts = {
+      query_type: QUERYTYPE_AUTOFILL_ORIGIN,
+      searchString: searchStr.toLowerCase(),
+    };
+
+    let bookmarked = this.hasBehavior("bookmark") &&
+                     !this.hasBehavior("history");
+
+    if (this._strippedPrefix) {
+      opts.prefix = this._strippedPrefix;
+      if (bookmarked) {
+        return [SQL_ORIGIN_PREFIX_BOOKMARKED_QUERY, opts];
+      }
+      return [SQL_ORIGIN_PREFIX_QUERY, opts];
+    }
     if (bookmarked) {
-      query.push(typed ? SQL_BOOKMARKED_TYPED_HOST_QUERY
-                       : SQL_BOOKMARKED_HOST_QUERY);
-    } else {
-      query.push(typed ? SQL_TYPED_HOST_QUERY
-                       : SQL_HOST_QUERY);
+      return [SQL_ORIGIN_BOOKMARKED_QUERY, opts];
     }
-
-    query.push({
-      query_type: QUERYTYPE_AUTOFILL_HOST,
-      searchString: this._searchString.toLowerCase()
-    });
-
-    return query;
+    return [SQL_ORIGIN_QUERY, opts];
   },
 
   /**
    * Obtains the query to search for autoFill url results.
    *
    * @return an array consisting of the correctly optimized query to search the
    *         database with and an object containing the params to bound.
    */
   get _urlQuery() {
-    // We expect this to be a full URL, not just a host. We want to extract the
-    // host and use that as a guess for whether we'll get a result from a URL
-    // query.
-    // The URIs in the database are fixed-up, so we can match on a lowercased
-    // host, but the path must be matched in a case sensitive way.
-    let pathIndex = this._trimmedOriginalSearchString.indexOf("/", this._strippedPrefix.length);
-    let revHost = this._trimmedOriginalSearchString
-                      .substring(this._strippedPrefix.length, pathIndex)
-                      .toLowerCase().split("").reverse().join("") + ".";
-    let searchString = stripPrefix(
-      this._trimmedOriginalSearchString.slice(0, pathIndex).toLowerCase() +
-      this._trimmedOriginalSearchString.slice(pathIndex)
-    );
-
-    let typed = Prefs.get("autoFill.typed") || this.hasBehavior("typed");
-    let bookmarked = this.hasBehavior("bookmark") && !this.hasBehavior("history");
-
-    let query = [];
-    if (bookmarked) {
-      query.push(typed ? SQL_BOOKMARKED_TYPED_URL_QUERY
-                       : SQL_BOOKMARKED_URL_QUERY);
-    } else {
-      query.push(typed ? SQL_TYPED_URL_QUERY
-                       : SQL_URL_QUERY);
+    // 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.
+    if (!this._urlQueryHostRegexp) {
+      this._urlQueryHostRegexp = /^[^/:?]+/;
+    }
+    let hostMatch = this._urlQueryHostRegexp.exec(this._searchString);
+    if (!hostMatch) {
+      return [null, null];
     }
 
-    query.push({
+    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 the host.  Use _trimmedOriginalSearchString instead of
+    // this._searchString because this._searchString has had unEscapeURIForUI()
+    // called on it.  It's therefore not necessarily the literal URL.
+    let strippedURL = this._trimmedOriginalSearchString;
+    if (this._strippedPrefix) {
+      strippedURL = strippedURL.substr(this._strippedPrefix.length);
+    }
+    strippedURL = host + strippedURL.substr(host.length);
+
+    let opts = {
       query_type: QUERYTYPE_AUTOFILL_URL,
-      searchString,
-      revHost
-    });
+      revHost,
+      strippedURL,
+    };
+
+    let bookmarked = this.hasBehavior("bookmark") &&
+                     !this.hasBehavior("history");
 
-    return query;
+    if (this._strippedPrefix) {
+      opts.prefix = this._strippedPrefix;
+      if (bookmarked) {
+        return [SQL_URL_PREFIX_BOOKMARKED_QUERY, opts];
+      }
+      return [SQL_URL_PREFIX_QUERY, opts];
+    }
+    if (bookmarked) {
+      return [SQL_URL_BOOKMARKED_QUERY, opts];
+    }
+    return [SQL_URL_QUERY, opts];
   },
 
   // The result is notified to the search listener on a timer, to chunk multiple
   // match updates together and avoid rebuilding the popup at every new match.
   _notifyTimer: null,
 
   /**
    * Notifies the current result to the listener.
--- a/toolkit/components/places/nsPlacesIndexes.h
+++ b/toolkit/components/places/nsPlacesIndexes.h
@@ -46,16 +46,21 @@
     "lastvisitdateindex", "moz_places", "last_visit_date", "" \
   )
 
 #define CREATE_IDX_MOZ_PLACES_GUID \
   CREATE_PLACES_IDX( \
     "guid_uniqueindex", "moz_places", "guid", "UNIQUE" \
   )
 
+#define CREATE_IDX_MOZ_PLACES_ORIGIN_ID \
+  CREATE_PLACES_IDX( \
+    "originidindex", "moz_places", "origin_id", "" \
+  )
+
 /**
  * moz_historyvisits
  */
 
 #define CREATE_IDX_MOZ_HISTORYVISITS_PLACEDATE \
   CREATE_PLACES_IDX( \
     "placedateindex", "moz_historyvisits", "place_id, visit_date", "" \
   )
--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -2,48 +2,47 @@
  * vim: sw=2 ts=2 et lcs=trail\:.,tab\:>~ :
  * 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/. */
 
 #ifndef __nsPlacesTables_h__
 #define __nsPlacesTables_h__
 
-
 #define CREATE_MOZ_PLACES NS_LITERAL_CSTRING( \
     "CREATE TABLE moz_places ( " \
     "  id INTEGER PRIMARY KEY" \
     ", url LONGVARCHAR" \
     ", title LONGVARCHAR" \
     ", rev_host LONGVARCHAR" \
     ", visit_count INTEGER DEFAULT 0" \
     ", hidden INTEGER DEFAULT 0 NOT NULL" \
     ", typed INTEGER DEFAULT 0 NOT NULL" \
     ", frecency INTEGER DEFAULT -1 NOT NULL" \
     ", last_visit_date INTEGER " \
     ", guid TEXT" \
     ", foreign_count INTEGER DEFAULT 0 NOT NULL" \
     ", url_hash INTEGER DEFAULT 0 NOT NULL " \
     ", description TEXT" \
     ", preview_image_url TEXT" \
+    ", origin_id INTEGER REFERENCES moz_origins(id)" \
   ")" \
 )
 
 #define CREATE_MOZ_HISTORYVISITS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_historyvisits (" \
     "  id INTEGER PRIMARY KEY" \
     ", from_visit INTEGER" \
     ", place_id INTEGER" \
     ", visit_date INTEGER" \
     ", visit_type INTEGER" \
     ", session INTEGER" \
   ")" \
 )
 
-
 #define CREATE_MOZ_INPUTHISTORY NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_inputhistory (" \
     "  place_id INTEGER NOT NULL" \
     ", input LONGVARCHAR NOT NULL" \
     ", use_count INTEGER" \
     ", PRIMARY KEY (place_id, input)" \
   ")" \
 )
@@ -131,54 +130,58 @@
   "CREATE TABLE moz_keywords (" \
     "  id INTEGER PRIMARY KEY AUTOINCREMENT" \
     ", keyword TEXT UNIQUE" \
     ", place_id INTEGER" \
     ", post_data TEXT" \
   ")" \
 )
 
-#define CREATE_MOZ_HOSTS NS_LITERAL_CSTRING( \
-  "CREATE TABLE moz_hosts (" \
-    "  id INTEGER PRIMARY KEY" \
-    ", host TEXT NOT NULL UNIQUE" \
-    ", frecency INTEGER" \
-    ", typed INTEGER NOT NULL DEFAULT 0" \
-    ", prefix TEXT" \
+#define CREATE_MOZ_ORIGINS NS_LITERAL_CSTRING( \
+  "CREATE TABLE moz_origins ( " \
+    "id INTEGER PRIMARY KEY, " \
+    "prefix TEXT NOT NULL, " \
+    "host TEXT NOT NULL, " \
+    "frecency INTEGER NOT NULL, " \
+    "UNIQUE (prefix, host) " \
   ")" \
 )
 
 // Note: this should be kept up-to-date with the definition in
 //       nsPlacesAutoComplete.js.
 #define CREATE_MOZ_OPENPAGES_TEMP NS_LITERAL_CSTRING( \
   "CREATE TEMP TABLE moz_openpages_temp (" \
     "  url TEXT" \
     ", userContextId INTEGER" \
     ", open_count INTEGER" \
     ", PRIMARY KEY (url, userContextId)" \
   ")" \
 )
 
 // This table is used, along with moz_places_afterdelete_trigger, to update
 // hosts after places removals. During a DELETE FROM moz_places, hosts are
-// accumulated into this table, then a DELETE FROM moz_updatehostsdelete_temp
-// will take care of updating the moz_hosts table for every modified host. See
-// CREATE_PLACES_AFTERDELETE_TRIGGER in nsPlacestriggers.h for details.
-#define CREATE_UPDATEHOSTSDELETE_TEMP NS_LITERAL_CSTRING( \
-  "CREATE TEMP TABLE moz_updatehostsdelete_temp (" \
-    "  host TEXT PRIMARY KEY " \
-  ") WITHOUT ROWID " \
+// accumulated into this table, then a DELETE FROM moz_updateoriginsdelete_temp
+// will take care of updating the moz_origin_hosts table for every modified
+// host. See CREATE_PLACES_AFTERDELETE_TRIGGER in nsPlacestriggers.h for
+// details.
+#define CREATE_UPDATEORIGINSDELETE_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updateoriginsdelete_temp ( " \
+    "origin_id INTEGER PRIMARY KEY, " \
+    "host TEXT " \
+  ") " \
 )
 
-// This table is used in a similar way to moz_updatehostsdelete_temp, but for
+// This table is used in a similar way to moz_updateoriginsdelete_temp, but for
 // inserts, and triggered via moz_places_afterinsert_trigger.
-#define CREATE_UPDATEHOSTSINSERT_TEMP NS_LITERAL_CSTRING( \
-  "CREATE TEMP TABLE moz_updatehostsinsert_temp (" \
-    "  host TEXT PRIMARY KEY " \
-  ") WITHOUT ROWID " \
+#define CREATE_UPDATEORIGINSINSERT_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updateoriginsinsert_temp ( " \
+    "place_id INTEGER PRIMARY KEY, " \
+    "prefix TEXT NOT NULL, " \
+    "host TEXT NOT NULL " \
+  ") " \
 )
 
 // This table would not be strictly needed for functionality since it's just
 // mimicking moz_places, though it's great for database portability.
 // With this we don't have to take care into account a bunch of database
 // mismatch cases, where places.sqlite could be mixed up with a favicons.sqlite
 // created with a different places.sqlite (not just in case of a user messing
 // up with the profile, but also in case of corruption).
--- a/toolkit/components/places/nsPlacesTriggers.h
+++ b/toolkit/components/places/nsPlacesTriggers.h
@@ -43,175 +43,112 @@
       "visit_count = visit_count - (SELECT OLD.visit_type NOT IN (" EXCLUDED_VISIT_TYPES ")), "\
       "last_visit_date = (SELECT visit_date FROM moz_historyvisits " \
                          "WHERE place_id = OLD.place_id " \
                          "ORDER BY visit_date DESC LIMIT 1) " \
     "WHERE id = OLD.place_id;" \
   "END" \
 )
 
-/**
- * A predicate matching pages on rev_host, based on a given host value.
- * 'host' may be either the moz_hosts.host column or an alias representing an
- * equivalent value.
- */
-#define HOST_TO_REVHOST_PREDICATE \
-  "rev_host = get_unreversed_host(host || '.') || '.' " \
-  "OR rev_host = get_unreversed_host(host || '.') || '.www.'"
-
-#define OLDHOST_TO_REVHOST_PREDICATE \
-  "rev_host = get_unreversed_host(OLD.host || '.') || '.' " \
-  "OR rev_host = get_unreversed_host(OLD.host || '.') || '.www.'"
-
-/**
- * Select the best prefix for a host, based on existing pages registered for it.
- * Prefixes have a priority, from the top to the bottom, so that secure pages
- * have higher priority, and more generically "www." prefixed hosts come before
- * unprefixed ones.
- * Given a host, examine associated pages and:
- *  - if at least half the typed pages start with https://www. return https://www.
- *  - if at least half the typed pages start with https:// return https://
- *  - if all of the typed pages start with ftp: return ftp://
- *     - This is because mostly people will want to visit the http version
- *       of the site.
- *  - if at least half the typed pages start with www. return www.
- *  - otherwise don't use any prefix
- */
-#define HOSTS_PREFIX_PRIORITY_FRAGMENT \
-  "SELECT CASE " \
-    "WHEN ( " \
-      "SELECT round(avg(substr(url,1,12) = 'https://www.')) FROM moz_places h " \
-      "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
-    ") THEN 'https://www.' " \
-    "WHEN ( " \
-      "SELECT round(avg(substr(url,1,8) = 'https://')) FROM moz_places h " \
-      "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
-    ") THEN 'https://' " \
-    "WHEN 1 = ( " \
-      "SELECT min(substr(url,1,4) = 'ftp:') FROM moz_places h " \
-      "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
-    ") THEN 'ftp://' " \
-    "WHEN ( " \
-      "SELECT round(avg(substr(url,1,11) = 'http://www.')) FROM moz_places h " \
-      "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
-    ") THEN 'www.' " \
-  "END "
-
 // The next few triggers are a workaround for the lack of FOR EACH STATEMENT in
 // Sqlite, until bug 871908 can be fixed properly.
 // While doing inserts or deletes into moz_places, we accumulate the affected
-// hosts into a temp table. Afterwards, we delete everything from the temp
+// origins into a temp table. Afterwards, we delete everything from the temp
 // table, causing the AFTER DELETE trigger to fire for it, which will then
-// update the moz_hosts table.
+// update moz_origins.
 // Note this way we lose atomicity, crashing between the 2 queries may break the
-// hosts table coherency. So it's better to run those DELETE queries in a single
+// tables' coherency. So it's better to run those DELETE queries in a single
 // transaction.
 // Regardless, this is still better than hanging the browser for several minutes
 // on a fast machine.
 #define CREATE_PLACES_AFTERINSERT_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterinsert_trigger " \
   "AFTER INSERT ON moz_places FOR EACH ROW " \
   "BEGIN " \
     "SELECT store_last_inserted_id('moz_places', NEW.id); " \
-    "INSERT OR IGNORE INTO moz_updatehostsinsert_temp (host)" \
-    "VALUES (fixup_url(get_unreversed_host(NEW.rev_host)));" \
+    "INSERT OR IGNORE INTO moz_updateoriginsinsert_temp (place_id, prefix, host) " \
+    "VALUES (NEW.id, get_prefix(NEW.url), get_host_and_port(NEW.url)); " \
   "END" \
 )
 
 // See CREATE_PLACES_AFTERINSERT_TRIGGER. For each delete in moz_places we
-// add the host to moz_updatehostsdelete_temp - we then delete everything
-// from moz_updatehostsdelete_temp, allowing us to run a trigger only once
-// per host.
+// add the origin to moz_updateoriginsdelete_temp - we then delete everything
+// from moz_updateoriginsdelete_temp, allowing us to run a trigger only once
+// per origin.
 #define CREATE_PLACES_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterdelete_trigger " \
   "AFTER DELETE ON moz_places FOR EACH ROW " \
   "BEGIN " \
-    "INSERT OR IGNORE INTO moz_updatehostsdelete_temp (host)" \
-    "VALUES (fixup_url(get_unreversed_host(OLD.rev_host)));" \
-  "END" \
-)
-
-// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
-// to ensure gets run for each distinct host that we insert into moz_places.
-#define CREATE_UPDATEHOSTSINSERT_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
-  "CREATE TEMP TRIGGER moz_updatehostsinsert_afterdelete_trigger " \
-  "AFTER DELETE ON moz_updatehostsinsert_temp FOR EACH ROW " \
-  "BEGIN " \
-    "INSERT OR REPLACE INTO moz_hosts (id, host, frecency, typed, prefix) " \
-    "SELECT " \
-        "(SELECT id FROM moz_hosts WHERE host = OLD.host), " \
-        "OLD.host, " \
-        "MAX(IFNULL((SELECT frecency FROM moz_hosts WHERE host = OLD.host), -1), " \
-          "(SELECT MAX(frecency) FROM moz_places h " \
-            "WHERE (" OLDHOST_TO_REVHOST_PREDICATE "))), " \
-        "MAX(IFNULL((SELECT typed FROM moz_hosts WHERE host = OLD.host), 0), " \
-          "(SELECT MAX(typed) FROM moz_places h " \
-            "WHERE (" OLDHOST_TO_REVHOST_PREDICATE "))), " \
-        "(" HOSTS_PREFIX_PRIORITY_FRAGMENT \
-         "FROM ( " \
-            "SELECT OLD.host AS host " \
-          ")" \
-        ") " \
-    " WHERE LENGTH(OLD.host) > 1; " \
+    "INSERT OR IGNORE INTO moz_updateoriginsdelete_temp (origin_id, host) " \
+    "VALUES (OLD.origin_id, get_host_and_port(OLD.url)); " \
   "END" \
 )
 
 // See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
-// to ensure gets run for each distinct host that we delete from moz_places.
-#define CREATE_UPDATEHOSTSDELETE_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
-  "CREATE TEMP TRIGGER moz_updatehostsdelete_afterdelete_trigger " \
-  "AFTER DELETE ON moz_updatehostsdelete_temp FOR EACH ROW " \
+// to ensure gets run for each origin that we insert into moz_places.
+#define CREATE_UPDATEORIGINSINSERT_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
+  "CREATE TEMP TRIGGER moz_updateoriginsinsert_afterdelete_trigger " \
+  "AFTER DELETE ON moz_updateoriginsinsert_temp FOR EACH ROW " \
   "BEGIN " \
-    "DELETE FROM moz_hosts " \
-    "WHERE host = OLD.host " \
-      "AND NOT EXISTS(" \
-        "SELECT 1 FROM moz_places " \
-          "WHERE rev_host = get_unreversed_host(host || '.') || '.' " \
-             "OR rev_host = get_unreversed_host(host || '.') || '.www.' " \
-      "); " \
-    "UPDATE moz_hosts " \
-    "SET prefix = (" HOSTS_PREFIX_PRIORITY_FRAGMENT ") " \
-    "WHERE host = OLD.host; " \
-    "DELETE FROM moz_icons " \
-    "WHERE fixed_icon_url_hash = hash(fixup_url(OLD.host || '/favicon.ico')) " \
-      "AND fixup_url(icon_url) = fixup_url(OLD.host || '/favicon.ico') "\
-      "AND NOT EXISTS (SELECT 1 FROM moz_hosts WHERE host = OLD.host " \
-                                                 "OR host = fixup_url(OLD.host));" \
+    "INSERT OR IGNORE INTO moz_origins (prefix, host, frecency) " \
+    "VALUES (OLD.prefix, OLD.host, 0); " \
+    "UPDATE moz_places SET origin_id = ( " \
+      "SELECT id " \
+      "FROM moz_origins " \
+      "WHERE prefix = OLD.prefix AND host = OLD.host " \
+    ") " \
+    "WHERE id = OLD.place_id; " \
+    "UPDATE moz_origins SET frecency = ( " \
+      "SELECT IFNULL(MAX(frecency), 0) " \
+      "FROM moz_places " \
+      "WHERE moz_places.origin_id = moz_origins.id " \
+    "); " \
   "END" \
 )
 
-// For performance reasons the host frecency is updated only when the page
-// frecency changes by a meaningful percentage.  This is because the frecency
-// decay algorithm requires to update all the frecencies at once, causing a
-// too high overhead, while leaving the ordering unchanged.
+// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
+// to ensure gets run for each origin that we delete from moz_places.
+#define CREATE_UPDATEORIGINSDELETE_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
+  "CREATE TEMP TRIGGER moz_updateoriginsdelete_afterdelete_trigger " \
+  "AFTER DELETE ON moz_updateoriginsdelete_temp FOR EACH ROW " \
+  "BEGIN " \
+    "DELETE FROM moz_origins " \
+    "WHERE id = OLD.origin_id " \
+      "AND id NOT IN (SELECT origin_id FROM moz_places); " \
+    "DELETE FROM moz_icons " \
+    "WHERE fixed_icon_url_hash = hash(fixup_url(OLD.host || '/favicon.ico')) " \
+      "AND fixup_url(icon_url) = fixup_url(OLD.host || '/favicon.ico') "\
+      "AND NOT EXISTS (SELECT 1 FROM moz_origins WHERE host = OLD.host " \
+                                                   "OR host = fixup_url(OLD.host)); " \
+  "END" \
+)
+
+// This trigger keeps frecencies in the moz_origins table in sync with
+// frecencies in moz_places.  However, we skip this when frecency changes are
+// due to frecency decay since (1) decay updates all frecencies at once, so this
+// trigger would run for each moz_place, which would be expensive; and (2) decay
+// does not change the ordering of frecencies since all frecencies decay by the
+// same percentage.
 #define CREATE_PLACES_AFTERUPDATE_FRECENCY_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterupdate_frecency_trigger " \
   "AFTER UPDATE OF frecency ON moz_places FOR EACH ROW " \
-  "WHEN NEW.frecency >= 0 " \
-    "AND ABS(" \
-      "IFNULL((NEW.frecency - OLD.frecency) / CAST(NEW.frecency AS REAL), " \
-             "(NEW.frecency - OLD.frecency))" \
-    ") > .05 " \
+  "WHEN NEW.frecency >= 0 AND NOT ( " \
+    "OLD.frecency > 0 " \
+    "AND is_frecency_decaying() " \
+    "AND NEW.frecency < OLD.frecency " \
+    "AND (OLD.frecency - NEW.frecency) / OLD.frecency <= 0.975 " \
+  ") " \
   "BEGIN " \
-    "UPDATE moz_hosts " \
-    "SET frecency = (SELECT MAX(frecency) FROM moz_places " \
-                    "WHERE rev_host = get_unreversed_host(host || '.') || '.' " \
-                       "OR rev_host = get_unreversed_host(host || '.') || '.www.') " \
-    "WHERE host = fixup_url(get_unreversed_host(NEW.rev_host)); " \
-  "END" \
-)
-
-#define CREATE_PLACES_AFTERUPDATE_TYPED_TRIGGER NS_LITERAL_CSTRING( \
-  "CREATE TEMP TRIGGER moz_places_afterupdate_typed_trigger " \
-  "AFTER UPDATE OF typed ON moz_places FOR EACH ROW " \
-  "WHEN NEW.typed = 1 " \
-  "BEGIN " \
-    "UPDATE moz_hosts " \
-    "SET typed = 1 " \
-    "WHERE host = fixup_url(get_unreversed_host(NEW.rev_host)); " \
+    "UPDATE moz_origins " \
+    "SET frecency = ( " \
+      "SELECT IFNULL(MAX(frecency), 0) " \
+      "FROM moz_places " \
+      "WHERE moz_places.origin_id = moz_origins.id " \
+    ") " \
+    "WHERE id = NEW.origin_id; " \
   "END" \
 )
 
 /**
  * This trigger removes a row from moz_openpages_temp when open_count reaches 0.
  *
  * @note this should be kept up-to-date with the definition in
  *       nsPlacesAutoComplete.js