--- a/b2g/installer/package-manifest.in
+++ b/b2g/installer/package-manifest.in
@@ -442,16 +442,17 @@
 @BINPATH@/components/nsContentDispatchChooser.js
 @BINPATH@/components/nsHandlerService.manifest
 @BINPATH@/components/nsHandlerService.js
 @BINPATH@/components/nsWebHandlerApp.manifest
 @BINPATH@/components/nsWebHandlerApp.js
 @BINPATH@/components/satchel.manifest
 @BINPATH@/components/nsFormAutoComplete.js
 @BINPATH@/components/nsFormHistory.js
+@BINPATH@/components/FormHistoryStartup.js
 @BINPATH@/components/nsInputListAutoComplete.js
 @BINPATH@/components/contentSecurityPolicy.manifest
 @BINPATH@/components/contentSecurityPolicy.js
 @BINPATH@/components/contentAreaDropListener.manifest
 @BINPATH@/components/contentAreaDropListener.js
 @BINPATH@/components/messageWakeupService.js
 @BINPATH@/components/messageWakeupService.manifest
 @BINPATH@/components/SettingsManager.js

--- a/browser/base/content/sanitize.js
+++ b/browser/base/content/sanitize.js
@@ -1,77 +1,99 @@
 # -*- Mode: Java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 # 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/.
 
 Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+                                  "resource://gre/modules/FormHistory.jsm");
 
 function Sanitizer() {}
 Sanitizer.prototype = {
   // warning to the caller: this one may raise an exception (e.g. bug #265028)
   clearItem: function (aItemName)
   {
     if (this.items[aItemName].canClear)
       this.items[aItemName].clear();
   },
 
-  canClearItem: function (aItemName)
+  canClearItem: function (aItemName, aCallback, aArg)
   {
-    return this.items[aItemName].canClear;
+    let canClear = this.items[aItemName].canClear;
+    if (typeof canClear == "function") {
+      canClear(aCallback, aArg);
+      return false;
+    }
+
+    aCallback(aItemName, canClear, aArg);
+    return canClear;
   },
   
   prefDomain: "",
   
   getNameFromPreference: function (aPreferenceName)
   {
     return aPreferenceName.substr(this.prefDomain.length);
   },
   
   /**
-   * Deletes privacy sensitive data in a batch, according to user preferences
-   *
-   * @returns  null if everything's fine;  an object in the form
-   *           { itemName: error, ... } on (partial) failure
+   * Deletes privacy sensitive data in a batch, according to user preferences. Calls
+   * errorHandler with a list of errors on failure.
    */
-  sanitize: function ()
+  sanitize: function (errorHandler)
   {
     var psvc = Components.classes["@mozilla.org/preferences-service;1"]
                          .getService(Components.interfaces.nsIPrefService);
     var branch = psvc.getBranch(this.prefDomain);
     var errors = null;
 
     // Cache the range of times to clear
     if (this.ignoreTimespan)
       var range = null;  // If we ignore timespan, clear everything
     else
       range = this.range || Sanitizer.getClearRange();
-      
+
+    let itemCount = this.items.length;
     for (var itemName in this.items) {
-      var item = this.items[itemName];
+      let item = this.items[itemName];
       item.range = range;
-      if ("clear" in item && item.canClear && branch.getBoolPref(itemName)) {
-        // Some of these clear() may raise exceptions (see bug #265028)
-        // to sanitize as much as possible, we catch and store them, 
-        // rather than fail fast.
-        // Callers should check returned errors and give user feedback
-        // about items that could not be sanitized
-        try {
-          item.clear();
-        } catch(er) {
-          if (!errors) 
-            errors = {};
-          errors[itemName] = er;
-          dump("Error sanitizing " + itemName + ": " + er + "\n");
-        }
+      if ("clear" in item && branch.getBoolPref(itemName)) {
+        let clearCallback = (itemName, aCanClear) => {
+          // Some of these clear() may raise exceptions (see bug #265028)
+          // to sanitize as much as possible, we catch and store them,
+          // rather than fail fast.
+          // Callers should check returned errors and give user feedback
+          // about items that could not be sanitized
+          let item = this.items[itemName];
+          try {
+            if (aCanClear)
+              item.clear();
+          } catch(er) {
+            if (!errors)
+              errors = {};
+            errors[itemName] = er;
+            dump("Error sanitizing " + itemName + ": " + er + "\n");
+          }
+
+          // If this is the last item that needs to receive the callback, call the error handler
+          if (!--itemCount && errors) {
+            errorHandler(error);
+          }
+        };
+
+        this.canClearItem(itemName, clearCallback);
       }
     }
-    return errors;
+
+    if (errors) {
+      errorHandler(error);
+    }
   },
   
   // Time span only makes sense in certain cases.  Consumers who want
   // to only clear some private data can opt in by setting this to false,
   // and can optionally specify a specific range.  If timespan is not ignored,
   // and range is not set, sanitize() will use the value of the timespan
   // pref to determine a range
   ignoreTimespan : true,
@@ -226,47 +248,56 @@ Sanitizer.prototype = {
           let searchBar = currentDocument.getElementById("searchbar");
           if (searchBar)
             searchBar.textbox.reset();
           let findBar = currentDocument.getElementById("FindToolbar");
           if (findBar)
             findBar.clear();
         }
 
-        let formHistory = Components.classes["@mozilla.org/satchel/form-history;1"]
-                                    .getService(Components.interfaces.nsIFormHistory2);
-        if (this.range)
-          formHistory.removeEntriesByTimeframe(this.range[0], this.range[1]);
-        else
-          formHistory.removeAllEntries();
+        let change = { op: "remove" };
+        if (this.range) {
+          [ change.firstUsedStart, change.firstUsedEnd ] = this.range;
+        }
+        FormHistory.update(change);
       },
 
-      get canClear()
+      canClear : function(aCallback, aArg)
       {
         var windowManager = Components.classes['@mozilla.org/appshell/window-mediator;1']
                                       .getService(Components.interfaces.nsIWindowMediator);
         var windows = windowManager.getEnumerator("navigator:browser");
         while (windows.hasMoreElements()) {
           let currentDocument = windows.getNext().document;
           let searchBar = currentDocument.getElementById("searchbar");
           if (searchBar) {
             let transactionMgr = searchBar.textbox.editor.transactionManager;
             if (searchBar.value ||
                 transactionMgr.numberOfUndoItems ||
-                transactionMgr.numberOfRedoItems)
-              return true;
+                transactionMgr.numberOfRedoItems) {
+              aCallback("formdata", true, aArg);
+              return false;
+            }
           }
           let findBar = currentDocument.getElementById("FindToolbar");
-          if (findBar && findBar.canClear)
-            return true;
+          if (findBar && findBar.canClear) {
+            aCallback("formdata", true, aArg);
+            return false;
+          }
         }
 
-        let formHistory = Components.classes["@mozilla.org/satchel/form-history;1"]
-                                    .getService(Components.interfaces.nsIFormHistory2);
-        return formHistory.hasEntries;
+        let count = 0;
+        let countDone = {
+          handleResult : function(aResult) count = aResult,
+          handleError : function(aError) Components.utils.reportError(aError),
+          handleCompletion :
+            function(aReason) { aCallback("formdata", aReason == 0 && count > 0, aArg); }
+        };
+        FormHistory.count({}, countDone);
+        return false;
       }
     },
     
     downloads: {
       clear: function ()
       {
         var dlMgr = Components.classes["@mozilla.org/download-manager;1"]
                               .getService(Components.interfaces.nsIDownloadManager);
@@ -481,14 +512,12 @@ Sanitizer.onShutdown = function()
 Sanitizer._checkAndSanitize = function() 
 {
   const prefs = Sanitizer.prefs;
   if (prefs.getBoolPref(Sanitizer.prefShutdown) && 
       !prefs.prefHasUserValue(Sanitizer.prefDidShutdown)) {
     // this is a shutdown or a startup after an unclean exit
     var s = new Sanitizer();
     s.prefDomain = "privacy.clearOnShutdown.";
-    s.sanitize() || // sanitize() returns null on full success
-      prefs.setBoolPref(Sanitizer.prefDidShutdown, true);
+    let errorHandler = function() prefs.setBoolPref(Sanitizer.prefDidShutdown, true);
+    s.sanitize(errorHandler);
   }
 };
-
-

--- a/browser/base/content/sanitizeDialog.js
+++ b/browser/base/content/sanitizeDialog.js
@@ -42,21 +42,23 @@ var gSanitizePromptDialog = {
 
     var s = new Sanitizer();
     s.prefDomain = "privacy.cpd.";
 
     let sanitizeItemList = document.querySelectorAll("#itemList > [preference]");
     for (let i = 0; i < sanitizeItemList.length; i++) {
       let prefItem = sanitizeItemList[i];
       let name = s.getNameFromPreference(prefItem.getAttribute("preference"));
-      if (!s.canClearItem(name)) {
-        prefItem.preference = null;
-        prefItem.checked = false;
-        prefItem.disabled = true;
-      }
+      s.canClearItem(name, function canClearCallback(aItem, aCanClear, aPrefItem) {
+        if (!aCanClear) {
+          aPrefItem.preference = null;
+          aPrefItem.checked = false;
+          aPrefItem.disabled = true;
+        }
+      }, prefItem);
     }
 
     document.documentElement.getButton("accept").label =
       this.bundleBrowser.getString("sanitizeButtonOK");
 
     if (this.selectedTimespan === Sanitizer.TIMESPAN_EVERYTHING) {
       this.prepareWarning();
       this.warningBox.hidden = false;
@@ -276,21 +278,23 @@ var gSanitizePromptDialog = {
 
     var s = new Sanitizer();
     s.prefDomain = "privacy.cpd.";
 
     let sanitizeItemList = document.querySelectorAll("#itemList > [preference]");
     for (let i = 0; i < sanitizeItemList.length; i++) {
       let prefItem = sanitizeItemList[i];
       let name = s.getNameFromPreference(prefItem.getAttribute("preference"));
-      if (!s.canClearItem(name)) {
-        prefItem.preference = null;
-        prefItem.checked = false;
-        prefItem.disabled = true;
-      }
+      s.canClearItem(name, function canClearCallback(aCanClear) {
+        if (!aCanClear) {
+          prefItem.preference = null;
+          prefItem.checked = false;
+          prefItem.disabled = true;
+        }
+      });
     }
 
     document.documentElement.getButton("accept").label =
       this.bundleBrowser.getString("sanitizeButtonOK");
 
     this.selectByTimespan();
   },
 

--- a/browser/base/content/test/browser_bug409624.js
+++ b/browser/base/content/test/browser_bug409624.js
@@ -1,15 +1,30 @@
 /* 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/. */
 
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+                                  "resource://gre/modules/FormHistory.jsm");
+
 function test() {
   waitForExplicitFinish();
 
+  // This test relies on the form history being empty to start with delete
+  // all the items first.
+  FormHistory.update({ op: "remove" },
+                     { handleError: function (error) {
+                         do_throw("Error occurred updating form history: " + error);
+                       },
+                       handleCompletion: function (reason) { if (!reason) test2(); },
+                     });
+}
+
+function test2()
+{
   let prefService = Cc["@mozilla.org/preferences-service;1"]
                     .getService(Components.interfaces.nsIPrefBranch2);
 
   let findBar = gFindBar;
   let textbox = gFindBar.getElement("findbar-textbox");
 
   let tempScope = {};
   Cc["@mozilla.org/moz/jssubscript-loader;1"].getService(Ci.mozIJSSubScriptLoader)
@@ -24,18 +39,33 @@ function test() {
   prefBranch.setBoolPref("downloads", false);
   prefBranch.setBoolPref("formdata", true);
   prefBranch.setBoolPref("history", false);
   prefBranch.setBoolPref("offlineApps", false);
   prefBranch.setBoolPref("passwords", false);
   prefBranch.setBoolPref("sessions", false);
   prefBranch.setBoolPref("siteSettings", false);
 
-  // Sanitize now so we can test that canClear is correct
+  // Sanitize now so we can test that canClear is correct. Formdata is cleared asynchronously.
   s.sanitize();
-  ok(!s.canClearItem("formdata"), "pre-test baseline for sanitizer");
-  textbox.value = "m";
-  ok(s.canClearItem("formdata"), "formdata can be cleared after input");
-  s.sanitize();
-  is(textbox.value, "", "findBar textbox should be empty after sanitize");
-  ok(!s.canClearItem("formdata"), "canClear now false after sanitize");
+  s.canClearItem("formdata", clearDone1, s);
+}
+
+function clearDone1(aItemName, aResult, aSanitizer)
+{
+  ok(!aResult, "pre-test baseline for sanitizer");
+  gFindBar.getElement("findbar-textbox").value = "m";
+  aSanitizer.canClearItem("formdata", inputEntered, aSanitizer);
+}
+
+function inputEntered(aItemName, aResult, aSanitizer)
+{
+  ok(aResult, "formdata can be cleared after input");
+  aSanitizer.sanitize();
+  aSanitizer.canClearItem("formdata", clearDone2);
+}
+
+function clearDone2(aItemName, aResult)
+{
+  is(gFindBar.getElement("findbar-textbox").value, "", "findBar textbox should be empty after sanitize");
+  ok(!aResult, "canClear now false after sanitize");
   finish();
 }

--- a/browser/base/content/test/browser_sanitize-timespans.js
+++ b/browser/base/content/test/browser_sanitize-timespans.js
@@ -1,29 +1,67 @@
+Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://gre/modules/Services.jsm");
+
 // Bug 453440 - Test the timespan-based logic of the sanitizer code
 var now_uSec = Date.now() * 1000;
 
 const dm = Cc["@mozilla.org/download-manager;1"].getService(Ci.nsIDownloadManager);
-const formhist = Cc["@mozilla.org/satchel/form-history;1"].getService(Ci.nsIFormHistory2);
 
 const kUsecPerMin = 60 * 1000000;
 
 let tempScope = {};
 Cc["@mozilla.org/moz/jssubscript-loader;1"].getService(Ci.mozIJSSubScriptLoader)
                                            .loadSubScript("chrome://browser/content/sanitize.js", tempScope);
 let Sanitizer = tempScope.Sanitizer;
 
+let FormHistory = (Components.utils.import("resource://gre/modules/FormHistory.jsm", {})).FormHistory;
+
+function promiseFormHistoryRemoved() {
+  let deferred = Promise.defer();
+  Services.obs.addObserver(function onfh() {
+    Services.obs.removeObserver(onfh, "satchel-storage-changed", false);
+    deferred.resolve();
+  }, "satchel-storage-changed", false);
+  return deferred.promise;
+}
+
 function test() {
   waitForExplicitFinish();
 
-  setupDownloads();
-  setupFormHistory();
-  setupHistory(function() {
-    Task.spawn(onHistoryReady).then(finish);
-  });
+  Task.spawn(function() {
+    setupDownloads();
+    yield setupFormHistory();
+    yield setupHistory();
+    yield onHistoryReady();
+  }).then(finish);
+}
+
+function countEntries(name, message, check) {
+  let deferred = Promise.defer();
+
+  var obj = {};
+  if (name !== null)
+    obj.fieldname = name;
+
+  let count;
+  FormHistory.count(obj, { handleResult: function (result) count = result,
+                           handleError: function (error) {
+                             do_throw("Error occurred searching form history: " + error);
+                             deferred.reject(error)
+                           },
+                           handleCompletion: function (reason) {
+                             if (!reason) {
+                               check(count, message);
+                               deferred.resolve();
+                             }
+                           },
+                         });
+
+  return deferred.promise;
 }
 
 function onHistoryReady() {
   var hoursSinceMidnight = new Date().getHours();
   var minutesSinceMidnight = hoursSinceMidnight * 60 + new Date().getMinutes();
 
   // Should test cookies here, but nsICookieManager/nsICookieService
   // doesn't let us fake creation times.  bug 463127
@@ -42,16 +80,18 @@ function onHistoryReady() {
   itemPrefs.setBoolPref("sessions", false);
   itemPrefs.setBoolPref("siteSettings", false);
 
   // Clear 10 minutes ago
   s.range = [now_uSec - 10*60*1000000, now_uSec];
   s.sanitize();
   s.range = null;
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://10minutes.com"))),
      "Pretend visit to 10minutes.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://1hour.com"))),
      "Pretend visit to 1hour.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://1hour10minutes.com"))),
      "Pretend visit to 1hour10minutes.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://2hour.com"))),
      "Pretend visit to 2hour.com should should still exist");
