--- a/browser/components/places/tests/unit/test_browserGlue_prefs.js
+++ b/browser/components/places/tests/unit/test_browserGlue_prefs.js
@@ -17,17 +17,17 @@ const TOPICDATA_FORCE_PLACES_INIT = "for
 let bg = Cc["@mozilla.org/browser/browserglue;1"].
          getService(Ci.nsIBrowserGlue);
 
 function waitForImportAndSmartBookmarks(aCallback) {
   Services.obs.addObserver(function waitImport() {
     Services.obs.removeObserver(waitImport, "bookmarks-restore-success");
     // Delay to test eventual smart bookmarks creation.
     do_execute_soon(function () {
-      waitForAsyncUpdates(aCallback);
+      promiseAsyncUpdates().then(aCallback);
     });
   }, "bookmarks-restore-success", false);
 }
 
 let gTests = [
 
   // This test must be the first one.
   function test_checkPreferences() {

--- a/browser/components/places/tests/unit/test_browserGlue_smartBookmarks.js
+++ b/browser/components/places/tests/unit/test_browserGlue_smartBookmarks.js
@@ -335,12 +335,12 @@ function run_test() {
   waitForImportAndSmartBookmarks(next_test);
 }
 
 function waitForImportAndSmartBookmarks(aCallback) {
   Services.obs.addObserver(function waitImport() {
     Services.obs.removeObserver(waitImport, "bookmarks-restore-success");
     // Delay to test eventual smart bookmarks creation.
     do_execute_soon(function () {
-      waitForAsyncUpdates(aCallback);
+      promiseAsyncUpdates().then(aCallback);
     });
   }, "bookmarks-restore-success", false);
 }

--- a/toolkit/components/places/tests/autocomplete/head_autocomplete.js
+++ b/toolkit/components/places/tests/autocomplete/head_autocomplete.js
@@ -252,17 +252,17 @@ function run_test() {
 
   // Do an extra function if necessary
   if (func)
     func();
 
   // At this point frecency could still be updating due to latest pages updates.
   // This is not a problem in real life, but autocomplete tests should return
   // reliable resultsets, thus we have to wait.
-  waitForAsyncUpdates(ensure_results, this, [search, expected]);
+  promiseAsyncUpdates().then(function () ensure_results(search, expected));
 }
 
 // Utility function to remove history pages
 function removePages(aURIs)
 {
   for each (let uri in aURIs)
     histsvc.removePage(toURI(kURIs[uri]));
 }

--- a/toolkit/components/places/tests/bookmarks/test_keywords.js
+++ b/toolkit/components/places/tests/bookmarks/test_keywords.js
@@ -64,34 +64,34 @@ add_test(function test_addBookmarkWithKe
     PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                          URIS[0],
                                          PlacesUtils.bookmarks.DEFAULT_INDEX,
                                          "test");
   PlacesUtils.bookmarks.setKeywordForBookmark(itemId, "keyword");
   check_bookmark_keyword(itemId, "keyword");
   check_uri_keyword(URIS[0], "keyword");
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     check_orphans();
     run_next_test();
   });
 });
 
 add_test(function test_addBookmarkToURIHavingKeyword()
 {
   let itemId =
     PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                          URIS[0],
                                          PlacesUtils.bookmarks.DEFAULT_INDEX,
                                          "test");
   // The uri has a keyword, but this specific bookmark has not.
   check_bookmark_keyword(itemId, null);
   check_uri_keyword(URIS[0], "keyword");
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     check_orphans();
     run_next_test();
   });
 });
 
 add_test(function test_addSameKeywordToOtherURI()
 {
   let itemId =
@@ -107,17 +107,17 @@ add_test(function test_addSameKeywordToO
   check_uri_keyword(URIS[1], "kEyWoRd");
 
   // Check case insensitivity.
   check_uri_keyword(URIS[0], "kEyWoRd");
   check_bookmark_keyword(itemId, "keyword");
   check_uri_keyword(URIS[1], "keyword");
   check_uri_keyword(URIS[0], "keyword");
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     check_orphans();
     run_next_test();
   });
 });
 
 add_test(function test_removeBookmarkWithKeyword()
 {
   let itemId =
@@ -130,31 +130,31 @@ add_test(function test_removeBookmarkWit
   check_uri_keyword(URIS[1], "keyword");
 
   // The keyword should not be removed from other bookmarks.
   PlacesUtils.bookmarks.removeItem(itemId);
 
   check_uri_keyword(URIS[1], "keyword");
   check_uri_keyword(URIS[0], "keyword");
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     check_orphans();
     run_next_test();
   });
 });
 
 add_test(function test_removeFolderWithKeywordedBookmarks()
 {
   // Keyword should be removed as well.
   PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.unfiledBookmarksFolderId);
 
   check_uri_keyword(URIS[1], null);
   check_uri_keyword(URIS[0], null);
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     check_orphans();
     run_next_test();
   });
 });
 
 function run_test()
 {
   run_next_test();

--- a/toolkit/components/places/tests/browser/browser_bug399606.js
+++ b/toolkit/components/places/tests/browser/browser_bug399606.js
@@ -43,17 +43,17 @@ function test() {
 
   function confirm_results() {
     gBrowser.removeCurrentTab();
     hs.removeObserver(historyObserver, false);
     for (let aURI in historyObserver.visitCount) {
       is(historyObserver.visitCount[aURI], 1,
          "onVisit has been received right number of times for " + aURI);
     }
-    waitForClearHistory(finish);
+    promiseClearHistory().then(finish);
   }
 
   var loadCount = 0;
   function handleLoad(aEvent) {
     loadCount++;
     info("new load count is " + loadCount);
 
     if (loadCount == 3) {

--- a/toolkit/components/places/tests/browser/browser_bug680727.js
+++ b/toolkit/components/places/tests/browser/browser_bug680727.js
@@ -50,17 +50,17 @@ function errorListener() {
      "about:neterror?e=netOffline",
      "Document URI is the error page.");
 
   // But location bar should show the original request.
   is(content.location.href, kUniqueURI.spec,
      "Docshell URI is the original URI.");
 
   // Global history does not record URI of a failed request.
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     gAsyncHistory.isURIVisited(kUniqueURI, errorAsyncListener);
   });
 }
 
 function errorAsyncListener(aURI, aIsVisited) {
   ok(kUniqueURI.equals(aURI) && !aIsVisited,
      "The neterror page is not listed in global history.");
 
@@ -86,24 +86,24 @@ function reloadListener() {
   // IHistory::VisitURI(...) is called.
   ok(!Services.io.offline, "Services.io.offline is false.");
 
   // This is not an error page.
   is(gBrowser.contentDocument.documentURI, kUniqueURI.spec, 
      "Document URI is not the offline-error page, but the original URI.");
 
   // Check if global history remembers the successfully-requested URI.
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     gAsyncHistory.isURIVisited(kUniqueURI, reloadAsyncListener);
   });
 }
 
 function reloadAsyncListener(aURI, aIsVisited) {
   ok(kUniqueURI.equals(aURI) && aIsVisited, "We have visited the URI.");
-  waitForClearHistory(finish);
+  promiseClearHistory().then(finish);
 }
 
 registerCleanupFunction(function() {
   Services.prefs.setIntPref("network.proxy.type", proxyPrefValue);
   Services.io.offline = false;
   window.removeEventListener("DOMContentLoaded", errorListener, false);
   window.removeEventListener("DOMContentLoaded", reloadListener, false);
   gBrowser.removeCurrentTab();

--- a/toolkit/components/places/tests/browser/browser_notfound.js
+++ b/toolkit/components/places/tests/browser/browser_notfound.js
@@ -16,17 +16,17 @@ function test() {
     onVisit: function (aURI, aVisitID, aTime, aSessionID, aReferringID,
                       aTransitionType) {
       PlacesUtils.history.removeObserver(historyObserver);
       info("Received onVisit: " + aURI.spec);
       fieldForUrl(aURI, "frecency", function (aFrecency) {
         is(aFrecency, 0, "Frecency should be 0");
         fieldForUrl(aURI, "hidden", function (aHidden) {
           is(aHidden, 0, "Page should not be hidden");
-          waitForClearHistory(finish);
+          promiseClearHistory().then(finish);
         });
       });
     },
     onBeginUpdateBatch: function () {},
     onEndUpdateBatch: function () {},
     onTitleChanged: function () {},
     onBeforeDeleteURI: function () {},
     onDeleteURI: function () {},

--- a/toolkit/components/places/tests/browser/browser_redirect.js
+++ b/toolkit/components/places/tests/browser/browser_redirect.js
@@ -30,17 +30,17 @@ function test() {
           is(aHidden, 1, "The redirecting page should be hidden");
 
           fieldForUrl(TARGET_URI, "frecency", function (aFrecency) {
             ok(aFrecency != 0, "Frecency of the target page should not be 0");
 
             fieldForUrl(TARGET_URI, "hidden", function (aHidden) {
               is(aHidden, 0, "The target page should not be hidden");
 
-              waitForClearHistory(finish);
+              promiseClearHistory().then(finish);
             });
           });
         });
       });
     },
     onBeginUpdateBatch: function () {},
     onEndUpdateBatch: function () {},
     onTitleChanged: function () {},