@@ -63,26 +103,29 @@ function onHistoryReady() {
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (minutesSinceMidnight > 10) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("10minutes"), "10minutes form entry should be deleted");
-  ok(formhist.nameExists("1hour"), "1hour form entry should still exist");
-  ok(formhist.nameExists("1hour10minutes"), "1hour10minutes form entry should still exist");
-  ok(formhist.nameExists("2hour"), "2hour form entry should still exist");
-  ok(formhist.nameExists("2hour10minutes"), "2hour10minutes form entry should still exist");
-  ok(formhist.nameExists("4hour"), "4hour form entry should still exist");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  let checkZero = function(num, message) { is(num, 0, message); }
+  let checkOne = function(num, message) { is(num, 1, message); }
+
+  yield countEntries("10minutes", "10minutes form entry should be deleted", checkZero);
+  yield countEntries("1hour", "1hour form entry should still exist", checkOne);
+  yield countEntries("1hour10minutes", "1hour10minutes form entry should still exist", checkOne);
+  yield countEntries("2hour", "2hour form entry should still exist", checkOne);
+  yield countEntries("2hour10minutes", "2hour10minutes form entry should still exist", checkOne);
+  yield countEntries("4hour", "4hour form entry should still exist", checkOne);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (minutesSinceMidnight > 10)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
   ok(!downloadExists(5555555), "10 minute download should now be deleted");
   ok(downloadExists(5555551), "<1 hour download should still be present");
   ok(downloadExists(5555556), "1 hour 10 minute download should still be present");
   ok(downloadExists(5555550), "Year old download should still be present");
   ok(downloadExists(5555552), "<2 hour old download should still be present");
   ok(downloadExists(5555557), "2 hour 10 minute download should still be present");
   ok(downloadExists(5555553), "<4 hour old download should still be present");
@@ -90,16 +133,18 @@ function onHistoryReady() {
 
   if (minutesSinceMidnight > 10)
     ok(downloadExists(5555554), "'Today' download should still be present");
 
   // Clear 1 hour
   Sanitizer.prefs.setIntPref("timeSpan", 1);
   s.sanitize();
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://1hour.com"))),
      "Pretend visit to 1hour.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://1hour10minutes.com"))),
      "Pretend visit to 1hour10minutes.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://2hour.com"))),
      "Pretend visit to 2hour.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://2hour10minutes.com"))),
      "Pretend visit to 2hour10minutes.com should should still exist");
@@ -109,25 +154,25 @@ function onHistoryReady() {
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (hoursSinceMidnight > 1) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("1hour"), "1hour form entry should be deleted");
-  ok(formhist.nameExists("1hour10minutes"), "1hour10minutes form entry should still exist");
-  ok(formhist.nameExists("2hour"), "2hour form entry should still exist");
-  ok(formhist.nameExists("2hour10minutes"), "2hour10minutes form entry should still exist");
-  ok(formhist.nameExists("4hour"), "4hour form entry should still exist");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  yield countEntries("1hour", "1hour form entry should be deleted", checkZero);
+  yield countEntries("1hour10minutes", "1hour10minutes form entry should still exist", checkOne);
+  yield countEntries("2hour", "2hour form entry should still exist", checkOne);
+  yield countEntries("2hour10minutes", "2hour10minutes form entry should still exist", checkOne);
+  yield countEntries("4hour", "4hour form entry should still exist", checkOne);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (hoursSinceMidnight > 1)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
   ok(!downloadExists(5555551), "<1 hour download should now be deleted");
   ok(downloadExists(5555556), "1 hour 10 minute download should still be present");
   ok(downloadExists(5555550), "Year old download should still be present");
   ok(downloadExists(5555552), "<2 hour old download should still be present");
   ok(downloadExists(5555557), "2 hour 10 minute download should still be present");
   ok(downloadExists(5555553), "<4 hour old download should still be present");
   ok(downloadExists(5555558), "4 hour 10 minute download should still be present");
@@ -135,16 +180,18 @@ function onHistoryReady() {
   if (hoursSinceMidnight > 1)
     ok(downloadExists(5555554), "'Today' download should still be present");
   
   // Clear 1 hour 10 minutes
   s.range = [now_uSec - 70*60*1000000, now_uSec];
   s.sanitize();
   s.range = null;
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://1hour10minutes.com"))),
      "Pretend visit to 1hour10minutes.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://2hour.com"))),
      "Pretend visit to 2hour.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://2hour10minutes.com"))),
      "Pretend visit to 2hour10minutes.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://4hour.com"))),
      "Pretend visit to 4hour.com should should still exist");
@@ -152,188 +199,202 @@ function onHistoryReady() {
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (minutesSinceMidnight > 70) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("1hour10minutes"), "1hour10minutes form entry should be deleted");
-  ok(formhist.nameExists("2hour"), "2hour form entry should still exist");
-  ok(formhist.nameExists("2hour10minutes"), "2hour10minutes form entry should still exist");
-  ok(formhist.nameExists("4hour"), "4hour form entry should still exist");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  yield countEntries("1hour10minutes", "1hour10minutes form entry should be deleted", checkZero);
+  yield countEntries("2hour", "2hour form entry should still exist", checkOne);
+  yield countEntries("2hour10minutes", "2hour10minutes form entry should still exist", checkOne);
+  yield countEntries("4hour", "4hour form entry should still exist", checkOne);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (minutesSinceMidnight > 70)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
   ok(!downloadExists(5555556), "1 hour 10 minute old download should now be deleted");
   ok(downloadExists(5555550), "Year old download should still be present");
   ok(downloadExists(5555552), "<2 hour old download should still be present");
   ok(downloadExists(5555557), "2 hour 10 minute download should still be present");
   ok(downloadExists(5555553), "<4 hour old download should still be present");
   ok(downloadExists(5555558), "4 hour 10 minute download should still be present");
   if (minutesSinceMidnight > 70)
     ok(downloadExists(5555554), "'Today' download should still be present");
 
   // Clear 2 hours
   Sanitizer.prefs.setIntPref("timeSpan", 2);
   s.sanitize();
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://2hour.com"))),
      "Pretend visit to 2hour.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://2hour10minutes.com"))),
      "Pretend visit to 2hour10minutes.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://4hour.com"))),
      "Pretend visit to 4hour.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://4hour10minutes.com"))),
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (hoursSinceMidnight > 2) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("2hour"), "2hour form entry should be deleted");
-  ok(formhist.nameExists("2hour10minutes"), "2hour10minutes form entry should still exist");
-  ok(formhist.nameExists("4hour"), "4hour form entry should still exist");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  yield countEntries("2hour", "2hour form entry should be deleted", checkZero);
+  yield countEntries("2hour10minutes", "2hour10minutes form entry should still exist", checkOne);
+  yield countEntries("4hour", "4hour form entry should still exist", checkOne);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (hoursSinceMidnight > 2)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
   ok(!downloadExists(5555552), "<2 hour old download should now be deleted");
   ok(downloadExists(5555550), "Year old download should still be present");
   ok(downloadExists(5555557), "2 hour 10 minute download should still be present");
   ok(downloadExists(5555553), "<4 hour old download should still be present");
   ok(downloadExists(5555558), "4 hour 10 minute download should still be present");
   if (hoursSinceMidnight > 2)
     ok(downloadExists(5555554), "'Today' download should still be present");
   
   // Clear 2 hours 10 minutes
   s.range = [now_uSec - 130*60*1000000, now_uSec];
   s.sanitize();
   s.range = null;
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://2hour10minutes.com"))),
      "Pretend visit to 2hour10minutes.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://4hour.com"))),
      "Pretend visit to 4hour.com should should still exist");
   ok((yield promiseIsURIVisited(makeURI("http://4hour10minutes.com"))),
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (minutesSinceMidnight > 130) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("2hour10minutes"), "2hour10minutes form entry should be deleted");
-  ok(formhist.nameExists("4hour"), "4hour form entry should still exist");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  yield countEntries("2hour10minutes", "2hour10minutes form entry should be deleted", checkZero);
+  yield countEntries("4hour", "4hour form entry should still exist", checkOne);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (minutesSinceMidnight > 130)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
   ok(!downloadExists(5555557), "2 hour 10 minute old download should now be deleted");
   ok(downloadExists(5555553), "<4 hour old download should still be present");
   ok(downloadExists(5555558), "4 hour 10 minute download should still be present");
   ok(downloadExists(5555550), "Year old download should still be present");
   if (minutesSinceMidnight > 130)
     ok(downloadExists(5555554), "'Today' download should still be present");
 
   // Clear 4 hours
   Sanitizer.prefs.setIntPref("timeSpan", 3);
   s.sanitize();
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://4hour.com"))),
      "Pretend visit to 4hour.com should now be deleted");
   ok((yield promiseIsURIVisited(makeURI("http://4hour10minutes.com"))),
      "Pretend visit to 4hour10minutes.com should should still exist");
   if (hoursSinceMidnight > 4) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
 