--- a/toolkit/components/places/tests/browser/browser_settitle.js
+++ b/toolkit/components/places/tests/browser/browser_settitle.js
@@ -3,17 +3,17 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 gBrowser.selectedTab = gBrowser.addTab();
 
 function finishAndCleanUp()
 {
   gBrowser.removeCurrentTab();
-  waitForClearHistory(finish);
+  promiseClearHistory().then(finish);
 }
 
 /**
  * One-time DOMContentLoaded callback.
  */
 function load(href, callback)
 {
   content.location.href = href;

--- a/toolkit/components/places/tests/browser/browser_visituri.js
+++ b/toolkit/components/places/tests/browser/browser_visituri.js
@@ -3,17 +3,17 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 gBrowser.selectedTab = gBrowser.addTab();
 
 function finishAndCleanUp()
 {
   gBrowser.removeCurrentTab();
-  waitForClearHistory(finish);
+  promiseClearHistory().then(finish);
 }
 
 /**
  * One-time observer callback.
  */
 function waitForObserve(name, callback)
 {
   var observerService = Cc["@mozilla.org/observer-service;1"]

--- a/toolkit/components/places/tests/browser/browser_visituri_nohistory.js
+++ b/toolkit/components/places/tests/browser/browser_visituri_nohistory.js
@@ -45,17 +45,17 @@ function test()
 
   waitForObserve("uri-visit-saved", function(subject, topic, data)
   {
     let uri = subject.QueryInterface(Ci.nsIURI);
     is(uri.spec, FINAL_URL, "received expected visit");
     if (uri.spec != FINAL_URL)
       return;
     gBrowser.removeCurrentTab();
-    waitForClearHistory(finish);
+    promiseClearHistory().then(finish);
   });
 
   Services.prefs.setBoolPref("places.history.enabled", false);
   content.location.href = INITIAL_URL;
   waitForLoad(function()
   {
     try {
       Services.prefs.clearUserPref("places.history.enabled");

--- a/toolkit/components/places/tests/browser/browser_visituri_privatebrowsing.js
+++ b/toolkit/components/places/tests/browser/browser_visituri_privatebrowsing.js
@@ -55,17 +55,17 @@ function test()
 
   waitForObserve("uri-visit-saved", function(subject, topic, data)
   {
     let uri = subject.QueryInterface(Ci.nsIURI);
     is(uri.spec, FINAL_URL, "received expected visit");
     if (uri.spec != FINAL_URL)
       return;
     gBrowser.removeCurrentTab();
-    waitForClearHistory(finish);
+    promiseClearHistory().then(finish);
   });
 
   content.location.href = INITIAL_URL;
   waitForLoad(function()
   {
     pb.privateBrowsingEnabled = false;
     try {
       Services.prefs.clearUserPref("browser.privatebrowsing.keep_current_session");

--- a/toolkit/components/places/tests/browser/head.js
+++ b/toolkit/components/places/tests/browser/head.js
@@ -1,65 +1,87 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 Components.utils.import("resource://gre/modules/NetUtil.jsm");
 
+XPCOMUtils.defineLazyModuleGetter(this, "Promise",
+                                  "resource://gre/modules/commonjs/promise/core.js");
+
 /**
- * Waits for completion of a clear history operation, before
- * proceeding with aCallback.
+ * Allows waiting for an observer notification once.
  *
- * @param aCallback
- *        Function to be called when done.
+ * @param aTopic
+ *        Notification topic to observe.
+ *
+ * @return {Promise}
+ * @resolves The array [aSubject, aData] from the observed notification.
+ * @rejects Never.
  */
-function waitForClearHistory(aCallback) {
-  Services.obs.addObserver(function observeCH(aSubject, aTopic, aData) {
-    Services.obs.removeObserver(observeCH, PlacesUtils.TOPIC_EXPIRATION_FINISHED);
-    aCallback();
-  }, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
-  PlacesUtils.bhistory.removeAllPages();
+function promiseTopicObserved(aTopic)
+{
+  let deferred = Promise.defer();
+
+  Services.obs.addObserver(
+    function PTO_observe(aSubject, aTopic, aData) {
+      Services.obs.removeObserver(PTO_observe, aTopic);
+      deferred.resolve([aSubject, aData]);
+    }, aTopic, false);
+
+  return deferred.promise;
 }
 
 /**
- * Waits for all pending async statements on the default connection, before
- * proceeding with aCallback.
+ * Clears history asynchronously.
  *
- * @param aCallback
- *        Function to be called when done.
- * @param aScope
- *        Scope for the callback.
- * @param aArguments
- *        Arguments array for the callback.
+ * @return {Promise}
+ * @resolves When history has been cleared.
+ * @rejects Never.
+ */
+function promiseClearHistory() {
+  let promise = promiseTopicObserved(PlacesUtils.TOPIC_EXPIRATION_FINISHED);
+  PlacesUtils.bhistory.removeAllPages();
+  return promise;
+}
+
+/**
+ * Waits for all pending async statements on the default connection.
+ *
+ * @return {Promise}
+ * @resolves When all pending async statements finished.
+ * @rejects Never.
  *
  * @note The result is achieved by asynchronously executing a query requiring
  *       a write lock.  Since all statements on the same connection are
  *       serialized, the end of this write operation means that all writes are
  *       complete.  Note that WAL makes so that writers don't block readers, but
  *       this is a problem only across different connections.
  */
-function waitForAsyncUpdates(aCallback, aScope, aArguments)
+function promiseAsyncUpdates()
 {
-  let scope = aScope || this;
-  let args = aArguments || [];
+  let deferred = Promise.defer();
+
   let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)
                               .DBConnection;
   let begin = db.createAsyncStatement("BEGIN EXCLUSIVE");
   begin.executeAsync();
   begin.finalize();
 
   let commit = db.createAsyncStatement("COMMIT");
   commit.executeAsync({
     handleResult: function() {},
     handleError: function() {},
     handleCompletion: function(aReason)
     {
-      aCallback.apply(scope, args);
+      deferred.resolve();
     }
   });
   commit.finalize();
+
+  return deferred.promise;
 }
 
 /**
  * Returns a moz_places field value for a url.
  *
  * @param aURI
  *        The URI or spec to get field for.
  * param aCallback
@@ -85,30 +107,8 @@ function fieldForUrl(aURI, aFieldName, a
     handleCompletion: function(aReason) {
       if (aReason != Ci.mozIStorageStatementCallback.REASON_FINISHED)
          ok(false, "The statement should properly succeed");
       aCallback(this._value);
     }
   });
   stmt.finalize();
 }
-
-function waitForAsyncUpdates(aCallback, aScope, aArguments)
-{
-  let scope = aScope || this;
-  let args = aArguments || [];
-  let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)
-                              .DBConnection;
-  let begin = db.createAsyncStatement("BEGIN EXCLUSIVE");
-  begin.executeAsync();
-  begin.finalize();
-
-  let commit = db.createAsyncStatement("COMMIT");
-  commit.executeAsync({
-    handleResult: function() {},
-    handleError: function() {},
-    handleCompletion: function(aReason)
-    {
-      aCallback.apply(scope, args);
-    }
-  });
-  commit.finalize();
-}

--- a/toolkit/components/places/tests/expiration/test_debug_expiration.js
+++ b/toolkit/components/places/tests/expiration/test_debug_expiration.js
@@ -31,17 +31,17 @@ add_test(function test_expire_orphans()
     Services.obs.removeObserver(arguments.callee, aTopic);
 
     // Check that visits survived.
     do_check_eq(visits_in_database("http://page1.mozilla.org/"), 1);
     do_check_eq(visits_in_database("http://page2.mozilla.org/"), 1);
     do_check_false(page_in_database("http://page3.mozilla.org/"));
 
     // Clean up.
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   }, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
   // Expire now.
   force_expiration_step(0);
 });
 
 add_test(function test_expire_orphans_optionalarg()
 {
@@ -64,17 +64,17 @@ add_test(function test_expire_orphans_op
     Services.obs.removeObserver(arguments.callee, aTopic);
 
     // Check that visits survived.
     do_check_eq(visits_in_database("http://page1.mozilla.org/"), 1);
     do_check_eq(visits_in_database("http://page2.mozilla.org/"), 1);
     do_check_false(page_in_database("http://page3.mozilla.org/"));
 
     // Clean up.
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   }, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
   // Expire now.
   force_expiration_step();
 });
 
 add_test(function test_expire_limited()
 {
@@ -91,17 +91,17 @@ add_test(function test_expire_limited()
   {
     Services.obs.removeObserver(arguments.callee, aTopic);
 
     // Check that visits to the more recent page survived.
     do_check_false(page_in_database("http://page1.mozilla.org/"));
     do_check_eq(visits_in_database("http://page2.mozilla.org/"), 1);
 
     // Clean up.
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   }, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
   // Expire now.
   force_expiration_step(1);
 });
 
 add_test(function test_expire_unlimited()
 {
@@ -118,17 +118,17 @@ add_test(function test_expire_unlimited(
   {
     Services.obs.removeObserver(arguments.callee, aTopic);
 
     // Check that visits to the more recent page survived.
     do_check_false(page_in_database("http://page1.mozilla.org/"));
     do_check_false(page_in_database("http://page2.mozilla.org/"));
 
     // Clean up.
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   }, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
   // Expire now.
   force_expiration_step(-1);
 });
 
 function run_test()
 {

--- a/toolkit/components/places/tests/expiration/test_notifications_onDeleteURI.js
+++ b/toolkit/components/places/tests/expiration/test_notifications_onDeleteURI.js
@@ -115,21 +115,21 @@ function run_next_test() {
     os.addObserver(observer, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
     // Expire now, observers will check results.
     force_expiration_step(-1);
   }
   else {
     clearMaxPages();
     bs.removeFolderChildren(bs.unfiledBookmarksFolder);
-    waitForClearHistory(do_test_finished);
+    promiseClearHistory().then(do_test_finished);
   }
 }
 
 function check_result() {
 
   do_check_eq(gCurrentTest.receivedNotifications,
               gCurrentTest.expectedNotifications);
 
   // Clean up.
   bs.removeFolderChildren(bs.unfiledBookmarksFolder);
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 }

--- a/toolkit/components/places/tests/expiration/test_notifications_onDeleteVisits.js
+++ b/toolkit/components/places/tests/expiration/test_notifications_onDeleteVisits.js
@@ -137,21 +137,21 @@ function run_next_test() {
     os.addObserver(observer, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
     // Expire now, observers will check results.
     force_expiration_step(gCurrentTest.limitExpiration);
   }
   else {
     clearMaxPages();
     bs.removeFolderChildren(bs.unfiledBookmarksFolder);
-    waitForClearHistory(do_test_finished);
+    promiseClearHistory().then(do_test_finished);
   }
 }
 
 function check_result() {
 
   do_check_eq(gCurrentTest.receivedNotifications,
               gCurrentTest.expectedNotifications);
 
   // Clean up.
   bs.removeFolderChildren(bs.unfiledBookmarksFolder);
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 }

--- a/toolkit/components/places/tests/expiration/test_pref_maxpages.js
+++ b/toolkit/components/places/tests/expiration/test_pref_maxpages.js
@@ -126,20 +126,20 @@ function run_next_test() {
     os.addObserver(observer, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
 
     setMaxPages(gCurrentTest.maxPages);
     // Expire now, observers will check results.
     force_expiration_step(-1);
   }
   else {
     clearMaxPages();
-    waitForClearHistory(do_test_finished);
+    promiseClearHistory().then(do_test_finished);
   }
 }
 
 function check_result() {
 
   do_check_eq(gCurrentTest.receivedNotifications,
               gCurrentTest.expectedNotifications);
 
   // Clean up.
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 }

--- a/toolkit/components/places/tests/favicons/test_query_result_favicon_changed_on_child.js
+++ b/toolkit/components/places/tests/favicons/test_query_result_favicon_changed_on_child.js
@@ -64,17 +64,17 @@ add_test(function test_query_result_favi
   result.addObserver(resultObserver, false);
 
   waitForFaviconChanged(PAGE_URI, SMALLPNG_DATA_URI,
                         function QRFCOC_faviconChanged() {
     // We must wait for the asynchronous database thread to finish the
     // operation, and then for the main thread to process any pending
     // notifications that came from the asynchronous thread, before we can be
     // sure that nodeIconChanged was not invoked in the meantime.
-    waitForAsyncUpdates(function QRFCOC_asyncUpdates() {
+    promiseAsyncUpdates().then(function QRFCOC_asyncUpdates() {
       do_execute_soon(function QRFCOC_soon() {
         result.removeObserver(resultObserver);
 
         // Free the resources immediately.
         result.root.containerOpen = false;
         run_next_test();
       });
     });

--- a/toolkit/components/places/tests/favicons/test_replaceFaviconData.js
+++ b/toolkit/components/places/tests/favicons/test_replaceFaviconData.js
@@ -82,17 +82,17 @@ add_test(function test_replaceFaviconDat
   iconsvc.setAndFetchFaviconForPage(pageURI, favicon.uri, true,
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconData_validHistoryURI_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, favicon.mimetype, favicon.data);
       checkFaviconDataForPage(
         pageURI, favicon.mimetype, favicon.data,
         function test_replaceFaviconData_validHistoryURI_callback() {
           favicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconData_overrideDefaultFavicon() {
   do_log_info("test replaceFaviconData to override a later setAndFetchFaviconForPage");
 
   let pageURI = uri("http://test2.bar/");
@@ -109,17 +109,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconData_overrideDefaultFavicon_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconData_overrideDefaultFavicon_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconData_replaceExisting() {
   do_log_info("test replaceFaviconData to override a previous setAndFetchFaviconForPage");
 
   let pageURI = uri("http://test3.bar");
@@ -134,23 +134,23 @@ add_test(function test_replaceFaviconDat
     function test_replaceFaviconData_replaceExisting_firstSet_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, firstFavicon.mimetype, firstFavicon.data);
       checkFaviconDataForPage(
         pageURI, firstFavicon.mimetype, firstFavicon.data,
         function test_replaceFaviconData_overrideDefaultFavicon_firstCallback() {
           iconsvc.replaceFaviconData(
             firstFavicon.uri, secondFavicon.data, secondFavicon.data.length,
             secondFavicon.mimetype);
-          waitForAsyncUpdates(function() {
+          promiseAsyncUpdates().then(function() {
             checkFaviconDataForPage(
               pageURI, secondFavicon.mimetype, secondFavicon.data,
               function test_replaceFaviconData_overrideDefaultFavicon_secondCallback() {
                 firstFavicon.file.remove(false);
                 secondFavicon.file.remove(false);
-                waitForClearHistory(run_next_test);
+                promiseClearHistory().then(run_next_test);
               });
           });
         });
     });
 });
 
 add_test(function test_replaceFaviconData_unrelatedReplace() {
   do_log_info("test replaceFaviconData to not make unrelated changes");
@@ -169,17 +169,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconData_unrelatedReplace_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, favicon.mimetype, favicon.data);
       checkFaviconDataForPage(
         pageURI, favicon.mimetype, favicon.data,
         function test_replaceFaviconData_unrelatedReplace_callback() {
           favicon.file.remove(false);
           unrelatedFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconData_badInputs() {
   do_log_info("test replaceFaviconData to throw on bad inputs");
 
   let favicon = createFavicon("favicon8.png");
@@ -210,17 +210,17 @@ add_test(function test_replaceFaviconDat
       favicon.uri, null, 0, favicon.mimeType);
   } catch (e) {
     ex = e;
   } finally {
     do_check_true(!!ex);
   }
 
   favicon.file.remove(false);
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 });
 
 add_test(function test_replaceFaviconData_twiceReplace() {
   do_log_info("test replaceFaviconData on multiple replacements");
 
   let pageURI = uri("http://test5.bar/");
   addVisit(pageURI);
 
@@ -239,12 +239,12 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconData_twiceReplace_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconData_twiceReplace_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });

--- a/toolkit/components/places/tests/favicons/test_replaceFaviconDataFromDataURL.js
+++ b/toolkit/components/places/tests/favicons/test_replaceFaviconDataFromDataURL.js
@@ -84,17 +84,17 @@ add_test(function test_replaceFaviconDat
   iconsvc.setAndFetchFaviconForPage(pageURI, favicon.uri, true,
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_validHistoryURI_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, favicon.mimetype, favicon.data);
       checkFaviconDataForPage(
         pageURI, favicon.mimetype, favicon.data,
         function test_replaceFaviconDataFromDataURL_validHistoryURI_callback() {
           favicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_overrideDefaultFavicon() {
   do_log_info("test replaceFaviconDataFromDataURL to override a later setAndFetchFaviconForPage");
 
   let pageURI = uri("http://test2.bar/");
@@ -109,17 +109,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_overrideDefaultFavicon_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconDataFromDataURL_overrideDefaultFavicon_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_replaceExisting() {
   do_log_info("test replaceFaviconDataFromDataURL to override a previous setAndFetchFaviconForPage");
 
   let pageURI = uri("http://test3.bar");
@@ -137,17 +137,17 @@ add_test(function test_replaceFaviconDat
         pageURI, firstFavicon.mimetype, firstFavicon.data,
         function test_replaceFaviconDataFromDataURL_replaceExisting_firstCallback() {
           iconsvc.replaceFaviconDataFromDataURL(firstFavicon.uri, createDataURLForFavicon(secondFavicon));
           checkFaviconDataForPage(
             pageURI, secondFavicon.mimetype, secondFavicon.data,
             function test_replaceFaviconDataFromDataURL_replaceExisting_secondCallback() {
               firstFavicon.file.remove(false);
               secondFavicon.file.remove(false);
-              waitForClearHistory(run_next_test);
+              promiseClearHistory().then(run_next_test);
             });
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_unrelatedReplace() {
   do_log_info("test replaceFaviconDataFromDataURL to not make unrelated changes");
 
@@ -163,17 +163,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_unrelatedReplace_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, favicon.mimetype, favicon.data);
       checkFaviconDataForPage(
         pageURI, favicon.mimetype, favicon.data,
         function test_replaceFaviconDataFromDataURL_unrelatedReplace_callback() {
           favicon.file.remove(false);
           unrelatedFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_badInputs() {
   do_log_info("test replaceFaviconDataFromDataURL to throw on bad inputs");
 
   let favicon = createFavicon("favicon8.png");
@@ -192,17 +192,17 @@ add_test(function test_replaceFaviconDat
     iconsvc.replaceFaviconDataFromDataURL(null, createDataURLForFavicon(favicon));
   } catch (e) {
     ex = e;
   } finally {
     do_check_true(!!ex);
   }
 
   favicon.file.remove(false);
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_twiceReplace() {
   do_log_info("test replaceFaviconDataFromDataURL on multiple replacements");
 
   let pageURI = uri("http://test5.bar/");
   addVisit(pageURI);
 
@@ -217,17 +217,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_twiceReplace_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconDataFromDataURL_twiceReplace_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_afterRegularAssign() {
   do_log_info("test replaceFaviconDataFromDataURL after replaceFaviconData");
 
   let pageURI = uri("http://test6.bar/");
@@ -246,17 +246,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_afterRegularAssign_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconDataFromDataURL_afterRegularAssign_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 add_test(function test_replaceFaviconDataFromDataURL_beforeRegularAssign() {
   do_log_info("test replaceFaviconDataFromDataURL before replaceFaviconData");
 
   let pageURI = uri("http://test7.bar/");
@@ -275,17 +275,17 @@ add_test(function test_replaceFaviconDat
     PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
     function test_replaceFaviconDataFromDataURL_beforeRegularAssign_check(aURI, aDataLen, aData, aMimeType) {
       checkCallbackSucceeded(aMimeType, aData, secondFavicon.mimetype, secondFavicon.data);
       checkFaviconDataForPage(
         pageURI, secondFavicon.mimetype, secondFavicon.data,
         function test_replaceFaviconDataFromDataURL_beforeRegularAssign_callback() {
           firstFavicon.file.remove(false);
           secondFavicon.file.remove(false);
-          waitForClearHistory(run_next_test);
+          promiseClearHistory().then(run_next_test);
         });
     });
 });
 
 /* toBase64 copied from image/test/unit/test_encoder_png.js */
 
 /* Convert data (an array of integers) to a Base64 string. */
 const toBase64Table = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' +

--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -18,32 +18,28 @@ const TRANSITION_FRAMED_LINK = Ci.nsINav
 const TRANSITION_REDIRECT_PERMANENT = Ci.nsINavHistoryService.TRANSITION_REDIRECT_PERMANENT;
 const TRANSITION_REDIRECT_TEMPORARY = Ci.nsINavHistoryService.TRANSITION_REDIRECT_TEMPORARY;
 const TRANSITION_DOWNLOAD = Ci.nsINavHistoryService.TRANSITION_DOWNLOAD;
 
 const TITLE_LENGTH_MAX = 4096;
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 
-XPCOMUtils.defineLazyGetter(this, "Services", function() {
-  Cu.import("resource://gre/modules/Services.jsm");
-  return Services;
-});
+XPCOMUtils.defineLazyModuleGetter(this, "FileUtils",
+                                  "resource://gre/modules/FileUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "NetUtil",
+                                  "resource://gre/modules/NetUtil.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "Promise",
+                                  "resource://gre/modules/commonjs/promise/core.js");
+XPCOMUtils.defineLazyModuleGetter(this, "Services",
+                                  "resource://gre/modules/Services.jsm");
 
-XPCOMUtils.defineLazyGetter(this, "NetUtil", function() {
-  Cu.import("resource://gre/modules/NetUtil.jsm");
-  return NetUtil;
-});
+// This imports various other objects in addition to PlacesUtils.
+Cu.import("resource://gre/modules/PlacesUtils.jsm");
 
-XPCOMUtils.defineLazyGetter(this, "FileUtils", function() {
-  Cu.import("resource://gre/modules/FileUtils.jsm");
-  return FileUtils;
-});
-
-Cu.import("resource://gre/modules/PlacesUtils.jsm");
 XPCOMUtils.defineLazyGetter(this, "SMALLPNG_DATA_URI", function() {
   return NetUtil.newURI(
          "data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAA" +
          "AAAA6fptVAAAACklEQVQI12NgAAAAAgAB4iG8MwAAAABJRU5ErkJggg==");
 });
 
 function LOG(aMsg) {
   aMsg = ("*** PLACES TESTS: " + aMsg);
@@ -370,33 +366,50 @@ function check_no_bookmarks() {
  * @throws if the page is not found in the database.
  *
  * @note This is just a test compatibility mock.
  */
 function setPageTitle(aURI, aTitle) {
   PlacesUtils.history.setPageTitle(aURI, aTitle);
 }
 
+/**
+ * Allows waiting for an observer notification once.
+ *
+ * @param aTopic
+ *        Notification topic to observe.
+ *
+ * @return {Promise}
+ * @resolves The array [aSubject, aData] from the observed notification.
+ * @rejects Never.
+ */
+function promiseTopicObserved(aTopic)
+{
+  let deferred = Promise.defer();
+
+  Services.obs.addObserver(
+    function PTO_observe(aSubject, aTopic, aData) {
+      Services.obs.removeObserver(PTO_observe, aTopic);
+      deferred.resolve([aSubject, aData]);
+    }, aTopic, false);
+
+  return deferred.promise;
+}
 
 /**
- * Clears history invoking callback when done.
+ * Clears history asynchronously.
  *
- * @param aCallback
- *        Callback function to be called once clear history has finished.
+ * @return {Promise}
+ * @resolves When history has been cleared.
+ * @rejects Never.
  */
-function waitForClearHistory(aCallback) {
-  let observer = {
-    observe: function(aSubject, aTopic, aData) {
-      Services.obs.removeObserver(this, PlacesUtils.TOPIC_EXPIRATION_FINISHED);
-      aCallback();
-    }
-  };
-  Services.obs.addObserver(observer, PlacesUtils.TOPIC_EXPIRATION_FINISHED, false);
-
+function promiseClearHistory() {
+  let promise = promiseTopicObserved(PlacesUtils.TOPIC_EXPIRATION_FINISHED);
   PlacesUtils.bhistory.removeAllPages();
+  return promise;
 }
 
 
 /**
  * Simulates a Places shutdown.
  */
 function shutdownPlaces(aKeepAliveConnection)
 {
@@ -511,67 +524,38 @@ function remove_all_JSON_backups() {
 function check_JSON_backup() {
   let profileBookmarksJSONFile = gProfD.clone();
   profileBookmarksJSONFile.append("bookmarkbackups");
   profileBookmarksJSONFile.append(FILENAME_BOOKMARKS_JSON);
   do_check_true(profileBookmarksJSONFile.exists());
   return profileBookmarksJSONFile;
 }
 
-
-/**
- * Waits for a frecency update then calls back.
- *
- * @param aURI
- *        URI or spec of the page we are waiting frecency for.
- * @param aValidator
- *        Validator function for the current frecency. If it returns true we
- *        have the expected frecency, otherwise we wait for next update.
- * @param aCallback
- *        function invoked when frecency update finishes.
- * @param aCbScope
- *        "this" scope for the callback
- * @param aCbArguments
- *        array of arguments to be passed to the callback
- *
- * @note since frecency is something that can be changed by a bunch of stuff
- *       like adding and removing visits, bookmarks we use a polling strategy.
- */
-function waitForFrecency(aURI, aValidator, aCallback, aCbScope, aCbArguments) {
-  Services.obs.addObserver(function (aSubject, aTopic, aData) {
-    let frecency = frecencyForUrl(aURI);
-    if (!aValidator(frecency)) {
-      print("Has to wait for frecency...");
-      return;
-    }
-    Services.obs.removeObserver(arguments.callee, aTopic);
-    aCallback.apply(aCbScope, aCbArguments);
-  }, "places-frecency-updated", false);
-}
-
 /**
  * Returns the frecency of a url.
  *
  * @param aURI
  *        The URI or spec to get frecency for.
  * @return the frecency value.
  */
 function frecencyForUrl(aURI)
 {
   let url = aURI instanceof Ci.nsIURI ? aURI.spec : aURI;
   let stmt = DBConn().createStatement(
     "SELECT frecency FROM moz_places WHERE url = ?1"
   );
   stmt.bindByIndex(0, url);
-  if (!stmt.executeStep())
-    throw new Error("No result for frecency.");
-  let frecency = stmt.getInt32(0);
-  stmt.finalize();
-
-  return frecency;
+  try {
+    if (!stmt.executeStep()) {
+      throw new Error("No result for frecency.");
+    }
+    return stmt.getInt32(0);
+  } finally {
+    stmt.finalize();
+  }
 }
 
 /**
  * Returns the hidden status of a url.
  *
  * @param aURI
  *        The URI or spec to get hidden for.
  * @return @return true if the url is hidden, false otherwise.
@@ -606,51 +590,49 @@ function is_time_ordered(before, after) 
   // amount of time.  See bug 558745 and bug 557406.
   let isWindows = ("@mozilla.org/windows-registry-key;1" in Cc);
   // Just to be safe we consider 20ms.
   let skew = isWindows ? 20000000 : 0;
   return after - before > -skew;
 }
 
 /**
- * Waits for all pending async statements on the default connection, before
- * proceeding with aCallback.
+ * Waits for all pending async statements on the default connection.
  *
- * @param aCallback
- *        Function to be called when done.
- * @param aScope
- *        Scope for the callback.
- * @param aArguments
- *        Arguments array for the callback.
+ * @return {Promise}
+ * @resolves When all pending async statements finished.
+ * @rejects Never.
  *
  * @note The result is achieved by asynchronously executing a query requiring
  *       a write lock.  Since all statements on the same connection are
  *       serialized, the end of this write operation means that all writes are
  *       complete.  Note that WAL makes so that writers don't block readers, but
  *       this is a problem only across different connections.
  */
-function waitForAsyncUpdates(aCallback, aScope, aArguments)
+function promiseAsyncUpdates()
 {
-  let scope = aScope || this;
-  let args = aArguments || [];
+  let deferred = Promise.defer();
+
   let db = DBConn();
   let begin = db.createAsyncStatement("BEGIN EXCLUSIVE");
   begin.executeAsync();
   begin.finalize();
 
   let commit = db.createAsyncStatement("COMMIT");
   commit.executeAsync({
-    handleResult: function() {},
-    handleError: function() {},
+    handleResult: function () {},
+    handleError: function () {},
     handleCompletion: function(aReason)
     {
-      aCallback.apply(scope, args);
+      deferred.resolve();
     }
   });
   commit.finalize();
+
+  return deferred.promise;
 }
 
 /**
  * Shutdowns Places, invoking the callback when the connection has been closed.
  *
  * @param aCallback
  *        Function to be called when done.
  */

--- a/toolkit/components/places/tests/inline/head_autocomplete.js
+++ b/toolkit/components/places/tests/inline/head_autocomplete.js
@@ -161,31 +161,32 @@ function run_test() {
       if (setupFunc) {
         setupFunc();
       }
 
       // At this point frecency could still be updating due to latest pages
       // updates.
       // This is not a problem in real life, but autocomplete tests should
       // return reliable resultsets, thus we have to wait.
-      waitForAsyncUpdates(ensure_results, this, [searchString, expectedValue]);
+      promiseAsyncUpdates().then(function () ensure_results(searchString,
+                                                            expectedValue));
     })
   }, this);
 
   run_next_test();
 }
 
 let gAutoCompleteTests = [];
 function add_autocomplete_test(aTestData) {
   gAutoCompleteTests.push(aTestData);
 }
 
 function waitForCleanup(aCallback) {
   remove_all_bookmarks();
-  waitForClearHistory(aCallback);
+  promiseClearHistory().then(aCallback);
 }
 
 function addBookmark(aBookmarkObj) {
   do_check_true(!!aBookmarkObj.url);
   let parentId = aBookmarkObj.parentId ? aBookmarkObj.parentId
                                        : PlacesUtils.unfiledBookmarksFolderId;
   let itemId = PlacesUtils.bookmarks
                           .insertBookmark(parentId,

--- a/toolkit/components/places/tests/queries/test_redirects.js
+++ b/toolkit/components/places/tests/queries/test_redirects.js
@@ -277,17 +277,17 @@ function add_visits_to_database() {
 // Main
 function run_test() {
   do_test_pending();
 
   // Populate the database.
   add_visits_to_database();
 
   // Frecency and hidden are updated asynchronously, wait for them.
-  waitForAsyncUpdates(continue_test);
+  promiseAsyncUpdates().then(continue_test);
  }
 
  function continue_test() {
   // This array will be used by cartProd to generate a matrix of all possible
   // combinations.
   let includeHidden_options = [true, false];
   let maxResults_options = [5, 10, 20, null];
   // These sortingMode are choosen to toggle using special queries for history
@@ -295,10 +295,10 @@ function run_test() {
   let sorting_options = [Ci.nsINavHistoryQueryOptions.SORT_BY_NONE,
                          Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING,
                          Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING];
   // Will execute check_results_callback() for each generated combination.
   cartProd([includeHidden_options, maxResults_options, sorting_options],
            check_results_callback);
 
   remove_all_bookmarks();
-  waitForClearHistory(do_test_finished);
+  promiseClearHistory().then(do_test_finished);
 }

--- a/toolkit/components/places/tests/queries/test_sorting.js
+++ b/toolkit/components/places/tests/queries/test_sorting.js
@@ -1267,21 +1267,21 @@ function run_test() {
   do_test_pending();
   runNextTest();
 }
 
 function runNextTest() {
   if (tests.length) {
     let test = tests.shift();
     test.setup();
-    waitForAsyncUpdates(function () {
+    promiseAsyncUpdates().then(function () {
       test.check();
       // sorting reversed, usually SORT_BY have ASC and DESC
       test.check_reverse();
       // Execute cleanup tasks
       remove_all_bookmarks();
-      waitForClearHistory(runNextTest);
+      promiseClearHistory().then(runNextTest);
     });
   }
   else {
     do_test_finished();
   }
 }

--- a/toolkit/components/places/tests/queries/test_tags.js
+++ b/toolkit/components/places/tests/queries/test_tags.js
@@ -597,17 +597,17 @@ function addVisit(aURI) {
   do_check_true(visitId > 0);
 }
 
 /**
  * Removes all pages from history and bookmarks.
  */
 function cleanDatabase(aCallback) {
   remove_all_bookmarks();
-  waitForClearHistory(aCallback);
+  promiseClearHistory().then(aCallback);
 }
 
 /**
  * Sets up a query with the specified tags, converts it to a URI, and makes sure
  * the URI is what we expect it to be.
  *
  * @param aTags
  *        The query's tags will be set to those in this array

--- a/toolkit/components/places/tests/unit/test_000_frecency.js
+++ b/toolkit/components/places/tests/unit/test_000_frecency.js
@@ -204,17 +204,17 @@ AutoCompleteInput.prototype = {
       return this;
 
     throw Components.results.NS_ERROR_NO_INTERFACE;
   }
 }
 
 function run_test() {
   do_test_pending();
-  waitForAsyncUpdates(continue_test);
+  promiseAsyncUpdates().then(continue_test);
 }
 
 function continue_test() {
   var controller = Components.classes["@mozilla.org/autocomplete/controller;1"].
                    getService(Components.interfaces.nsIAutoCompleteController);
 
   // Make an AutoCompleteInput that uses our searches
   // and confirms results on search complete

--- a/toolkit/components/places/tests/unit/test_317472.js
+++ b/toolkit/components/places/tests/unit/test_317472.js
@@ -50,17 +50,17 @@ function run_test() {
   // check that we have created a page annotation
   do_check_eq(annosvc.getPageAnnotation(TEST_URI, CHARSET_ANNO), charset);
 
   // get charset from not-bookmarked page
   do_check_eq(histsvc.getCharsetForURI(TEST_URI), charset);
   // get charset from bookmarked page
   do_check_eq(histsvc.getCharsetForURI(TEST_BOOKMARKED_URI), charset);
 
-  waitForClearHistory(continue_test);
+  promiseClearHistory().then(continue_test);
 
   do_test_pending();
 }
 
 function continue_test() {
   // ensure that charset has gone for not-bookmarked page
   do_check_neq(histsvc.getCharsetForURI(TEST_URI), charset);
 

--- a/toolkit/components/places/tests/unit/test_384370.js
+++ b/toolkit/components/places/tests/unit/test_384370.js
@@ -55,17 +55,17 @@ function run_test() {
       do_throw("Couldn't import legacy bookmarks file.");
     }
 
     populate();
 
     // 2. run the test-suite
     validate();
   
-    waitForAsyncUpdates(function testJsonExport() {
+    promiseAsyncUpdates().then(function testJsonExport() {
       // Test exporting a Places canonical json file.
       // 1. export to bookmarks.exported.json
       try {
         PlacesUtils.backups.saveBookmarksToJSONFile(jsonFile);
       } catch(ex) { do_throw("couldn't export to file: " + ex); }
       LOG("exported json");
 
       // 2. empty bookmarks db
@@ -74,17 +74,17 @@ function run_test() {
         PlacesUtils.restoreBookmarksFromJSONFile(jsonFile);
       } catch(ex) { do_throw("couldn't import the exported file: " + ex); }
       LOG("imported json");
 
       // 4. run the test-suite
       validate();
       LOG("validated import");
   
-      waitForAsyncUpdates(do_test_finished);
+      promiseAsyncUpdates().then(do_test_finished);
     });
   }
 }
 
 var tagData = [
   { uri: uri("http://slint.us"), tags: ["indie", "kentucky", "music"] },
   { uri: uri("http://en.wikipedia.org/wiki/Diplodocus"), tags: ["dinosaur", "dj", "rad word"] }
 ];

--- a/toolkit/components/places/tests/unit/test_412132.js
+++ b/toolkit/components/places/tests/unit/test_412132.js
@@ -16,60 +16,60 @@ add_test(function changeuri_unvisited_bo
   do_log_info("After changing URI of bookmark, frecency of bookmark's " +
               "original URI should be zero if original URI is unvisited and " +
               "no longer bookmarked.");
   const TEST_URI = NetUtil.newURI("http://example.com/1");
   let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     PlacesUtils.bookmarks.changeBookmarkURI(id, uri("http://example.com/2"));
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("Unvisited URI no longer bookmarked => frecency should = 0");
       do_check_eq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function changeuri_visited_bookmark()
 {
   do_log_info("After changing URI of bookmark, frecency of bookmark's " +
               "original URI should not be zero if original URI is visited.");
   const TEST_URI = NetUtil.newURI("http://example.com/1");
   let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     visit(TEST_URI);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       PlacesUtils.bookmarks.changeBookmarkURI(id, uri("http://example.com/2"));
-      waitForAsyncUpdates(function ()
+      promiseAsyncUpdates().then(function ()
       {
         do_log_info("*Visited* URI no longer bookmarked => frecency should != 0");
         do_check_neq(frecencyForUrl(TEST_URI), 0);
 
         remove_all_bookmarks();
-        waitForClearHistory(run_next_test);
+        promiseClearHistory().then(run_next_test);
       });
     });
   });
 });
 
 add_test(function changeuri_bookmark_still_bookmarked()
 {
   do_log_info("After changing URI of bookmark, frecency of bookmark's " +
@@ -79,29 +79,29 @@ add_test(function changeuri_bookmark_sti
   let id1 = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                  TEST_URI,
                                                  PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                  "bookmark 1 title");
   let id2 = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                  TEST_URI,
                                                  PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                  "bookmark 2 title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     PlacesUtils.bookmarks.changeBookmarkURI(id1, uri("http://example.com/2"));
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("URI still bookmarked => frecency should != 0");
       do_check_neq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function changeuri_nonexistent_bookmark()
 {
   do_log_info("Changing the URI of a nonexistent bookmark should fail.");
     function tryChange(itemId)
@@ -125,17 +125,17 @@ add_test(function changeuri_nonexistent_
     let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                   uri("http://example.com/"),
                                                   PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                   "bookmark title");
     PlacesUtils.bookmarks.removeItem(id);
     tryChange(id);
 
     remove_all_bookmarks();
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
 });
 
 ///////////////////////////////////////////////////////////////////////////////
 
 /**
  * Adds a visit for aURI.
  *
  * @param aURI

--- a/toolkit/components/places/tests/unit/test_421180.js
+++ b/toolkit/components/places/tests/unit/test_421180.js
@@ -35,17 +35,17 @@ add_test(function test_keywordRemovedOnU
   var bookmarkId = bmsvc.insertBookmark(bmsvc.bookmarksMenuFolder,
                                         bookmarkedURI,
                                         bmsvc.DEFAULT_INDEX,
                                         "A bookmark");
   bmsvc.setKeywordForBookmark(bookmarkId, keyword);
   // remove bookmark
   bmsvc.removeItem(bookmarkId);
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     // Check that keyword has been removed from the database.
     // The removal is asynchronous.
     var sql = "SELECT id FROM moz_keywords WHERE keyword = ?1";
     var stmt = mDBConn.createStatement(sql);
     stmt.bindByIndex(0, keyword);
     do_check_false(stmt.executeStep());
     stmt.finalize();
 
@@ -72,17 +72,17 @@ add_test(function test_keywordNotRemoved
                                         bookmarkedURI,
                                         bmsvc.DEFAULT_INDEX,
                                         keyword);
   bmsvc.setKeywordForBookmark(bookmarkId2, keyword);
 
   // remove first bookmark
   bmsvc.removeItem(bookmarkId1);
 
-  waitForAsyncUpdates(function() {
+  promiseAsyncUpdates().then(function() {
     // check that keyword is still there
     var sql = "SELECT id FROM moz_keywords WHERE keyword = ?1";
     var stmt = mDBConn.createStatement(sql);
     stmt.bindByIndex(0, keyword);
     do_check_true(stmt.executeStep());
     stmt.finalize();
 
     run_next_test();

--- a/toolkit/components/places/tests/unit/test_adaptive.js
+++ b/toolkit/components/places/tests/unit/test_adaptive.js
@@ -358,15 +358,15 @@ function run_test() {
 function next_test() {
   if (tests.length) {
     // Cleanup.
     PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.unfiledBookmarksFolderId);
     PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.tagsFolderId);
     observer.runCount = -1;
 
     let test = tests.shift();
-    waitForClearHistory(test);
+    promiseClearHistory().then(test);
   }
   else {
     Services.obs.removeObserver(observer, PlacesUtils.TOPIC_FEEDBACK_UPDATED);
     do_test_finished();
   }
 }

--- a/toolkit/components/places/tests/unit/test_asyncExecuteLegacyQueries.js
+++ b/toolkit/components/places/tests/unit/test_asyncExecuteLegacyQueries.js
@@ -90,13 +90,13 @@ function run_test()
 
 function run_next_test() {
   if (tests.length == 0) {
     do_test_finished();
     return;
   }
 
   let test = tests.shift();
-  waitForClearHistory(function() {
+  promiseClearHistory().then(function() {
     remove_all_bookmarks();
     do_execute_soon(test);
   });
 }

--- a/toolkit/components/places/tests/unit/test_async_history_api.js
+++ b/toolkit/components/places/tests/unit/test_async_history_api.js
@@ -433,17 +433,17 @@ function test_non_addable_uri_errors()
   let callbackCount = 0;
   gHistory.updatePlaces(places, expectHandleError(function(aResultCode, aPlaceInfo) {
     do_log_info("Checking '" + aPlaceInfo.uri.spec + "'");
     do_check_eq(aResultCode, Cr.NS_ERROR_INVALID_ARG);
     do_check_false(gGlobalHistory.isVisited(aPlaceInfo.uri));
 
     // If we have had all of our callbacks, continue running tests.
     if (++callbackCount == places.length) {
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }
   }));
 }
 
 function test_duplicate_guid_errors()
 {
   // This test ensures that trying to add a visit, with a guid already found in
   // another visit, fails.
@@ -466,17 +466,17 @@ function test_duplicate_guid_errors()
       guid: aPlaceInfo.guid,
     };
 
     do_check_false(gGlobalHistory.isVisited(badPlace.uri));
     gHistory.updatePlaces(badPlace, expectHandleError(function(aResultCode, aPlaceInfo) {
       do_check_eq(aResultCode, Cr.NS_ERROR_STORAGE_CONSTRAINT);
       do_check_false(gGlobalHistory.isVisited(badPlace.uri));
 
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }));
   }));
 }
 
 function test_invalid_referrerURI_ignored()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN +
@@ -502,17 +502,17 @@ function test_invalid_referrerURI_ignore
       "FROM moz_historyvisits " +
       "WHERE id = :visit_id"
     );
     stmt.params.visit_id = aPlaceInfo.visits[0].visitId;
     do_check_true(stmt.executeStep());
     do_check_eq(stmt.row.from_visit, 0);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_nonnsIURI_referrerURI_ignored()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN +
                         "test_nonnsIURI_referrerURI_ignored"),
@@ -533,17 +533,17 @@ function test_nonnsIURI_referrerURI_igno
       "FROM moz_historyvisits " +
       "WHERE id = :visit_id"
     );
     stmt.params.visit_id = aPlaceInfo.visits[0].visitId;
     do_check_true(stmt.executeStep());
     do_check_eq(stmt.row.from_visit, 0);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_invalid_sessionId_ignored()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN +
                         "test_invalid_sessionId_ignored"),
@@ -568,17 +568,17 @@ function test_invalid_sessionId_ignored(
       "FROM moz_historyvisits " +
       "WHERE id = :visit_id"
     );
     stmt.params.visit_id = visit.visitId;
     do_check_true(stmt.executeStep());
     do_check_neq(stmt.row.session, place.visits[0].sessionId);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_unstored_sessionId_ignored()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN +
                         "test_unstored_sessionId_ignored"),
@@ -616,17 +616,17 @@ function test_unstored_sessionId_ignored
     do_check_true(stmt.executeStep());
 
     // Max sessionId should increase by 1 because we will generate a new
     // non-bogus sessionId.
     let newMaxSessionId = stmt.row.max_session;
     do_check_eq(maxSessionId + 1, newMaxSessionId);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 
 function test_old_referrer_ignored()
 {
   // This tests that a referrer for a visit which is not recent (specifically,
   // older than 15 minutes as per RECENT_EVENT_THRESHOLD) is not saved by
@@ -670,17 +670,17 @@ function test_old_referrer_ignored()
         "WHERE place_id = (SELECT id FROM moz_places WHERE url = :page_url) " +
         "AND from_visit = 0 "
       );
       stmt.params.page_url = place.uri.spec;
       do_check_true(stmt.executeStep());
       do_check_eq(stmt.row.count, 1);
       stmt.finalize();
 
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }));
   }));
 }
 
 function test_place_id_ignored()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN + "test_place_id_ignored_first"),
@@ -705,17 +705,17 @@ function test_place_id_ignored()
     };
 
     do_check_false(gGlobalHistory.isVisited(badPlace.uri));
     gHistory.updatePlaces(badPlace, {
       handleResult: function handleResult(aPlaceInfo) {
         do_check_neq(aPlaceInfo.placeId, placeId);
         do_check_true(gGlobalHistory.isVisited(badPlace.uri));
 
-        waitForAsyncUpdates(run_next_test);
+        promiseAsyncUpdates().then(run_next_test);
       },
       handleError: function handleError(aResultCode) {
         do_throw("Unexpected error: " + aResultCode);
       }
     });
   }));
 }
 
@@ -753,17 +753,17 @@ function test_handleCompletion_called_wh
       callbackCountSuccess++;
     },
     handleError: function handleError(aResultCode, aPlaceInfo) {
       callbackCountFailure++;
     },
     handleCompletion: function handleCompletion() {
       do_check_eq(callbackCountSuccess, EXPECTED_COUNT_SUCCESS);
       do_check_eq(callbackCountFailure, EXPECTED_COUNT_FAILURE);
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     },
   });
 }
 
 function test_add_visit()
 {
   const VISIT_TIME = Date.now() * 1000;
   let place = {
@@ -815,17 +815,17 @@ function test_add_visit()
 
       // Check mozIVisitInfo properties.
       do_check_true(visit.visitId > 0);
       do_check_true(visit.sessionId > 0);
     }
 
     // If we have had all of our callbacks, continue running tests.
     if (++callbackCount == place.visits.length) {
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }
   }));
 }
 
 function test_properties_saved()
 {
   // Check each transition type to make sure it is saved properly.
   let places = [];
@@ -910,17 +910,17 @@ function test_properties_saved()
     stmt.params.page_url = uri.spec;
     stmt.params.title = aPlaceInfo.title;
     do_check_true(stmt.executeStep());
     do_check_eq(stmt.row.count, EXPECTED_COUNT);
     stmt.finalize();
 
     // If we have had all of our callbacks, continue running tests.
     if (++callbackCount == places.length) {
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }
   }));
 }
 
 function test_guid_saved()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN + "test_guid_saved"),
@@ -932,17 +932,17 @@ function test_guid_saved()
   do_check_valid_places_guid(place.guid);
   do_check_false(gGlobalHistory.isVisited(place.uri));
 
   gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
     let uri = aPlaceInfo.uri;
     do_check_true(gGlobalHistory.isVisited(uri));
     do_check_eq(aPlaceInfo.guid, place.guid);
     do_check_guid_for_uri(uri, place.guid);
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_referrer_saved()
 {
   let places = [
     { uri: NetUtil.newURI(TEST_DOMAIN + "test_referrer_saved/referrer"),
       visits: [
@@ -986,17 +986,17 @@ function test_referrer_saved()
       ") "
     );
     stmt.params.page_url = uri.spec;
     stmt.params.referrer = visit.referrerURI.spec;
     do_check_true(stmt.executeStep());
     do_check_eq(stmt.row.count, 1);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_sessionId_saved()
 {
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN + "test_sessionId_saved"),
     visits: [
@@ -1020,17 +1020,17 @@ function test_sessionId_saved()
       "AND session = :session_id "
     );
     stmt.params.page_url = uri.spec;
     stmt.params.session_id = visit.sessionId;
     do_check_true(stmt.executeStep());
     do_check_eq(stmt.row.count, 1);
     stmt.finalize();
 
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   }));
 }
 
 function test_guid_change_saved()
 {
   // First, add a visit for it.
   let place = {
     uri: NetUtil.newURI(TEST_DOMAIN + "test_guid_change_saved"),
@@ -1043,17 +1043,17 @@ function test_guid_change_saved()
   gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
 
     // Then, change the guid with visits.
     place.guid = "_GUIDCHANGE_";
     place.visits = [new VisitInfo()];
     gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
       do_check_guid_for_uri(place.uri, place.guid);
 
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }));
   }));
 }
 
 function test_title_change_saved()
 {
   // First, add a visit for it.
   let place = {
@@ -1080,17 +1080,17 @@ function test_title_change_saved()
         do_check_title_for_uri(place.uri, place.title);
 
         // Lastly, check that the title is cleared if we set it to null.
         place.title = null;
         place.visits = [new VisitInfo()];
         gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
           do_check_title_for_uri(place.uri, place.title);
 
-          waitForAsyncUpdates(run_next_test);
+          promiseAsyncUpdates().then(run_next_test);
         }));
       }));
     }));
   }));
 }
 
 function test_no_title_does_not_clear_title()
 {
@@ -1107,17 +1107,17 @@ function test_no_title_does_not_clear_ti
 
   gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
     // Now, make sure that not specifying a title does not clear it.
     delete place.title;
     place.visits = [new VisitInfo()];
     gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
       do_check_title_for_uri(place.uri, TITLE);
 
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }));
   }));
 }
 
 function test_title_change_notifies()
 {
   // There are three cases to test.  The first case is to make sure we do not
   // get notified if we do not specify a title.
@@ -1150,17 +1150,17 @@ function test_title_change_notifies()
         // change an existing place.
         observer.expectedTitle = place.title = "title 2";
         place.visits = [new VisitInfo()];
         gHistory.updatePlaces(place);
         break;
       case 2:
         PlacesUtils.history.removeObserver(silentObserver);
         PlacesUtils.history.removeObserver(observer);
-        waitForAsyncUpdates(run_next_test);
+        promiseAsyncUpdates().then(run_next_test);
     };
   });
   PlacesUtils.history.addObserver(observer, false);
   gHistory.updatePlaces(place);
 }
 
 function test_visit_notifies()
 {
@@ -1173,17 +1173,17 @@ function test_visit_notifies()
       new VisitInfo(),
     ],
   };
   do_check_false(gGlobalHistory.isVisited(place.uri));
 
   let callbackCount = 0;
   let finisher = function() {
     if (++callbackCount == 2) {
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }
   }
   let visitObserver = new VisitObserver(place.uri, place.guid,
                                         function(aVisitDate,
                                                  aTransitionType) {
     let visit = place.visits[0];
     do_check_eq(visit.visitDate, aVisitDate);
     do_check_eq(visit.transitionType, aTransitionType);
@@ -1233,17 +1233,17 @@ function test_referrer_sessionId_persist
     place.visits[0].referrerURI = referrerPlace.uri;
 
     do_check_false(gGlobalHistory.isVisited(place.uri));
     gHistory.updatePlaces(place, expectHandleResult(function(aPlaceInfo) {
       do_check_true(gGlobalHistory.isVisited(place.uri));
 
       do_check_eq(aPlaceInfo.visits[0].sessionId, sessionId);
 
-      waitForAsyncUpdates(run_next_test);
+      promiseAsyncUpdates().then(run_next_test);
     }));
   }));
 }
 
 // test with empty mozIVisitInfoCallback object
 function test_callbacks_not_supplied()
 {
   const URLS = [
@@ -1266,33 +1266,33 @@ function test_callbacks_not_supplied()
       // NetUtil.newURI() can throw if e.g. our app knows about imap://
       // but the account is not set up and so the URL is invalid for us.
       // Note this in the log but ignore as it's not the subject of this test.
       do_log_info("Could not construct URI for '" + url + "'; ignoring");
     }
   });
   
   gHistory.updatePlaces(places, {});
-  waitForAsyncUpdates(run_next_test);
+  promiseAsyncUpdates().then(run_next_test);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 //// Test Runner
 
 [
   test_interface_exists,
   test_invalid_uri_throws,
   test_invalid_places_throws,
   test_invalid_guid_throws,
   test_no_visits_throws,
   test_add_visit_no_date_throws,
   test_add_visit_no_transitionType_throws,
   test_add_visit_invalid_transitionType_throws,
-  // Note: all asynchronous tests (every test below this point) should
-  // waitForAsyncUpdates before calling run_next_test.
+  // Note: all asynchronous tests (every test below this point) should wait for
+  // async updates before calling run_next_test.
   test_non_addable_uri_errors,
   test_duplicate_guid_errors,
   test_invalid_referrerURI_ignored,
   test_nonnsIURI_referrerURI_ignored,
   test_invalid_sessionId_ignored,
   test_unstored_sessionId_ignored,
   test_old_referrer_ignored,
   test_place_id_ignored,

--- a/toolkit/components/places/tests/unit/test_bookmarks_html.js
+++ b/toolkit/components/places/tests/unit/test_bookmarks_html.js
@@ -103,25 +103,25 @@ add_test(function setup() {
   // This test must be the first one, since it setups the new bookmarks.html.
   // Test importing a pre-Places canonical bookmarks file.
   // 1. import bookmarks.preplaces.html
   // 2. run the test-suite
   // Note: we do not empty the db before this import to catch bugs like 380999
   try {
     BookmarkHTMLUtils.importFromFile(gBookmarksFileOld, true, function(success) {
       if (success) {
-        waitForAsyncUpdates(function () {
+        promiseAsyncUpdates().then(function () {
           testImportedBookmarks();
 
           // Prepare for next tests.
           try {
             exporter.exportHTMLToFile(gBookmarksFileNew);
           } catch(ex) { do_throw("couldn't export to file: " + ex); }
 
-          waitForAsyncUpdates(function () {
+          promiseAsyncUpdates().then(function () {
             remove_all_bookmarks();
             run_next_test();
           });
         });
       } else {
         do_throw("couldn't import legacy bookmarks file.");
       }
     });
@@ -132,20 +132,20 @@ add_test(function test_import_new()
 {
   // Test importing a Places bookmarks.html file.
   // 1. import bookmarks.exported.html
   // 2. run the test-suite
 
   try {
     BookmarkHTMLUtils.importFromFile(gBookmarksFileNew, true, function(success) {
       if (success) {
-        waitForAsyncUpdates(function () {
+        promiseAsyncUpdates().then(function () {
           testImportedBookmarks();
 
-          waitForAsyncUpdates(function () {
+          promiseAsyncUpdates().then(function () {
             remove_all_bookmarks();
             run_next_test();
           });
         });
       } else {
         do_throw("couldn't import the exported file.");
       }
     });
@@ -179,28 +179,28 @@ add_test(function test_emptytitle_export
           exporter.exportHTMLToFile(gBookmarksFileNew);
         } catch(ex) { do_throw("couldn't export to file: " + ex); }
 
         remove_all_bookmarks();
 
         try {
           BookmarkHTMLUtils.importFromFile(gBookmarksFileNew, true, function(success) {
            if (success) {
-              waitForAsyncUpdates(function () {
+              promiseAsyncUpdates().then(function () {
                 testImportedBookmarks();
 
                 // Cleanup.
                 test_bookmarks.unfiled.pop();
                 PlacesUtils.bookmarks.removeItem(id);
 
                 try {
                   exporter.exportHTMLToFile(gBookmarksFileNew);
                 } catch(ex) { do_throw("couldn't export to file: " + ex); }
 
-                waitForAsyncUpdates(function () {
+                promiseAsyncUpdates().then(function () {
                   remove_all_bookmarks();
                   run_next_test();
                 });
               });
             } else {
               do_throw("couldn't import the exported file.");
             }
           });
@@ -263,28 +263,28 @@ add_test(function test_import_chromefavi
 
                   remove_all_bookmarks();
 
                   try {
                     BookmarkHTMLUtils.importFromFile(gBookmarksFileNew, true, function(success) {
                      if (!success) {
                         do_throw("couldn't import the exported file.");
                       }
-                      waitForAsyncUpdates(function () {
+                      promiseAsyncUpdates().then(function () {
                         testImportedBookmarks();
 
                         // Cleanup.
                         test_bookmarks.unfiled.pop();
                         PlacesUtils.bookmarks.removeItem(id);
 
                         try {
                           exporter.exportHTMLToFile(gBookmarksFileNew);
                         } catch(ex) { do_throw("couldn't export to file: " + ex); }
 
-                        waitForAsyncUpdates(function () {
+                        promiseAsyncUpdates().then(function () {
                           remove_all_bookmarks();
                           run_next_test();
                         });
                       });
                     });
                   } catch(ex) { do_throw("couldn't import the exported file: " + ex); }
                 });
             });
@@ -307,20 +307,20 @@ add_test(function test_import_ontop()
     BookmarkHTMLUtils.importFromFile(gBookmarksFileNew, true, function(success) {
       if (success) {
         try {
           exporter.exportHTMLToFile(gBookmarksFileNew);
         } catch(ex) { do_throw("couldn't export to file: " + ex); }
         try {
           BookmarkHTMLUtils.importFromFile(gBookmarksFileNew, true, function(success) {
             if (success) {
-              waitForAsyncUpdates(function () {
+              promiseAsyncUpdates().then(function () {
                 testImportedBookmarks();
 
-                waitForAsyncUpdates(function () {
+                promiseAsyncUpdates().then(function () {
                   remove_all_bookmarks();
                   run_next_test();
                 });
               });
             } else {
               do_throw("couldn't import the exported file.");
             }
           });

--- a/toolkit/components/places/tests/unit/test_browserhistory.js
+++ b/toolkit/components/places/tests/unit/test_browserhistory.js
@@ -57,17 +57,17 @@ add_test(function test_removePages()
     // Check the annotation on the non-bookmarked page does not exist anymore.
     try {
       PlacesUtils.annotations.getPageAnnotation(pages[ANNO_INDEX], ANNO_NAME);
       do_throw("did not expire expire_never anno on a not bookmarked item");
     } catch(ex) {}
   
     // Cleanup.
     PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.unfiledBookmarksFolderId);
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   });
 });
 
 add_test(function test_removePagesByTimeframe()
 {
   let visits = [];
   let startDate = Date.now() * 1000;
   for (let i = 0; i < 10; i++) {

--- a/toolkit/components/places/tests/unit/test_download_history.js
+++ b/toolkit/components/places/tests/unit/test_download_history.js
@@ -71,28 +71,28 @@ function run_test()
   run_next_test();
 }
 
 add_test(function test_dh_is_from_places()
 {
   // Test that this nsIDownloadHistory is the one places implements.
   do_check_true(gDownloadHistory instanceof Ci.mozIAsyncHistory);
 
-  waitForClearHistory(run_next_test);
+  promiseClearHistory().then(run_next_test);
 });
 
 add_test(function test_dh_addDownload()
 {
   waitForOnVisit(function DHAD_onVisit(aURI) {
     do_check_true(aURI.equals(DOWNLOAD_URI));
 
     // Verify that the URI is already available in results at this time.
     uri_in_db(DOWNLOAD_URI, true);
 
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   });
 
   gDownloadHistory.addDownload(DOWNLOAD_URI, null, Date.now() * 1000);
 });
 
 add_test(function test_dh_addDownload_referrer()
 {
   waitForOnVisit(function DHAD_prepareReferrer(aURI, aVisitID) {
@@ -102,17 +102,17 @@ add_test(function test_dh_addDownload_re
     waitForOnVisit(function DHAD_onVisit(aURI, aVisitID, aTime, aSessionID,
                                               aReferringID) {
       do_check_true(aURI.equals(DOWNLOAD_URI));
       do_check_eq(aReferringID, referrerVisitId);
 
       // Verify that the URI is already available in results at this time.
       uri_in_db(DOWNLOAD_URI, true);
 
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
 
     gDownloadHistory.addDownload(DOWNLOAD_URI, REFERRER_URI, Date.now() * 1000);
   });
 
   // Note that we don't pass the optional callback argument here because we must
   // ensure that we receive the onVisit notification before we call addDownload.
   gHistory.updatePlaces({
@@ -137,17 +137,17 @@ add_test(function test_dh_addDownload_pr
     // test is based on the assumption that visit notifications are received
     // in the same order of the addDownload calls, which is currently true
     // because database access is serialized on the same worker thread.
     do_check_true(aURI.equals(DOWNLOAD_URI));
 
     uri_in_db(DOWNLOAD_URI, true);
     uri_in_db(PRIVATE_URI, false);
 
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   });
 
   let pb = Cc["@mozilla.org/privatebrowsing;1"]
            .getService(Ci.nsIPrivateBrowsingService);
   Services.prefs.setBoolPref("browser.privatebrowsing.keep_current_session",
                              true);
   pb.privateBrowsingEnabled = true;
   gDownloadHistory.addDownload(PRIVATE_URI, REFERRER_URI, Date.now() * 1000);
@@ -166,17 +166,17 @@ add_test(function test_dh_addDownload_di
     // test is based on the assumption that visit notifications are received in
     // the same order of the addDownload calls, which is currently true because
     // database access is serialized on the same worker thread.
     do_check_true(aURI.equals(DOWNLOAD_URI));
 
     uri_in_db(DOWNLOAD_URI, true);
     uri_in_db(PRIVATE_URI, false);
 
-    waitForClearHistory(run_next_test);
+    promiseClearHistory().then(run_next_test);
   });
 
   Services.prefs.setBoolPref("places.history.enabled", false);
   gDownloadHistory.addDownload(PRIVATE_URI, REFERRER_URI, Date.now() * 1000);
 
   // The addDownload functions calls CanAddURI synchronously, thus we can set
   // the preference back to true immediately (not all apps enable places by
   // default).
@@ -202,17 +202,17 @@ add_test(function test_dh_details()
   let destinationFileNameSet = false;
 
   function checkFinished()
   {
     if (titleSet && destinationFileUriSet && destinationFileNameSet) {
       PlacesUtils.annotations.removeObserver(annoObserver);
       PlacesUtils.history.removeObserver(historyObserver);
 
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     }
   };
 
   let annoObserver = {
     onPageAnnotationSet: function AO_onPageAnnotationSet(aPage, aName)
     {
       if (aPage.equals(SOURCE_URI)) {
         let value = PlacesUtils.annotations.getPageAnnotation(aPage, aName);

--- a/toolkit/components/places/tests/unit/test_frecency.js
+++ b/toolkit/components/places/tests/unit/test_frecency.js
@@ -68,17 +68,18 @@ AutoCompleteInput.prototype = {
       return this;
 
     throw Components.results.NS_ERROR_NO_INTERFACE;
   }
 }
 
 function ensure_results(uris, searchTerm)
 {
-  waitForAsyncUpdates(ensure_results_internal, this, arguments);
+  promiseAsyncUpdates().then(function () ensure_results_internal(uris,
+                                                                 searchTerm));
 }
 
 function ensure_results_internal(uris, searchTerm)
 {
   var controller = Components.classes["@mozilla.org/autocomplete/controller;1"].
                    getService(Components.interfaces.nsIAutoCompleteController);
 
   // Make an AutoCompleteInput that uses our searches
@@ -272,13 +273,13 @@ function run_test() {
   do_test_pending();
   next_test();
 }
 
 function next_test() {
   if (tests.length) {
     remove_all_bookmarks();
     let test = tests.shift();
-    waitForClearHistory(test);
+    promiseClearHistory().then(test);
   }
   else
     do_test_finished();
 }

--- a/toolkit/components/places/tests/unit/test_history_removeAllPages.js
+++ b/toolkit/components/places/tests/unit/test_history_removeAllPages.js
@@ -21,17 +21,17 @@ let historyObserver = {
 
     // check browserHistory returns no entries
     do_check_eq(0, PlacesUtils.history.hasHistoryEntries);
 
     Services.obs.addObserver(function observeExpiration(aSubject, aTopic, aData)
     {
       Services.obs.removeObserver(observeExpiration, aTopic, false);
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         // Check that frecency for not cleared items (bookmarks) has been converted
         // to -MAX(visit_count, 1), so we will be able to recalculate frecency
         // starting from most frecent bookmarks.
         stmt = mDBConn.createStatement(
           "SELECT h.id FROM moz_places h WHERE h.frecency > 0 ");
         do_check_false(stmt.executeStep());
         stmt.finalize();
 
@@ -155,13 +155,10 @@ function continue_test() {
   PlacesUtils.history.addVisit(uri("http://typed.mozilla.org/"), Date.now(),
                                null, PlacesUtils.history.TRANSITION_BOOKMARK,
                                false, 0);
 
   // Add a last page and wait for its frecency.
   PlacesUtils.history.addVisit(uri("http://frecency.mozilla.org/"), Date.now(),
                                null, Ci.nsINavHistoryService.TRANSITION_LINK,
                                false, 0);
-  waitForFrecency("http://frecency.mozilla.org/", function (aFrecency) aFrecency > 0,
-                  function () {
-                    PlacesUtils.bhistory.removeAllPages();
-                  }, this, []);
+  promiseAsyncUpdates().then(function () PlacesUtils.bhistory.removeAllPages());
 }

--- a/toolkit/components/places/tests/unit/test_hosts_triggers.js
+++ b/toolkit/components/places/tests/unit/test_hosts_triggers.js
@@ -105,17 +105,17 @@ function test_moz_hosts_update()
 }
 
 function test_remove_places()
 {
   for (let idx in urls) {
     PlacesUtils.history.removePage(urls[idx].uri);
   }
 
-  waitForClearHistory(function (){
+  promiseClearHistory().then(function (){
     for (let idx in urls) {
       do_check_false(isHostInMozHosts(urls[idx].uri, urls[idx].typed, urls[idx].prefix));
     }
     run_next_test();
   });
 }
 
 function test_bookmark_changes()
@@ -127,32 +127,32 @@ function test_bookmark_changes()
                                                      PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                      "bookmark title");
 
   do_check_true(isHostInMozPlaces(testUri));
 
   // Change the hostname
   PlacesUtils.bookmarks.changeBookmarkURI(itemId, NetUtil.newURI(NEW_URL));
 
-  waitForClearHistory(function (){
+  promiseClearHistory().then(function (){
     let newUri = NetUtil.newURI(NEW_URL);
     do_check_true(isHostInMozPlaces(newUri));
     do_check_true(isHostInMozHosts(newUri, false, null));
     do_check_false(isHostInMozHosts(NetUtil.newURI("http://test.mozilla.org"), false, null));
     run_next_test();
   });
 }
 
 function test_bookmark_removal()
 {
   let itemId = PlacesUtils.bookmarks.getIdForItemAt(PlacesUtils.unfiledBookmarksFolderId,
                                                     PlacesUtils.bookmarks.DEFAULT_INDEX);
   let newUri = NetUtil.newURI(NEW_URL);
   PlacesUtils.bookmarks.removeItem(itemId);
-  waitForClearHistory(function (){
+  promiseClearHistory().then(function (){
     do_check_false(isHostInMozHosts(newUri, false, null));
     run_next_test();
   });
 }
 
 function test_moz_hosts_typed_update()
 {
   const TEST_URI = NetUtil.newURI("http://typed.mozilla.com");
@@ -193,26 +193,26 @@ function test_moz_hosts_www_remove()
       },
       handleError: function () {
         do_throw("gHistory.updatePlaces() failed");
       },
       handleCompletion: function () {
         PlacesUtils.history.removePage(aURIToRemove);
         let prefix = /www/.test(aURIToKeep.spec) ? "www." : null;
         do_check_true(isHostInMozHosts(aURIToKeep, false, prefix));
-        waitForClearHistory(aCallback);
+        promiseClearHistory().then(aCallback);
       }
     });
   }
 
   const TEST_URI = NetUtil.newURI("http://rem.mozilla.com");
   const TEST_WWW_URI = NetUtil.newURI("http://www.rem.mozilla.com");
   test_removal(TEST_URI, TEST_WWW_URI, function() {
     test_removal(TEST_WWW_URI, TEST_URI, function() {
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 //// Test Runner
 
 [

--- a/toolkit/components/places/tests/unit/test_isURIVisited.js
+++ b/toolkit/components/places/tests/unit/test_isURIVisited.js
@@ -65,17 +65,17 @@ function step()
           handleCompletion: function () {
             do_log_info("Added visit to " + uri.spec);
 
             history.isURIVisited(uri, function (aURI, aIsVisited) {
               do_check_true(uri.equals(aURI));
               let checker = SCHEMES[scheme] ? do_check_true : do_check_false;
               checker(aIsVisited);
 
-              waitForClearHistory(function () {
+              promiseClearHistory().then(function () {
                 history.isURIVisited(uri, function(aURI, aIsVisited) {
                   do_check_true(uri.equals(aURI));
                   do_check_false(aIsVisited);
                   gRunner.next();
                 });
               });
             });
           },

--- a/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
+++ b/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
@@ -168,17 +168,17 @@ add_test(function check_history_query() 
     }, null);
     do_check_false(resultObserver.inBatchMode);
 
     // nsINavHistoryResultObserver.containerClosed
     root.containerOpen = false;
     do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);
     result.removeObserver(resultObserver);
     resultObserver.reset();
-    waitForAsyncUpdates(run_next_test);
+    promiseAsyncUpdates().then(run_next_test);
   });
 });
 
 add_test(function check_bookmarks_query() {
   var options = histsvc.getNewQueryOptions();
   var query = histsvc.getNewQuery();
   query.setFolders([bmsvc.bookmarksMenuFolder], 1);
   var result = histsvc.executeQuery(query, options);
@@ -238,17 +238,17 @@ add_test(function check_bookmarks_query(
   }, null);
   do_check_false(resultObserver.inBatchMode);
 
   // nsINavHistoryResultObserver.containerClosed
   root.containerOpen = false;
   do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);
   result.removeObserver(resultObserver);
   resultObserver.reset();
-  waitForAsyncUpdates(run_next_test);
+  promiseAsyncUpdates().then(run_next_test);
 });
 
 add_test(function check_mixed_query() {
   var options = histsvc.getNewQueryOptions();
   var query = histsvc.getNewQuery();
   query.onlyBookmarked = true;
   var result = histsvc.executeQuery(query, options);
   result.addObserver(resultObserver, false);
@@ -273,10 +273,10 @@ add_test(function check_mixed_query() {
   }, null);
   do_check_false(resultObserver.inBatchMode);
 
   // nsINavHistoryResultObserver.containerClosed
   root.containerOpen = false;
   do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);
   result.removeObserver(resultObserver);
   resultObserver.reset();
-  waitForAsyncUpdates(run_next_test);
+  promiseAsyncUpdates().then(run_next_test);
 });

--- a/toolkit/components/places/tests/unit/test_removeVisitsByTimeframe.js
+++ b/toolkit/components/places/tests/unit/test_removeVisitsByTimeframe.js
@@ -21,17 +21,17 @@ var gTests = [
       for (let i = 0; i < 10; i++) {
         histsvc.addVisit(TEST_URI,
                          NOW - 1000 - i,
                          null,
                          histsvc.TRANSITION_TYPED,
                          false,
                          0);
       }
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run, this);
     },
     continue_run: function () {
       print("Remove visits using timerange outside the URI's visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(TEST_URL));
@@ -49,17 +49,17 @@ var gTests = [
         do_check_eq(visitTime, NOW - 1000 - i);
       }
       resultRoot.containerOpen = false;
 
       print("nsIGlobalHistory2.isVisited should return true.");
       do_check_true(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                     isVisited(TEST_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be positive.")
         do_check_true(frecencyForUrl(TEST_URI) > 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -76,17 +76,17 @@ var gTests = [
       }
 
       print("Bookmark the URI.");
       bmsvc.insertBookmark(bmsvc.unfiledBookmarksFolder,
                            TEST_URI,
                            bmsvc.DEFAULT_INDEX,
                            "bookmark title");
 
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove visits using timerange outside the URI's visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(TEST_URL));
@@ -104,17 +104,17 @@ var gTests = [
         do_check_eq(visitTime, NOW - 1000 - i);
       }
       resultRoot.containerOpen = false;
 
       print("nsIGlobalHistory2.isVisited should return true.");
       do_check_true(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                     isVisited(TEST_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be positive.")
         do_check_true(frecencyForUrl(TEST_URI) > 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -124,17 +124,17 @@ var gTests = [
       for (let i = 0; i < 10; i++) {
         histsvc.addVisit(TEST_URI,
                          NOW - i,
                          null,
                          histsvc.TRANSITION_TYPED,
                          false,
                          0);
       }
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove the 5 most recent visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 4, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(TEST_URL));
@@ -153,17 +153,17 @@ var gTests = [
         do_check_eq(visitTime, NOW - i - 5);
       }
       resultRoot.containerOpen = false;
 
       print("nsIGlobalHistory2.isVisited should return true.");
       do_check_true(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                     isVisited(TEST_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be positive.")
         do_check_true(frecencyForUrl(TEST_URI) > 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -179,17 +179,17 @@ var gTests = [
                          0);
       }
 
       print("Bookmark the URI.");
       bmsvc.insertBookmark(bmsvc.unfiledBookmarksFolder,
                            TEST_URI,
                            bmsvc.DEFAULT_INDEX,
                            "bookmark title");
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove the 5 most recent visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 4, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(TEST_URL));
@@ -208,17 +208,17 @@ var gTests = [
         do_check_eq(visitTime, NOW - i - 5);
       }
       resultRoot.containerOpen = false;
 
       print("nsIGlobalHistory2.isVisited should return true.");
       do_check_true(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                     isVisited(TEST_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be positive.")
         do_check_true(frecencyForUrl(TEST_URI) > 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -228,17 +228,17 @@ var gTests = [
       for (let i = 0; i < 10; i++) {
         histsvc.addVisit(TEST_URI,
                          NOW - i,
                          null,
                          histsvc.TRANSITION_TYPED,
                          false,
                          0);
       }
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove all visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
       print("URI should no longer exist in moz_places.");
       do_check_false(page_in_database(TEST_URL));
@@ -267,17 +267,17 @@ var gTests = [
       for (let i = 0; i < 10; i++) {
         histsvc.addVisit(PLACE_URI,
                          NOW - i,
                          null,
                          histsvc.TRANSITION_TYPED,
                          false,
                          0);
       }
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove all visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(PLACE_URL));
@@ -291,17 +291,17 @@ var gTests = [
       resultRoot.containerOpen = true;
       do_check_eq(resultRoot.childCount, 0);
       resultRoot.containerOpen = false;
 
       print("nsIGlobalHistory2.isVisited should return false.");
       do_check_false(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                        isVisited(PLACE_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be zero.")
         do_check_eq(frecencyForUrl(PLACE_URL), 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -317,17 +317,17 @@ var gTests = [
                          0);
       }
 
       print("Bookmark the URI.");
       bmsvc.insertBookmark(bmsvc.unfiledBookmarksFolder,
                            TEST_URI,
                            bmsvc.DEFAULT_INDEX,
                            "bookmark title");
-      waitForAsyncUpdates(this.continue_run, this);
+      promiseAsyncUpdates().then(this.continue_run.bind(this));
     },
     continue_run: function () {
       print("Remove all visits.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
       print("URI should still exist in moz_places.");
       do_check_true(page_in_database(TEST_URL));
@@ -344,17 +344,17 @@ var gTests = [
 
       print("nsIGlobalHistory2.isVisited should return false.");
       do_check_false(histsvc.QueryInterface(Ci.nsIGlobalHistory2).
                        isVisited(TEST_URI));
 
       print("nsINavBookmarksService.isBookmarked should return true.");
       do_check_true(bmsvc.isBookmarked(TEST_URI));
 
-      waitForAsyncUpdates(function () {
+      promiseAsyncUpdates().then(function () {
         print("Frecency should be negative.")
         do_check_true(frecencyForUrl(TEST_URI) < 0);
         run_next_test();
       });
     }
   },
 
   {
@@ -367,17 +367,17 @@ var gTests = [
                   visitDate: NOW }],
                 this.continue_run.bind(this));
     },
     continue_run: function () {
       do_log_info("Remove newer visit.");
       histsvc.QueryInterface(Ci.nsIBrowserHistory).
         removeVisitsByTimeframe(NOW - 10, NOW);
 
-      waitForAsyncUpdates(function() {
+      promiseAsyncUpdates().then(function() {
         do_log_info("URI should still exist in moz_places.");
         do_check_true(page_in_database(TEST_URL));
         do_log_info("Frecency should be zero.")
         do_check_eq(frecencyForUrl(TEST_URI), 0);
         run_next_test();
       });
     }
   }
@@ -390,17 +390,17 @@ function run_test()
   do_test_pending();
   run_next_test();
 }
 
 function run_next_test() {
   if (gTests.length) {
     let test = gTests.shift();
     print("\n ***Test: " + test.desc);
-    waitForClearHistory(function() {
+    promiseClearHistory().then(function() {
       remove_all_bookmarks();
       DBConn().executeSimpleSQL("DELETE FROM moz_places");
       test.run.call(test);
     });
   }
   else {
     do_test_finished();
   }

--- a/toolkit/components/places/tests/unit/test_result_sort.js
+++ b/toolkit/components/places/tests/unit/test_result_sort.js
@@ -116,17 +116,17 @@ function run_test() {
   // XXXtodo:  test lastModified sort
   
   // test live update
   annosvc.setItemAnnotation(id1, "testAnno", "c", 0, 0);
   checkOrder(id1, id3, id2);
 
   // Add a visit, then check frecency ordering.
   add_visit(NetUtil.newURI("http://foo.tld/b"));
-  waitForAsyncUpdates(function () {
+  promiseAsyncUpdates().then(function () {
     result.sortingMode = NHQO.SORT_BY_FRECENCY_DESCENDING;
     checkOrder(id2, id3, id1);
     result.sortingMode = NHQO.SORT_BY_FRECENCY_ASCENDING;
     checkOrder(id1, id3, id2);
 
     root.containerOpen = false;
     do_test_finished();
   });

--- a/toolkit/components/places/tests/unit/test_telemetry.js
+++ b/toolkit/components/places/tests/unit/test_telemetry.js
@@ -55,17 +55,17 @@ function run_test() {
   PlacesUtils.annotations.setPageAnnotation(uri, "test-anno", content, 0,
                                             PlacesUtils.annotations.EXPIRE_NEVER);
 
   // Request to gather telemetry data.
   Cc["@mozilla.org/places/categoriesStarter;1"]
     .getService(Ci.nsIObserver)
     .observe(null, "gather-telemetry", null);
 
-  waitForAsyncUpdates(continue_test);
+  promiseAsyncUpdates().then(continue_test);
 }
 
 function continue_test() {
   // Test expiration probes.
   for (let i = 0; i < 2; i++) {
     PlacesUtils.history.addVisit(NetUtil.newURI("http://" +  i + ".moz.org/"),
                                  Date.now(), null,
                                  PlacesUtils.history.TRANSITION_TYPED, false, 0);

--- a/toolkit/components/places/tests/unit/test_update_frecency_after_delete.js
+++ b/toolkit/components/places/tests/unit/test_update_frecency_after_delete.js
@@ -16,58 +16,58 @@ add_test(function removed_bookmark()
 {
   do_log_info("After removing bookmark, frecency of bookmark's URI should be " +
               "zero if URI is unvisited and no longer bookmarked.");
   const TEST_URI = NetUtil.newURI("http://example.com/1");
   let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     PlacesUtils.bookmarks.removeItem(id);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("Unvisited URI no longer bookmarked => frecency should = 0");
       do_check_eq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function removed_but_visited_bookmark()
 {
   do_log_info("After removing bookmark, frecency of bookmark's URI should " +
               "not be zero if URI is visited.");
   const TEST_URI = NetUtil.newURI("http://example.com/1");
   let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     visit(TEST_URI);
     PlacesUtils.bookmarks.removeItem(id);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("*Visited* URI no longer bookmarked => frecency should != 0");
       do_check_neq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function remove_bookmark_still_bookmarked()
 {
   do_log_info("After removing bookmark, frecency of bookmark's URI should ",
               "not be zero if URI is still bookmarked.");
@@ -75,58 +75,58 @@ add_test(function remove_bookmark_still_
   let id1 = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                  TEST_URI,
                                                  PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                  "bookmark 1 title");
   let id2 = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                  TEST_URI,
                                                  PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                  "bookmark 2 title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     PlacesUtils.bookmarks.removeItem(id1);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("URI still bookmarked => frecency should != 0");
       do_check_neq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function cleared_parent_of_visited_bookmark()
 {
   do_log_info("After removing all children from bookmark's parent, frecency " +
               "of bookmark's URI should not be zero if URI is visited.");
   const TEST_URI = NetUtil.newURI("http://example.com/1");
   let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     visit(TEST_URI);
     PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.unfiledBookmarksFolderId);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       do_log_info("*Visited* URI no longer bookmarked => frecency should != 0");
       do_check_neq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 add_test(function cleared_parent_of_bookmark_still_bookmarked()
 {
   do_log_info("After removing all children from bookmark's parent, frecency " +
               "of bookmark's URI should not be zero if URI is still " +
@@ -136,30 +136,30 @@ add_test(function cleared_parent_of_book
                                                  TEST_URI,
                                                  PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                  "bookmark 1 title");
 
   let id2 = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                 TEST_URI,
                                                 PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                 "bookmark 2 title");
-  waitForAsyncUpdates(function ()
+  promiseAsyncUpdates().then(function ()
   {
     do_log_info("Bookmarked => frecency of URI should be != 0");
     do_check_neq(frecencyForUrl(TEST_URI), 0);
 
     PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.unfiledBookmarksFolderId);
 
-    waitForAsyncUpdates(function ()
+    promiseAsyncUpdates().then(function ()
     {
       // URI still bookmarked => frecency should != 0.
       do_check_neq(frecencyForUrl(TEST_URI), 0);
 
       remove_all_bookmarks();
-      waitForClearHistory(run_next_test);
+      promiseClearHistory().then(run_next_test);
     });
   });
 });
 
 ///////////////////////////////////////////////////////////////////////////////
 
 /**
  * Adds a visit for aURI.