-  ok(!formhist.nameExists("4hour"), "4hour form entry should be deleted");
-  ok(formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should still exist");
+  yield countEntries("4hour", "4hour form entry should be deleted", checkZero);
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should still exist", checkOne);
   if (hoursSinceMidnight > 4)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
 
   ok(!downloadExists(5555553), "<4 hour old download should now be deleted");
   ok(downloadExists(5555558), "4 hour 10 minute download should still be present");
   ok(downloadExists(5555550), "Year old download should still be present");
   if (hoursSinceMidnight > 4)
     ok(downloadExists(5555554), "'Today' download should still be present");
 
   // Clear 4 hours 10 minutes
   s.range = [now_uSec - 250*60*1000000, now_uSec];
   s.sanitize();
   s.range = null;
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://4hour10minutes.com"))),
      "Pretend visit to 4hour10minutes.com should now be deleted");
   if (minutesSinceMidnight > 250) {
     ok((yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should still exist");
   }
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
     "Pretend visit to before-today.com should still exist");
-  
-  ok(!formhist.nameExists("4hour10minutes"), "4hour10minutes form entry should be deleted");
+
+  yield countEntries("4hour10minutes", "4hour10minutes form entry should be deleted", checkZero);
   if (minutesSinceMidnight > 250)
-    ok(formhist.nameExists("today"), "today form entry should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
-
+    yield countEntries("today", "today form entry should still exist", checkOne);
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
+  
   ok(!downloadExists(5555558), "4 hour 10 minute download should now be deleted");
   ok(downloadExists(5555550), "Year old download should still be present");
   if (minutesSinceMidnight > 250)
     ok(downloadExists(5555554), "'Today' download should still be present");
 
   // Clear Today
   Sanitizer.prefs.setIntPref("timeSpan", 4);
   s.sanitize();
 
+  yield promiseFormHistoryRemoved();
+
   // Be careful.  If we add our objectss just before midnight, and sanitize
   // runs immediately after, they won't be expired.  This is expected, but
   // we should not test in that case.  We cannot just test for opposite
   // condition because we could cross midnight just one moment after we
   // cache our time, then we would have an even worse random failure.
   var today = isToday(new Date(now_uSec/1000));
   if (today) {
     ok(!(yield promiseIsURIVisited(makeURI("http://today.com"))),
        "Pretend visit to today.com should now be deleted");
-    ok(!formhist.nameExists("today"), "today form entry should be deleted");
+
+    yield countEntries("today", "today form entry should be deleted", checkZero);
     ok(!downloadExists(5555554), "'Today' download should now be deleted");
   }
 
   ok((yield promiseIsURIVisited(makeURI("http://before-today.com"))),
      "Pretend visit to before-today.com should still exist");
-  ok(formhist.nameExists("b4today"), "b4today form entry should still exist");
+  yield countEntries("b4today", "b4today form entry should still exist", checkOne);
   ok(downloadExists(5555550), "Year old download should still be present");
 
   // Choose everything
   Sanitizer.prefs.setIntPref("timeSpan", 0);
   s.sanitize();
 
+  yield promiseFormHistoryRemoved();
+
   ok(!(yield promiseIsURIVisited(makeURI("http://before-today.com"))),
      "Pretend visit to before-today.com should now be deleted");
 
-  ok(!formhist.nameExists("b4today"), "b4today form entry should be deleted");
+  yield countEntries("b4today", "b4today form entry should be deleted", checkZero);
 
   ok(!downloadExists(5555550), "Year old download should now be deleted");
 }
 
-function setupHistory(aCallback) {
+function setupHistory() {
+  let deferred = Promise.defer();
+
   let places = [];
 
   function addPlace(aURI, aTitle, aVisitDate) {
     places.push({
       uri: aURI,
       title: aTitle,
       visits: [{
         visitDate: aVisitDate,
@@ -358,83 +419,150 @@ function setupHistory(aCallback) {
 
   let lastYear = new Date();
   lastYear.setFullYear(lastYear.getFullYear() - 1);
   addPlace(makeURI("http://before-today.com/"), "Before Today", lastYear.getTime() * 1000);
 
   PlacesUtils.asyncHistory.updatePlaces(places, {
     handleError: function () ok(false, "Unexpected error in adding visit."),
     handleResult: function () { },
-    handleCompletion: function () aCallback()
+    handleCompletion: function () deferred.resolve()
   });
+
+  return deferred.promise;
 }
 
 function setupFormHistory() {
-  // Make sure we've got a clean DB to start with.
-  formhist.removeAllEntries();
+
+  function searchEntries(terms, params) {
+    let deferred = Promise.defer();
+
+    let results = [];
+    FormHistory.search(terms, params, { handleResult: function (result) results.push(result),
+                                        handleError: function (error) {
+                                          do_throw("Error occurred searching form history: " + error);
+                                          deferred.reject(error);
+                                        },
+                                        handleCompletion: function (reason) { deferred.resolve(results); }
+                                      });
+    return deferred.promise;
+  }
+
+  function update(changes)
+  {
+    let deferred = Promise.defer();
+    FormHistory.update(changes, { handleError: function (error) {
+                                    do_throw("Error occurred searching form history: " + error);
+                                    deferred.reject(error);
+                                  },
+                                  handleCompletion: function (reason) { deferred.resolve(); }
+                                });
+    return deferred.promise;
+  }
 
-  // Add the entries we'll be testing.
-  formhist.addEntry("10minutes", "10m");
-  formhist.addEntry("1hour", "1h");
-  formhist.addEntry("1hour10minutes", "1h10m");
-  formhist.addEntry("2hour", "2h");
-  formhist.addEntry("2hour10minutes", "2h10m");
-  formhist.addEntry("4hour", "4h");
-  formhist.addEntry("4hour10minutes", "4h10m");
-  formhist.addEntry("today", "1d");
-  formhist.addEntry("b4today", "1y");
+  // Make sure we've got a clean DB to start with, then add the entries we'll be testing.
+  yield update(
+    [{
+        op: "remove"
+     },
+     {
+        op : "add",
+        fieldname : "10minutes",
+        value : "10m"
+      }, {
+        op : "add",
+        fieldname : "1hour",
+        value : "1h"
+      }, {
+        op : "add",
+        fieldname : "1hour10minutes",
+        value : "1h10m"
+      }, {
+        op : "add",
+        fieldname : "2hour",
+        value : "2h"
+      }, {
+        op : "add",
+        fieldname : "2hour10minutes",
+        value : "2h10m"
+      }, {
+        op : "add",
+        fieldname : "4hour",
+        value : "4h"
+      }, {
+        op : "add",
+        fieldname : "4hour10minutes",
+        value : "4h10m"
+      }, {
+        op : "add",
+        fieldname : "today",
+        value : "1d"
+      }, {
+        op : "add",
+        fieldname : "b4today",
+        value : "1y"
+      }]);
 
   // Artifically age the entries to the proper vintage.
-  let db = formhist.DBConnection;
   let timestamp = now_uSec - 10 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '10minutes'");
+  let results = yield searchEntries(["guid"], { fieldname: "10minutes" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 45 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '1hour'");
+  results = yield searchEntries(["guid"], { fieldname: "1hour" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 70 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '1hour10minutes'");
+  results = yield searchEntries(["guid"], { fieldname: "1hour10minutes" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 90 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '2hour'");
+  results = yield searchEntries(["guid"], { fieldname: "2hour" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 130 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '2hour10minutes'");
+  results = yield searchEntries(["guid"], { fieldname: "2hour10minutes" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 180 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '4hour'");
+  results = yield searchEntries(["guid"], { fieldname: "4hour" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
   timestamp = now_uSec - 250 * kUsecPerMin;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '4hour10minutes'");
+  results = yield searchEntries(["guid"], { fieldname: "4hour10minutes" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
 
   let today = new Date();
   today.setHours(0);
   today.setMinutes(0);
   today.setSeconds(1);
   timestamp = today.getTime() * 1000;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = 'today'");
+  results = yield searchEntries(["guid"], { fieldname: "today" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
 
   let lastYear = new Date();
   lastYear.setFullYear(lastYear.getFullYear() - 1);
   timestamp = lastYear.getTime() * 1000;
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = 'b4today'");
+  results = yield searchEntries(["guid"], { fieldname: "b4today" });
+  yield update({ op: "update", firstUsed: timestamp, guid: results[0].guid });
+
+  var checks = 0;
+  let checkOne = function(num, message) { is(num, 1, message); checks++; }
 
   // Sanity check.
-  ok(formhist.nameExists("10minutes"), "Checking for 10minutes form history entry creation");
-  ok(formhist.nameExists("1hour"), "Checking for 1hour form history entry creation");
-  ok(formhist.nameExists("1hour10minutes"), "Checking for 1hour10minutes form history entry creation");
-  ok(formhist.nameExists("2hour"), "Checking for 2hour form history entry creation");
-  ok(formhist.nameExists("2hour10minutes"), "Checking for 2hour10minutes form history entry creation");
-  ok(formhist.nameExists("4hour"), "Checking for 4hour form history entry creation");
-  ok(formhist.nameExists("4hour10minutes"), "Checking for 4hour10minutes form history entry creation");
-  ok(formhist.nameExists("today"), "Checking for today form history entry creation");
-  ok(formhist.nameExists("b4today"), "Checking for b4today form history entry creation");
+  yield countEntries("10minutes", "Checking for 10minutes form history entry creation", checkOne);
+  yield countEntries("1hour", "Checking for 1hour form history entry creation", checkOne);
+  yield countEntries("1hour10minutes", "Checking for 1hour10minutes form history entry creation", checkOne);
+  yield countEntries("2hour", "Checking for 2hour form history entry creation", checkOne);
+  yield countEntries("2hour10minutes", "Checking for 2hour10minutes form history entry creation", checkOne);
+  yield countEntries("4hour", "Checking for 4hour form history entry creation", checkOne);
+  yield countEntries("4hour10minutes", "Checking for 4hour10minutes form history entry creation", checkOne);
+  yield countEntries("today", "Checking for today form history entry creation", checkOne);
+  yield countEntries("b4today", "Checking for b4today form history entry creation", checkOne);
+  is(checks, 9, "9 checks made");
 }
 
 function setupDownloads() {
 
   // Add 10-minutes download to DB
   let data = {
     id:   "5555555",
     name: "fakefile-10-minutes",

--- a/browser/base/content/test/browser_sanitizeDialog.js
+++ b/browser/base/content/test/browser_sanitizeDialog.js
@@ -12,28 +12,33 @@
  * browser/base/content/test/browser_sanitize-timespans.js does that.  This
  * test checks the UI of the dialog and makes sure it's correctly connected to
  * the sanitize timespan code.
  *
  * Some of this code, especially the history creation parts, was taken from
  * browser/base/content/test/browser_sanitize-timespans.js.
  */
 
+Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
+
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+                                  "resource://gre/modules/FormHistory.jsm");
+
 let tempScope = {};
 Cc["@mozilla.org/moz/jssubscript-loader;1"].getService(Ci.mozIJSSubScriptLoader)
                                            .loadSubScript("chrome://browser/content/sanitize.js", tempScope);
 let Sanitizer = tempScope.Sanitizer;
 
 const dm = Cc["@mozilla.org/download-manager;1"].
            getService(Ci.nsIDownloadManager);
-const formhist = Cc["@mozilla.org/satchel/form-history;1"].
-                 getService(Ci.nsIFormHistory2);
 
 const kUsecPerMin = 60 * 1000000;
 
+let formEntries;
+
 // Add tests here.  Each is a function that's called by doNextTest().
 var gAllTests = [
 
   /**
    * Initializes the dialog to its default state.
    */
   function () {
     let wh = new WindowHelper();
@@ -75,17 +80,17 @@ var gAllTests = [
 
         // Hide details
         this.toggleDetails();
         this.checkDetails(false);
         this.cancelDialog();
       };
       wh.onunload = function () {
         yield promiseHistoryClearedState(uris, false);
-        blankSlate();
+        yield blankSlate();
         yield promiseHistoryClearedState(uris, true);
       };
       wh.open();
     });
   },
 
   /**
    * Ensures that the combined history-downloads checkbox clears both history
@@ -143,25 +148,42 @@ var gAllTests = [
         yield promiseHistoryClearedState(uris, true);
         ensureDownloadsClearedState(downloadIDs, true);
 
         // Visits and downloads > 1 hour should still exist.
         yield promiseHistoryClearedState(olderURIs, false);
         ensureDownloadsClearedState(olderDownloadIDs, false);
 
         // OK, done, cleanup after ourselves.
-        blankSlate();
+        yield blankSlate();
         yield promiseHistoryClearedState(olderURIs, true);
         ensureDownloadsClearedState(olderDownloadIDs, true);
       };
       wh.open();
     });
   },
 
   /**
+   * Add form history entries for the next test.
+   */
+  function () {
+    formEntries = [];
+
+    let iter = function() {
+      for (let i = 0; i < 5; i++) {
+        formEntries.push(addFormEntryWithMinutesAgo(iter, i));
+        yield;
+      }
+      doNextTest();
+    }();
+
+    iter.next();
+  },
+
+  /**
    * Ensures that the combined history-downloads checkbox removes neither
    * history visits nor downloads when not checked.
    */
   function () {
     // Add history, downloads, form entries (within the past hour).
     let uris = [];
     let places = [];
     let pURI;
@@ -171,20 +193,16 @@ var gAllTests = [
       uris.push(pURI);
     }
 
     addVisits(places, function() {
       let downloadIDs = [];
       for (let i = 0; i < 5; i++) {
         downloadIDs.push(addDownloadWithMinutesAgo(i));
       }
-      let formEntries = [];
-      for (let i = 0; i < 5; i++) {
-        formEntries.push(addFormEntryWithMinutesAgo(i));
-      }
 
       let wh = new WindowHelper();
       wh.onload = function () {
         is(this.isWarningPanelVisible(), false,
            "Warning panel should be hidden after previously accepting dialog " +
            "with a predefined timespan");
         this.selectDuration(Sanitizer.TIMESPAN_HOUR);
 
@@ -202,20 +220,24 @@ var gAllTests = [
         boolPrefIs("cpd.downloads", false,
                    "downloads pref should be false after accepting dialog with " +
                    "history checkbox unchecked");
       };
       wh.onunload = function () {
         // Of the three only form entries should be cleared.
         yield promiseHistoryClearedState(uris, false);
         ensureDownloadsClearedState(downloadIDs, false);
-        ensureFormEntriesClearedState(formEntries, true);
+
+        formEntries.forEach(function (entry) {
+          let exists = yield formNameExists(entry);
+          is(exists, false, "form entry " + entry + " should no longer exist");
+        });
 
         // OK, done, cleanup after ourselves.
-        blankSlate();
+        yield blankSlate();
         yield promiseHistoryClearedState(uris, true);
         ensureDownloadsClearedState(downloadIDs, true);
       };
       wh.open();
     });
   },
 
   /**
@@ -297,26 +319,38 @@ var gAllTests = [
       wh.onunload = function () {
         yield promiseHistoryClearedState(uris, true);
       };
       wh.open();
     });
   },
 
   /**
+   * Add form history entry for the next test.
+   */
+  function () {
+    let iter = function() {
+      formEntries = [ addFormEntryWithMinutesAgo(iter, 10) ];
+      yield;
+      doNextTest();
+    }();
+
+    iter.next();
+  },
+
+  /**
    * The next three tests checks that when a certain history item cannot be
    * cleared then the checkbox should be both disabled and unchecked.
    * In addition, we ensure that this behavior does not modify the preferences.
    */
   function () {
     // Add history.
     let pURI = makeURI("http://" + 10 + "-minutes-ago.com/");
     addVisits({uri: pURI, visitDate: visitTimeForMinutesAgo(10)}, function() {
       let uris = [ pURI ];
-      let formEntries = [ addFormEntryWithMinutesAgo(10) ];
 
       let wh = new WindowHelper();
       wh.onload = function() {
         // Check that the relevant checkboxes are enabled
         var cb = this.win.document.querySelectorAll(
                    "#itemList > [preference='privacy.cpd.formdata']");
         ok(cb.length == 1 && !cb[0].disabled, "There is formdata, checkbox to " +
            "clear formdata should be enabled.");
@@ -326,17 +360,19 @@ var gAllTests = [
         ok(cb.length == 1 && !cb[0].disabled, "There is history, checkbox to " +
            "clear history should be enabled.");
 
         this.checkAllCheckboxes();
         this.acceptDialog();
       };
       wh.onunload = function () {
         yield promiseHistoryClearedState(uris, true);
-        ensureFormEntriesClearedState(formEntries, true);
+
+        let exists = yield formNameExists(formEntries[0]);
+        is(exists, false, "form entry " + formEntries[0] + " should no longer exist");
       };
       wh.open();
     });
   },
   function () {
     let wh = new WindowHelper();
     wh.onload = function() {
       boolPrefIs("cpd.history", true,
@@ -360,35 +396,48 @@ var gAllTests = [
       ok(cb.length == 1 && !cb[0].disabled && cb[0].checked,
          "There is no history, but history checkbox should always be enabled " +
          "and will be checked from previous preference.");
 
       this.acceptDialog();
     }
     wh.open();
   },
+
+  /**
+   * Add form history entry for the next test.
+   */
   function () {
-    let formEntries = [ addFormEntryWithMinutesAgo(10) ];
+    let iter = function() {
+      formEntries = [ addFormEntryWithMinutesAgo(iter, 10) ];
+      yield;
+      doNextTest();
+    }();
 
+    iter.next();
+  },
+
+  function () {
     let wh = new WindowHelper();
     wh.onload = function() {
       boolPrefIs("cpd.formdata", true,
                  "formdata pref should persist previous value after accepting " +
                  "dialog where you could not clear formdata.");
 
       var cb = this.win.document.querySelectorAll(
                  "#itemList > [preference='privacy.cpd.formdata']");
       ok(cb.length == 1 && !cb[0].disabled && cb[0].checked,
          "There exists formEntries so the checkbox should be in sync with " +
          "the pref.");
 
       this.acceptDialog();
     };
     wh.onunload = function () {
-      ensureFormEntriesClearedState(formEntries, true);
+      let exists = yield formNameExists(formEntries[0]);
+      is(exists, false, "form entry " + formEntries[0] + " should no longer exist");
     };
     wh.open();
   },
 
 
   /**
    * These next six tests together ensure that toggling details persists
    * across dialog openings.
@@ -734,17 +783,19 @@ WindowHelper.prototype = {
   isWarningPanelVisible: function () {
     return !this.getWarningPanel().hidden;
   },
 
   /**
    * Opens the clear recent history dialog.  Before calling this, set
    * this.onload to a function to execute onload.  It should close the dialog
    * when done so that the tests may continue.  Set this.onunload to a function
-   * to execute onunload.  this.onunload is optional.
+   * to execute onunload.  this.onunload is optional. If it returns true, the
+   * caller is expected to call waitForAsyncUpdates at some point; if false is
+   * returned, waitForAsyncUpdates is called automatically.
    */
   open: function () {
     let wh = this;
 
     function windowObserver(aSubject, aTopic, aData) {
       if (aTopic != "domwindowopened")
         return;
 
@@ -886,38 +937,69 @@ function addDownloadWithMinutesAgo(aMinu
 }
 
 /**
  * Adds a form entry to history.
  *
  * @param aMinutesAgo
  *        The entry will be added this many minutes ago
  */
-function addFormEntryWithMinutesAgo(aMinutesAgo) {
+function addFormEntryWithMinutesAgo(then, aMinutesAgo) {
   let name = aMinutesAgo + "-minutes-ago";
-  formhist.addEntry(name, "dummy");
 
   // Artifically age the entry to the proper vintage.
-  let db = formhist.DBConnection;
   let timestamp = now_uSec - (aMinutesAgo * kUsecPerMin);
-  db.executeSimpleSQL("UPDATE moz_formhistory SET firstUsed = " +
-                      timestamp +  " WHERE fieldname = '" + name + "'");
+
+  FormHistory.update({ op: "add", fieldname: name, value: "dummy", firstUsed: timestamp },
+                     { handleError: function (error) {
+                         do_throw("Error occurred updating form history: " + error);
+                       },
+                       handleCompletion: function (reason) { then.next(); }
+                     });
+  return name;
+}
 
-  is(formhist.nameExists(name), true,
-     "Sanity check: form entry " + name + " should exist after creating it");
-  return name;
+/**
+ * Checks if a form entry exists.
+ */
+function formNameExists(name)
+{
+  let deferred = Promise.defer();
+
+  let count = 0;
+  FormHistory.count({ fieldname: name },
+                    { handleResult: function (result) count = result,
+                      handleError: function (error) {
+                        do_throw("Error occurred searching form history: " + error);
+                        deferred.reject(error);
+                      },
+                      handleCompletion: function (reason) {
+                          if (!reason) deferred.resolve(count);
+                      }
+                    });
+
+  return deferred.promise;
 }
 
 /**
  * Removes all history visits, downloads, and form entries.
  */
 function blankSlate() {
   PlacesUtils.bhistory.removeAllPages();
   dm.cleanUp();
-  formhist.removeAllEntries();
+
+  let deferred = Promise.defer();
+  FormHistory.update({ op: "remove" },
+                     { handleError: function (error) {
+                         do_throw("Error occurred updating form history: " + error);
+                         deferred.reject(error);
+                       },
+                       handleCompletion: function (reason) { if (!reason) deferred.resolve(); }
+                     });
+  return deferred.promise;
 }
 
 /**
  * Ensures that the given pref is the expected value.
  *
  * @param aPrefName
  *        The pref's sub-branch under the privacy branch
  * @param aExpectedVal
@@ -978,32 +1060,16 @@ function ensureDownloadsClearedState(aDo
   let niceStr = aShouldBeCleared ? "no longer" : "still";
   aDownloadIDs.forEach(function (id) {
     is(downloadExists(id), !aShouldBeCleared,
        "download " + id + " should " + niceStr + " exist");
   });
 }
 
 /**
- * Ensures that the specified form entries are either cleared or not.
- *
- * @param aFormEntries
- *        Array of form entry names
- * @param aShouldBeCleared
- *        True if each form entry should be cleared, false otherwise
- */
-function ensureFormEntriesClearedState(aFormEntries, aShouldBeCleared) {
-  let niceStr = aShouldBeCleared ? "no longer" : "still";
-  aFormEntries.forEach(function (entry) {
-    is(formhist.nameExists(entry), !aShouldBeCleared,
-       "form entry " + entry + " should " + niceStr + " exist");
-  });
-}
-
-/**
  * Ensures that the given pref is the expected value.
  *
  * @param aPrefName
  *        The pref's sub-branch under the privacy branch
  * @param aExpectedVal
  *        The pref's expected value
  * @param aMsg
  *        Passed to is()
@@ -1021,13 +1087,13 @@ function intPrefIs(aPrefName, aExpectedV
 function visitTimeForMinutesAgo(aMinutesAgo) {
   return now_uSec - aMinutesAgo * kUsecPerMin;
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 function test() {
   requestLongerTimeout(2);
+  waitForExplicitFinish();
   blankSlate();
-  waitForExplicitFinish();
   // Kick off all the tests in the gAllTests array.
   waitForAsyncUpdates(doNextTest);
 }

--- a/browser/components/places/tests/unit/test_clearHistory_shutdown.js
+++ b/browser/components/places/tests/unit/test_clearHistory_shutdown.js
@@ -25,16 +25,22 @@ let EXPECTED_NOTIFICATIONS = [
 ];
 
 const UNEXPECTED_NOTIFICATIONS = [
   "xpcom-shutdown"
 ];
 
 const URL = "ftp://localhost/clearHistoryOnShutdown/";
 
+// Send the profile-after-change notification to the form history component to ensure
+// that it has been initialized.
+var formHistoryStartup = Cc["@mozilla.org/satchel/form-history-startup;1"].
+                         getService(Ci.nsIObserver);
+formHistoryStartup.observe(null, "profile-after-change", null);
+
 let notificationIndex = 0;
 
 let notificationsObserver = {
   observe: function observe(aSubject, aTopic, aData) {
     print("Received notification: " + aTopic);
 
     // Note that some of these notifications could arrive multiple times, for
     // example in case of sync, we allow that.

--- a/browser/components/search/content/search.xml
+++ b/browser/components/search/content/search.xml
@@ -104,16 +104,19 @@
       <field name="_stringBundle">document.getAnonymousElementByAttribute(this,
           "anonid", "searchbar-stringbundle");</field>
       <field name="_textbox">document.getAnonymousElementByAttribute(this,
           "anonid", "searchbar-textbox");</field>
       <field name="_popup">document.getAnonymousElementByAttribute(this,
           "anonid", "searchbar-popup");</field>
       <field name="_ss">null</field>
       <field name="_engines">null</field>
+      <field name="FormHistory" readonly="true">
+        (Components.utils.import("resource://gre/modules/FormHistory.jsm", {})).FormHistory;
+      </field>
 
       <property name="engines" readonly="true">
         <getter><![CDATA[
           if (!this._engines)
             this._engines = this.searchService.getVisibleEngines();
           return this._engines;
         ]]></getter>
       </property>
@@ -450,22 +453,23 @@
           else {
             var newTabPref = textBox._prefBranch.getBoolPref("browser.search.openintab");
             if ((aEvent && aEvent.altKey) ^ newTabPref)
               where = "tab";
           }
 
           // Save the current value in the form history
           if (textValue && !PrivateBrowsingUtils.isWindowPrivate(window)) {
-            try {
-              textBox._formHistSvc.addEntry(textBox.getAttribute("autocompletesearchparam"),
-                                            textValue);
-            } catch (ex) {
-              Components.utils.reportError("Saving search to form history failed: " + ex);
-            }
+            this.FormHistory.update(
+              { op : "bump",
+                fieldname : textBox.getAttribute("autocompletesearchparam"),
+                value : textValue },
+              { handleError : function(aError) {
+                  Components.utils.reportError("Saving search to form history failed: " + aError.message);
+              }});
           }
 
           this.doSearch(textValue, where);
         ]]></body>
       </method>
 
       <method name="doSearch">
         <parameter name="aData"/>
@@ -549,30 +553,26 @@
         // Because XBL and the customize toolbar code interacts poorly,
         // there may not be anything to remove here
         try {
           this.controllers.removeController(this.searchbarController);
         } catch (ex) { }
       ]]></destructor>
 
       <field name="_stringBundle"/>
-      <field name="_formHistSvc"/>
       <field name="_prefBranch"/>
       <field name="_suggestMenuItem"/>
       <field name="_suggestEnabled"/>
 
       <method name="initialize">
         <body><![CDATA[
           const kXULNS =
             "http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul";
           // Initialize fields
           this._stringBundle = document.getBindingParent(this)._stringBundle;
-          this._formHistSvc =
-                   Components.classes["@mozilla.org/satchel/form-history;1"]
-                             .getService(Components.interfaces.nsIFormHistory2);
           this._prefBranch =
                     Components.classes["@mozilla.org/preferences-service;1"]
                               .getService(Components.interfaces.nsIPrefBranch);
           this._suggestEnabled =
               this._prefBranch.getBoolPref("browser.search.suggest.enabled");
 
           if (this._prefBranch.getBoolPref("browser.urlbar.clickSelectsAll"))
             this.setAttribute("clickSelectsAll", true);
@@ -743,28 +743,27 @@
       <field name="searchbarController" readonly="true"><![CDATA[({
         _self: this,
         supportsCommand: function(aCommand) {
           return aCommand == "cmd_clearhistory" ||
                  aCommand == "cmd_togglesuggest";
         },
 
         isCommandEnabled: function(aCommand) {
-          if (aCommand == "cmd_clearhistory") {
-            var param = this._self.getAttribute("autocompletesearchparam");
-            return this._self._formHistSvc.nameExists(param);
-          }
           return true;
         },
 
         doCommand: function (aCommand) {
           switch (aCommand) {
             case "cmd_clearhistory":
               var param = this._self.getAttribute("autocompletesearchparam");
-              this._self._formHistSvc.removeEntriesForName(param);
+
+              let searchBar = this._self.parentNode;
+
+              BrowserSearch.searchBar.FormHistory.update({ op : "remove", fieldname : param }, null);
               this._self.value = "";
               break;
             case "cmd_togglesuggest":
               // The pref observer will update _suggestEnabled and the menu
               // checkmark.
               this._self._prefBranch.setBoolPref("browser.search.suggest.enabled",
                                                  !this._self._suggestEnabled);
               break;

--- a/browser/components/search/test/browser_426329.js
+++ b/browser/components/search/test/browser_426329.js
@@ -1,30 +1,35 @@
 // Instead of loading ChromeUtils.js into the test scope in browser-test.js for all tests,
 // we only need ChromeUtils.js for a few files which is why we are using loadSubScript.
 var ChromeUtils = {};
 this._scriptLoader = Cc["@mozilla.org/moz/jssubscript-loader;1"].
                      getService(Ci.mozIJSSubScriptLoader);
 this._scriptLoader.loadSubScript("chrome://mochikit/content/tests/SimpleTest/ChromeUtils.js", ChromeUtils);
 
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+  "resource://gre/modules/FormHistory.jsm");
+
 function test() {
   waitForExplicitFinish();
 
   const ENGINE_HTML_BASE = "http://mochi.test:8888/browser/browser/components/search/test/test.html";
 
   var searchEntries = ["test", "More Text", "Some Text"];
   var searchBar = BrowserSearch.searchBar;
   var searchButton = document.getAnonymousElementByAttribute(searchBar,
                      "anonid", "search-go-button");
   ok(searchButton, "got search-go-button");
 
   searchBar.value = "test";
 
   var ss = Services.search;
 
+  let testIterator;
+
   function observer(aSub, aTopic, aData) {
     switch (aData) {
       case "engine-added":
         var engine = ss.getEngineByName("Bug 426329");
         ok(engine, "Engine was added.");
         //XXX Bug 493051
         //ss.currentEngine = engine;
         break;
@@ -177,43 +182,74 @@ function test() {
   }
 
   function testRightClick() {
     init();
     searchBar.removeEventListener("popupshowing", stopPopup, true);
     content.location.href = "about:blank";
     simulateClick({ button: 2 }, searchButton);
     setTimeout(function() {
-
       is(gBrowser.tabs.length, preTabNo, "RightClick did not open new tab");
       is(gBrowser.currentURI.spec, "about:blank", "RightClick did nothing");
 
-      testSearchHistory();
+      testIterator = testSearchHistory();
+      testIterator.next();
     }, 5000);
   }
 
+  function countEntries(name, value, message) {
+    let count = 0;
+    FormHistory.count({ fieldname: name, value: value },
+                      { handleResult: function(result) { count = result; },
+                        handleError: function(error) { throw error; },
+                        handleCompletion: function(reason) {
+                          if (!reason) {
+                            ok(count > 0, message);
+                            testIterator.next();
+                          }
+                        }
+                      });
+  }
+
   function testSearchHistory() {
     var textbox = searchBar._textbox;
     for (var i = 0; i < searchEntries.length; i++) {
-      let exists = textbox._formHistSvc.entryExists(textbox.getAttribute("autocompletesearchparam"), searchEntries[i]);
-      ok(exists, "form history entry '" + searchEntries[i] + "' should exist");
+      yield countEntries(textbox.getAttribute("autocompletesearchparam"), searchEntries[i],
+                         "form history entry '" + searchEntries[i] + "' should exist");
     }
     testAutocomplete();
   }
 
   function testAutocomplete() {
     var popup = searchBar.textbox.popup;
-    popup.addEventListener("popupshowing", function testACPopupShowing() {
-      popup.removeEventListener("popupshowing", testACPopupShowing);
+    popup.addEventListener("popupshown", function testACPopupShowing() {
+      popup.removeEventListener("popupshown", testACPopupShowing);
       checkMenuEntries(searchEntries);
-      SimpleTest.executeSoon(finalize);
+      testClearHistory();
     });
     searchBar.textbox.showHistoryPopup();
   }
 
+  function testClearHistory() {
+    let controller = searchBar.textbox.controllers.getControllerForCommand("cmd_clearhistory")
+    ok(controller.isCommandEnabled("cmd_clearhistory"), "Clear history command enabled");
+    controller.doCommand("cmd_clearhistory");
+    let count = 0;
+    FormHistory.count({ },
+                      { handleResult: function(result) { count = result; },
+                        handleError: function(error) { throw error; },
+                        handleCompletion: function(reason) {
+                          if (!reason) {
+                            ok(count == 0, "History cleared");
+                            finalize();
+                          }
+                        }
+                      });
+  }
+
   function finalize() {
     searchBar.value = "";
     while (gBrowser.tabs.length != 1) {
       gBrowser.removeTab(gBrowser.tabs[0]);
     }
     content.location.href = "about:blank";
     var engine = ss.getEngineByName("Bug 426329");
     ss.removeEngine(engine);

--- a/browser/installer/package-manifest.in
+++ b/browser/installer/package-manifest.in
@@ -427,16 +427,17 @@
 @BINPATH@/components/nsContentDispatchChooser.js
 @BINPATH@/components/nsHandlerService.manifest
 @BINPATH@/components/nsHandlerService.js
 @BINPATH@/components/nsWebHandlerApp.manifest
 @BINPATH@/components/nsWebHandlerApp.js
 @BINPATH@/components/satchel.manifest
 @BINPATH@/components/nsFormAutoComplete.js
 @BINPATH@/components/nsFormHistory.js
+@BINPATH@/components/FormHistoryStartup.js
 @BINPATH@/components/nsInputListAutoComplete.js
 @BINPATH@/components/contentSecurityPolicy.manifest
 @BINPATH@/components/contentSecurityPolicy.js
 @BINPATH@/components/contentAreaDropListener.manifest
 @BINPATH@/components/contentAreaDropListener.js
 #ifdef MOZ_B2G_RIL
 @BINPATH@/components/RadioInterfaceLayer.manifest
 @BINPATH@/components/RadioInterfaceLayer.js

--- a/editor/libeditor/text/tests/test_bug527935.html
+++ b/editor/libeditor/text/tests/test_bug527935.html
@@ -32,29 +32,29 @@ SimpleTest.waitForFocus(function() {
     newInput.setAttribute("name", "test");
     document.body.appendChild(newInput);
 
     setTimeout(function() {
       var popupShown = false;
       function listener() {
         popupShown = true;
       }
-      SpecialPowers.addAutoCompletePopupEventListener(window, listener);
+      SpecialPowers.addAutoCompletePopupEventListener(window, "popupshowing", listener);
 
       var event = document.createEvent("KeyboardEvent");
 
       event.initKeyEvent("keypress", true, true, null, false, false,
                          false, false, 0, "f".charCodeAt(0));
       newInput.value = "";
       newInput.focus();
       newInput.dispatchEvent(event);
 
       hitEventLoop(function() {
         ok(!popupShown, "Popup must not be opened");
-        SpecialPowers.removeAutoCompletePopupEventListener(window, listener);
+        SpecialPowers.removeAutoCompletePopupEventListener(window, "popupshowing", listener);
         SimpleTest.finish();
       }, 100);
     }, 0);
   }, false);
 
   initValue.focus();
   initValue.value = "foo";
   synthesizeKey("VK_ENTER", {});

--- a/mobile/android/chrome/content/browser.js
+++ b/mobile/android/chrome/content/browser.js
@@ -4656,17 +4656,17 @@ var FormAssistant = {
         if (aData == "NOTHING") {
           // only look for input elements, not contentEditable or multiline text areas
           let focused = BrowserApp.getFocusedInput(BrowserApp.selectedBrowser, true);
           if (!focused)
             break;
 
           if (this._showValidationMessage(focused))
             break;
-          this._showAutoCompleteSuggestions(focused);
+          this._showAutoCompleteSuggestions(focused, function () {});
         } else {
           // temporarily hide the form assist popup while we're panning or zooming the page
           this._hideFormAssistPopup();
         }
         break;
       case "FormAssist:AutoComplete":
         if (!this._currentInputElement)
           break;
@@ -4726,32 +4726,43 @@ var FormAssistant = {
       case "click":
         currentElement = aEvent.target;
 
         // Prioritize a form validation message over autocomplete suggestions
         // when the element is first focused (a form validation message will
         // only be available if an invalid form was submitted)
         if (this._showValidationMessage(currentElement))
           break;
-        if (!this._showAutoCompleteSuggestions(currentElement))
-          this._hideFormAssistPopup();
+
+        let checkResultsClick = hasResults => {
+          if (!hasResults) {
+            this._hideFormAssistPopup();
+          }
+        };
+
+        this._showAutoCompleteSuggestions(currentElement, checkResultsClick);
         break;
 
       case "input":
         currentElement = aEvent.target;
 
         // Since we can only show one popup at a time, prioritze autocomplete
         // suggestions over a form validation message
-        if (this._showAutoCompleteSuggestions(currentElement))
-          break;
-        if (this._showValidationMessage(currentElement))
-          break;
-
-        // If we're not showing autocomplete suggestions, hide the form assist popup
-        this._hideFormAssistPopup();
+        let checkResultsInput = hasResults => {
+          if (hasResults)
+            return;
+
+          if (!this._showValidationMessage(currentElement))
+            return;
+
+          // If we're not showing autocomplete suggestions, hide the form assist popup
+          this._hideFormAssistPopup();
+        };
+
+        this._showAutoCompleteSuggestions(currentElement, checkResultsInput);
         break;
 
       // Reset invalid submit state on each pageshow
       case "pageshow":
         let target = aEvent.originalTarget;
         let selectedDocument = BrowserApp.selectedBrowser.contentDocument;
         if (target == selectedDocument || target.ownerDocument == selectedDocument)
           this._invalidSubmit = false;
@@ -4765,37 +4776,41 @@ var FormAssistant = {
         (aElement.hasAttribute("autocomplete") &&
          aElement.getAttribute("autocomplete").toLowerCase() == "off"))
       return false;
 
     return true;
   },
 
   // Retrieves autocomplete suggestions for an element from the form autocomplete service.
-  _getAutoCompleteSuggestions: function _getAutoCompleteSuggestions(aSearchString, aElement) {
+  // aCallback(array_of_suggestions) is called when results are available.
+  _getAutoCompleteSuggestions: function _getAutoCompleteSuggestions(aSearchString, aElement, aCallback) {
     // Cache the form autocomplete service for future use
     if (!this._formAutoCompleteService)
       this._formAutoCompleteService = Cc["@mozilla.org/satchel/form-autocomplete;1"].
                                       getService(Ci.nsIFormAutoComplete);
 
-    let results = this._formAutoCompleteService.autoCompleteSearch(aElement.name || aElement.id,
-                                                                   aSearchString, aElement, null);
-    let suggestions = [];
-    for (let i = 0; i < results.matchCount; i++) {
-      let value = results.getValueAt(i);
-
-      // Do not show the value if it is the current one in the input field
-      if (value == aSearchString)
-        continue;
-
-      // Supply a label and value, since they can differ for datalist suggestions
-      suggestions.push({ label: value, value: value });
-    }
-
-    return suggestions;
+    let resultsAvailable = function (results) {
+      let suggestions = [];
+      for (let i = 0; i < results.matchCount; i++) {
+        let value = results.getValueAt(i);
+
+        // Do not show the value if it is the current one in the input field
+        if (value == aSearchString)
+          continue;
+
+        // Supply a label and value, since they can differ for datalist suggestions
+        suggestions.push({ label: value, value: value });
+        aCallback(suggestions);
+      }
+    };
+
+    this._formAutoCompleteService.autoCompleteSearchAsync(aElement.name || aElement.id,
+                                                          aSearchString, aElement, null,
+                                                          resultsAvailable);
   },
 
   /**
    * (Copied from mobile/xul/chrome/content/forms.js)
    * This function is similar to getListSuggestions from
    * components/satchel/src/nsInputListAutoComplete.js but sadly this one is
    * used by the autocomplete.xml binding which is not in used in fennec
    */
@@ -4822,50 +4837,57 @@ var FormAssistant = {
         continue;
       suggestions.push({ label: label, value: item.value });
     }
 
     return suggestions;
   },
 
   // Retrieves autocomplete suggestions for an element from the form autocomplete service
-  // and sends the suggestions to the Java UI, along with element position data.
-  // Returns true if there are suggestions to show, false otherwise.
-  _showAutoCompleteSuggestions: function _showAutoCompleteSuggestions(aElement) {
-    if (!this._isAutoComplete(aElement))
-      return false;
+  // and sends the suggestions to the Java UI, along with element position data. As
+  // autocomplete queries are asynchronous, calls aCallback when done with a true
+  // argument if results were found and false if no results were found.
+  _showAutoCompleteSuggestions: function _showAutoCompleteSuggestions(aElement, aCallback) {
+    if (!this._isAutoComplete(aElement)) {
+      aCallback(false);
+      return;
+    }
 
     // Don't display the form auto-complete popup after the user starts typing
     // to avoid confusing somes IME. See bug 758820 and bug 632744.
     if (this._isBlocklisted && aElement.value.length > 0) {
-      return false;
-    }
-
-    let autoCompleteSuggestions = this._getAutoCompleteSuggestions(aElement.value, aElement);
-    let listSuggestions = this._getListSuggestions(aElement);
-
-    // On desktop, we show datalist suggestions below autocomplete suggestions,
-    // without duplicates removed.
-    let suggestions = autoCompleteSuggestions.concat(listSuggestions);
-
-    // Return false if there are no suggestions to show
-    if (!suggestions.length)
-      return false;
-
-    sendMessageToJava({
-      type:  "FormAssist:AutoComplete",
-      suggestions: suggestions,
-      rect: ElementTouchHelper.getBoundingContentRect(aElement)
-    });
-
-    // Keep track of input element so we can fill it in if the user
-    // selects an autocomplete suggestion
-    this._currentInputElement = aElement;
-
-    return true;
+      aCallback(false);
+      return;
+    }
+
+    let resultsAvailable = autoCompleteSuggestions => {
+      // On desktop, we show datalist suggestions below autocomplete suggestions,
+      // without duplicates removed.
+      let listSuggestions = this._getListSuggestions(aElement);
+      let suggestions = autoCompleteSuggestions.concat(listSuggestions);
+
+      // Return false if there are no suggestions to show
+      if (!suggestions.length) {
+        aCallback(false);
+        return;
+      }
+
+      sendMessageToJava({
+        type:  "FormAssist:AutoComplete",
+        suggestions: suggestions,
+        rect: ElementTouchHelper.getBoundingContentRect(aElement)
+      });
+
+      // Keep track of input element so we can fill it in if the user
+      // selects an autocomplete suggestion
+      this._currentInputElement = aElement;
+      aCallback(true);
+    };
+
+    this._getAutoCompleteSuggestions(aElement.value, aElement, resultsAvailable);
   },
 
   // Only show a validation message if the user submitted an invalid form,
   // there's a non-empty message string, and the element is the correct type
   _isValidateable: function _isValidateable(aElement) {
     if (!this._invalidSubmit ||
         !aElement.validationMessage ||
         !(aElement instanceof HTMLInputElement ||

--- a/mobile/android/installer/package-manifest.in
+++ b/mobile/android/installer/package-manifest.in
@@ -338,16 +338,17 @@
 @BINPATH@/components/nsContentDispatchChooser.js
 @BINPATH@/components/nsHandlerService.manifest
 @BINPATH@/components/nsHandlerService.js
 @BINPATH@/components/nsWebHandlerApp.manifest
 @BINPATH@/components/nsWebHandlerApp.js
 @BINPATH@/components/satchel.manifest
 @BINPATH@/components/nsFormAutoComplete.js
 @BINPATH@/components/nsFormHistory.js
+@BINPATH@/components/FormHistoryStartup.js
 @BINPATH@/components/nsInputListAutoComplete.js
 @BINPATH@/components/contentSecurityPolicy.manifest
 @BINPATH@/components/contentSecurityPolicy.js
 @BINPATH@/components/contentAreaDropListener.manifest
 @BINPATH@/components/contentAreaDropListener.js
 @BINPATH@/components/messageWakeupService.js
 @BINPATH@/components/messageWakeupService.manifest
 @BINPATH@/components/nsFilePicker.js

--- a/testing/specialpowers/content/specialpowersAPI.js
+++ b/testing/specialpowers/content/specialpowersAPI.js
@@ -957,26 +957,31 @@ SpecialPowersAPI.prototype = {
                  .QueryInterface(Ci.nsIInterfaceRequestor)
                  .getInterface(Ci.nsIDOMWindow)
                  .QueryInterface(Ci.nsIDOMChromeWindow);
   },
   _getAutoCompletePopup: function(window) {
     return this._getTopChromeWindow(window).document
                                            .getElementById("PopupAutoComplete");
   },
-  addAutoCompletePopupEventListener: function(window, listener) {
-    this._getAutoCompletePopup(window).addEventListener("popupshowing",
+  addAutoCompletePopupEventListener: function(window, eventname, listener) {
+    this._getAutoCompletePopup(window).addEventListener(eventname,
                                                         listener,
                                                         false);
   },
-  removeAutoCompletePopupEventListener: function(window, listener) {
-    this._getAutoCompletePopup(window).removeEventListener("popupshowing",
+  removeAutoCompletePopupEventListener: function(window, eventname, listener) {
+    this._getAutoCompletePopup(window).removeEventListener(eventname,
                                                            listener,
                                                            false);
   },
+  get formHistory() {
+    let tmp = {};
+    Cu.import("resource://gre/modules/FormHistory.jsm", tmp);
+    return wrapPrivileged(tmp.FormHistory);
+  },
   getFormFillController: function(window) {
     return Components.classes["@mozilla.org/satchel/form-fill-controller;1"]
                      .getService(Components.interfaces.nsIFormFillController);
   },
   attachFormFillControllerTo: function(window) {
     this.getFormFillController()
         .attachToBrowser(this._getDocShell(window),
                          this._getAutoCompletePopup(window));

new file mode 100644
--- /dev/null
+++ b/toolkit/components/satchel/FormHistory.jsm
@@ -0,0 +1,1089 @@
+/* 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/. */
+
+/**
+ * FormHistory
+ *
+ * Used to store values that have been entered into forms which may later
+ * be used to automatically fill in the values when the form is visited again.
+ *
+ * search(terms, queryData, callback)
+ *   Look up values that have been previously stored.
+ *     terms - array of terms to return data for
+ *     queryData - object that contains the query terms
+ *       The query object contains properties for each search criteria to match, where the value
+ *       of the property specifies the value that term must have. For example,
+ *       { term1: value1, term2: value2 }
+ *     callback - callback that is called when results are available or an error occurs.
+ *       The callback is passed a result array containing each found entry. Each element in
+ *       the array is an object containing a property for each search term specified by 'terms'.
+ * count(terms, queryData, callback)
+ *   Find the number of stored entries that match the given criteria.
+ *     queryData - array of objects that indicate the query. See the search method for details.
+ *     callback - callback that is called when results are available or an error occurs.
+ *       The callback is passed the number of found entries.
+ * update(changes, callback)
+ *    Write data to form history storage.
+ *      changes - an array of changes to be made. If only one change is to be made, it
+ *                may be passed as an object rather than a one-element array.
+ *        Each change object is of the form:
+ *          { op: operation, term1: value1, term2: value2, ... }
+ *        Valid operations are:
+ *          add - add a new entry
+ *          update - update an existing entry
+ *          remove - remove an entry
+ *          bump - update the last accessed time on an entry
+ *        The terms specified allow matching of one or more specific entries. If no terms
+ *        are specified then all entries are matched. This means that { op: "remove" } is
+ *        used to remove all entries and clear the form history.
+ *      callback - callback that is called when results have been stored.
+ * getAutoCompeteResults(searchString, params, callback)
+ *   Retrieve an array of form history values suitable for display in an autocomplete list.
+ *   Returns an mozIStoragePendingStatement that can be used to cancel the operation if
+ *   needed.
+ *     searchString - the string to search for, typically the entered value of a textbox
+ *     params - zero or more filter arguments:
+ *       fieldname - form field name
+ *       agedWeight
+ *       bucketSize
+ *       expiryDate
+ *       maxTimeGroundings
+ *       timeGroupingSize
+ *       prefixWeight
+ *       boundaryWeight
+ *     callback - callback that is called with the array of results. Each result in the array
+ *                is an object with four arguments:
+ *                  text, textLowerCase, frecency, totalScore
+ * schemaVersion
+ *   This property holds the version of the database schema
+ *
+ * Terms:
+ *  guid - entry identifier. For 'add', a guid will be generated.
+ *  fieldname - form field name
+ *  value - form value
+ *  timesUsed - the number of times the entry has been accessed
+ *  firstUsed - the time the the entry was first created
+ *  lastUsed - the time the entry was last accessed
+ *  firstUsedStart - search for entries created after or at this time
+ *  firstUsedEnd - search for entries created before or at this time
+ *  lastUsedStart - search for entries last accessed after or at this time
+ *  lastUsedEnd - search for entries last accessed before or at this time
+ *
+ * In all of the above methods, the callback argument should be an object with
+ * handleResult(result), handleFailure(error) and handleCompletion(reason) functions.
+ * For search and getAutoCompeteResults, result is an object containing the desired
+ * properties. For count, result is the integer count. For, update, handleResult is
+ * not called. For handleCompletion, reason is either 0 if successful or 1 if
+ * an error occurred.
+ */
+
+EXPORTED_SYMBOLS = [ "FormHistory" ];
+
+const Cc = Components.classes;
+const Ci = Components.interfaces;
+const Cr = Components.results;
+
+Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
+Components.utils.import("resource://gre/modules/Services.jsm");
+
+XPCOMUtils.defineLazyServiceGetter(this, "uuidService",
+                                   "@mozilla.org/uuid-generator;1",
+                                   "nsIUUIDGenerator");
+
+const DB_SCHEMA_VERSION = 4;
+const DAY_IN_MS  = 86400000; // 1 day in milliseconds
+const NOOP = function noop() {};
+
+let supportsDeletedTable =
+#ifdef ANDROID
+  true;
+#else
+  false;
+#endif
+
+let Prefs = {
+  initialized: false,
+
+  get debug() { this.ensureInitialized(); return this._debug; },
+  get enabled() { this.ensureInitialized(); return this._enabled; },
+  get expireDays() { this.ensureInitialized(); return this._expireDays; },
+
+  ensureInitialized: function() {
+    if (this.initialized)
+      return;
+
+    this.initialized = true;
+
+    this._debug = Services.prefs.getBoolPref("browser.formfill.debug");
+    this._enabled = Services.prefs.getBoolPref("browser.formfill.enable");
+    this._expireDays = Services.prefs.getIntPref("browser.formfill.expire_days");
+  }
+};
+
+function log(aMessage) {
+  if (Prefs.debug) {
+    Services.console.logStringMessage("FormHistory: " + aMessage);
+  }
+}
+
+function sendNotification(aType, aData) {
+  if (typeof aData == "string") {
+    let strWrapper = Cc["@mozilla.org/supports-string;1"].
+                     createInstance(Ci.nsISupportsString);
+    strWrapper.data = aData;
+    aData = strWrapper;
+  }
+  else if (typeof aData == "number") {
+    let intWrapper = Cc["@mozilla.org/supports-PRInt64;1"].
+                     createInstance(Ci.nsISupportsPRInt64);
+    intWrapper.data = aData;
+    aData = intWrapper;
+  }
+  else if (aData) {
+    throw Components.Exception("Invalid type " + (typeof aType) + " passed to sendNotification",
+                               Cr.NS_ERROR_ILLEGAL_VALUE);
+  }
+
+  Services.obs.notifyObservers(aData, "satchel-storage-changed", aType);
+}
+
+/**
+ * Current database schema
+ */
+
+const dbSchema = {
+  tables : {
+    moz_formhistory : {
+      "id"        : "INTEGER PRIMARY KEY",
+      "fieldname" : "TEXT NOT NULL",
+      "value"     : "TEXT NOT NULL",
+      "timesUsed" : "INTEGER",
+      "firstUsed" : "INTEGER",
+      "lastUsed"  : "INTEGER",
+      "guid"      : "TEXT",
+    },
+    moz_deleted_formhistory: {
+        "id"          : "INTEGER PRIMARY KEY",
+        "timeDeleted" : "INTEGER",
+        "guid"        : "TEXT"
+    }
+  },
+  indices : {
+    moz_formhistory_index : {
+      table   : "moz_formhistory",
+      columns : [ "fieldname" ]
+    },
+    moz_formhistory_lastused_index : {
+      table   : "moz_formhistory",
+      columns : [ "lastUsed" ]
+    },
+    moz_formhistory_guid_index : {
+      table   : "moz_formhistory",
+      columns : [ "guid" ]
+    },
+  }
+};
+
+/**
+ * Validating and processing API querying data
+ */
+
+const validFields = [
+  "fieldname",
+  "value",
+  "timesUsed",
+  "firstUsed",
+  "lastUsed",
+  "guid",
+];
+
+const searchFilters = [
+  "firstUsedStart",
+  "firstUsedEnd",
+  "lastUsedStart",
+  "lastUsedEnd",
+];
+
+function validateOpData(aData, aDataType) {
+  for (let field in aData) {
+    if (field != "op" && validFields.indexOf(field) == -1) {
+      throw Components.Exception(
+        aDataType + " query contains an unrecognized field: " + field,
+        Cr.NS_ERROR_ILLEGAL_VALUE);
+    }
+  }
+  return aData;
+}
+
+function validateSearchData(aData, aDataType) {
+  for (let field in aData) {
+    if (field != "op" && validFields.indexOf(field) == -1 && searchFilters.indexOf(field) == -1) {
+      throw Components.Exception(
+        aDataType + " query contains an unrecognized field: " + field,
+        Cr.NS_ERROR_ILLEGAL_VALUE);
+    }
+  }
+}
+
+function makeQueryPredicates(aQueryData, delimiter = ' AND ') {
+  return Object.keys(aQueryData).map(function(field) {
+    if (field == "firstUsedStart") {
+      return "firstUsed >= :" + field;
+    } else if (field == "firstUsedEnd") {
+      return "firstUsed <= :" + field;
+    } else if (field == "lastUsedStart") {
+      return "lastUsed >= :" + field;
+    } else if (field == "lastUsedEnd") {
+      return "lastUsed <= :" + field;
+    }
+    return field + " = :" + field;
+  }).join(delimiter);
+}
+
+/**
+ * Storage statement creation and parameter binding
+ */
+
+function makeCountStatement(aSearchData) {
+  let query = "SELECT COUNT(*) AS numEntries FROM moz_formhistory";
+  let queryTerms = makeQueryPredicates(aSearchData);
+  if (queryTerms) {
+    query += " WHERE " + queryTerms;
+  }
+  return dbCreateAsyncStatement(query, aSearchData);
+}
+
+function makeSearchStatement(aSearchData, aSelectTerms) {
+  let query = "SELECT " + aSelectTerms.join(", ") + " FROM moz_formhistory";
+  let queryTerms = makeQueryPredicates(aSearchData);
+  if (queryTerms) {
+    query += " WHERE " + queryTerms;
+  }
+
+  return dbCreateAsyncStatement(query, aSearchData);
+}
+
+function makeAddStatement(aNewData, aNow, aBindingArrays) {
+  let query = "INSERT INTO moz_formhistory (fieldname, value, timesUsed, firstUsed, lastUsed, guid) " +
+              "VALUES (:fieldname, :value, :timesUsed, :firstUsed, :lastUsed, :guid)";
+
+  aNewData.timesUsed = aNewData.timesUsed || 1;
+  aNewData.firstUsed = aNewData.firstUsed || aNow;
+  aNewData.lastUsed = aNewData.lastUsed || aNow;
+  return dbCreateAsyncStatement(query, aNewData, aBindingArrays);
+}
+
+function makeBumpStatement(aGuid, aNow, aBindingArrays) {
+  let query = "UPDATE moz_formhistory SET timesUsed = timesUsed + 1, lastUsed = :lastUsed WHERE guid = :guid";
+  let queryParams = {
+    lastUsed : aNow,
+    guid : aGuid,
+  };
+
+  return dbCreateAsyncStatement(query, queryParams, aBindingArrays);
+}
+
+function makeRemoveStatement(aSearchData, aBindingArrays) {
+  let query = "DELETE FROM moz_formhistory";
+  let queryTerms = makeQueryPredicates(aSearchData);
+
+  if (queryTerms) {
+    log("removeEntries");
+    query += " WHERE " + queryTerms;
+  } else {
+    log("removeAllEntries");
+    // Not specifying any fields means we should remove all entries. We
+    // won't need to modify the query in this case.
+  }
+
+  return dbCreateAsyncStatement(query, aSearchData, aBindingArrays);
+}
+
+function makeUpdateStatement(aGuid, aNewData, aBindingArrays) {
+  let query = "UPDATE moz_formhistory SET ";
+  let queryTerms = makeQueryPredicates(aNewData, ', ');
+
+  if (!queryTerms) {
+    throw Components.Exception("Update query must define fields to modify.",
+                               Cr.NS_ERROR_ILLEGAL_VALUE);
+  }
+
+  query += queryTerms + " WHERE guid = :guid";
+  aNewData["guid"] = aGuid;
+
+  return dbCreateAsyncStatement(query, aNewData, aBindingArrays);
+}
+
+function makeMoveToDeletedStatement(aGuid, aNow, aData, aBindingArrays) {
+  if (supportsDeletedTable) {
+    let query = "INSERT INTO moz_deleted_formhistory (guid, timeDeleted)";
+    let queryTerms = makeQueryPredicates(aData);
+
+    if (aGuid) {
+      query += " VALUES (:guid, :timeDeleted)";
+    } else {
+      // TODO: Add these items to the deleted items table once we've sorted
+      //       out the issues from bug 756701
+      if (!queryTerms)
+        return;
+
+      query += " SELECT guid, :timeDeleted FROM moz_formhistory WHERE " + queryTerms;
+    }
+
+    aData.timeDeleted = aNow;
+
+    return dbCreateAsyncStatement(query, aData, aBindingArrays);
+  }
+
+  return null;
+}
+
+function generateGUID() {
+  // string like: "{f60d9eac-9421-4abc-8491-8e8322b063d4}"
+  let uuid = uuidService.generateUUID().toString();
+  let raw = ""; // A string with the low bytes set to random values
+  let bytes = 0;
+  for (let i = 1; bytes < 12 ; i+= 2) {
+    // Skip dashes
+    if (uuid[i] == "-")
+      i++;
+    let hexVal = parseInt(uuid[i] + uuid[i + 1], 16);
+    raw += String.fromCharCode(hexVal);
+    bytes++;
+  }
+  return btoa(raw);
+}
+
+/**
+ * Database creation and access
+ */
+
+let _dbConnection = null;
+XPCOMUtils.defineLazyGetter(this, "dbConnection", function() {
+  let dbFile;
+
+  try {
+    dbFile = Services.dirsvc.get("ProfD", Ci.nsIFile).clone();
+    dbFile.append("formhistory.sqlite");
+    log("Opening database at " + dbFile.path);
+
+    _dbConnection = Services.storage.openUnsharedDatabase(dbFile);
+    dbInit();
+  } catch (e if e.result == Cr.NS_ERROR_FILE_CORRUPTED) {
+    dbCleanup(dbFile);
+    _dbConnection = Services.storage.openUnsharedDatabase(dbFile);
+    dbInit();
+  }
+
+  return _dbConnection;
+});
+
+
+let dbStmts = new Map();
+
+/*
+ * dbCreateAsyncStatement
+ *
+ * Creates a statement, wraps it, and then does parameter replacement
+ */
+function dbCreateAsyncStatement(aQuery, aParams, aBindingArrays) {
+  if (!aQuery)
+    return null;
+
+  let stmt = dbStmts.get(aQuery);
+  if (!stmt) {
+    log("Creating new statement for query: " + aQuery);
+    stmt = dbConnection.createAsyncStatement(aQuery);
+    dbStmts.set(aQuery, stmt);
+  }
+
+  if (aBindingArrays) {
+    let bindingArray = aBindingArrays.get(stmt);
+    if (!bindingArray) {
+      // first time using a particular statement in update
+      bindingArray = stmt.newBindingParamsArray();
+      aBindingArrays.set(stmt, bindingArray);
+    }
+
+    if (aParams) {
+      let bindingParams = bindingArray.newBindingParams();
+      for (let field in aParams) {
+        bindingParams.bindByName(field, aParams[field]);
+      }
+      bindingArray.addParams(bindingParams);
+    }
+  } else {
+    if (aParams) {
+      for (let field in aParams) {
+        stmt.params[field] = aParams[field];
+      }
+    }
+  }
+
+  return stmt;
+}
+
+/**
+ * dbInit
+ *
+ * Attempts to initialize the database. This creates the file if it doesn't
+ * exist, performs any migrations, etc.
+ */
+function dbInit() {
+  log("Initializing Database");
+
+  if (!_dbConnection.tableExists("moz_formhistory")) {
+    dbCreate();
+    return;
+  }
+
+  // When FormHistory is released, we will no longer support the various schema versions prior to
+  // this release that nsIFormHistory2 once did.
+  let version = _dbConnection.schemaVersion;
+  if (version < 3) {
+    throw Components.Exception("DB version is unsupported.",
+                               Cr.NS_ERROR_FILE_CORRUPTED);
+  } else if (version != DB_SCHEMA_VERSION) {
+    dbMigrate(version);
+  }
+}
+
+function dbCreate() {
+  log("Creating DB -- tables");
+  for (let name in dbSchema.tables) {
+    let table = dbSchema.tables[name];
+    let tSQL = [[col, table[col]].join(" ") for (col in table)].join(", ");
+    log("Creating table " + name + " with " + tSQL);
+    _dbConnection.createTable(name, tSQL);
+  }
+
+  log("Creating DB -- indices");
+  for (let name in dbSchema.indices) {
+    let index = dbSchema.indices[name];
+    let statement = "CREATE INDEX IF NOT EXISTS " + name + " ON " + index.table +
+                    "(" + index.columns.join(", ") + ")";
+    _dbConnection.executeSimpleSQL(statement);
+  }
+
+  _dbConnection.schemaVersion = DB_SCHEMA_VERSION;
+}
+
+function dbMigrate(oldVersion) {
+  log("Attempting to migrate from version " + oldVersion);
+
+  if (oldVersion > DB_SCHEMA_VERSION) {
+    log("Downgrading to version " + DB_SCHEMA_VERSION);
+    // User's DB is newer. Sanity check that our expected columns are
+    // present, and if so mark the lower version and merrily continue
+    // on. If the columns are borked, something is wrong so blow away
+    // the DB and start from scratch. [Future incompatible upgrades
+    // should switch to a different table or file.]
+
+    if (!dbAreExpectedColumnsPresent()) {
+      throw Components.Exception("DB is missing expected columns",
+                                 Cr.NS_ERROR_FILE_CORRUPTED);
+    }
+
+    // Change the stored version to the current version. If the user
+    // runs the newer code again, it will see the lower version number
+    // and re-upgrade (to fixup any entries the old code added).
+    _dbConnection.schemaVersion = DB_SCHEMA_VERSION;
+    return;
+  }
+
+  // Note that migration is currently performed synchronously.
+  _dbConnection.beginTransaction();
+
+  try {
+    for (let v = oldVersion + 1; v <= DB_SCHEMA_VERSION; v++) {
+      this.log("Upgrading to version " + v + "...");
+      Migrators["dbMigrateToVersion" + v]();
+    }
+  } catch (e) {
+    this.log("Migration failed: "  + e);
+    this.dbConnection.rollbackTransaction();
+    throw e;
+  }
+
+  _dbConnection.schemaVersion = DB_SCHEMA_VERSION;
+  _dbConnection.commitTransaction();
+
+  log("DB migration completed.");
+}
+
+var Migrators = {
+  /*
+   * Updates the DB schema to v3 (bug 506402).
+   * Adds deleted form history table.
+   */
+  dbMigrateToVersion4: function dbMigrateToVersion4() {
+    if (!_dbConnection.tableExists("moz_deleted_formhistory")) {
+      let table = dbSchema.tables["moz_deleted_formhistory"];
+      let tSQL = [[col, table[col]].join(" ") for (col in table)].join(", ");
+      _dbConnection.createTable("moz_deleted_formhistory", tSQL);
+    }
+  }
+};
+
+/**
+ * dbAreExpectedColumnsPresent
+ *
+ * Sanity check to ensure that the columns this version of the code expects
+ * are present in the DB we're using.
+ */
+function dbAreExpectedColumnsPresent() {
+  for (let name in dbSchema.tables) {
+    let table = dbSchema.tables[name];
+    let query = "SELECT " +
+                [col for (col in table)].join(", ") +
+                " FROM " + name;
+    try {
+      let stmt = _dbConnection.createStatement(query);
+      // (no need to execute statement, if it compiled we're good)
+      stmt.finalize();
+    } catch (e) {
+      return false;
+    }
+  }
+
+  log("verified that expected columns are present in DB.");
+  return true;
+}
+
+/**
+ * dbCleanup
+ *
+ * Called when database creation fails. Finalizes database statements,
+ * closes the database connection, deletes the database file.
+ */
+function dbCleanup(dbFile) {
+  log("Cleaning up DB file - close & remove & backup");
+
+  // Create backup file
+  let backupFile = dbFile.leafName + ".corrupt";
+  Services.storage.backupDatabaseFile(dbFile, backupFile);
+
+  dbClose(false);
+  dbFile.remove(false);
+}
+
+function dbClose(aShutdown) {
+  log("dbClose(" + aShutdown + ")");
+
+  if (aShutdown) {
+    sendNotification("formhistory-shutdown", null);
+  }
+
+  // Connection may never have been created if say open failed but we still
+  // end up calling dbClose as part of the rest of dbCleanup.
+  if (!_dbConnection) {
+    return;
+  }
+
+  log("dbClose finalize statements");
+  for (let stmt of dbStmts.values()) {
+    stmt.finalize();
+  }
+
+  dbStmts = new Map();
+
+  let closed = false;
+  _dbConnection.asyncClose(function () closed = true);
+
+  if (!aShutdown) {
+    let thread = Services.tm.currentThread;
+    while (!closed) {
+      thread.processNextEvent(true);
+    }
+  }
+}
+
+/**
+ * updateFormHistoryWrite
+ *
+ * Constructs and executes database statements from a pre-processed list of
+ * inputted changes.
+ */
+function updateFormHistoryWrite(aChanges, aCallbacks) {
+  log("updateFormHistoryWrite  " + aChanges.length);
+
+  // pass 'now' down so that every entry in the batch has the same timestamp
+  let now = Date.now() * 1000;
+
+  // for each change, we either create and append a new storage statement to
+  // stmts or bind a new set of parameters to an existing storage statement.
+  // stmts and bindingArrays are updated when makeXXXStatement eventually
+  // calls dbCreateAsyncStatement.
+  let stmts = [];
+  let notifications = [];
+  let bindingArrays = new Map();
+
+  for each (let change in aChanges) {
+    let operation = change.op;
+    delete change.op;
+    let stmt;
+    switch (operation) {
+      case "remove":
+        log("Remove from form history  " + change);
+        let delStmt = makeMoveToDeletedStatement(change.guid, now, change, bindingArrays);
+        if (delStmt && stmts.indexOf(delStmt) == -1)
+          stmts.push(delStmt);
+        if ("timeDeleted" in change)
+          delete change.timeDeleted;
+        stmt = makeRemoveStatement(change, bindingArrays);
+        notifications.push([ "formhistory-remove", null ]);
+        break;
+      case "update":
+        log("Update form history " + change);
+        let guid = change.guid;
+        delete change.guid;
+        stmt = makeUpdateStatement(guid, change, bindingArrays);
+        notifications.push([ "formhistory-update", guid ]);
+        break;
+      case "bump":
+        log("Bump form history " + change);
+        if (change.guid) {
+          stmt = makeBumpStatement(change.guid, now, bindingArrays);
+          notifications.push([ "formhistory-update", change.guid ]);
+        } else {
+          change.guid = generateGUID();
+          stmt = makeAddStatement(change, now, bindingArrays);
+          notifications.push([ "formhistory-add", change.guid ]);
+        }
+        break;
+      case "add":
+        log("Add to form history " + change);
+        change.guid = generateGUID();
+        stmt = makeAddStatement(change, now, bindingArrays);
+        notifications.push([ "formhistory-add", change.guid ]);
+        break;
+      default:
+        // We should've already guaranteed that change.op is one of the above
+        throw Components.Exception("Invalid operation " + operation,
+                                   Cr.NS_ERROR_ILLEGAL_VALUE);
+    }
+
+    // As identical statements are reused, only add statements if they aren't already present.
+    if (stmt && stmts.indexOf(stmt) == -1) {
+      stmts.push(stmt);
+    }
+  }
+
+  for (let stmt of stmts) {
+    stmt.bindParameters(bindingArrays.get(stmt));
+  }
+
+  let handlers = {
+    handleCompletion : function(aReason) {
+      if (aReason == Ci.mozIStorageStatementCallback.REASON_FINISHED) {
+        for (let [notification, param] of notifications) {
+          // We're either sending a GUID or nothing at all.
+          sendNotification(notification, param);
+        }
+      }
+
+      if (aCallbacks && aCallbacks.handleCompletion) {
+        aCallbacks.handleCompletion(aReason == Ci.mozIStorageStatementCallback.REASON_FINISHED ? 0 : 1);
+      }
+    },
+    handleError : function(aError) {
+      if (aCallbacks && aCallbacks.handleError) {
+        aCallbacks.handleError(aError);
+      }
+    },
+    handleResult : NOOP
+  };
+
+  dbConnection.executeAsync(stmts, stmts.length, handlers);
+}
+
+/**
+ * Functions that expire entries in form history and shrinks database
+ * afterwards as necessary initiated by expireOldEntries.
+ */
+
+/**
+ * expireOldEntriesDeletion
+ *
+ * Removes entries from database.
+ */
+function expireOldEntriesDeletion(aExpireTime, aBeginningCount) {
+  log("expireOldEntriesDeletion(" + aExpireTime + "," + aBeginningCount + ")");
+
+  FormHistory.update([
+    {
+      op: "remove",
+      lastUsedEnd : aExpireTime,
+    }], {
+      handleCompletion: function() {
+        expireOldEntriesVacuum(aExpireTime, aBeginningCount);
+      },
+      handleError: function(aError) {
+        log("expireOldEntriesDeletionFailure");
+      }
+  });
+}
+
+/**
+ * expireOldEntriesVacuum
+ *
+ * Counts number of entries removed and shrinks database as necessary.
+ */
+function expireOldEntriesVacuum(aExpireTime, aBeginningCount) {
+  FormHistory.count({}, {
+    handleResult: function(aEndingCount) {
+      if (aBeginningCount - aEndingCount > 500) {
+        log("expireOldEntriesVacuum");
+
+        let stmt = dbCreateAsyncStatement("VACUUM");
+        stmt.executeAsync({
+          handleResult : NOOP,
+          handleError : function(aError) {
+            log("expireVacuumError");
+          },
+          handleCompletion : NOOP
+        });
+      }
+
+      sendNotification("formhistory-expireoldentries", aExpireTime);
+    },
+    handleError: function(aError) {
+      log("expireEndCountFailure");
+    }
+  });
+}
+
+const FormHistory = {
+  search : function formHistorySearch(aSelectTerms, aSearchData, aCallbacks) {
+    // if no terms selected, select everything
+    aSelectTerms = (aSelectTerms) ?  aSelectTerms : validFields;
+    validateSearchData(aSearchData, "Search");
+
+    let stmt = makeSearchStatement(aSearchData, aSelectTerms);
+
+    let handlers = {
+      handleResult : function(aResultSet) {
+        let formHistoryFields = dbSchema.tables.moz_formhistory;
+        for (let row = aResultSet.getNextRow(); row; row = aResultSet.getNextRow()) {
+          let result = {};
+          for each (let field in aSelectTerms) {
+            result[field] = row.getResultByName(field);
+          }
+
+          if (aCallbacks && aCallbacks.handleResult) {
+            aCallbacks.handleResult(result);
+          }
+        }
+      },
+
+      handleError : function(aError) {
+        if (aCallbacks && aCallbacks.handleError) {
+          aCallbacks.handleError(aError);
+        }
+      },
+
+      handleCompletion : function searchCompletionHandler(aReason) {
+        if (aCallbacks && aCallbacks.handleCompletion) {
+          aCallbacks.handleCompletion(aReason == Ci.mozIStorageStatementCallback.REASON_FINISHED ? 0 : 1);
+        }
+      }
+    };
+
+    stmt.executeAsync(handlers);
+  },
+
+  count : function formHistoryCount(aSearchData, aCallbacks) {
+    validateSearchData(aSearchData, "Count");
+    let stmt = makeCountStatement(aSearchData);
+    let handlers = {
+      handleResult : function countResultHandler(aResultSet) {
+        let row = aResultSet.getNextRow();
+        let count = row.getResultByName("numEntries");
+        if (aCallbacks && aCallbacks.handleResult) {
+          aCallbacks.handleResult(count);
+        }
+      },
+
+      handleError : function(aError) {
+        if (aCallbacks && aCallbacks.handleError) {
+          aCallbacks.handleError(aError);
+        }
+      },
+
+      handleCompletion : function searchCompletionHandler(aReason) {
+        if (aCallbacks && aCallbacks.handleCompletion) {
+          aCallbacks.handleCompletion(aReason == Ci.mozIStorageStatementCallback.REASON_FINISHED ? 0 : 1);
+        }
+      }
+    };
+
+    stmt.executeAsync(handlers);
+  },
+
+  update : function formHistoryUpdate(aChanges, aCallbacks) {
+    if (!Prefs.enabled) {
+      return;
+    }
+
+    // Used to keep track of how many searches have been started. When that number
+    // are finished, updateFormHistoryWrite can be called.
+    let numSearches = 0;
+    let completedSearches = 0;
+    let searchFailed = false;
+
+    function validIdentifier(change) {
+      // The identifier is only valid if one of either the guid or the (fieldname/value) are set
+      return Boolean(change.guid) != Boolean(change.fieldname && change.value);
+    }
+
+    if (!("length" in aChanges))
+      aChanges = [aChanges];
+
+    for each (let change in aChanges) {
+      switch (change.op) {
+        case "remove":
+          validateSearchData(change, "Remove");
+          continue;
+        case "update":
+          if (validIdentifier(change)) {
+            validateOpData(change, "Update");
+            if (change.guid) {
+              continue;
+            }
+          } else {
+            throw Components.Exception(
+              "update op='update' does not correctly reference a entry.",
+              Cr.NS_ERROR_ILLEGAL_VALUE);
+          }
+          break;
+        case "bump":
+          if (validIdentifier(change)) {
+            validateOpData(change, "Bump");
+            if (change.guid) {
+              continue;
+            }
+          } else {
+            throw Components.Exception(
+              "update op='bump' does not correctly reference a entry.",
+              Cr.NS_ERROR_ILLEGAL_VALUE);
+          }
+          break;
+        case "add":
+          if (change.guid) {
+            throw Components.Exception(
+              "op='add' cannot contain field 'guid'. Either use op='update' " +
+                "explicitly or make 'guid' undefined.",
+              Cr.NS_ERROR_ILLEGAL_VALUE);
+          } else if (change.fieldname && change.value) {
+            validateOpData(change, "Add");
+          }
+          break;
+        default:
+          throw Components.Exception(
+            "update does not recognize op='" + change.op + "'",
+            Cr.NS_ERROR_ILLEGAL_VALUE);
+      }
+
+      numSearches++;
+      FormHistory.search(
+        [ "guid" ],
+        {
+          fieldname : change.fieldname,
+          value : change.value
+        }, {
+          foundResult : false,
+          handleResult : function(aResult) {
+            if (this.foundResult) {
+              log("Database contains multiple entries with the same fieldname/value pair.");
+              if (aCallbacks && aCallbacks.handleError) {
+                aCallbacks.handleError({
+                  message :
+                    "Database contains multiple entries with the same fieldname/value pair.",
+                  result : 19 // Constraint violation
+                });
+              }
+
+              searchFailed = true;
+              return;
+            }
+
+            this.foundResult = true;
+            change.guid = aResult["guid"];
+          },
+
+          handleError : function(aError) {
+            if (aCallbacks && aCallbacks.handleError) {
+              aCallbacks.handleError(aError);
+            }
+          },
+
+          handleCompletion : function(aReason) {
+            completedSearches++;
+            if (completedSearches == numSearches) {
+              if (!aReason && !searchFailed) {
+                updateFormHistoryWrite(aChanges, aCallbacks);
+              }
+              else if (aCallbacks && aCallbacks.handleCompletion) {
+                aCallbacks.handleCompletion(1);
+              }
+            }
+          }
+        });
+    }
+
+    if (numSearches == 0) {
+      // We don't have to wait for any statements to return.
+      updateFormHistoryWrite(aChanges, aCallbacks);
+    }
+  },
+
+  getAutoCompleteResults: function getAutoCompleteResults(searchString, params, aCallbacks) {
+    // only do substring matching when the search string contains more than one character
+    let searchTokens;
+    let where = ""
+    let boundaryCalc = "";
+    if (searchString.length > 1) {
+        searchTokens = searchString.split(/\s+/);
+
+        // build up the word boundary and prefix match bonus calculation
+        boundaryCalc = "MAX(1, :prefixWeight * (value LIKE :valuePrefix ESCAPE '/') + (";
+        // for each word, calculate word boundary weights for the SELECT clause and
+        // add word to the WHERE clause of the query
+        let tokenCalc = [];
+        for (let i = 0; i < searchTokens.length; i++) {
+            tokenCalc.push("(value LIKE :tokenBegin" + i + " ESCAPE '/') + " +
+                            "(value LIKE :tokenBoundary" + i + " ESCAPE '/')");
+            where += "AND (value LIKE :tokenContains" + i + " ESCAPE '/') ";
+        }
+        // add more weight if we have a traditional prefix match and
+        // multiply boundary bonuses by boundary weight
+        boundaryCalc += tokenCalc.join(" + ") + ") * :boundaryWeight)";
+    } else if (searchString.length == 1) {
+        where = "AND (value LIKE :valuePrefix ESCAPE '/') ";
+        boundaryCalc = "1";
+        delete params.prefixWeight;
+        delete params.boundaryWeight;
+    } else {
+        where = "";
+        boundaryCalc = "1";
+        delete params.prefixWeight;
+        delete params.boundaryWeight;
+    }
+
+    params.now = Date.now() * 1000; // convert from ms to microseconds
+
+    /* Three factors in the frecency calculation for an entry (in order of use in calculation):
+     * 1) average number of times used - items used more are ranked higher
+     * 2) how recently it was last used - items used recently are ranked higher
+     * 3) additional weight for aged entries surviving expiry - these entries are relevant
+     *    since they have been used multiple times over a large time span so rank them higher
+     * The score is then divided by the bucket size and we round the result so that entries
+     * with a very similar frecency are bucketed together with an alphabetical sort. This is
+     * to reduce the amount of moving around by entries while typing.
+     */
+
+    let query = "/* do not warn (bug 496471): can't use an index */ " +
+                "SELECT value, " +
+                "ROUND( " +
+                    "timesUsed / MAX(1.0, (lastUsed - firstUsed) / :timeGroupingSize) * " +
+                    "MAX(1.0, :maxTimeGroupings - (:now - lastUsed) / :timeGroupingSize) * "+
+                    "MAX(1.0, :agedWeight * (firstUsed < :expiryDate)) / " +
+                    ":bucketSize "+
+                ", 3) AS frecency, " +
+                boundaryCalc + " AS boundaryBonuses " +
+                "FROM moz_formhistory " +
+                "WHERE fieldname=:fieldname " + where +
+                "ORDER BY ROUND(frecency * boundaryBonuses) DESC, UPPER(value) ASC";
+
+    let stmt = dbCreateAsyncStatement(query, params);
+
+    // Chicken and egg problem: Need the statement to escape the params we
+    // pass to the function that gives us the statement. So, fix it up now.
+    if (searchString.length >= 1)
+      stmt.params.valuePrefix = stmt.escapeStringForLIKE(searchString, "/") + "%";
+    if (searchString.length > 1) {
+      for (let i = 0; i < searchTokens.length; i++) {
+        let escapedToken = stmt.escapeStringForLIKE(searchTokens[i], "/");
+        stmt.params["tokenBegin" + i] = escapedToken + "%";
+        stmt.params["tokenBoundary" + i] =  "% " + escapedToken + "%";
+        stmt.params["tokenContains" + i] = "%" + escapedToken + "%";
+      }
+    } else {
+      // no additional params need to be substituted into the query when the
+      // length is zero or one
+    }
+
+    let pending = stmt.executeAsync({
+      handleResult : function (aResultSet) {
+        for (let row = aResultSet.getNextRow(); row; row = aResultSet.getNextRow()) {
+          let value = row.getResultByName("value");
+          let frecency = row.getResultByName("frecency");
+          let entry = {
+            text :          value,
+            textLowerCase : value.toLowerCase(),
+            frecency :      frecency,
+            totalScore :    Math.round(frecency * row.getResultByName("boundaryBonuses"))
+          };
+          if (aCallbacks && aCallbacks.handleResult) {
+            aCallbacks.handleResult(entry);
+          }
+        }
+      },
+
+      handleError : function (aError) {
+        if (aCallbacks && aCallbacks.handleError) {
+          aCallbacks.handleError(aError);
+        }
+      },
+
+      handleCompletion : function (aReason) {
+        if (aCallbacks && aCallbacks.handleCompletion) {
+          aCallbacks.handleCompletion(aReason == Ci.mozIStorageStatementCallback.REASON_FINISHED ? 0 : 1);
+        }
+      }
+    });
+    return pending;
+  },
+
+  get schemaVersion() {
+    return dbConnection.schemaVersion;
+  },
+
+  // This is used only so that the test can verify deleted table support.
+  get _supportsDeletedTable() {
+    return supportsDeletedTable;
+  },
+  set _supportsDeletedTable(val) {
+    supportsDeletedTable = val;
+  },
+
+  // The remaining methods are called by FormHistoryStartup.js
+  updatePrefs: function updatePrefs() {
+    Prefs.initialized = false;
+  },
+
+  expireOldEntries: function expireOldEntries() {
+    log("expireOldEntries");
+
+    // Determine how many days of history we're supposed to keep.
+    // Calculate expireTime in microseconds
+    let expireTime = (Date.now() - Prefs.expireDays * DAY_IN_MS) * 1000;
+
+    sendNotification("formhistory-beforeexpireoldentries", expireTime);
+
+    FormHistory.count({}, {
+      handleResult: function(aBeginningCount) {
+        expireOldEntriesDeletion(expireTime, aBeginningCount);
+      },
+      handleError: function(aError) {
+        log("expireStartCountFailure");
+      }
+    });
+  },
+
+  shutdown: function shutdown() { dbClose(true); }
+};
+
+// Prevent add-ons from redefining this API
+Object.freeze(FormHistory);

new file mode 100644
--- /dev/null
+++ b/toolkit/components/satchel/FormHistoryStartup.js
@@ -0,0 +1,78 @@
+/* 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/. */
+
+const Cc = Components.classes;
+const Ci = Components.interfaces;
+
+Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
+Components.utils.import("resource://gre/modules/Services.jsm");
+
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+                                  "resource://gre/modules/FormHistory.jsm");
+
+function FormHistoryStartup() { }
+
+FormHistoryStartup.prototype = {
+  classID: Components.ID("{3A0012EB-007F-4BB8-AA81-A07385F77A25}"),
+
+  QueryInterface: XPCOMUtils.generateQI([
+    Ci.nsIObserver,
+    Ci.nsISupportsWeakReference,
+    Ci.nsIFrameMessageListener
+  ]),
+
+  observe: function(subject, topic, data) {
+    switch (topic) {
+      case "nsPref:changed":
+        FormHistory.updatePrefs();
+        break;
+      case "idle-daily":
+      case "formhistory-expire-now":
+        FormHistory.expireOldEntries();
+        break;
+      case "profile-before-change":
+        FormHistory.shutdown();
+        break;
+      case "profile-after-change":
+        this.init();
+      default:
+        break;
+    }
+  },
+
+  inited: false,
+
+  init: function()
+  {
+    if (this.inited)
+      return;
+    this.inited = true;
+
+    Services.prefs.addObserver("browser.formfill.", this, true);
+
+    // triggers needed service cleanup and db shutdown
+    Services.obs.addObserver(this, "profile-before-change", true);
+    Services.obs.addObserver(this, "formhistory-expire-now", true);
+
+    let messageManager = Cc["@mozilla.org/globalmessagemanager;1"].
+                         getService(Ci.nsIMessageListenerManager);
+    messageManager.loadFrameScript("chrome://satchel/content/formSubmitListener.js", true);
+    messageManager.addMessageListener("FormHistory:FormSubmitEntries", this);
+  },
+
+  receiveMessage: function(message) {
+    let entries = message.json;
+    let changes = entries.map(function(entry) {
+      return {
+        op : "bump",
+        fieldname : entry.name,
+        value : entry.value,
+      }
+    });
+
+    FormHistory.update(changes);
+  }
+};
+
+this.NSGetFactory = XPCOMUtils.generateNSGetFactory([FormHistoryStartup]);

--- a/toolkit/components/satchel/Makefile.in
+++ b/toolkit/components/satchel/Makefile.in
@@ -20,21 +20,26 @@ LOCAL_INCLUDES = \
   $(NULL)
 
 CPPSRCS = \
   nsFormFillController.cpp \
   $(NULL)
 
 EXTRA_COMPONENTS = \
   nsFormAutoComplete.js \
+  FormHistoryStartup.js \
   nsInputListAutoComplete.js \
   satchel.manifest \
   $(NULL)
 
 EXTRA_PP_COMPONENTS = \
 	nsFormHistory.js \
 	$(NULL)
 
 EXTRA_JS_MODULES = \
   nsFormAutoCompleteResult.jsm \
   $(NULL)
 
+EXTRA_PP_JS_MODULES = \
+  FormHistory.jsm \
+	$(NULL)
+
 include $(topsrcdir)/config/rules.mk

--- a/toolkit/components/satchel/nsFormAutoComplete.js
+++ b/toolkit/components/satchel/nsFormAutoComplete.js
@@ -5,60 +5,60 @@
 
 const Cc = Components.classes;
 const Ci = Components.interfaces;
 const Cr = Components.results;
 
 Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
 Components.utils.import("resource://gre/modules/Services.jsm");
 
+XPCOMUtils.defineLazyModuleGetter(this, "Deprecated",
+                                  "resource://gre/modules/Deprecated.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "FormHistory",
+                                  "resource://gre/modules/FormHistory.jsm");
+
 function FormAutoComplete() {
     this.init();
 }
 
 FormAutoComplete.prototype = {
     classID          : Components.ID("{c11c21b2-71c9-4f87-a0f8-5e13f50495fd}"),
     QueryInterface   : XPCOMUtils.generateQI([Ci.nsIFormAutoComplete, Ci.nsISupportsWeakReference]),
 
-    __formHistory : null,
-    get _formHistory() {
-        if (!this.__formHistory)
-            this.__formHistory = Cc["@mozilla.org/satchel/form-history;1"].
-                                 getService(Ci.nsIFormHistory2);
-        return this.__formHistory;
-    },
-
     _prefBranch         : null,
     _debug              : true, // mirrors browser.formfill.debug
     _enabled            : true, // mirrors browser.formfill.enable preference
     _agedWeight         : 2,
     _bucketSize         : 1,
     _maxTimeGroupings   : 25,
     _timeGroupingSize   : 7 * 24 * 60 * 60 * 1000 * 1000,
     _expireDays         : null,
     _boundaryWeight     : 25,
     _prefixWeight       : 5,
 
+    // Only one query is performed at a time, which will be stored in _pendingQuery
+    // while the query is being performed. It will be cleared when the query finishes,
+    // is cancelled, or an error occurs. If a new query occurs while one is already
+    // pending, the existing one is cancelled. The pending query will be an
+    // mozIStoragePendingStatement object.
+    _pendingQuery       : null,
+
     init : function() {
         // Preferences. Add observer so we get notified of changes.
         this._prefBranch = Services.prefs.getBranch("browser.formfill.");
         this._prefBranch.addObserver("", this.observer, true);
         this.observer._self = this;
 
         this._debug            = this._prefBranch.getBoolPref("debug");
         this._enabled          = this._prefBranch.getBoolPref("enable");
         this._agedWeight       = this._prefBranch.getIntPref("agedWeight");
         this._bucketSize       = this._prefBranch.getIntPref("bucketSize");
         this._maxTimeGroupings = this._prefBranch.getIntPref("maxTimeGroupings");
         this._timeGroupingSize = this._prefBranch.getIntPref("timeGroupingSize") * 1000 * 1000;
         this._expireDays       = this._prefBranch.getIntPref("expire_days");
-
-        this._dbStmts = {};
-
-        Services.obs.addObserver(this.observer, "profile-before-change", true);
     },
 
     observer : {
         _self : null,
 
         QueryInterface : XPCOMUtils.generateQI([Ci.nsIObserver,
                                                 Ci.nsISupportsWeakReference]),
 
@@ -91,22 +91,16 @@ FormAutoComplete.prototype = {
                         self._boundaryWeight = self._prefBranch.getIntPref(prefName);
                         break;
                     case "prefixWeight":
                         self._prefixWeight = self._prefBranch.getIntPref(prefName);
                         break;
                     default:
                         self.log("Oops! Pref not handled, change ignored.");
                 }
-            } else if (topic == "profile-before-change") {
-                for each (let stmt in self._dbStmts) {
-                    stmt.finalize();
-                }
-                self._dbStmts = {};
-                self.__formHistory = null;
             }
         }
     },
 
 
     /*
      * log
      *
@@ -116,43 +110,74 @@ FormAutoComplete.prototype = {
     log : function (message) {
         if (!this._debug)
             return;
         dump("FormAutoComplete: " + message + "\n");
         Services.console.logStringMessage("FormAutoComplete: " + message);
     },
 
 
+    autoCompleteSearch : function (aInputName, aUntrimmedSearchString, aField, aPreviousResult) {
+      Deprecated.warning("nsIFormAutoComplete::autoCompleteSearch is deprecated", "https://bugzilla.mozilla.org/show_bug.cgi?id=697377");
+
+      let result = null;
+      let listener = {
+        onSearchCompletion: function (r) result = r
+      };
+      this._autoCompleteSearchShared(aInputName, aUntrimmedSearchString, aField, aPreviousResult, listener);
+
+      // Just wait for the result to to be available.
+      let thread = Components.classes["@mozilla.org/thread-manager;1"].getService().currentThread;
+      while (!result && this._pendingQuery) {
+        thread.processNextEvent(true);
+      }
+
+      return result;
+    },
+
+    autoCompleteSearchAsync : function (aInputName, aUntrimmedSearchString, aField, aPreviousResult, aListener) {
+      this._autoCompleteSearchShared(aInputName, aUntrimmedSearchString, aField, aPreviousResult, aListener);
+    },
+
     /*
-     * autoCompleteSearch
+     * autoCompleteSearchShared
      *
      * aInputName    -- |name| attribute from the form input being autocompleted.
      * aUntrimmedSearchString -- current value of the input
      * aField -- nsIDOMHTMLInputElement being autocompleted (may be null if from chrome)
      * aPreviousResult -- previous search result, if any.
-     *
-     * Returns: an nsIAutoCompleteResult
+     * aListener -- nsIFormAutoCompleteObserver that listens for the nsIAutoCompleteResult
+     *              that may be returned asynchronously.
      */
-    autoCompleteSearch : function (aInputName, aUntrimmedSearchString, aField, aPreviousResult) {
+    _autoCompleteSearchShared : function (aInputName, aUntrimmedSearchString, aField, aPreviousResult, aListener) {
         function sortBytotalScore (a, b) {
             return b.totalScore - a.totalScore;
         }
 
-        if (!this._enabled)
-            return null;
+        let result = null;
+        if (!this._enabled) {
+            result = new FormAutoCompleteResult(FormHistory, [], aInputName, aUntrimmedSearchString);
+            if (aListener) {
+              aListener.onSearchCompletion(result);
+            }
+            return;
+        }
 
         // don't allow form inputs (aField != null) to get results from search bar history
         if (aInputName == 'searchbar-history' && aField) {
             this.log('autoCompleteSearch for input name "' + aInputName + '" is denied');
-            return null;
+            result = new FormAutoCompleteResult(FormHistory, [], aInputName, aUntrimmedSearchString);
+            if (aListener) {
+              aListener.onSearchCompletion(result);
+            }
+            return;
         }
 
         this.log("AutoCompleteSearch invoked. Search is: " + aUntrimmedSearchString);
         let searchString = aUntrimmedSearchString.trim().toLowerCase();
-        let result = null;
 
         // reuse previous results if:
         // a) length greater than one character (others searches are special cases) AND
         // b) the the new results will be a subset of the previous results
         if (aPreviousResult && aPreviousResult.searchString.trim().length > 1 &&
             searchString.indexOf(aPreviousResult.searchString.trim().toLowerCase()) >= 0) {
             this.log("Using previous autocomplete result");
             result = aPreviousResult;
@@ -171,155 +196,90 @@ FormAutoComplete.prototype = {
                     continue;
                 this._calculateScore(entry, searchString, searchTokens);
                 this.log("Reusing autocomplete entry '" + entry.text +
                          "' (" + entry.frecency +" / " + entry.totalScore + ")");
                 filteredEntries.push(entry);
             }
             filteredEntries.sort(sortBytotalScore);
             result.wrappedJSObject.entries = filteredEntries;
+
+            if (aListener) {
+              aListener.onSearchCompletion(result);
+            }
         } else {
             this.log("Creating new autocomplete search result.");
-            let entries = this.getAutoCompleteValues(aInputName, searchString);
-            result = new FormAutoCompleteResult(this._formHistory, entries, aInputName, aUntrimmedSearchString);
-            if (aField && aField.maxLength > -1) {
-                let original = result.wrappedJSObject.entries;
-                let filtered = original.filter(function (el) el.text.length <= this.maxLength, aField);
-                result.wrappedJSObject.entries = filtered;
+
+            // Start with an empty list.
+            result = new FormAutoCompleteResult(FormHistory, [], aInputName, aUntrimmedSearchString);
+
+            let processEntry = function(aEntries) {
+              if (aField && aField.maxLength > -1) {
+                result.entries =
+                  aEntries.filter(function (el) { return el.text.length <= aField.maxLength; });
+              } else {
+                result.entries = aEntries;
+              }
+
+              if (aListener) {
+                aListener.onSearchCompletion(result);
+              }
             }
+
+            this.getAutoCompleteValues(aInputName, searchString, processEntry);
         }
-
-        return result;
     },
 
-    getAutoCompleteValues : function (fieldName, searchString) {
-        let values = [];
-        let searchTokens;
+    stopAutoCompleteSearch : function () {
+        if (this._pendingQuery) {
+            this._pendingQuery.cancel();
+            this._pendingQuery = null;
+        }
+    },
 
+    /*
+     * Get the values for an autocomplete list given a search string.
+     *
+     *  fieldName - fieldname field within form history (the form input name)
+     *  searchString - string to search for
+     *  callback - called when the values are available. Passed an array of objects,
+     *             containing properties for each result. The callback is only called
+     *             when successful.
+     */
+    getAutoCompleteValues : function (fieldName, searchString, callback) {
         let params = {
             agedWeight:         this._agedWeight,
             bucketSize:         this._bucketSize,
             expiryDate:         1000 * (Date.now() - this._expireDays * 24 * 60 * 60 * 1000),
             fieldname:          fieldName,
             maxTimeGroupings:   this._maxTimeGroupings,
-            now:                Date.now() * 1000,          // convert from ms to microseconds
-            timeGroupingSize:   this._timeGroupingSize
+            timeGroupingSize:   this._timeGroupingSize,
+            prefixWeight:       this._prefixWeight,
+            boundaryWeight:     this._boundaryWeight
         }
 
-        // only do substring matching when more than one character is typed
-        let where = ""
-        let boundaryCalc = "";
-        if (searchString.length > 1) {
-            searchTokens = searchString.split(/\s+/);
-
-            // build up the word boundary and prefix match bonus calculation
-            boundaryCalc = "MAX(1, :prefixWeight * (value LIKE :valuePrefix ESCAPE '/') + (";
-            // for each word, calculate word boundary weights for the SELECT clause and
-            // add word to the WHERE clause of the query
-            let tokenCalc = [];
-            for (let i = 0; i < searchTokens.length; i++) {
-                tokenCalc.push("(value LIKE :tokenBegin" + i + " ESCAPE '/') + " +
-                                "(value LIKE :tokenBoundary" + i + " ESCAPE '/')");
-                where += "AND (value LIKE :tokenContains" + i + " ESCAPE '/') ";
-            }
-            // add more weight if we have a traditional prefix match and
-            // multiply boundary bonuses by boundary weight
-            boundaryCalc += tokenCalc.join(" + ") + ") * :boundaryWeight)";
-            params.prefixWeight = this._prefixWeight;
-            params.boundaryWeight = this._boundaryWeight;
-        } else if (searchString.length == 1) {
-            where = "AND (value LIKE :valuePrefix ESCAPE '/') ";
-            boundaryCalc = "1";
-        } else {
-            where = "";
-            boundaryCalc = "1";
-        }
-        /* Three factors in the frecency calculation for an entry (in order of use in calculation):
-         * 1) average number of times used - items used more are ranked higher
-         * 2) how recently it was last used - items used recently are ranked higher
-         * 3) additional weight for aged entries surviving expiry - these entries are relevant
-         *    since they have been used multiple times over a large time span so rank them higher
-         * The score is then divided by the bucket size and we round the result so that entries
-         * with a very similar frecency are bucketed together with an alphabetical sort. This is
-         * to reduce the amount of moving around by entries while typing.
-         */
-
-        let query = "/* do not warn (bug 496471): can't use an index */ " +
-                    "SELECT value, " +
-                    "ROUND( " +
-                        "timesUsed / MAX(1.0, (lastUsed - firstUsed) / :timeGroupingSize) * " +
-                        "MAX(1.0, :maxTimeGroupings - (:now - lastUsed) / :timeGroupingSize) * "+
-                        "MAX(1.0, :agedWeight * (firstUsed < :expiryDate)) / " +
-                        ":bucketSize "+
-                    ", 3) AS frecency, " +
-                    boundaryCalc + " AS boundaryBonuses " +
-                    "FROM moz_formhistory " +
-                    "WHERE fieldname=:fieldname " + where +
-                    "ORDER BY ROUND(frecency * boundaryBonuses) DESC, UPPER(value) ASC";
-
-        let stmt;
-        try {
-            stmt = this._dbCreateStatement(query, params);
+        this.stopAutoCompleteSearch();
 
-            // Chicken and egg problem: Need the statement to escape the params we
-            // pass to the function that gives us the statement. So, fix it up now.
-            if (searchString.length >= 1)
-                stmt.params.valuePrefix = stmt.escapeStringForLIKE(searchString, "/") + "%";
-            if (searchString.length > 1) {
-                for (let i = 0; i < searchTokens.length; i++) {
-                    let escapedToken = stmt.escapeStringForLIKE(searchTokens[i], "/");
-                    stmt.params["tokenBegin" + i] = escapedToken + "%";
-                    stmt.params["tokenBoundary" + i] =  "% " + escapedToken + "%";
-                    stmt.params["tokenContains" + i] = "%" + escapedToken + "%";
-                }
-            } else {
-                // no addional params need to be substituted into the query when the
-                // length is zero or one
+        let results = [];
+        let processResults = {
+          handleResult: aResult => {
+            results.push(aResult);
+          },
+          handleError: aError => {
+            this.log("getAutocompleteValues failed: " + aError.message);
+          },
+          handleCompletion: aReason => {
+            this._pendingQuery = null;
+            if (!aReason) {
+              callback(results);
             }
-
-            while (stmt.executeStep()) {
-                let entry = {
-                    text:           stmt.row.value,
-                    textLowerCase:  stmt.row.value.toLowerCase(),
-                    frecency:       stmt.row.frecency,
-                    totalScore:     Math.round(stmt.row.frecency * stmt.row.boundaryBonuses)
-                }
-                values.push(entry);
-            }
+          }
+        };
 
-        } catch (e) {
-            this.log("getValues failed: " + e.name + " : " + e.message);
-            throw "DB failed getting form autocomplete values";
-        } finally {
-            if (stmt) {
-                stmt.reset();
-            }
-        }
-
-        return values;
-    },
-
-
-    _dbStmts      : null,
-
-    _dbCreateStatement : function (query, params) {
-        let stmt = this._dbStmts[query];
-        // Memoize the statements
-        if (!stmt) {
-            this.log("Creating new statement for query: " + query);
-            stmt = this._formHistory.DBConnection.createStatement(query);
-            this._dbStmts[query] = stmt;
-        }
-        // Replace parameters, must be done 1 at a time
-        if (params) {
-            let stmtparams = stmt.params;
-            for (let i in params)
-                stmtparams[i] = params[i];
-        }
-        return stmt;
+        this._pendingQuery = FormHistory.getAutoCompleteResults(searchString, params, processResults);
     },
 
     /*
      * _calculateScore
      *
      * entry    -- an nsIAutoCompleteResult entry
      * aSearchString -- current value of the input (lowercase)
      * searchTokens -- array of tokens of the search string
@@ -417,15 +377,18 @@ FormAutoCompleteResult.prototype = {
         return "";
     },
 
     removeValueAt : function (index, removeFromDB) {
         this._checkIndexBounds(index);
 
         let [removedEntry] = this.entries.splice(index, 1);
 
-        if (removeFromDB)
-            this.formHistory.removeEntry(this.fieldName, removedEntry.text);
+        if (removeFromDB) {
+          this.formHistory.update({ op: "remove",
+                                    fieldname: this.fieldName,
+                                    value: removedEntry.text });
+        }
     }
 };
 
 let component = [FormAutoComplete];
 this.NSGetFactory = XPCOMUtils.generateNSGetFactory(component);