Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

19 files changed, 5172 insertions, 0 deletions

diff --git a/toolkit/components/places/tests/history/head_history.js b/toolkit/components/places/tests/history/head_history.js
new file mode 100644
index 0000000000..4adce13cce
--- /dev/null
+++ b/toolkit/components/places/tests/history/head_history.js
@@ -0,0 +1,13 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// Import common head.
+{
+  /* import-globals-from ../head_common.js */
+  let commonFile = do_get_file("../head_common.js", false);
+  let uri = Services.io.newFileURI(commonFile);
+  Services.scriptloader.loadSubScript(uri.spec, this);
+}
diff --git a/toolkit/components/places/tests/history/test_async_history_api.js b/toolkit/components/places/tests/history/test_async_history_api.js
new file mode 100644
index 0000000000..d23e947c7e
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_async_history_api.js
@@ -0,0 +1,1343 @@
+/**
+ * This file tests the async history API exposed by mozIAsyncHistory.
+ */
+
+// Globals
+
+XPCOMUtils.defineLazyServiceGetter(
+  this,
+  "asyncHistory",
+  "@mozilla.org/browser/history;1",
+  "mozIAsyncHistory"
+);
+
+const TEST_DOMAIN = "http://mozilla.org/";
+const URI_VISIT_SAVED = "uri-visit-saved";
+const RECENT_EVENT_THRESHOLD = 15 * 60 * 1000000;
+
+// Helpers
+/**
+ * Object that represents a mozIVisitInfo object.
+ *
+ * @param [optional] aTransitionType
+ *        The transition type of the visit.  Defaults to TRANSITION_LINK if not
+ *        provided.
+ * @param [optional] aVisitTime
+ *        The time of the visit.  Defaults to now if not provided.
+ */
+function VisitInfo(aTransitionType, aVisitTime) {
+  this.transitionType =
+    aTransitionType === undefined ? TRANSITION_LINK : aTransitionType;
+  this.visitDate = aVisitTime || Date.now() * 1000;
+}
+
+function promiseUpdatePlaces(aPlaces, aOptions = {}) {
+  return new Promise((resolve, reject) => {
+    asyncHistory.updatePlaces(
+      aPlaces,
+      Object.assign(
+        {
+          _errors: [],
+          _results: [],
+          handleError(aResultCode, aPlace) {
+            this._errors.push({ resultCode: aResultCode, info: aPlace });
+          },
+          handleResult(aPlace) {
+            this._results.push(aPlace);
+          },
+          handleCompletion(resultCount) {
+            resolve({
+              errors: this._errors,
+              results: this._results,
+              resultCount,
+            });
+          },
+        },
+        aOptions
+      )
+    );
+  });
+}
+
+/**
+ * Listens for a title change notification, and calls aCallback when it gets it.
+ */
+class TitleChangedObserver {
+  /**
+   * Constructor.
+   *
+   * @param aURI
+   *        The URI of the page we expect a notification for.
+   * @param aExpectedTitle
+   *        The expected title of the URI we expect a notification for.
+   * @param aCallback
+   *        The method to call when we have gotten the proper notification about
+   *        the title changing.
+   */
+  constructor(aURI, aExpectedTitle, aCallback) {
+    this.uri = aURI;
+    this.expectedTitle = aExpectedTitle;
+    this.callback = aCallback;
+    this.handlePlacesEvent = this.handlePlacesEvent.bind(this);
+    PlacesObservers.addListener(["page-title-changed"], this.handlePlacesEvent);
+  }
+
+  async handlePlacesEvent(aEvents) {
+    info("'page-title-changed'!!!");
+    Assert.equal(aEvents.length, 1, "Right number of title changed notified");
+    Assert.equal(aEvents[0].type, "page-title-changed");
+    if (this.uri.spec !== aEvents[0].url) {
+      return;
+    }
+    Assert.equal(aEvents[0].title, this.expectedTitle);
+    await check_guid_for_uri(this.uri, aEvents[0].pageGuid);
+    this.callback();
+
+    PlacesObservers.removeListener(
+      ["page-title-changed"],
+      this.handlePlacesEvent
+    );
+  }
+}
+
+/**
+ * Listens for a visit notification, and calls aCallback when it gets it.
+ */
+class VisitObserver {
+  constructor(aURI, aGUID, aCallback) {
+    this.uri = aURI;
+    this.guid = aGUID;
+    this.callback = aCallback;
+    this.handlePlacesEvent = this.handlePlacesEvent.bind(this);
+    PlacesObservers.addListener(["page-visited"], this.handlePlacesEvent);
+  }
+
+  handlePlacesEvent(aEvents) {
+    info("'page-visited'!!!");
+    Assert.equal(aEvents.length, 1, "Right number of visits notified");
+    Assert.equal(aEvents[0].type, "page-visited");
+    let {
+      url,
+      visitId,
+      visitTime,
+      referringVisitId,
+      transitionType,
+      pageGuid,
+      hidden,
+      visitCount,
+      typedCount,
+      lastKnownTitle,
+    } = aEvents[0];
+    let args = [
+      visitId,
+      visitTime,
+      referringVisitId,
+      transitionType,
+      pageGuid,
+      hidden,
+      visitCount,
+      typedCount,
+      lastKnownTitle,
+    ];
+    info("'page-visited' (" + url + args.join(", ") + ")");
+    if (this.uri.spec != url || this.guid != pageGuid) {
+      return;
+    }
+    this.callback(visitTime * 1000, transitionType, lastKnownTitle);
+
+    PlacesObservers.removeListener(["page-visited"], this.handlePlacesEvent);
+  }
+}
+
+/**
+ * Tests that a title was set properly in the database.
+ *
+ * @param aURI
+ *        The uri to check.
+ * @param aTitle
+ *        The expected title in the database.
+ */
+function do_check_title_for_uri(aURI, aTitle) {
+  let stmt = DBConn().createStatement(
+    `SELECT title
+     FROM moz_places
+     WHERE url_hash = hash(:url) AND url = :url`
+  );
+  stmt.params.url = aURI.spec;
+  Assert.ok(stmt.executeStep());
+  Assert.equal(stmt.row.title, aTitle);
+  stmt.finalize();
+}
+
+// Test Functions
+
+add_task(async function test_interface_exists() {
+  let history = Cc["@mozilla.org/browser/history;1"].getService(Ci.nsISupports);
+  Assert.ok(history instanceof Ci.mozIAsyncHistory);
+});
+
+add_task(async function test_invalid_uri_throws() {
+  // First, test passing in nothing.
+  let place = {
+    visits: [new VisitInfo()],
+  };
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+
+  // Now, test other bogus things.
+  const TEST_VALUES = [
+    null,
+    undefined,
+    {},
+    [],
+    TEST_DOMAIN + "test_invalid_id_throws",
+  ];
+  for (let i = 0; i < TEST_VALUES.length; i++) {
+    place.uri = TEST_VALUES[i];
+    try {
+      await promiseUpdatePlaces(place);
+      do_throw("Should have thrown!");
+    } catch (e) {
+      Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+    }
+  }
+});
+
+add_task(async function test_invalid_places_throws() {
+  // First, test passing in nothing.
+  try {
+    asyncHistory.updatePlaces();
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_XPC_NOT_ENOUGH_ARGS);
+  }
+
+  // Now, test other bogus things.
+  const TEST_VALUES = [null, undefined, {}, [], ""];
+  for (let i = 0; i < TEST_VALUES.length; i++) {
+    let value = TEST_VALUES[i];
+    try {
+      await promiseUpdatePlaces(value);
+      do_throw("Should have thrown!");
+    } catch (e) {
+      Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+    }
+  }
+});
+
+add_task(async function test_invalid_guid_throws() {
+  // First check invalid length guid.
+  let place = {
+    guid: "BAD_GUID",
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_invalid_guid_throws"),
+    visits: [new VisitInfo()],
+  };
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+
+  // Now check invalid character guid.
+  place.guid = "__BADGUID+__";
+  Assert.equal(place.guid.length, 12);
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+});
+
+add_task(async function test_no_visits_throws() {
+  const TEST_URI = NetUtil.newURI(
+    TEST_DOMAIN + "test_no_id_or_guid_no_visits_throws"
+  );
+  const TEST_GUID = "_RANDOMGUID_";
+
+  let log_test_conditions = function (aPlace) {
+    let str =
+      "Testing place with " +
+      (aPlace.uri ? "uri" : "no uri") +
+      ", " +
+      (aPlace.guid ? "guid" : "no guid") +
+      ", " +
+      (aPlace.visits ? "visits array" : "no visits array");
+    info(str);
+  };
+
+  // Loop through every possible case.  Note that we don't actually care about
+  // the case where we have no uri, place id, or guid (covered by another test),
+  // but it is easier to just make sure it too throws than to exclude it.
+  let place = {};
+  for (let uri = 1; uri >= 0; uri--) {
+    place.uri = uri ? TEST_URI : undefined;
+
+    for (let guid = 1; guid >= 0; guid--) {
+      place.guid = guid ? TEST_GUID : undefined;
+
+      for (let visits = 1; visits >= 0; visits--) {
+        place.visits = visits ? [] : undefined;
+
+        log_test_conditions(place);
+        try {
+          await promiseUpdatePlaces(place);
+          do_throw("Should have thrown!");
+        } catch (e) {
+          Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+        }
+      }
+    }
+  }
+});
+
+add_task(async function test_add_visit_no_date_throws() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_add_visit_no_date_throws"),
+    visits: [new VisitInfo()],
+  };
+  delete place.visits[0].visitDate;
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+});
+
+add_task(async function test_add_visit_no_transitionType_throws() {
+  let place = {
+    uri: NetUtil.newURI(
+      TEST_DOMAIN + "test_add_visit_no_transitionType_throws"
+    ),
+    visits: [new VisitInfo()],
+  };
+  delete place.visits[0].transitionType;
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+});
+
+add_task(async function test_add_visit_invalid_transitionType_throws() {
+  // First, test something that has a transition type lower than the first one.
+  let place = {
+    uri: NetUtil.newURI(
+      TEST_DOMAIN + "test_add_visit_invalid_transitionType_throws"
+    ),
+    visits: [new VisitInfo(TRANSITION_LINK - 1)],
+  };
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+
+  // Now, test something that has a transition type greater than the last one.
+  place.visits[0] = new VisitInfo(TRANSITION_RELOAD + 1);
+  try {
+    await promiseUpdatePlaces(place);
+    do_throw("Should have thrown!");
+  } catch (e) {
+    Assert.equal(e.result, Cr.NS_ERROR_INVALID_ARG);
+  }
+});
+
+add_task(async function test_non_addable_uri_errors() {
+  // Array of protocols that nsINavHistoryService::canAddURI returns false for.
+  const URLS = [
+    "about:config",
+    "imap://cyrus.andrew.cmu.edu/archive.imap",
+    "news://new.mozilla.org/mozilla.dev.apps.firefox",
+    "mailbox:Inbox",
+    "moz-anno:favicon:http://mozilla.org/made-up-favicon",
+    "view-source:http://mozilla.org",
+    "chrome://browser/content/browser.xhtml",
+    "resource://gre-resources/hiddenWindow.html",
+    "data:,Hello%2C%20World!",
+    "javascript:alert('hello wolrd!');",
+    "blob:foo",
+    "moz-extension://f49fb5b3-a1e7-cd41-85e1-d61a3950f5e4/index.html",
+  ];
+  let places = [];
+  URLS.forEach(function (url) {
+    try {
+      let place = {
+        uri: NetUtil.newURI(url),
+        title: "test for " + url,
+        visits: [new VisitInfo()],
+      };
+      places.push(place);
+    } catch (e) {
+      if (e.result != Cr.NS_ERROR_FAILURE) {
+        throw e;
+      }
+      // 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.
+      info("Could not construct URI for '" + url + "'; ignoring");
+    }
+  });
+
+  let placesResult = await promiseUpdatePlaces(places);
+  if (placesResult.results.length) {
+    do_throw("Unexpected success.");
+  }
+  for (let place of placesResult.errors) {
+    info("Checking '" + place.info.uri.spec + "'");
+    Assert.equal(place.resultCode, Cr.NS_ERROR_INVALID_ARG);
+    Assert.equal(false, await PlacesUtils.history.hasVisits(place.info.uri));
+  }
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_duplicate_guid_errors() {
+  // This test ensures that trying to add a visit, with a guid already found in
+  // another visit, fails.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_first"),
+    visits: [new VisitInfo()],
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(placeInfo.uri));
+
+  let badPlace = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_second"),
+    visits: [new VisitInfo()],
+    guid: placeInfo.guid,
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(badPlace.uri));
+  placesResult = await promiseUpdatePlaces(badPlace);
+  if (placesResult.results.length) {
+    do_throw("Unexpected success.");
+  }
+  let badPlaceInfo = placesResult.errors[0];
+  Assert.equal(badPlaceInfo.resultCode, Cr.NS_ERROR_STORAGE_CONSTRAINT);
+  Assert.equal(
+    false,
+    await PlacesUtils.history.hasVisits(badPlaceInfo.info.uri)
+  );
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_invalid_referrerURI_ignored() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_invalid_referrerURI_ignored"),
+    visits: [new VisitInfo()],
+  };
+  place.visits[0].referrerURI = NetUtil.newURI(
+    place.uri.spec + "_unvisistedURI"
+  );
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  Assert.equal(
+    false,
+    await PlacesUtils.history.hasVisits(place.visits[0].referrerURI)
+  );
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(placeInfo.uri));
+
+  // Check to make sure we do not visit the invalid referrer.
+  Assert.equal(
+    false,
+    await PlacesUtils.history.hasVisits(place.visits[0].referrerURI)
+  );
+
+  // Check to make sure from_visit is zero in database.
+  let stmt = DBConn().createStatement(
+    `SELECT from_visit
+     FROM moz_historyvisits
+     WHERE id = :visit_id`
+  );
+  stmt.params.visit_id = placeInfo.visits[0].visitId;
+  Assert.ok(stmt.executeStep());
+  Assert.equal(stmt.row.from_visit, 0);
+  stmt.finalize();
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_nonnsIURI_referrerURI_ignored() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_nonnsIURI_referrerURI_ignored"),
+    visits: [new VisitInfo()],
+  };
+  place.visits[0].referrerURI = place.uri.spec + "_nonnsIURI";
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(placeInfo.uri));
+
+  // Check to make sure from_visit is zero in database.
+  let stmt = DBConn().createStatement(
+    `SELECT from_visit
+     FROM moz_historyvisits
+     WHERE id = :visit_id`
+  );
+  stmt.params.visit_id = placeInfo.visits[0].visitId;
+  Assert.ok(stmt.executeStep());
+  Assert.equal(stmt.row.from_visit, 0);
+  stmt.finalize();
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async 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
+  // updatePlaces.
+  let oldTime = Date.now() * 1000 - (RECENT_EVENT_THRESHOLD + 1);
+  let referrerPlace = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_old_referrer_ignored_referrer"),
+    visits: [new VisitInfo(TRANSITION_LINK, oldTime)],
+  };
+
+  // First we must add our referrer to the history so that it is not ignored
+  // as being invalid.
+  Assert.equal(false, await PlacesUtils.history.hasVisits(referrerPlace.uri));
+  let placesResult = await promiseUpdatePlaces(referrerPlace);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+
+  // Now that the referrer is added, we can add a page with a valid
+  // referrer to determine if the recency of the referrer is taken into
+  // account.
+  Assert.ok(await PlacesUtils.history.hasVisits(referrerPlace.uri));
+
+  let visitInfo = new VisitInfo();
+  visitInfo.referrerURI = referrerPlace.uri;
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_old_referrer_ignored_page"),
+    visits: [visitInfo],
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(place.uri));
+
+  // Though the visit will not contain the referrer, we must examine the
+  // database to be sure.
+  Assert.equal(placeInfo.visits[0].referrerURI, null);
+  let stmt = DBConn().createStatement(
+    `SELECT COUNT(1) AS count
+     FROM moz_historyvisits
+     JOIN moz_places h ON h.id = place_id
+     WHERE url_hash = hash(:page_url) AND url = :page_url
+     AND from_visit = 0`
+  );
+  stmt.params.page_url = place.uri.spec;
+  Assert.ok(stmt.executeStep());
+  Assert.equal(stmt.row.count, 1);
+  stmt.finalize();
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_place_id_ignored() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_place_id_ignored_first"),
+    visits: [new VisitInfo()],
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(place.uri));
+
+  let placeId = placeInfo.placeId;
+  Assert.notEqual(placeId, 0);
+
+  let badPlace = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_place_id_ignored_second"),
+    visits: [new VisitInfo()],
+    placeId,
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(badPlace.uri));
+  placesResult = await promiseUpdatePlaces(badPlace);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  placeInfo = placesResult.results[0];
+
+  Assert.notEqual(placeInfo.placeId, placeId);
+  Assert.ok(await PlacesUtils.history.hasVisits(badPlace.uri));
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_handleCompletion_called_when_complete() {
+  // We test a normal visit, and embeded visit, and a uri that would fail
+  // the canAddURI test to make sure that the notification happens after *all*
+  // of them have had a callback.
+  let places = [
+    {
+      uri: NetUtil.newURI(
+        TEST_DOMAIN + "test_handleCompletion_called_when_complete"
+      ),
+      visits: [new VisitInfo(), new VisitInfo(TRANSITION_EMBED)],
+    },
+    {
+      uri: NetUtil.newURI("data:,Hello%2C%20World!"),
+      visits: [new VisitInfo()],
+    },
+  ];
+  Assert.equal(false, await PlacesUtils.history.hasVisits(places[0].uri));
+  Assert.equal(false, await PlacesUtils.history.hasVisits(places[1].uri));
+
+  const EXPECTED_COUNT_SUCCESS = 2;
+  const EXPECTED_COUNT_FAILURE = 1;
+
+  let { results, errors } = await promiseUpdatePlaces(places);
+
+  Assert.equal(results.length, EXPECTED_COUNT_SUCCESS);
+  Assert.equal(errors.length, EXPECTED_COUNT_FAILURE);
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_add_visit() {
+  const VISIT_TIME = Date.now() * 1000;
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_add_visit"),
+    title: "test_add_visit title",
+    visits: [],
+  };
+  for (let t in PlacesUtils.history.TRANSITIONS) {
+    if (t == "EMBED") {
+      continue;
+    }
+    let transitionType = PlacesUtils.history.TRANSITIONS[t];
+    place.visits.push(new VisitInfo(transitionType, VISIT_TIME));
+  }
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let callbackCount = 0;
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  for (let placeInfo of placesResult.results) {
+    Assert.ok(await PlacesUtils.history.hasVisits(place.uri));
+
+    // Check mozIPlaceInfo properties.
+    Assert.ok(place.uri.equals(placeInfo.uri));
+    Assert.equal(placeInfo.frecency, -1); // We don't pass frecency here!
+    Assert.equal(placeInfo.title, place.title);
+
+    // Check mozIVisitInfo properties.
+    let visits = placeInfo.visits;
+    Assert.equal(visits.length, 1);
+    let visit = visits[0];
+    Assert.equal(visit.visitDate, VISIT_TIME);
+    Assert.ok(
+      Object.values(PlacesUtils.history.TRANSITIONS).includes(
+        visit.transitionType
+      )
+    );
+    Assert.ok(visit.referrerURI === null);
+
+    // For TRANSITION_EMBED visits, many properties will always be zero or
+    // undefined.
+    if (visit.transitionType == TRANSITION_EMBED) {
+      // Check mozIPlaceInfo properties.
+      Assert.equal(placeInfo.placeId, 0, "//");
+      Assert.equal(placeInfo.guid, null);
+
+      // Check mozIVisitInfo properties.
+      Assert.equal(visit.visitId, 0);
+    } else {
+      // But they should be valid for non-embed visits.
+      // Check mozIPlaceInfo properties.
+      Assert.ok(placeInfo.placeId > 0);
+      do_check_valid_places_guid(placeInfo.guid);
+
+      // Check mozIVisitInfo properties.
+      Assert.ok(visit.visitId > 0);
+    }
+
+    // If we have had all of our callbacks, continue running tests.
+    if (++callbackCount == place.visits.length) {
+      await PlacesTestUtils.promiseAsyncUpdates();
+    }
+  }
+});
+
+add_task(async function test_properties_saved() {
+  // Check each transition type to make sure it is saved properly.
+  let places = [];
+  for (let t in PlacesUtils.history.TRANSITIONS) {
+    if (t == "EMBED") {
+      continue;
+    }
+    let transitionType = PlacesUtils.history.TRANSITIONS[t];
+    let place = {
+      uri: NetUtil.newURI(
+        TEST_DOMAIN + "test_properties_saved/" + transitionType
+      ),
+      title: "test_properties_saved test",
+      visits: [new VisitInfo(transitionType)],
+    };
+    Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+    places.push(place);
+  }
+
+  let callbackCount = 0;
+  let placesResult = await promiseUpdatePlaces(places);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  for (let placeInfo of placesResult.results) {
+    let uri = placeInfo.uri;
+    Assert.ok(await PlacesUtils.history.hasVisits(uri));
+    let visit = placeInfo.visits[0];
+    print(
+      "TEST-INFO | test_properties_saved | updatePlaces callback for " +
+        "transition type " +
+        visit.transitionType
+    );
+
+    // Note that TRANSITION_EMBED should not be in the database.
+    const EXPECTED_COUNT = visit.transitionType == TRANSITION_EMBED ? 0 : 1;
+
+    // mozIVisitInfo::date
+    let stmt = DBConn().createStatement(
+      `SELECT COUNT(1) AS count
+       FROM moz_places h
+       JOIN moz_historyvisits v
+       ON h.id = v.place_id
+       WHERE h.url_hash = hash(:page_url) AND h.url = :page_url
+       AND v.visit_date = :visit_date`
+    );
+    stmt.params.page_url = uri.spec;
+    stmt.params.visit_date = visit.visitDate;
+    Assert.ok(stmt.executeStep());
+    Assert.equal(stmt.row.count, EXPECTED_COUNT);
+    stmt.finalize();
+
+    // mozIVisitInfo::transitionType
+    stmt = DBConn().createStatement(
+      `SELECT COUNT(1) AS count
+       FROM moz_places h
+       JOIN moz_historyvisits v
+       ON h.id = v.place_id
+       WHERE h.url_hash = hash(:page_url) AND h.url = :page_url
+       AND v.visit_type = :transition_type`
+    );
+    stmt.params.page_url = uri.spec;
+    stmt.params.transition_type = visit.transitionType;
+    Assert.ok(stmt.executeStep());
+    Assert.equal(stmt.row.count, EXPECTED_COUNT);
+    stmt.finalize();
+
+    // mozIPlaceInfo::title
+    stmt = DBConn().createStatement(
+      `SELECT COUNT(1) AS count
+       FROM moz_places h
+       WHERE h.url_hash = hash(:page_url) AND h.url = :page_url
+       AND h.title = :title`
+    );
+    stmt.params.page_url = uri.spec;
+    stmt.params.title = placeInfo.title;
+    Assert.ok(stmt.executeStep());
+    Assert.equal(stmt.row.count, EXPECTED_COUNT);
+    stmt.finalize();
+
+    // If we have had all of our callbacks, continue running tests.
+    if (++callbackCount == places.length) {
+      await PlacesTestUtils.promiseAsyncUpdates();
+    }
+  }
+});
+
+add_task(async function test_guid_saved() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_guid_saved"),
+    guid: "__TESTGUID__",
+    visits: [new VisitInfo()],
+  };
+  do_check_valid_places_guid(place.guid);
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  let uri = placeInfo.uri;
+  Assert.ok(await PlacesUtils.history.hasVisits(uri));
+  Assert.equal(placeInfo.guid, place.guid);
+  await check_guid_for_uri(uri, place.guid);
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_referrer_saved() {
+  let places = [
+    {
+      uri: NetUtil.newURI(TEST_DOMAIN + "test_referrer_saved/referrer"),
+      visits: [new VisitInfo()],
+    },
+    {
+      uri: NetUtil.newURI(TEST_DOMAIN + "test_referrer_saved/test"),
+      visits: [new VisitInfo()],
+    },
+  ];
+  places[1].visits[0].referrerURI = places[0].uri;
+  Assert.equal(false, await PlacesUtils.history.hasVisits(places[0].uri));
+  Assert.equal(false, await PlacesUtils.history.hasVisits(places[1].uri));
+
+  let resultCount = 0;
+  let placesResult = await promiseUpdatePlaces(places);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  for (let placeInfo of placesResult.results) {
+    let uri = placeInfo.uri;
+    Assert.ok(await PlacesUtils.history.hasVisits(uri));
+    let visit = placeInfo.visits[0];
+
+    // We need to insert all of our visits before we can test conditions.
+    if (++resultCount == places.length) {
+      Assert.ok(places[0].uri.equals(visit.referrerURI));
+
+      let stmt = DBConn().createStatement(
+        `SELECT COUNT(1) AS count
+         FROM moz_historyvisits
+         JOIN moz_places h ON h.id = place_id
+         WHERE url_hash = hash(:page_url) AND url = :page_url
+         AND from_visit = (
+           SELECT v.id
+           FROM moz_historyvisits v
+           JOIN moz_places h ON h.id = place_id
+           WHERE url_hash = hash(:referrer) AND url = :referrer
+         )`
+      );
+      stmt.params.page_url = uri.spec;
+      stmt.params.referrer = visit.referrerURI.spec;
+      Assert.ok(stmt.executeStep());
+      Assert.equal(stmt.row.count, 1);
+      stmt.finalize();
+
+      await PlacesTestUtils.promiseAsyncUpdates();
+    }
+  }
+});
+
+add_task(async function test_guid_change_saved() {
+  // First, add a visit for it.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_guid_change_saved"),
+    visits: [new VisitInfo()],
+  };
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  // Then, change the guid with visits.
+  place.guid = "_GUIDCHANGE_";
+  place.visits = [new VisitInfo()];
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  await check_guid_for_uri(place.uri, place.guid);
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_title_change_saved() {
+  // First, add a visit for it.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_title_change_saved"),
+    title: "original title",
+    visits: [new VisitInfo()],
+  };
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+
+  // Now, make sure the empty string clears the title.
+  place.title = "";
+  place.visits = [new VisitInfo()];
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  do_check_title_for_uri(place.uri, null);
+
+  // Then, change the title with visits.
+  place.title = "title change";
+  place.visits = [new VisitInfo()];
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  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()];
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  do_check_title_for_uri(place.uri, place.title);
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_no_title_does_not_clear_title() {
+  const TITLE = "test title";
+  // First, add a visit for it.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_no_title_does_not_clear_title"),
+    title: TITLE,
+    visits: [new VisitInfo()],
+  };
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  // Now, make sure that not specifying a title does not clear it.
+  delete place.title;
+  place.visits = [new VisitInfo()];
+  placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  do_check_title_for_uri(place.uri, TITLE);
+
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async 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.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_title_change_notifies"),
+    visits: [new VisitInfo()],
+  };
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  new TitleChangedObserver(place.uri, "DO NOT WANT", function () {
+    do_throw("unexpected callback!");
+  });
+
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+
+  // The second case to test is that we don't get the notification when we add
+  // it for the first time.  The first case will fail before our callback if it
+  // is busted, so we can do this now.
+  place.uri = NetUtil.newURI(place.uri.spec + "/new-visit-with-title");
+  place.title = "title 1";
+  let expectedNotification = false;
+  let titleChangeObserver;
+  let titleChangePromise = new Promise((resolve, reject) => {
+    titleChangeObserver = new TitleChangedObserver(
+      place.uri,
+      place.title,
+      function () {
+        Assert.ok(
+          expectedNotification,
+          "Should not get notified for " +
+            place.uri.spec +
+            " with title " +
+            place.title
+        );
+        if (expectedNotification) {
+          resolve();
+        }
+      }
+    );
+  });
+
+  let visitPromise = new Promise(resolve => {
+    function onVisits(events) {
+      Assert.equal(events.length, 1, "Should only get notified for one visit.");
+      Assert.equal(events[0].type, "page-visited");
+      let { url } = events[0];
+      Assert.equal(
+        url,
+        place.uri.spec,
+        "Should get notified for visiting the new URI."
+      );
+      PlacesObservers.removeListener(["page-visited"], onVisits);
+      resolve();
+    }
+    PlacesObservers.addListener(["page-visited"], onVisits);
+  });
+  asyncHistory.updatePlaces(place);
+  await visitPromise;
+
+  // The third case to test is to make sure we get a notification when
+  // we change an existing place.
+  expectedNotification = true;
+  titleChangeObserver.expectedTitle = place.title = "title 2";
+  place.visits = [new VisitInfo()];
+  asyncHistory.updatePlaces(place);
+
+  await titleChangePromise;
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_visit_notifies() {
+  // There are two observers we need to see for each visit. One is an
+  // PlacesObservers and the other is the uri-visit-saved observer topic.
+  let place = {
+    guid: "abcdefghijkl",
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_visit_notifies"),
+    visits: [new VisitInfo()],
+  };
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+
+  function promiseVisitObserver(aPlace) {
+    return new Promise((resolve, reject) => {
+      let callbackCount = 0;
+      let finisher = function () {
+        if (++callbackCount == 2) {
+          resolve();
+        }
+      };
+      new VisitObserver(place.uri, place.guid, function (
+        aVisitDate,
+        aTransitionType
+      ) {
+        let visit = place.visits[0];
+        Assert.equal(visit.visitDate, aVisitDate);
+        Assert.equal(visit.transitionType, aTransitionType);
+
+        finisher();
+      });
+      let observer = function (aSubject, aTopic, aData) {
+        info("observe(" + aSubject + ", " + aTopic + ", " + aData + ")");
+        Assert.ok(aSubject instanceof Ci.nsIURI);
+        Assert.ok(aSubject.equals(place.uri));
+
+        Services.obs.removeObserver(observer, URI_VISIT_SAVED);
+        finisher();
+      };
+      Services.obs.addObserver(observer, URI_VISIT_SAVED);
+      asyncHistory.updatePlaces(place);
+    });
+  }
+
+  await promiseVisitObserver(place);
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+// test with empty mozIVisitInfoCallback object
+add_task(async function test_callbacks_not_supplied() {
+  const URLS = [
+    "imap://cyrus.andrew.cmu.edu/archive.imap", // bad URI
+    "http://mozilla.org/", // valid URI
+  ];
+  let places = [];
+  URLS.forEach(function (url) {
+    try {
+      let place = {
+        uri: NetUtil.newURI(url),
+        title: "test for " + url,
+        visits: [new VisitInfo()],
+      };
+      places.push(place);
+    } catch (e) {
+      if (e.result != Cr.NS_ERROR_FAILURE) {
+        throw e;
+      }
+      // 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.
+      info("Could not construct URI for '" + url + "'; ignoring");
+    }
+  });
+
+  asyncHistory.updatePlaces(places, {});
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+// Test that we don't wrongly overwrite typed and hidden when adding new visits.
+add_task(async function test_typed_hidden_not_overwritten() {
+  await PlacesUtils.history.clear();
+  let places = [
+    {
+      uri: NetUtil.newURI("http://mozilla.org/"),
+      title: "test",
+      visits: [new VisitInfo(TRANSITION_TYPED), new VisitInfo(TRANSITION_LINK)],
+    },
+    {
+      uri: NetUtil.newURI("http://mozilla.org/"),
+      title: "test",
+      visits: [new VisitInfo(TRANSITION_FRAMED_LINK)],
+    },
+  ];
+  await promiseUpdatePlaces(places);
+
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(
+    "SELECT hidden, typed FROM moz_places WHERE url_hash = hash(:url) AND url = :url",
+    { url: "http://mozilla.org/" }
+  );
+  Assert.equal(
+    rows[0].getResultByName("typed"),
+    1,
+    "The page should be marked as typed"
+  );
+  Assert.equal(
+    rows[0].getResultByName("hidden"),
+    0,
+    "The page should be marked as not hidden"
+  );
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_omit_frecency_notifications() {
+  await PlacesUtils.history.clear();
+  let places = [
+    {
+      uri: NetUtil.newURI("http://mozilla.org/"),
+      title: "test",
+      visits: [new VisitInfo(TRANSITION_TYPED)],
+    },
+    {
+      uri: NetUtil.newURI("http://example.org/"),
+      title: "test",
+      visits: [new VisitInfo(TRANSITION_TYPED)],
+    },
+  ];
+
+  const promiseRankingChanged =
+    PlacesTestUtils.waitForNotification("pages-rank-changed");
+
+  await promiseUpdatePlaces(places);
+  await promiseRankingChanged;
+});
+
+add_task(async function test_ignore_errors() {
+  await PlacesUtils.history.clear();
+  // This test ensures that trying to add a visit, with a guid already found in
+  // another visit, fails - but doesn't report if we told it not to.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_first"),
+    visits: [new VisitInfo()],
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(placeInfo.uri));
+
+  let badPlace = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_second"),
+    visits: [new VisitInfo()],
+    guid: placeInfo.guid,
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(badPlace.uri));
+  placesResult = await promiseUpdatePlaces(badPlace, { ignoreErrors: true });
+  if (placesResult.results.length) {
+    do_throw("Unexpected success.");
+  }
+  Assert.equal(
+    placesResult.errors.length,
+    0,
+    "Should have seen 0 errors because we disabled reporting."
+  );
+  Assert.equal(
+    placesResult.results.length,
+    0,
+    "Should have seen 0 results because there were none."
+  );
+  Assert.equal(
+    placesResult.resultCount,
+    0,
+    "Should know that we updated 0 items from the completion callback."
+  );
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_ignore_results() {
+  await PlacesUtils.history.clear();
+  let place = {
+    uri: NetUtil.newURI("http://mozilla.org/"),
+    title: "test",
+    visits: [new VisitInfo()],
+  };
+  let placesResult = await promiseUpdatePlaces(place, { ignoreResults: true });
+  Assert.equal(
+    placesResult.results.length,
+    0,
+    "Should have seen 0 results because we disabled reporting."
+  );
+  Assert.equal(
+    placesResult.errors.length,
+    0,
+    "Should have seen 0 errors because there were none."
+  );
+  Assert.equal(
+    placesResult.resultCount,
+    1,
+    "Should know that we updated 1 item from the completion callback."
+  );
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_ignore_results_and_errors() {
+  await PlacesUtils.history.clear();
+  // This test ensures that trying to add a visit, with a guid already found in
+  // another visit, fails - but doesn't report if we told it not to.
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_first"),
+    visits: [new VisitInfo()],
+  };
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(place.uri));
+  let placesResult = await promiseUpdatePlaces(place);
+  if (placesResult.errors.length) {
+    do_throw("Unexpected error.");
+  }
+  let placeInfo = placesResult.results[0];
+  Assert.ok(await PlacesUtils.history.hasVisits(placeInfo.uri));
+
+  let badPlace = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_duplicate_guid_fails_second"),
+    visits: [new VisitInfo()],
+    guid: placeInfo.guid,
+  };
+  let allPlaces = [
+    {
+      uri: NetUtil.newURI(TEST_DOMAIN + "test_other_successful_item"),
+      visits: [new VisitInfo()],
+    },
+    badPlace,
+  ];
+
+  Assert.equal(false, await PlacesUtils.history.hasVisits(badPlace.uri));
+  placesResult = await promiseUpdatePlaces(allPlaces, {
+    ignoreErrors: true,
+    ignoreResults: true,
+  });
+  Assert.equal(
+    placesResult.errors.length,
+    0,
+    "Should have seen 0 errors because we disabled reporting."
+  );
+  Assert.equal(
+    placesResult.results.length,
+    0,
+    "Should have seen 0 results because we disabled reporting."
+  );
+  Assert.equal(
+    placesResult.resultCount,
+    1,
+    "Should know that we updated 1 item from the completion callback."
+  );
+  await PlacesTestUtils.promiseAsyncUpdates();
+});
+
+add_task(async function test_title_on_initial_visit() {
+  let place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_visit_title"),
+    title: "My title",
+    visits: [new VisitInfo()],
+    guid: "mnopqrstuvwx",
+  };
+  let visitPromise = new Promise(resolve => {
+    new VisitObserver(place.uri, place.guid, function (
+      aVisitDate,
+      aTransitionType,
+      aLastKnownTitle
+    ) {
+      Assert.equal(place.title, aLastKnownTitle);
+
+      resolve();
+    });
+  });
+  await promiseUpdatePlaces(place);
+  await visitPromise;
+
+  // Now check an empty title doesn't get reported as null
+  place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_visit_title"),
+    title: "",
+    visits: [new VisitInfo()],
+    guid: "fghijklmnopq",
+  };
+  visitPromise = new Promise(resolve => {
+    new VisitObserver(place.uri, place.guid, function (
+      aVisitDate,
+      aTransitionType,
+      aLastKnownTitle
+    ) {
+      Assert.equal(place.title, aLastKnownTitle);
+
+      resolve();
+    });
+  });
+  await promiseUpdatePlaces(place);
+  await visitPromise;
+
+  // and that a missing title correctly gets reported as null.
+  place = {
+    uri: NetUtil.newURI(TEST_DOMAIN + "test_visit_title"),
+    visits: [new VisitInfo()],
+    guid: "fghijklmnopq",
+  };
+  visitPromise = new Promise(resolve => {
+    new VisitObserver(place.uri, place.guid, function (
+      aVisitDate,
+      aTransitionType,
+      aLastKnownTitle
+    ) {
+      Assert.equal(null, aLastKnownTitle);
+
+      resolve();
+    });
+  });
+  await promiseUpdatePlaces(place);
+  await visitPromise;
+});
diff --git a/toolkit/components/places/tests/history/test_bookmark_unhide.js b/toolkit/components/places/tests/history/test_bookmark_unhide.js
new file mode 100644
index 0000000000..1295c6e8c5
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_bookmark_unhide.js
@@ -0,0 +1,26 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests that bookmarking an hidden page unhides it.
+
+"use strict";
+
+add_task(async function test_hidden() {
+  const url = "http://moz.com/";
+  await PlacesTestUtils.addVisits({
+    url,
+    transition: TRANSITION_FRAMED_LINK,
+  });
+  Assert.equal(
+    await PlacesTestUtils.getDatabaseValue("moz_places", "hidden", { url }),
+    1
+  );
+  await PlacesUtils.bookmarks.insert({
+    url,
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+  });
+  Assert.equal(
+    await PlacesTestUtils.getDatabaseValue("moz_places", "hidden", { url }),
+    0
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_fetch.js b/toolkit/components/places/tests/history/test_fetch.js
new file mode 100644
index 0000000000..899e459403
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_fetch.js
@@ -0,0 +1,270 @@
+/* Any copyright is dedicated to the Public Domain. http://creativecommons.org/publicdomain/zero/1.0/ */
+"use strict";
+
+add_task(async function test_fetch_existent() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  // Populate places and historyvisits.
+  let uriString = `http://mozilla.com/test_browserhistory/test_fetch`;
+  let uri = NetUtil.newURI(uriString);
+  let title = `Test Visit ${Math.random()}`;
+  let dates = [];
+  let visits = [];
+  let transitions = [
+    PlacesUtils.history.TRANSITION_LINK,
+    PlacesUtils.history.TRANSITION_TYPED,
+    PlacesUtils.history.TRANSITION_BOOKMARK,
+    PlacesUtils.history.TRANSITION_REDIRECT_TEMPORARY,
+    PlacesUtils.history.TRANSITION_REDIRECT_PERMANENT,
+    PlacesUtils.history.TRANSITION_DOWNLOAD,
+    PlacesUtils.history.TRANSITION_FRAMED_LINK,
+    PlacesUtils.history.TRANSITION_RELOAD,
+  ];
+  let guid = "";
+  for (let i = 0; i != transitions.length; i++) {
+    dates.push(new Date(Date.now() - i * 10000000));
+    visits.push({
+      uri,
+      title,
+      transition: transitions[i],
+      visitDate: dates[i],
+    });
+  }
+  await PlacesTestUtils.addVisits(visits);
+  Assert.ok(await PlacesTestUtils.isPageInDB(uri));
+  Assert.equal(await PlacesTestUtils.visitsInDB(uri), visits.length);
+
+  // Store guid for further use in testing.
+  guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+    url: uri,
+  });
+  Assert.ok(guid, guid);
+
+  // Initialize the objects to compare against.
+  let idealPageInfo = {
+    url: new URL(uriString),
+    guid,
+    title,
+  };
+  let idealVisits = visits.map(v => {
+    return {
+      date: v.visitDate,
+      transition: v.transition,
+    };
+  });
+
+  // We should check these 4 cases:
+  // 1, 2: visits not included, by URL and guid (same result expected).
+  // 3, 4: visits included, by URL and guid (same result expected).
+  for (let includeVisits of [true, false]) {
+    for (let guidOrURL of [uri, guid]) {
+      let pageInfo = await PlacesUtils.history.fetch(guidOrURL, {
+        includeVisits,
+      });
+      if (includeVisits) {
+        idealPageInfo.visits = idealVisits;
+      } else {
+        // We need to explicitly delete this property since deepEqual looks at
+        // the list of properties as well (`visits in pageInfo` is true here).
+        delete idealPageInfo.visits;
+      }
+
+      // Since idealPageInfo doesn't contain a frecency, check it and delete.
+      Assert.ok(typeof pageInfo.frecency === "number");
+      delete pageInfo.frecency;
+
+      // Visits should be from newer to older.
+      if (includeVisits) {
+        for (let i = 0; i !== pageInfo.visits.length - 1; i++) {
+          Assert.lessOrEqual(
+            pageInfo.visits[i + 1].date.getTime(),
+            pageInfo.visits[i].date.getTime()
+          );
+        }
+      }
+      Assert.deepEqual(idealPageInfo, pageInfo);
+    }
+  }
+});
+
+add_task(async function test_fetch_page_meta_info() {
+  await PlacesUtils.history.clear();
+
+  let TEST_URI = NetUtil.newURI("http://mozilla.com/test_fetch_page_meta_info");
+  await PlacesTestUtils.addVisits(TEST_URI);
+  Assert.ok(page_in_database(TEST_URI));
+
+  // Test fetching the null values
+  let includeMeta = true;
+  let pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeMeta });
+  Assert.strictEqual(
+    null,
+    pageInfo.previewImageURL,
+    "fetch should return a null previewImageURL"
+  );
+  Assert.strictEqual(
+    "",
+    pageInfo.siteName,
+    "fetch should return a null siteName"
+  );
+  Assert.equal(
+    "",
+    pageInfo.description,
+    "fetch should return a empty string description"
+  );
+
+  // Now set the pageMetaInfo for this page
+  let description = "Test description";
+  let siteName = "Mozilla";
+  let previewImageURL = "http://mozilla.com/test_preview_image.png";
+  await PlacesUtils.history.update({
+    url: TEST_URI,
+    description,
+    previewImageURL,
+    siteName,
+  });
+
+  includeMeta = true;
+  pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeMeta });
+  Assert.equal(
+    previewImageURL,
+    pageInfo.previewImageURL.href,
+    "fetch should return a previewImageURL"
+  );
+  Assert.equal(siteName, pageInfo.siteName, "fetch should return a siteName");
+  Assert.equal(
+    description,
+    pageInfo.description,
+    "fetch should return a description"
+  );
+
+  includeMeta = false;
+  pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeMeta });
+  Assert.ok(
+    !("description" in pageInfo),
+    "fetch should not return a description if includeMeta is false"
+  );
+  Assert.ok(
+    !("siteName" in pageInfo),
+    "fetch should not return a siteName if includeMeta is false"
+  );
+  Assert.ok(
+    !("previewImageURL" in pageInfo),
+    "fetch should not return a previewImageURL if includeMeta is false"
+  );
+});
+
+add_task(async function test_fetch_annotations() {
+  await PlacesUtils.history.clear();
+
+  const TEST_URI = "http://mozilla.com/test_fetch_page_meta_info";
+  await PlacesTestUtils.addVisits(TEST_URI);
+  Assert.ok(page_in_database(TEST_URI));
+
+  let includeAnnotations = true;
+  let pageInfo = await PlacesUtils.history.fetch(TEST_URI, {
+    includeAnnotations,
+  });
+  Assert.equal(
+    pageInfo.annotations.size,
+    0,
+    "fetch should return an empty annotation map"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URI,
+    annotations: new Map([["test/annotation", "testContent"]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeAnnotations });
+  Assert.equal(
+    pageInfo.annotations.size,
+    1,
+    "fetch should have only one annotation"
+  );
+
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    "testContent",
+    "fetch should return the expected annotation"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URI,
+    annotations: new Map([["test/annotation2", 123]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeAnnotations });
+  Assert.equal(
+    pageInfo.annotations.size,
+    2,
+    "fetch should have returned two annotations"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    "testContent",
+    "fetch should still have the first annotation"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    123,
+    "fetch should have the second annotation"
+  );
+
+  includeAnnotations = false;
+  pageInfo = await PlacesUtils.history.fetch(TEST_URI, { includeAnnotations });
+  Assert.ok(
+    !("annotations" in pageInfo),
+    "fetch should not return annotations if includeAnnotations is false"
+  );
+});
+
+add_task(async function test_fetch_nonexistent() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  let uri = NetUtil.newURI("http://doesntexist.in.db");
+  let pageInfo = await PlacesUtils.history.fetch(uri);
+  Assert.equal(pageInfo, null);
+});
+
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.fetch("3"),
+    /TypeError: URL constructor: 3 is not a valid /
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetch({ not: "a valid string or guid" }),
+    /TypeError: Invalid url or guid/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetch("http://valid.uri.com", "not an object"),
+    /TypeError: options should be/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetch("http://valid.uri.com", null),
+    /TypeError: options should be/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.fetch("http://valid.uri.come", {
+        includeVisits: "not a boolean",
+      }),
+    /TypeError: includeVisits should be a/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.fetch("http://valid.uri.come", {
+        includeMeta: "not a boolean",
+      }),
+    /TypeError: includeMeta should be a/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.fetch("http://valid.url.com", {
+        includeAnnotations: "not a boolean",
+      }),
+    /TypeError: includeAnnotations should be a/
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_fetchAnnotatedPages.js b/toolkit/components/places/tests/history/test_fetchAnnotatedPages.js
new file mode 100644
index 0000000000..0f487e8090
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_fetchAnnotatedPages.js
@@ -0,0 +1,146 @@
+/* Any copyright is dedicated to the Public Domain. http://creativecommons.org/publicdomain/zero/1.0/ */
+"use strict";
+
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.fetchAnnotatedPages(),
+    /TypeError: annotations should be an Array and not null/,
+    "Should throw an exception for a null parameter"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetchAnnotatedPages("3"),
+    /TypeError: annotations should be an Array and not null/,
+    "Should throw an exception for a parameter of the wrong type"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetchAnnotatedPages([3]),
+    /TypeError: all annotation values should be strings/,
+    "Should throw an exception for a non-string annotation name"
+  );
+});
+
+add_task(async function test_fetchAnnotatedPages_no_matching() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  const TEST_URL = "http://example.com/1";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL),
+    "Should have inserted the page into the database."
+  );
+
+  let result = await PlacesUtils.history.fetchAnnotatedPages(["test/anno"]);
+
+  Assert.equal(result.size, 0, "Should be no items returned.");
+});
+
+add_task(async function test_fetchAnnotatedPages_simple_match() {
+  await PlacesUtils.history.clear();
+
+  const TEST_URL = "http://example.com/1";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL),
+    "Should have inserted the page into the database."
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/anno", "testContent"]]),
+  });
+
+  let result = await PlacesUtils.history.fetchAnnotatedPages(["test/anno"]);
+
+  Assert.equal(
+    result.size,
+    1,
+    "Should have returned one match for the annotation"
+  );
+
+  Assert.deepEqual(
+    result.get("test/anno"),
+    [
+      {
+        uri: new URL(TEST_URL),
+        content: "testContent",
+      },
+    ],
+    "Should have returned the page and its content for the annotation"
+  );
+});
+
+add_task(async function test_fetchAnnotatedPages_multiple_match() {
+  await PlacesUtils.history.clear();
+
+  const TEST_URL1 = "http://example.com/1";
+  const TEST_URL2 = "http://example.com/2";
+  const TEST_URL3 = "http://example.com/3";
+  await PlacesTestUtils.addVisits([
+    { uri: TEST_URL1 },
+    { uri: TEST_URL2 },
+    { uri: TEST_URL3 },
+  ]);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL1),
+    "Should have inserted the first page into the database."
+  );
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL2),
+    "Should have inserted the second page into the database."
+  );
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL3),
+    "Should have inserted the third page into the database."
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL1,
+    annotations: new Map([["test/anno", "testContent1"]]),
+  });
+
+  await PlacesUtils.history.update({
+    url: TEST_URL2,
+    annotations: new Map([
+      ["test/anno", "testContent2"],
+      ["test/anno2", 1234],
+    ]),
+  });
+
+  let result = await PlacesUtils.history.fetchAnnotatedPages([
+    "test/anno",
+    "test/anno2",
+  ]);
+
+  Assert.equal(
+    result.size,
+    2,
+    "Should have returned matches for both annotations"
+  );
+
+  Assert.deepEqual(
+    result.get("test/anno"),
+    [
+      {
+        uri: new URL(TEST_URL1),
+        content: "testContent1",
+      },
+      {
+        uri: new URL(TEST_URL2),
+        content: "testContent2",
+      },
+    ],
+    "Should have returned two pages and their content for the first annotation"
+  );
+
+  Assert.deepEqual(
+    result.get("test/anno2"),
+    [
+      {
+        uri: new URL(TEST_URL2),
+        content: 1234,
+      },
+    ],
+    "Should have returned one page for the second annotation"
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_fetchMany.js b/toolkit/components/places/tests/history/test_fetchMany.js
new file mode 100644
index 0000000000..53c3f6847e
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_fetchMany.js
@@ -0,0 +1,96 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+add_task(async function test_fetchMany() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  let pages = [
+    {
+      url: "https://mozilla.org/test1/",
+      title: "test 1",
+    },
+    {
+      url: "https://mozilla.org/test2/",
+      title: "test 2",
+    },
+    {
+      url: "https://mozilla.org/test3/",
+      title: "test 3",
+    },
+  ];
+  await PlacesTestUtils.addVisits(pages);
+
+  // Add missing page info from the database.
+  for (let page of pages) {
+    page.guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+      url: page.url,
+    });
+    page.frecency = await PlacesTestUtils.getDatabaseValue(
+      "moz_places",
+      "frecency",
+      { url: page.url }
+    );
+  }
+
+  info("Fetch by url");
+  let fetched = await PlacesUtils.history.fetchMany(pages.map(p => p.url));
+  Assert.equal(fetched.size, 3, "Map should contain same number of entries");
+  for (let page of pages) {
+    Assert.deepEqual(page, fetched.get(page.url));
+  }
+  info("Fetch by GUID");
+  fetched = await PlacesUtils.history.fetchMany(pages.map(p => p.guid));
+  Assert.equal(fetched.size, 3, "Map should contain same number of entries");
+  for (let page of pages) {
+    Assert.deepEqual(page, fetched.get(page.guid));
+  }
+  info("Fetch mixed");
+  let keys = pages.map((p, i) => (i % 2 == 0 ? p.guid : p.url));
+  fetched = await PlacesUtils.history.fetchMany(keys);
+  Assert.equal(fetched.size, 3, "Map should contain same number of entries");
+  for (let key of keys) {
+    let page = pages.find(p => p.guid == key || p.url == key);
+    Assert.deepEqual(page, fetched.get(key));
+    Assert.ok(URL.isInstance(fetched.get(key).url));
+  }
+});
+
+add_task(async function test_fetch_empty() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  let fetched = await PlacesUtils.history.fetchMany([]);
+  Assert.equal(fetched.size, 0, "Map should contain no entries");
+});
+
+add_task(async function test_fetch_nonexistent() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  let uri = NetUtil.newURI("http://doesntexist.in.db");
+  let fetched = await PlacesUtils.history.fetchMany([uri]);
+  Assert.equal(fetched.size, 0, "Map should contain no entries");
+});
+
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.fetchMany("3"),
+    /TypeError: Input is not an array/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetchMany([{ not: "a valid string or guid" }]),
+    /TypeError: Invalid url or guid/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.fetchMany(["http://valid.uri.com", "not an object"]),
+    /TypeError: URL constructor/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.fetchMany(["http://valid.uri.com", null]),
+    /TypeError: Invalid url or guid/
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_hasVisits.js b/toolkit/components/places/tests/history/test_hasVisits.js
new file mode 100644
index 0000000000..36fc9fd7be
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_hasVisits.js
@@ -0,0 +1,60 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests for `History.hasVisits` as implemented in History.jsm
+
+"use strict";
+
+add_task(async function test_has_visits_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.hasVisits(),
+    /TypeError: Invalid url or guid: undefined/,
+    "passing a null into History.hasVisits should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.hasVisits(1),
+    /TypeError: Invalid url or guid: 1/,
+    "passing an invalid url into History.hasVisits should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.hasVisits({}),
+    /TypeError: Invalid url or guid: \[object Object\]/,
+    `passing an invalid (not of type URI or nsIURI) object to History.hasVisits
+     should throw a TypeError`
+  );
+});
+
+add_task(async function test_history_has_visits() {
+  const TEST_URL = "http://mozilla.com/";
+  await PlacesUtils.history.clear();
+  Assert.equal(
+    await PlacesUtils.history.hasVisits(TEST_URL),
+    false,
+    "Test Url should not be in history."
+  );
+  Assert.equal(
+    await PlacesUtils.history.hasVisits(Services.io.newURI(TEST_URL)),
+    false,
+    "Test Url should not be in history."
+  );
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.equal(
+    await PlacesUtils.history.hasVisits(TEST_URL),
+    true,
+    "Test Url should be in history."
+  );
+  Assert.equal(
+    await PlacesUtils.history.hasVisits(Services.io.newURI(TEST_URL)),
+    true,
+    "Test Url should be in history."
+  );
+  let guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+    url: TEST_URL,
+  });
+  Assert.equal(
+    await PlacesUtils.history.hasVisits(guid),
+    true,
+    "Test Url should be in history."
+  );
+  await PlacesUtils.history.clear();
+});
diff --git a/toolkit/components/places/tests/history/test_insert.js b/toolkit/components/places/tests/history/test_insert.js
new file mode 100644
index 0000000000..a3a820ade9
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_insert.js
@@ -0,0 +1,196 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests for `History.insert` as implemented in History.jsm
+
+"use strict";
+
+add_task(async function test_insert_error_cases() {
+  const TEST_URL = "http://mozilla.com";
+
+  Assert.throws(
+    () => PlacesUtils.history.insert(),
+    /Error: PageInfo: Input should be /,
+    "passing a null into History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert(1),
+    /Error: PageInfo: Input should be/,
+    "passing a non object into History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert({}),
+    /Error: PageInfo: The following properties were expected/,
+    "passing an object without a url to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert({ url: 123 }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing an object with an invalid url to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert({ url: TEST_URL }),
+    /Error: PageInfo: The following properties were expected/,
+    "passing an object without a visits property to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert({ url: TEST_URL, visits: 1 }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing an object with a non-array visits property to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insert({ url: TEST_URL, visits: [] }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing an object with an empty array as the visits property to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.insert({
+        url: TEST_URL,
+        visits: [
+          {
+            transition: TRANSITION_LINK,
+            date: "a",
+          },
+        ],
+      }),
+    /PageInfo: Invalid value for property/,
+    "passing a visit object with an invalid date to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.insert({
+        url: TEST_URL,
+        visits: [
+          {
+            transition: TRANSITION_LINK,
+          },
+          {
+            transition: TRANSITION_LINK,
+            date: "a",
+          },
+        ],
+      }),
+    /PageInfo: Invalid value for property/,
+    "passing a second visit object with an invalid date to History.insert should throw an Error"
+  );
+  let futureDate = new Date();
+  futureDate.setDate(futureDate.getDate() + 1000);
+  Assert.throws(
+    () =>
+      PlacesUtils.history.insert({
+        url: TEST_URL,
+        visits: [
+          {
+            transition: TRANSITION_LINK,
+            date: futureDate,
+          },
+        ],
+      }),
+    /PageInfo: Invalid value for property/,
+    "passing a visit object with a future date to History.insert should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.insert({
+        url: TEST_URL,
+        visits: [{ transition: "a" }],
+      }),
+    /PageInfo: Invalid value for property/,
+    "passing a visit object with an invalid transition to History.insert should throw an Error"
+  );
+});
+
+add_task(async function test_history_insert() {
+  const TEST_URL = "http://mozilla.com/";
+
+  let inserter = async function (name, filter, referrer, date, transition) {
+    info(name);
+    info(
+      `filter: ${filter}, referrer: ${referrer}, date: ${date}, transition: ${transition}`
+    );
+
+    let uri = NetUtil.newURI(TEST_URL + Math.random());
+    let title = "Visit " + Math.random();
+
+    let pageInfo = {
+      title,
+      visits: [{ transition, referrer, date }],
+    };
+
+    pageInfo.url = await filter(uri);
+
+    let result = await PlacesUtils.history.insert(pageInfo);
+
+    Assert.ok(
+      PlacesUtils.isValidGuid(result.guid),
+      "guid for pageInfo object is valid"
+    );
+    Assert.equal(
+      uri.spec,
+      result.url.href,
+      "url is correct for pageInfo object"
+    );
+    Assert.equal(title, result.title, "title is correct for pageInfo object");
+    Assert.equal(
+      TRANSITION_LINK,
+      result.visits[0].transition,
+      "transition is correct for pageInfo object"
+    );
+    if (referrer) {
+      Assert.equal(
+        referrer,
+        result.visits[0].referrer.href,
+        "url of referrer for visit is correct"
+      );
+    } else {
+      Assert.equal(
+        null,
+        result.visits[0].referrer,
+        "url of referrer for visit is correct"
+      );
+    }
+    if (date) {
+      Assert.equal(
+        Number(date),
+        Number(result.visits[0].date),
+        "date of visit is correct"
+      );
+    }
+
+    Assert.ok(await PlacesTestUtils.isPageInDB(uri), "Page was added");
+    Assert.ok(await PlacesTestUtils.visitsInDB(uri), "Visit was added");
+  };
+
+  try {
+    for (let referrer of [TEST_URL, null]) {
+      for (let date of [new Date(), null]) {
+        for (let transition of [TRANSITION_LINK, null]) {
+          await inserter(
+            "Testing History.insert() with an nsIURI",
+            x => x,
+            referrer,
+            date,
+            transition
+          );
+          await inserter(
+            "Testing History.insert() with a string url",
+            x => x.spec,
+            referrer,
+            date,
+            transition
+          );
+          await inserter(
+            "Testing History.insert() with a URL object",
+            x => URL.fromURI(x),
+            referrer,
+            date,
+            transition
+          );
+        }
+      }
+    }
+  } finally {
+    await PlacesUtils.history.clear();
+  }
+});
diff --git a/toolkit/components/places/tests/history/test_insertMany.js b/toolkit/components/places/tests/history/test_insertMany.js
new file mode 100644
index 0000000000..d261d3eaaa
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_insertMany.js
@@ -0,0 +1,247 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests for `History.insertMany` as implemented in History.jsm
+
+"use strict";
+
+add_task(async function test_error_cases() {
+  let validPageInfo = {
+    url: "http://mozilla.com",
+    visits: [{ transition: TRANSITION_LINK }],
+  };
+
+  Assert.throws(
+    () => PlacesUtils.history.insertMany(),
+    /TypeError: pageInfos must be an array/,
+    "passing a null into History.insertMany should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insertMany([]),
+    /TypeError: pageInfos may not be an empty array/,
+    "passing an empty array into History.insertMany should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.insertMany([validPageInfo, {}]),
+    /Error: PageInfo: The following properties were expected/,
+    "passing a second invalid PageInfo object to History.insertMany should throw an Error"
+  );
+});
+
+add_task(async function test_insertMany() {
+  const BAD_URLS = ["about:config", "chrome://browser/content/browser.xhtml"];
+  const GOOD_URLS = [1, 2, 3].map(x => {
+    return `http://mozilla.com/${x}`;
+  });
+
+  let makePageInfos = async function (urls, filter = x => x) {
+    let pageInfos = [];
+    for (let url of urls) {
+      let uri = NetUtil.newURI(url);
+
+      let pageInfo = {
+        title: `Visit to ${url}`,
+        visits: [{ transition: TRANSITION_LINK }],
+      };
+
+      pageInfo.url = await filter(uri);
+      pageInfos.push(pageInfo);
+    }
+    return pageInfos;
+  };
+
+  let inserter = async function (name, filter, useCallbacks) {
+    info(name);
+    info(`filter: ${filter}`);
+    info(`useCallbacks: ${useCallbacks}`);
+    await PlacesUtils.history.clear();
+
+    let result;
+    let allUrls = GOOD_URLS.concat(BAD_URLS);
+    let pageInfos = await makePageInfos(allUrls, filter);
+
+    if (useCallbacks) {
+      let onResultUrls = [];
+      let onErrorUrls = [];
+      result = await PlacesUtils.history.insertMany(
+        pageInfos,
+        pageInfo => {
+          let url = pageInfo.url.href;
+          Assert.ok(
+            GOOD_URLS.includes(url),
+            "onResult callback called for correct url"
+          );
+          onResultUrls.push(url);
+          Assert.equal(
+            `Visit to ${url}`,
+            pageInfo.title,
+            "onResult callback provides the correct title"
+          );
+          Assert.ok(
+            PlacesUtils.isValidGuid(pageInfo.guid),
+            "onResult callback provides a valid guid"
+          );
+        },
+        pageInfo => {
+          let url = pageInfo.url.href;
+          Assert.ok(
+            BAD_URLS.includes(url),
+            "onError callback called for correct uri"
+          );
+          onErrorUrls.push(url);
+          Assert.equal(
+            undefined,
+            pageInfo.title,
+            "onError callback provides the correct title"
+          );
+          Assert.equal(
+            undefined,
+            pageInfo.guid,
+            "onError callback provides the expected guid"
+          );
+        }
+      );
+      Assert.equal(
+        GOOD_URLS.sort().toString(),
+        onResultUrls.sort().toString(),
+        "onResult callback was called for each good url"
+      );
+      Assert.equal(
+        BAD_URLS.sort().toString(),
+        onErrorUrls.sort().toString(),
+        "onError callback was called for each bad url"
+      );
+    } else {
+      const promiseRankingChanged =
+        PlacesTestUtils.waitForNotification("pages-rank-changed");
+      result = await PlacesUtils.history.insertMany(pageInfos);
+      await promiseRankingChanged;
+    }
+
+    Assert.equal(undefined, result, "insertMany returned undefined");
+
+    for (let url of allUrls) {
+      let expected = GOOD_URLS.includes(url);
+      Assert.equal(
+        expected,
+        await PlacesTestUtils.isPageInDB(url),
+        `isPageInDB for ${url} is ${expected}`
+      );
+      Assert.equal(
+        expected,
+        await PlacesTestUtils.visitsInDB(url),
+        `visitsInDB for ${url} is ${expected}`
+      );
+    }
+  };
+
+  try {
+    for (let useCallbacks of [false, true]) {
+      await inserter(
+        "Testing History.insertMany() with an nsIURI",
+        x => x,
+        useCallbacks
+      );
+      await inserter(
+        "Testing History.insertMany() with a string url",
+        x => x.spec,
+        useCallbacks
+      );
+      await inserter(
+        "Testing History.insertMany() with a URL object",
+        x => URL.fromURI(x),
+        useCallbacks
+      );
+    }
+    // Test rejection when no items added
+    let pageInfos = await makePageInfos(BAD_URLS);
+    PlacesUtils.history.insertMany(pageInfos).then(
+      () => {
+        Assert.ok(
+          false,
+          "History.insertMany rejected promise with all bad URLs"
+        );
+      },
+      error => {
+        Assert.equal(
+          "No items were added to history.",
+          error.message,
+          "History.insertMany rejected promise with all bad URLs"
+        );
+      }
+    );
+  } finally {
+    await PlacesUtils.history.clear();
+  }
+});
+
+add_task(async function test_transitions() {
+  const places = Object.keys(PlacesUtils.history.TRANSITIONS).map(
+    transition => {
+      return {
+        url: `http://places.test/${transition}`,
+        visits: [{ transition: PlacesUtils.history.TRANSITIONS[transition] }],
+      };
+    }
+  );
+  // Should not reject.
+  await PlacesUtils.history.insertMany(places);
+  // Check callbacks.
+  let count = 0;
+  await PlacesUtils.history.insertMany(places, pageInfo => {
+    ++count;
+  });
+  Assert.equal(count, Object.keys(PlacesUtils.history.TRANSITIONS).length);
+});
+
+add_task(async function test_guid() {
+  const guidA = "aaaaaaaaaaaa";
+  const guidB = "bbbbbbbbbbbb";
+  const guidC = "cccccccccccc";
+
+  await PlacesUtils.history.insertMany([
+    {
+      title: "foo",
+      url: "http://example.com/foo",
+      guid: guidA,
+      visits: [{ transition: TRANSITION_LINK, date: new Date() }],
+    },
+  ]);
+
+  Assert.ok(
+    await PlacesUtils.history.fetch(guidA),
+    "Record is inserted with correct GUID"
+  );
+
+  let expectedGuids = new Set([guidB, guidC]);
+  await PlacesUtils.history.insertMany(
+    [
+      {
+        title: "bar",
+        url: "http://example.com/bar",
+        guid: guidB,
+        visits: [{ transition: TRANSITION_LINK, date: new Date() }],
+      },
+      {
+        title: "baz",
+        url: "http://example.com/baz",
+        guid: guidC,
+        visits: [{ transition: TRANSITION_LINK, date: new Date() }],
+      },
+    ],
+    pageInfo => {
+      Assert.ok(expectedGuids.has(pageInfo.guid));
+      expectedGuids.delete(pageInfo.guid);
+    }
+  );
+  Assert.equal(expectedGuids.size, 0);
+
+  Assert.ok(
+    await PlacesUtils.history.fetch(guidB),
+    "Record B is fetchable after insertMany"
+  );
+  Assert.ok(
+    await PlacesUtils.history.fetch(guidC),
+    "Record C is fetchable after insertMany"
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_insert_null_title.js b/toolkit/components/places/tests/history/test_insert_null_title.js
new file mode 100644
index 0000000000..8cdcddd1e8
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_insert_null_title.js
@@ -0,0 +1,78 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests that passing a null title to history insert or update doesn't overwrite
+// an existing title, while an empty string does.
+
+"use strict";
+
+async function fetchTitle(url) {
+  let entry;
+  await TestUtils.waitForCondition(async () => {
+    entry = await PlacesUtils.history.fetch(url);
+    return !!entry;
+  }, "fetch title for entry");
+  return entry.title;
+}
+
+add_task(async function () {
+  const url = "http://mozilla.com";
+  let title = "Mozilla";
+
+  info("Insert a visit with a title");
+  let result = await PlacesUtils.history.insert({
+    url,
+    title,
+    visits: [{ transition: PlacesUtils.history.TRANSITIONS.LINK }],
+  });
+  Assert.equal(title, result.title, "title should be stored");
+  Assert.equal(title, await fetchTitle(url), "title should be stored");
+
+  // This is shared by the next tests.
+  let promiseTitleChange = PlacesTestUtils.waitForNotification(
+    "page-title-changed",
+    () => (notified = true)
+  );
+
+  info("Insert a visit with a null title, should not clear the previous title");
+  let notified = false;
+  result = await PlacesUtils.history.insert({
+    url,
+    title: null,
+    visits: [{ transition: PlacesUtils.history.TRANSITIONS.LINK }],
+  });
+  Assert.equal(title, result.title, "title should be unchanged");
+  Assert.equal(title, await fetchTitle(url), "title should be unchanged");
+  await Promise.race([
+    promiseTitleChange,
+    new Promise(r => do_timeout(1000, r)),
+  ]);
+  Assert.ok(!notified, "A title change should not be notified");
+
+  info(
+    "Insert a visit without specifying a title, should not clear the previous title"
+  );
+  notified = false;
+  result = await PlacesUtils.history.insert({
+    url,
+    visits: [{ transition: PlacesUtils.history.TRANSITIONS.LINK }],
+  });
+  Assert.equal(title, result.title, "title should be unchanged");
+  Assert.equal(title, await fetchTitle(url), "title should be unchanged");
+  await Promise.race([
+    promiseTitleChange,
+    new Promise(r => do_timeout(1000, r)),
+  ]);
+  Assert.ok(!notified, "A title change should not be notified");
+
+  info("Insert a visit with an empty title, should clear the previous title");
+  result = await PlacesUtils.history.insert({
+    url,
+    title: "",
+    visits: [{ transition: PlacesUtils.history.TRANSITIONS.LINK }],
+  });
+  info("Waiting for the title change notification");
+  await promiseTitleChange;
+  Assert.equal("", result.title, "title should be empty");
+  Assert.equal("", await fetchTitle(url), "title should be empty");
+});
diff --git a/toolkit/components/places/tests/history/test_remove.js b/toolkit/components/places/tests/history/test_remove.js
new file mode 100644
index 0000000000..8c5e941fd0
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_remove.js
@@ -0,0 +1,354 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+
+// Tests for `History.remove`, as implemented in History.jsm
+
+"use strict";
+
+// Test removing a single page
+add_task(async function test_remove_single() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  let WITNESS_URI = NetUtil.newURI(
+    "http://mozilla.com/test_browserhistory/test_remove/" + Math.random()
+  );
+  await PlacesTestUtils.addVisits(WITNESS_URI);
+  Assert.ok(page_in_database(WITNESS_URI));
+
+  let remover = async function (name, filter, options) {
+    info(name);
+    info(JSON.stringify(options));
+    info("Setting up visit");
+
+    let uri = NetUtil.newURI(
+      "http://mozilla.com/test_browserhistory/test_remove/" + Math.random()
+    );
+    let title = "Visit " + Math.random();
+    await PlacesTestUtils.addVisits({ uri, title });
+    Assert.ok(visits_in_database(uri), "History entry created");
+
+    let removeArg = await filter(uri);
+
+    if (options.addBookmark) {
+      await PlacesUtils.bookmarks.insert({
+        parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+        url: uri,
+        title: "test bookmark",
+      });
+    }
+
+    let shouldRemove = !options.addBookmark;
+    let placesEventListener;
+    let promiseObserved = new Promise((resolve, reject) => {
+      placesEventListener = events => {
+        for (const event of events) {
+          switch (event.type) {
+            case "page-title-changed": {
+              reject(
+                "Unexpected page-title-changed event happens on " + event.url
+              );
+              break;
+            }
+            case "history-cleared": {
+              reject("Unexpected history-cleared event happens");
+              break;
+            }
+            case "pages-rank-changed": {
+              try {
+                Assert.ok(!shouldRemove, "Observing pages-rank-changed event");
+              } finally {
+                resolve();
+              }
+              break;
+            }
+            case "page-removed": {
+              Assert.equal(
+                event.isRemovedFromStore,
+                shouldRemove,
+                "Observe page-removed event with right removal type"
+              );
+              Assert.equal(
+                event.url,
+                uri.spec,
+                "Observing effect on the right uri"
+              );
+              resolve();
+              break;
+            }
+          }
+        }
+      };
+    });
+    PlacesObservers.addListener(
+      [
+        "page-title-changed",
+        "history-cleared",
+        "pages-rank-changed",
+        "page-removed",
+      ],
+      placesEventListener
+    );
+
+    info("Performing removal");
+    let removed = false;
+    if (options.useCallback) {
+      let onRowCalled = false;
+      let guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+        url: uri,
+      });
+      removed = await PlacesUtils.history.remove(removeArg, page => {
+        Assert.equal(onRowCalled, false, "Callback has not been called yet");
+        onRowCalled = true;
+        Assert.equal(
+          page.url.href,
+          uri.spec,
+          "Callback provides the correct url"
+        );
+        Assert.equal(page.guid, guid, "Callback provides the correct guid");
+        Assert.equal(page.title, title, "Callback provides the correct title");
+      });
+      Assert.ok(onRowCalled, "Callback has been called");
+    } else {
+      removed = await PlacesUtils.history.remove(removeArg);
+    }
+
+    await promiseObserved;
+    PlacesObservers.removeListener(
+      [
+        "page-title-changed",
+        "history-cleared",
+        "pages-rank-changed",
+        "page-removed",
+      ],
+      placesEventListener
+    );
+
+    Assert.equal(visits_in_database(uri), 0, "History entry has disappeared");
+    Assert.notEqual(
+      visits_in_database(WITNESS_URI),
+      0,
+      "Witness URI still has visits"
+    );
+    Assert.notEqual(
+      page_in_database(WITNESS_URI),
+      0,
+      "Witness URI is still here"
+    );
+    if (shouldRemove) {
+      Assert.ok(removed, "Something was removed");
+      Assert.equal(page_in_database(uri), 0, "Page has disappeared");
+    } else {
+      Assert.ok(!removed, "The page was not removed, as there was a bookmark");
+      Assert.notEqual(page_in_database(uri), 0, "The page is still present");
+    }
+  };
+
+  try {
+    for (let useCallback of [false, true]) {
+      for (let addBookmark of [false, true]) {
+        let options = { useCallback, addBookmark };
+        await remover(
+          "Testing History.remove() with a single URI",
+          x => x,
+          options
+        );
+        await remover(
+          "Testing History.remove() with a single string url",
+          x => x.spec,
+          options
+        );
+        await remover(
+          "Testing History.remove() with a single string guid",
+          async x =>
+            PlacesTestUtils.getDatabaseValue("moz_places", "guid", { url: x }),
+          options
+        );
+        await remover(
+          "Testing History.remove() with a single URI in an array",
+          x => [x],
+          options
+        );
+        await remover(
+          "Testing History.remove() with a single string url in an array",
+          x => [x.spec],
+          options
+        );
+        await remover(
+          "Testing History.remove() with a single string guid in an array",
+          x =>
+            PlacesTestUtils.getDatabaseValue("moz_places", "guid", { url: x }),
+          options
+        );
+      }
+    }
+  } finally {
+    await PlacesUtils.history.clear();
+  }
+});
+
+add_task(async function cleanup() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+});
+
+// Test the various error cases
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.remove(),
+    /TypeError: Invalid url/,
+    "History.remove with no argument should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove(null),
+    /TypeError: Invalid url/,
+    "History.remove with `null` should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove(undefined),
+    /TypeError: Invalid url/,
+    "History.remove with `undefined` should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove("not a guid, obviously"),
+    /TypeError: .* is not a valid URL/,
+    "History.remove with an ill-formed guid/url argument should throw a TypeError"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.remove({
+        "not the kind of object we know how to handle": true,
+      }),
+    /TypeError: Invalid url/,
+    "History.remove with an unexpected object should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove([]),
+    /TypeError: Expected at least one page/,
+    "History.remove with an empty array should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove([null]),
+    /TypeError: Invalid url or guid/,
+    "History.remove with an array containing null should throw a TypeError"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.remove([
+        "http://example.org",
+        "not a guid, obviously",
+      ]),
+    /TypeError: .* is not a valid URL/,
+    "History.remove with an array containing an ill-formed guid/url argument should throw a TypeError"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.remove(["0123456789ab" /* valid guid*/, null]),
+    /TypeError: Invalid url or guid: null/,
+    "History.remove with an array containing a guid and a second argument that is null should throw a TypeError"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.remove([
+        "http://example.org",
+        { "not the kind of object we know how to handle": true },
+      ]),
+    /TypeError: Invalid url/,
+    "History.remove with an array containing an unexpected objecgt should throw a TypeError"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.remove(
+        "http://example.org",
+        "not a function, obviously"
+      ),
+    /TypeError: Invalid function/,
+    "History.remove with a second argument that is not a function argument should throw a TypeError"
+  );
+  try {
+    PlacesUtils.history.remove(
+      "http://example.org/I/have/clearly/not/been/added",
+      null
+    );
+    Assert.ok(true, "History.remove should ignore `null` as a second argument");
+  } catch (ex) {
+    Assert.ok(
+      false,
+      "History.remove should ignore `null` as a second argument"
+    );
+  }
+});
+
+add_task(async function test_orphans() {
+  let uri = NetUtil.newURI("http://moz.org/");
+  await PlacesTestUtils.addVisits({ uri });
+
+  PlacesUtils.favicons.setAndFetchFaviconForPage(
+    uri,
+    SMALLPNG_DATA_URI,
+    true,
+    PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+    null,
+    Services.scriptSecurityManager.getSystemPrincipal()
+  );
+  // Also create a root icon.
+  let faviconURI = Services.io.newURI(uri.spec + "favicon.ico");
+  PlacesUtils.favicons.replaceFaviconDataFromDataURL(
+    faviconURI,
+    SMALLPNG_DATA_URI.spec,
+    0,
+    Services.scriptSecurityManager.getSystemPrincipal()
+  );
+  PlacesUtils.favicons.setAndFetchFaviconForPage(
+    uri,
+    faviconURI,
+    true,
+    PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+    null,
+    Services.scriptSecurityManager.getSystemPrincipal()
+  );
+
+  await PlacesUtils.history.update({
+    url: uri,
+    annotations: new Map([["test", "restval"]]),
+  });
+
+  await PlacesUtils.history.remove(uri);
+  Assert.ok(
+    !(await PlacesTestUtils.isPageInDB(uri)),
+    "Page should have been removed"
+  );
+
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(`SELECT (SELECT count(*) FROM moz_annos) +
+                                      (SELECT count(*) FROM moz_icons) +
+                                      (SELECT count(*) FROM moz_pages_w_icons) +
+                                      (SELECT count(*) FROM moz_icons_to_pages) AS count`);
+  Assert.equal(rows[0].getResultByName("count"), 0, "Should not find orphans");
+});
+
+add_task(async function test_remove_backslash() {
+  // Backslash is an escape char in Sqlite, we must take care of that when
+  // removing a url containing a backslash.
+  const url = "https://www.mozilla.org/?test=\u005C";
+  await PlacesTestUtils.addVisits(url);
+  Assert.ok(await PlacesUtils.history.remove(url), "A page should be removed");
+  Assert.deepEqual(
+    await PlacesUtils.history.fetch(url),
+    null,
+    "The page should not be found"
+  );
+});
+
+add_task(async function test_url_with_apices() {
+  // Apices may confuse code and cause injection if mishandled.
+  // The ideal test would be with a javascript url, because it would not be
+  // encoded by URL(), unfortunately it would also not be added to history.
+  const url = `http://mozilla.org/\u0022\u0027`;
+  await PlacesTestUtils.addVisits(url);
+  Assert.ok(await PlacesUtils.history.remove(url), "A page should be removed");
+  Assert.deepEqual(
+    await PlacesUtils.history.fetch(url),
+    null,
+    "The page should not be found"
+  );
+});
diff --git a/toolkit/components/places/tests/history/test_removeByFilter.js b/toolkit/components/places/tests/history/test_removeByFilter.js
new file mode 100644
index 0000000000..fb18bf8e74
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_removeByFilter.js
@@ -0,0 +1,497 @@
+"use strict";
+
+/*
+This test will ideally test the following cases
+(each with and without a callback associated with it)
+  Case A: Tests which should remove pages (Positives)
+    Case A 1: Page has multiple visits both in/out of timeframe, all get deleted
+    Case A 2: Page has single uri, removed by host
+    Case A 3: Page has random subhost, with same host, removed by wildcard
+    Case A 4: Page is localhost and localhost:port, removed by host
+    Case A 5: Page is a `file://` type address, removed by empty host
+    Cases A 1,2,3 will be tried with and without bookmarks added (which prevent page deletion)
+  Case B: Tests in which no pages are removed (Inverses)
+    Case B 1 (inverse): Page has no visits in timeframe, and nothing is deleted
+    Case B 2: Page has single uri, not removed since hostname is different
+    Case B 3: Page has multiple subhosts, not removed since wildcard doesn't match
+  Case C: Combinations tests
+    Case C 1: Single hostname, multiple visits, at least one in timeframe and hostname
+    Case C 2: Random subhosts, multiple visits, at least one in timeframe and hostname-wildcard
+*/
+
+add_task(async function test_removeByFilter() {
+  // Cleanup
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  // Adding a witness URI
+  let witnessURI = NetUtil.newURI(
+    "http://witnessmozilla.org/test_browserhistory/test_removeByFilter" +
+      Math.random()
+  );
+  await PlacesTestUtils.addVisits(witnessURI);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(witnessURI),
+    "Witness URI is in database"
+  );
+
+  let removeByFilterTester = async function (
+    visits,
+    filter,
+    checkBeforeRemove,
+    checkAfterRemove,
+    useCallback,
+    bookmarkedUri
+  ) {
+    // Add visits for URIs
+    await PlacesTestUtils.addVisits(visits);
+    if (
+      bookmarkedUri !== null &&
+      visits.map(v => v.uri).includes(bookmarkedUri)
+    ) {
+      await PlacesUtils.bookmarks.insert({
+        parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+        url: bookmarkedUri,
+        title: "test bookmark",
+      });
+    }
+    await checkBeforeRemove();
+
+    // Take care of any observers (due to bookmarks)
+    let { placesEventListener, promiseObserved } =
+      getObserverPromise(bookmarkedUri);
+    if (placesEventListener) {
+      PlacesObservers.addListener(
+        ["page-title-changed", "history-cleared", "page-removed"],
+        placesEventListener
+      );
+    }
+    // Perfom delete operation on database
+    let removed = false;
+    if (useCallback) {
+      // The amount of callbacks will be the unique URIs to remove from the database
+      let netCallbacksRequired = new Set(visits.map(v => v.uri)).size;
+      removed = await PlacesUtils.history.removeByFilter(filter, pageInfo => {
+        Assert.ok(
+          PlacesUtils.validatePageInfo(pageInfo, false),
+          "pageInfo should follow a basic format"
+        );
+        Assert.ok(
+          netCallbacksRequired > 0,
+          "Callback called as many times as required"
+        );
+        netCallbacksRequired--;
+      });
+    } else {
+      removed = await PlacesUtils.history.removeByFilter(filter);
+    }
+    await checkAfterRemove();
+    await promiseObserved;
+    if (placesEventListener) {
+      await PlacesUtils.bookmarks.eraseEverything();
+      PlacesObservers.removeListener(
+        ["page-title-changed", "history-cleared", "page-removed"],
+        placesEventListener
+      );
+    }
+    Assert.ok(
+      await PlacesTestUtils.isPageInDB(witnessURI),
+      "Witness URI is still in database"
+    );
+    return removed;
+  };
+
+  const remoteUriList = [
+    "http://mozilla.org/test_browserhistory/test_removeByFilter/" +
+      Math.random(),
+    "http://subdomain1.mozilla.org/test_browserhistory/test_removeByFilter/" +
+      Math.random(),
+    "http://subdomain2.mozilla.org/test_browserhistory/test_removeByFilter/" +
+      Math.random(),
+  ];
+  const localhostUriList = [
+    "http://localhost:4500/" + Math.random(),
+    "http://localhost/" + Math.random(),
+  ];
+  const fileUriList = ["file:///home/user/files" + Math.random()];
+  const title = "Title " + Math.random();
+  let sameHostVisits = [
+    {
+      uri: remoteUriList[0],
+      title,
+      visitDate: new Date(2005, 1, 1) * 1000,
+    },
+    {
+      uri: remoteUriList[0],
+      title,
+      visitDate: new Date(2005, 3, 3) * 1000,
+    },
+    {
+      uri: remoteUriList[0],
+      title,
+      visitDate: new Date(2007, 1, 1) * 1000,
+    },
+  ];
+  let randomHostVisits = [
+    {
+      uri: remoteUriList[0],
+      title,
+      visitDate: new Date(2005, 1, 1) * 1000,
+    },
+    {
+      uri: remoteUriList[1],
+      title,
+      visitDate: new Date(2005, 3, 3) * 1000,
+    },
+    {
+      uri: remoteUriList[2],
+      title,
+      visitDate: new Date(2007, 1, 1) * 1000,
+    },
+  ];
+  let localhostVisits = [
+    {
+      uri: localhostUriList[0],
+      title,
+    },
+    {
+      uri: localhostUriList[1],
+      title,
+    },
+  ];
+  let fileVisits = [
+    {
+      uri: fileUriList[0],
+      title,
+    },
+  ];
+  let assertInDB = async function (aUri) {
+    Assert.ok(await PlacesTestUtils.isPageInDB(aUri));
+  };
+  let assertNotInDB = async function (aUri) {
+    Assert.ok(!(await PlacesTestUtils.isPageInDB(aUri)));
+  };
+  for (let callbackUse of [true, false]) {
+    // Case A Positives
+    for (let bookmarkUse of [true, false]) {
+      let bookmarkedUri = arr => undefined;
+      let checkableArray = arr => arr;
+      let checkClosure = assertNotInDB;
+      if (bookmarkUse) {
+        bookmarkedUri = arr => arr[0];
+        checkableArray = arr => arr.slice(1);
+        checkClosure = function (aUri) {};
+      }
+      // Case A 1: Dates
+      await removeByFilterTester(
+        sameHostVisits,
+        { beginDate: new Date(2004, 1, 1), endDate: new Date(2006, 1, 1) },
+        () => assertInDB(remoteUriList[0]),
+        () => checkClosure(remoteUriList[0]),
+        callbackUse,
+        bookmarkedUri(remoteUriList)
+      );
+      // Case A 2: Single Sub-host
+      await removeByFilterTester(
+        sameHostVisits,
+        { host: "mozilla.org" },
+        () => assertInDB(remoteUriList[0]),
+        () => checkClosure(remoteUriList[0]),
+        callbackUse,
+        bookmarkedUri(remoteUriList)
+      );
+      // Case A 3: Multiple subhost
+      await removeByFilterTester(
+        randomHostVisits,
+        { host: ".mozilla.org" },
+        async () => {
+          for (let uri of remoteUriList) {
+            await assertInDB(uri);
+          }
+        },
+        async () => {
+          for (let uri of checkableArray(remoteUriList)) {
+            await checkClosure(uri);
+          }
+        },
+        callbackUse,
+        bookmarkedUri(remoteUriList)
+      );
+    }
+
+    // Case A 4: Localhost
+    await removeByFilterTester(
+      localhostVisits,
+      { host: "localhost" },
+      async () => {
+        for (let uri of localhostUriList) {
+          await assertInDB(uri);
+        }
+      },
+      async () => {
+        for (let uri of localhostUriList) {
+          await assertNotInDB(uri);
+        }
+      },
+      callbackUse
+    );
+    // Case A 5: Local Files
+    await removeByFilterTester(
+      fileVisits,
+      { host: "." },
+      async () => {
+        for (let uri of fileUriList) {
+          await assertInDB(uri);
+        }
+      },
+      async () => {
+        for (let uri of fileUriList) {
+          await assertNotInDB(uri);
+        }
+      },
+      callbackUse
+    );
+
+    // Case B: Tests which do not remove anything (inverses)
+    // Case B 1: Date
+    await removeByFilterTester(
+      sameHostVisits,
+      { beginDate: new Date(2001, 1, 1), endDate: new Date(2002, 1, 1) },
+      () => assertInDB(remoteUriList[0]),
+      () => assertInDB(remoteUriList[0]),
+      callbackUse
+    );
+    // Case B 2 : Single subhost
+    await removeByFilterTester(
+      sameHostVisits,
+      { host: "notthere.org" },
+      () => assertInDB(remoteUriList[0]),
+      () => assertInDB(remoteUriList[0]),
+      callbackUse
+    );
+    // Case B 3 : Multiple subhosts
+    await removeByFilterTester(
+      randomHostVisits,
+      { host: ".notthere.org" },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertInDB(uri);
+        }
+      },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertInDB(uri);
+        }
+      },
+      callbackUse
+    );
+    // Case B 4 : invalid local subhost
+    await removeByFilterTester(
+      randomHostVisits,
+      { host: ".org" },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertInDB(uri);
+        }
+      },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertInDB(uri);
+        }
+      },
+      callbackUse
+    );
+
+    // Case C: Combination Cases
+    // Case C 1: single subhost
+    await removeByFilterTester(
+      sameHostVisits,
+      {
+        host: "mozilla.org",
+        beginDate: new Date(2004, 1, 1),
+        endDate: new Date(2006, 1, 1),
+      },
+      () => assertInDB(remoteUriList[0]),
+      () => assertNotInDB(remoteUriList[0]),
+      callbackUse
+    );
+    // Case C 2: multiple subhost
+    await removeByFilterTester(
+      randomHostVisits,
+      {
+        host: ".mozilla.org",
+        beginDate: new Date(2005, 1, 1),
+        endDate: new Date(2017, 1, 1),
+      },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertInDB(uri);
+        }
+      },
+      async () => {
+        for (let uri of remoteUriList) {
+          await assertNotInDB(uri);
+        }
+      },
+      callbackUse
+    );
+  }
+});
+
+// Test various error cases
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter(),
+    /TypeError: Expected a filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter("obviously, not a filter"),
+    /TypeError: Expected a filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({}),
+    /TypeError: Expected a non-empty filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ beginDate: "now" }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ beginDate: Date.now() }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ beginDate: new Date(NaN) }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeByFilter(
+        { beginDate: new Date() },
+        "obviously, not a callback"
+      ),
+    /TypeError: Invalid function/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeByFilter({
+        beginDate: new Date(1000),
+        endDate: new Date(0),
+      }),
+    /TypeError: `beginDate` should be at least as old/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "#" }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "www..org" }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: {} }),
+    /TypeError: `host` should be a string/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "*.mozilla.org" }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "*" }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "local.host." }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "(local files)" }),
+    /TypeError: Expected well formed hostname string for/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeByFilter({ host: "" }),
+    /TypeError: Expected a non-empty filter/
+  );
+});
+
+add_task(async function test_chunking() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  info("Insert many visited pages");
+  let pages = [];
+  for (let i = 1; i <= 1500; i++) {
+    let visits = [
+      {
+        date: new Date(Date.now() - (86400 + i) * 1000),
+        transition: PlacesUtils.history.TRANSITIONS.TYPED,
+      },
+    ];
+    pages.push(
+      {
+        url: `http://example.com/${i}`,
+        title: `Page ${i}`,
+        visits,
+      },
+      {
+        url: `http://subdomain.example.com/${i}`,
+        title: `Subdomain ${i}`,
+        visits,
+      }
+    );
+  }
+  await PlacesUtils.history.insertMany(pages);
+
+  info("Remove all visited pages");
+  await PlacesUtils.history.removeByFilter({
+    host: ".example.com",
+  });
+});
+
+// Helper functions
+
+function getObserverPromise(bookmarkedUri) {
+  if (!bookmarkedUri) {
+    return { promiseObserved: Promise.resolve() };
+  }
+  let placesEventListener;
+  let promiseObserved = new Promise((resolve, reject) => {
+    placesEventListener = events => {
+      for (const event of events) {
+        switch (event.type) {
+          case "page-title-changed": {
+            reject(new Error("Unexpected page-title-changed event happens"));
+            break;
+          }
+          case "history-cleared": {
+            reject(new Error("Unexpected history-cleared event happens"));
+            break;
+          }
+          case "page-removed": {
+            if (event.isRemovedFromStore) {
+              Assert.notEqual(
+                event.url,
+                bookmarkedUri,
+                "Bookmarked URI should not be deleted"
+              );
+            } else {
+              Assert.equal(
+                event.isPartialVisistsRemoval,
+                false,
+                "Observing page-removed deletes all visits"
+              );
+              Assert.equal(
+                event.url,
+                bookmarkedUri,
+                "Bookmarked URI should have all visits removed but not the page itself"
+              );
+            }
+            resolve();
+            break;
+          }
+        }
+      }
+    };
+  });
+  return { placesEventListener, promiseObserved };
+}
diff --git a/toolkit/components/places/tests/history/test_removeMany.js b/toolkit/components/places/tests/history/test_removeMany.js
new file mode 100644
index 0000000000..ff8c3a21ee
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_removeMany.js
@@ -0,0 +1,206 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+
+// Tests for `History.remove` with removing many urls, as implemented in
+// History.jsm.
+
+"use strict";
+
+// Test removing a list of pages
+add_task(async function test_remove_many() {
+  // This is set so that we are guaranteed to trigger REMOVE_PAGES_CHUNKLEN.
+  const SIZE = 310;
+
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  info("Adding a witness page");
+  let WITNESS_URI = NetUtil.newURI(
+    "http://mozilla.com/test_browserhistory/test_remove/" + Math.random()
+  );
+  await PlacesTestUtils.addVisits(WITNESS_URI);
+  Assert.ok(page_in_database(WITNESS_URI), "Witness page added");
+
+  info("Generating samples");
+  let pages = [];
+  for (let i = 0; i < SIZE; ++i) {
+    let uri = NetUtil.newURI(
+      "http://mozilla.com/test_browserhistory/test_remove?sample=" +
+        i +
+        "&salt=" +
+        Math.random()
+    );
+    let title = "Visit " + i + ", " + Math.random();
+    let hasBookmark = i % 3 == 0;
+    let page = {
+      uri,
+      title,
+      hasBookmark,
+      // `true` once `onResult` has been called for this page
+      onResultCalled: false,
+      // `true` once page-removed for store has been fired for this page
+      pageRemovedFromStore: false,
+      // `true` once page-removed for all visits has been fired for this page
+      pageRemovedAllVisits: false,
+    };
+    info("Pushing: " + uri.spec);
+    pages.push(page);
+
+    await PlacesTestUtils.addVisits(page);
+    page.guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+      url: uri,
+    });
+    if (hasBookmark) {
+      await PlacesUtils.bookmarks.insert({
+        parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+        url: uri,
+        title: "test bookmark " + i,
+      });
+    }
+    Assert.ok(page_in_database(uri), "Page added");
+  }
+
+  info("Mixing key types and introducing dangling keys");
+  let keys = [];
+  for (let i = 0; i < SIZE; ++i) {
+    if (i % 4 == 0) {
+      keys.push(pages[i].uri);
+      keys.push(NetUtil.newURI("http://example.org/dangling/nsIURI/" + i));
+    } else if (i % 4 == 1) {
+      keys.push(new URL(pages[i].uri.spec));
+      keys.push(new URL("http://example.org/dangling/URL/" + i));
+    } else if (i % 4 == 2) {
+      keys.push(pages[i].uri.spec);
+      keys.push("http://example.org/dangling/stringuri/" + i);
+    } else {
+      keys.push(pages[i].guid);
+      keys.push(("guid_" + i + "_01234567890").substr(0, 12));
+    }
+  }
+
+  let onPageRankingChanged = false;
+  const placesEventListener = events => {
+    for (const event of events) {
+      switch (event.type) {
+        case "page-title-changed": {
+          Assert.ok(
+            false,
+            "Unexpected page-title-changed event happens on " + event.url
+          );
+          break;
+        }
+        case "history-cleared": {
+          Assert.ok(false, "Unexpected history-cleared event happens");
+          break;
+        }
+        case "pages-rank-changed": {
+          onPageRankingChanged = true;
+          break;
+        }
+        case "page-removed": {
+          const origin = pages.find(x => x.uri.spec === event.url);
+          Assert.ok(origin);
+
+          if (event.isRemovedFromStore) {
+            Assert.ok(
+              !origin.hasBookmark,
+              "Observing page-removed event on a page without a bookmark"
+            );
+            Assert.ok(
+              !origin.pageRemovedFromStore,
+              "Observing page-removed for store for the first time"
+            );
+            origin.pageRemovedFromStore = true;
+          } else {
+            Assert.ok(
+              !origin.pageRemovedAllVisits,
+              "Observing page-removed for all visits for the first time"
+            );
+            origin.pageRemovedAllVisits = true;
+          }
+          break;
+        }
+      }
+    }
+  };
+
+  PlacesObservers.addListener(
+    [
+      "page-title-changed",
+      "history-cleared",
+      "pages-rank-changed",
+      "page-removed",
+    ],
+    placesEventListener
+  );
+
+  info("Removing the pages and checking the callbacks");
+
+  let removed = await PlacesUtils.history.remove(keys, page => {
+    let origin = pages.find(candidate => candidate.uri.spec == page.url.href);
+
+    Assert.ok(origin, "onResult has a valid page");
+    Assert.ok(!origin.onResultCalled, "onResult has not seen this page yet");
+    origin.onResultCalled = true;
+    Assert.equal(page.guid, origin.guid, "onResult has the right guid");
+    Assert.equal(page.title, origin.title, "onResult has the right title");
+  });
+  Assert.ok(removed, "Something was removed");
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  PlacesObservers.removeListener(
+    [
+      "page-title-changed",
+      "history-cleared",
+      "pages-rank-changed",
+      "page-removed",
+    ],
+    placesEventListener
+  );
+
+  info("Checking out results");
+  // By now the observers should have been called.
+  for (let i = 0; i < pages.length; ++i) {
+    let page = pages[i];
+    Assert.ok(
+      page.onResultCalled,
+      `We have reached the page #${i} from the callback`
+    );
+    Assert.ok(
+      visits_in_database(page.uri) == 0,
+      "History entry has disappeared"
+    );
+    Assert.equal(
+      page_in_database(page.uri) != 0,
+      page.hasBookmark,
+      "Page is present only if it also has bookmarks"
+    );
+    Assert.notEqual(
+      page.pageRemovedFromStore,
+      page.pageRemovedAllVisits,
+      "Either only page-removed event for store or all visits should be called"
+    );
+  }
+
+  Assert.equal(
+    onPageRankingChanged,
+    pages.some(p => p.pageRemovedFromStore || p.pageRemovedAllVisits),
+    "page-rank-changed was fired"
+  );
+
+  Assert.notEqual(
+    visits_in_database(WITNESS_URI),
+    0,
+    "Witness URI still has visits"
+  );
+  Assert.notEqual(
+    page_in_database(WITNESS_URI),
+    0,
+    "Witness URI is still here"
+  );
+});
+
+add_task(async function cleanup() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+});
diff --git a/toolkit/components/places/tests/history/test_removeVisits.js b/toolkit/components/places/tests/history/test_removeVisits.js
new file mode 100644
index 0000000000..3a82132bd8
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_removeVisits.js
@@ -0,0 +1,376 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+const JS_NOW = Date.now();
+const DB_NOW = JS_NOW * 1000;
+const TEST_URI = uri("http://example.com/");
+
+async function cleanup() {
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+  // This is needed to remove place: entries.
+  DBConn().executeSimpleSQL("DELETE FROM moz_places");
+}
+
+add_task(async function remove_visits_outside_unbookmarked_uri() {
+  info(
+    "*** TEST: Remove some visits outside valid timeframe from an unbookmarked URI"
+  );
+
+  info("Add 10 visits for the URI from way in the past.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - 100000 - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+
+  info("Remove visits using timerange outside the URI's visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 10),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+
+  info("Run a history query and check that all visits still exist.");
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 10);
+  for (let i = 0; i < root.childCount; i++) {
+    let visitTime = root.getChild(i).time;
+    Assert.equal(visitTime, DB_NOW - 100000 - i * 1000);
+  }
+  root.containerOpen = false;
+
+  Assert.ok(
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should exist"
+  );
+
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+  info("Frecency should be positive.");
+  Assert.ok(
+    (await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    })) > 0
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_visits_outside_bookmarked_uri() {
+  info(
+    "*** TEST: Remove some visits outside valid timeframe from a bookmarked URI"
+  );
+
+  info("Add 10 visits for the URI from way in the past.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - 100000 - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+  info("Bookmark the URI.");
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: TEST_URI,
+    title: "bookmark title",
+  });
+
+  info("Remove visits using timerange outside the URI's visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 10),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+
+  info("Run a history query and check that all visits still exist.");
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 10);
+  for (let i = 0; i < root.childCount; i++) {
+    let visitTime = root.getChild(i).time;
+    Assert.equal(visitTime, DB_NOW - 100000 - i * 1000);
+  }
+  root.containerOpen = false;
+
+  Assert.ok(
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should exist"
+  );
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("Frecency should be positive.");
+  Assert.ok(
+    (await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    })) > 0
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_visits_unbookmarked_uri() {
+  info("*** TEST: Remove some visits from an unbookmarked URI");
+
+  info("Add 10 visits for the URI from now to 9 usecs in the past.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+
+  info("Remove the 5 most recent visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 4),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+
+  info(
+    "Run a history query and check that only the older 5 visits still exist."
+  );
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 5);
+  for (let i = 0; i < root.childCount; i++) {
+    let visitTime = root.getChild(i).time;
+    Assert.equal(visitTime, DB_NOW - i * 1000 - 5000);
+  }
+  root.containerOpen = false;
+
+  Assert.ok(
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should exist"
+  );
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("Frecency should be positive.");
+  Assert.ok(
+    (await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    })) > 0
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_visits_bookmarked_uri() {
+  info("*** TEST: Remove some visits from a bookmarked URI");
+
+  info("Add 10 visits for the URI from now to 9 usecs in the past.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+  info("Bookmark the URI.");
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: TEST_URI,
+    title: "bookmark title",
+  });
+
+  info("Remove the 5 most recent visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 4),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+
+  info(
+    "Run a history query and check that only the older 5 visits still exist."
+  );
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 5);
+  for (let i = 0; i < root.childCount; i++) {
+    let visitTime = root.getChild(i).time;
+    Assert.equal(visitTime, DB_NOW - i * 1000 - 5000);
+  }
+  root.containerOpen = false;
+
+  Assert.ok(
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should exist"
+  );
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("Frecency should be positive.");
+  Assert.ok(
+    (await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    })) > 0
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_all_visits_unbookmarked_uri() {
+  info("*** TEST: Remove all visits from an unbookmarked URI");
+
+  info("Add some visits for the URI.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+
+  info("Remove all visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 10),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should no longer exist in moz_places.");
+  Assert.ok(!page_in_database(TEST_URI.spec));
+
+  info("Run a history query and check that no visits exist.");
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 0);
+  root.containerOpen = false;
+
+  Assert.equal(
+    false,
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should not exist"
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_all_visits_bookmarked_uri() {
+  info("*** TEST: Remove all visits from a bookmarked URI");
+
+  info("Add some visits for the URI.");
+  let visits = [];
+  for (let i = 0; i < 10; i++) {
+    visits.push({ uri: TEST_URI, visitDate: DB_NOW - i * 1000 });
+  }
+  await PlacesTestUtils.addVisits(visits);
+  info("Bookmark the URI.");
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: TEST_URI,
+    title: "bookmark title",
+  });
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+  let initialFrecency = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "frecency",
+    { url: TEST_URI }
+  );
+
+  info("Remove all visits.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 10),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+
+  info("Run a history query and check that no visits exist.");
+  let query = PlacesUtils.history.getNewQuery();
+  let opts = PlacesUtils.history.getNewQueryOptions();
+  opts.resultType = opts.RESULTS_AS_VISIT;
+  opts.sortingMode = opts.SORT_BY_DATE_DESCENDING;
+  let root = PlacesUtils.history.executeQuery(query, opts).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 0);
+  root.containerOpen = false;
+
+  Assert.equal(
+    false,
+    await PlacesUtils.history.hasVisits(TEST_URI),
+    "visit should not exist"
+  );
+
+  info("URI should be bookmarked");
+  Assert.ok(await PlacesUtils.bookmarks.fetch({ url: TEST_URI }));
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("Frecency should be smaller.");
+  Assert.ok(
+    (await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    })) < initialFrecency
+  );
+
+  await cleanup();
+});
+
+add_task(async function remove_all_visits_bookmarked_uri() {
+  info(
+    "*** TEST: Remove some visits from a zero frecency URI retains zero frecency"
+  );
+
+  info("Add some visits for the URI.");
+  await PlacesTestUtils.addVisits([
+    {
+      uri: TEST_URI,
+      transition: TRANSITION_FRAMED_LINK,
+      visitDate: DB_NOW - 86400000000000,
+    },
+    { uri: TEST_URI, transition: TRANSITION_FRAMED_LINK, visitDate: DB_NOW },
+  ]);
+
+  info("Remove newer visit.");
+  let filter = {
+    beginDate: new Date(JS_NOW - 10),
+    endDate: new Date(JS_NOW),
+  };
+  await PlacesUtils.history.removeVisitsByFilter(filter);
+  await PlacesFrecencyRecalculator.recalculateAnyOutdatedFrecencies();
+
+  info("URI should still exist in moz_places.");
+  Assert.ok(page_in_database(TEST_URI.spec));
+  info("Frecency should be zero.");
+  Assert.equal(
+    await PlacesTestUtils.getDatabaseValue("moz_places", "frecency", {
+      url: TEST_URI,
+    }),
+    0
+  );
+
+  await cleanup();
+});
diff --git a/toolkit/components/places/tests/history/test_removeVisitsByFilter.js b/toolkit/components/places/tests/history/test_removeVisitsByFilter.js
new file mode 100644
index 0000000000..3d71c7348a
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_removeVisitsByFilter.js
@@ -0,0 +1,409 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+
+// Tests for `History.removeVisitsByFilter`, as implemented in History.jsm
+
+"use strict";
+
+const { PromiseUtils } = ChromeUtils.importESModule(
+  "resource://gre/modules/PromiseUtils.sys.mjs"
+);
+
+add_task(async function test_removeVisitsByFilter() {
+  let referenceDate = new Date(1999, 9, 9, 9, 9);
+
+  // Populate a database with 20 entries, remove a subset of entries,
+  // ensure consistency.
+  let remover = async function (options) {
+    info("Remover with options " + JSON.stringify(options));
+    let SAMPLE_SIZE = options.sampleSize;
+
+    await PlacesUtils.history.clear();
+    await PlacesUtils.bookmarks.eraseEverything();
+
+    // Populate the database.
+    // Create `SAMPLE_SIZE` visits, from the oldest to the newest.
+
+    let bookmarkIndices = new Set(options.bookmarks);
+    let visits = [];
+    let rankingChangePromises = [];
+    let uriDeletePromises = new Map();
+    let getURL = options.url
+      ? i =>
+          "http://mozilla.com/test_browserhistory/test_removeVisitsByFilter/removeme/byurl/" +
+          Math.floor(i / (SAMPLE_SIZE / 5)) +
+          "/"
+      : i =>
+          "http://mozilla.com/test_browserhistory/test_removeVisitsByFilter/removeme/" +
+          i +
+          "/" +
+          Math.random();
+    for (let i = 0; i < SAMPLE_SIZE; ++i) {
+      let spec = getURL(i);
+      let uri = NetUtil.newURI(spec);
+      let jsDate = new Date(Number(referenceDate) + 3600 * 1000 * i);
+      let dbDate = jsDate * 1000;
+      let hasBookmark = bookmarkIndices.has(i);
+      let hasOwnBookmark = hasBookmark;
+      if (!hasOwnBookmark && options.url) {
+        // Also mark as bookmarked if one of the earlier bookmarked items has the same URL.
+        hasBookmark = options.bookmarks
+          .filter(n => n < i)
+          .some(n => visits[n].uri.spec == spec && visits[n].test.hasBookmark);
+      }
+      info("Generating " + uri.spec + ", " + dbDate);
+      let visit = {
+        uri,
+        title: "visit " + i,
+        visitDate: dbDate,
+        test: {
+          // `visitDate`, as a Date
+          jsDate,
+          // `true` if we expect that the visit will be removed
+          toRemove: false,
+          // `true` if `onRow` informed of the removal of this visit
+          announcedByOnRow: false,
+          // `true` if there is a bookmark for this URI, i.e. of the page
+          // should not be entirely removed.
+          hasBookmark,
+        },
+      };
+      visits.push(visit);
+      if (hasOwnBookmark) {
+        info("Adding a bookmark to visit " + i);
+        await PlacesUtils.bookmarks.insert({
+          url: uri,
+          parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+          title: "test bookmark",
+        });
+        info("Bookmark added");
+      }
+    }
+
+    info("Adding visits");
+    await PlacesTestUtils.addVisits(visits);
+
+    info("Preparing filters");
+    let filter = {};
+    let beginIndex = 0;
+    let endIndex = visits.length - 1;
+    if ("begin" in options) {
+      let ms = Number(visits[options.begin].test.jsDate) - 1000;
+      filter.beginDate = new Date(ms);
+      beginIndex = options.begin;
+    }
+    if ("end" in options) {
+      let ms = Number(visits[options.end].test.jsDate) + 1000;
+      filter.endDate = new Date(ms);
+      endIndex = options.end;
+    }
+    if ("limit" in options) {
+      endIndex = beginIndex + options.limit - 1; // -1 because the start index is inclusive.
+      filter.limit = options.limit;
+    }
+    let removedItems = visits.slice(beginIndex);
+    endIndex -= beginIndex;
+    if (options.url) {
+      let rawURL = "";
+      switch (options.url) {
+        case 1:
+          filter.url = new URL(removedItems[0].uri.spec);
+          rawURL = filter.url.href;
+          break;
+        case 2:
+          filter.url = removedItems[0].uri;
+          rawURL = filter.url.spec;
+          break;
+        case 3:
+          filter.url = removedItems[0].uri.spec;
+          rawURL = filter.url;
+          break;
+      }
+      endIndex = Math.min(
+        endIndex,
+        removedItems.findIndex((v, index) => v.uri.spec != rawURL) - 1
+      );
+    }
+    removedItems.splice(endIndex + 1);
+    let remainingItems = visits.filter(v => !removedItems.includes(v));
+    for (let i = 0; i < removedItems.length; i++) {
+      let test = removedItems[i].test;
+      info("Marking visit " + (beginIndex + i) + " as expecting removal");
+      test.toRemove = true;
+      if (
+        test.hasBookmark ||
+        (options.url &&
+          remainingItems.some(v => v.uri.spec == removedItems[i].uri.spec))
+      ) {
+        rankingChangePromises.push(PromiseUtils.defer());
+      } else if (!options.url || i == 0) {
+        uriDeletePromises.set(removedItems[i].uri.spec, PromiseUtils.defer());
+      }
+    }
+
+    const placesEventListener = events => {
+      for (const event of events) {
+        switch (event.type) {
+          case "page-title-changed": {
+            this.deferred.reject(
+              "Unexpected page-title-changed event happens on " + event.url
+            );
+            break;
+          }
+          case "history-cleared": {
+            info("history-cleared");
+            this.deferred.reject("Unexpected history-cleared event happens");
+            break;
+          }
+          case "pages-rank-changed": {
+            info("pages-rank-changed");
+            for (const deferred of rankingChangePromises) {
+              deferred.resolve();
+            }
+            break;
+          }
+        }
+      }
+    };
+    PlacesObservers.addListener(
+      ["page-title-changed", "history-cleared", "pages-rank-changed"],
+      placesEventListener
+    );
+
+    let cbarg;
+    if (options.useCallback) {
+      info("Setting up callback");
+      cbarg = [
+        info => {
+          for (let visit of visits) {
+            info("Comparing " + info.date + " and " + visit.test.jsDate);
+            if (Math.abs(visit.test.jsDate - info.date) < 100) {
+              // Assume rounding errors
+              Assert.ok(
+                !visit.test.announcedByOnRow,
+                "This is the first time we announce the removal of this visit"
+              );
+              Assert.ok(
+                visit.test.toRemove,
+                "This is a visit we intended to remove"
+              );
+              visit.test.announcedByOnRow = true;
+              return;
+            }
+          }
+          Assert.ok(false, "Could not find the visit we attempt to remove");
+        },
+      ];
+    } else {
+      info("No callback");
+      cbarg = [];
+    }
+    let result = await PlacesUtils.history.removeVisitsByFilter(
+      filter,
+      ...cbarg
+    );
+
+    Assert.ok(result, "Removal succeeded");
+
+    // Make sure that we have eliminated exactly the entries we expected
+    // to eliminate.
+    for (let i = 0; i < visits.length; ++i) {
+      let visit = visits[i];
+      info("Controlling the results on visit " + i);
+      let remainingVisitsForURI = remainingItems.filter(
+        v => visit.uri.spec == v.uri.spec
+      ).length;
+      Assert.equal(
+        visits_in_database(visit.uri),
+        remainingVisitsForURI,
+        "Visit is still present iff expected"
+      );
+      if (options.useCallback) {
+        Assert.equal(
+          visit.test.toRemove,
+          visit.test.announcedByOnRow,
+          "Visit removal has been announced by onResult iff expected"
+        );
+      }
+      if (visit.test.hasBookmark || remainingVisitsForURI) {
+        Assert.notEqual(
+          page_in_database(visit.uri),
+          0,
+          "The page should still appear in the db"
+        );
+      } else {
+        Assert.equal(
+          page_in_database(visit.uri),
+          0,
+          "The page should have been removed from the db"
+        );
+      }
+    }
+
+    // Make sure that the observer has been called wherever applicable.
+    info("Checking URI delete promises.");
+    await Promise.all(Array.from(uriDeletePromises.values()));
+    info("Checking frecency change promises.");
+    await Promise.all(rankingChangePromises);
+    PlacesObservers.removeListener(
+      ["page-title-changed", "history-cleared", "pages-rank-changed"],
+      placesEventListener
+    );
+  };
+
+  let size = 20;
+  for (let range of [
+    { begin: 0 },
+    { end: 19 },
+    { begin: 0, end: 10 },
+    { begin: 3, end: 4 },
+    { begin: 5, end: 8, limit: 2 },
+    { begin: 10, end: 18, limit: 5 },
+  ]) {
+    for (let bookmarks of [[], [5, 6]]) {
+      let options = {
+        sampleSize: size,
+        bookmarks,
+      };
+      if ("begin" in range) {
+        options.begin = range.begin;
+      }
+      if ("end" in range) {
+        options.end = range.end;
+      }
+      if ("limit" in range) {
+        options.limit = range.limit;
+      }
+      await remover(options);
+      options.url = 1;
+      await remover(options);
+      options.url = 2;
+      await remover(options);
+      options.url = 3;
+      await remover(options);
+    }
+  }
+  await PlacesUtils.history.clear();
+});
+
+// Test the various error cases
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter(),
+    /TypeError: Expected a filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter("obviously, not a filter"),
+    /TypeError: Expected a filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({}),
+    /TypeError: Expected a non-empty filter/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ beginDate: "now" }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ beginDate: Date.now() }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeVisitsByFilter({ beginDate: new Date(NaN) }),
+    /TypeError: Expected a valid Date/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeVisitsByFilter(
+        { beginDate: new Date() },
+        "obviously, not a callback"
+      ),
+    /TypeError: Invalid function/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeVisitsByFilter({
+        beginDate: new Date(1000),
+        endDate: new Date(0),
+      }),
+    /TypeError: `beginDate` should be at least as old/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ limit: {} }),
+    /Expected a non-zero positive integer as a limit/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ limit: -1 }),
+    /Expected a non-zero positive integer as a limit/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ limit: 0.1 }),
+    /Expected a non-zero positive integer as a limit/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ limit: Infinity }),
+    /Expected a non-zero positive integer as a limit/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ url: {} }),
+    /Expected a valid URL for `url`/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ url: 0 }),
+    /Expected a valid URL for `url`/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeVisitsByFilter({
+        beginDate: new Date(1000),
+        endDate: new Date(0),
+      }),
+    /TypeError: `beginDate` should be at least as old/
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.removeVisitsByFilter({
+        beginDate: new Date(1000),
+        endDate: new Date(0),
+      }),
+    /TypeError: `beginDate` should be at least as old/
+  );
+  Assert.throws(
+    () => PlacesUtils.history.removeVisitsByFilter({ transition: -1 }),
+    /TypeError: `transition` should be valid/
+  );
+});
+
+add_task(async function test_orphans() {
+  let uri = NetUtil.newURI("http://moz.org/");
+  await PlacesTestUtils.addVisits({ uri });
+
+  PlacesUtils.favicons.setAndFetchFaviconForPage(
+    uri,
+    SMALLPNG_DATA_URI,
+    true,
+    PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+    null,
+    Services.scriptSecurityManager.getSystemPrincipal()
+  );
+  await PlacesUtils.history.update({
+    url: uri,
+    annotations: new Map([["test", "restval"]]),
+  });
+
+  await PlacesUtils.history.removeVisitsByFilter({
+    beginDate: new Date(1999, 9, 9, 9, 9),
+    endDate: new Date(),
+  });
+  Assert.ok(
+    !(await PlacesTestUtils.isPageInDB(uri)),
+    "Page should have been removed"
+  );
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(`SELECT (SELECT count(*) FROM moz_annos) +
+                                      (SELECT count(*) FROM moz_icons) +
+                                      (SELECT count(*) FROM moz_pages_w_icons) +
+                                      (SELECT count(*) FROM moz_icons_to_pages) AS count`);
+  Assert.equal(rows[0].getResultByName("count"), 0, "Should not find orphans");
+});
diff --git a/toolkit/components/places/tests/history/test_sameUri_titleChanged.js b/toolkit/components/places/tests/history/test_sameUri_titleChanged.js
new file mode 100644
index 0000000000..87fb3f455c
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_sameUri_titleChanged.js
@@ -0,0 +1,54 @@
+// Test that repeated additions of the same URI to history, properly
+// update from_visit and notify titleChanged.
+
+add_task(async function test() {
+  let uri = "http://test.com/";
+
+  const promiseTitleChangedNotifications =
+    PlacesTestUtils.waitForNotification("page-title-changed");
+
+  // This repeats the url on purpose, don't merge it into a single place entry.
+  await PlacesTestUtils.addVisits([
+    { uri, title: "test" },
+    { uri, referrer: uri, title: "test2" },
+  ]);
+
+  const events = await promiseTitleChangedNotifications;
+  Assert.equal(events.length, 1, "Right number of title changed notified");
+  Assert.equal(events[0].url, uri, "Should notify the proper url");
+
+  let options = PlacesUtils.history.getNewQueryOptions();
+  let query = PlacesUtils.history.getNewQuery();
+  query.uri = NetUtil.newURI(uri);
+  options.resultType = options.RESULTS_AS_VISIT;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  Assert.equal(root.childCount, 2);
+
+  let child = root.getChild(0);
+  Assert.equal(
+    child.visitType,
+    TRANSITION_LINK,
+    "Visit type should be TRANSITION_LINK"
+  );
+  Assert.equal(child.visitId, 1, "Visit ID should be 1");
+  Assert.equal(child.fromVisitId, -1, "Should have no referrer visit ID");
+  Assert.equal(child.title, "test2", "Should have the correct title");
+
+  child = root.getChild(1);
+  Assert.equal(
+    child.visitType,
+    TRANSITION_LINK,
+    "Visit type should be TRANSITION_LINK"
+  );
+  Assert.equal(child.visitId, 2, "Visit ID should be 2");
+  Assert.equal(
+    child.fromVisitId,
+    1,
+    "First visit should be the referring visit"
+  );
+  Assert.equal(child.title, "test2", "Should have the correct title");
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/history/test_update.js b/toolkit/components/places/tests/history/test_update.js
new file mode 100644
index 0000000000..d7beafd368
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_update.js
@@ -0,0 +1,700 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests for `History.update` as implemented in History.jsm
+
+"use strict";
+
+add_task(async function test_error_cases() {
+  Assert.throws(
+    () => PlacesUtils.history.update("not an object"),
+    /Error: PageInfo: Input should be a valid object/,
+    "passing a string as pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.update(null),
+    /Error: PageInfo: Input should be/,
+    "passing a null as pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        description: "Test description",
+      }),
+    /Error: PageInfo: The following properties were expected: url, guid/,
+    "not included a url or a guid should throw"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.update({ url: "not a valid url string" }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing an invalid url should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        description: 123,
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a non-string description in pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        guid: "invalid guid",
+        description: "Test description",
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a invalid guid in pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        previewImageURL: "not a valid url string",
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing an invlid preview image url in pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () => {
+      let imageName = "a-very-long-string".repeat(10000);
+      let previewImageURL = `http://valid.uri.com/${imageName}.png`;
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        previewImageURL,
+      });
+    },
+    /Error: PageInfo: Invalid value for property/,
+    "passing an oversized previewImageURL in pageInfo should throw an Error"
+  );
+  Assert.throws(
+    () => PlacesUtils.history.update({ url: "http://valid.uri.com" }),
+    /TypeError: pageInfo object must at least/,
+    "passing a pageInfo with neither description, previewImageURL, nor annotations should throw a TypeError"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        annotations: "asd",
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a pageInfo with incorrect annotations type should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        annotations: new Map(),
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a pageInfo with an empty annotations type should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        annotations: new Map([[1234, "value"]]),
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a pageInfo with an invalid key type should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        annotations: new Map([["test", ["myarray"]]]),
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a pageInfo with an invalid key type should throw an Error"
+  );
+  Assert.throws(
+    () =>
+      PlacesUtils.history.update({
+        url: "http://valid.uri.com",
+        annotations: new Map([["test", { anno: "value" }]]),
+      }),
+    /Error: PageInfo: Invalid value for property/,
+    "passing a pageInfo with an invalid key type should throw an Error"
+  );
+});
+
+add_task(async function test_description_change_saved() {
+  await PlacesUtils.history.clear();
+
+  let TEST_URL = "http://mozilla.org/test_description_change_saved";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(await PlacesTestUtils.isPageInDB(TEST_URL));
+
+  let description = "Test description";
+  await PlacesUtils.history.update({ url: TEST_URL, description });
+  let descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    { url: TEST_URL }
+  );
+  Assert.equal(
+    description,
+    descriptionInDB,
+    "description should be updated via URL as expected"
+  );
+
+  description = "";
+  await PlacesUtils.history.update({ url: TEST_URL, description });
+  descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    { url: TEST_URL }
+  );
+  Assert.strictEqual(
+    null,
+    descriptionInDB,
+    "an empty description should set it to null in the database"
+  );
+
+  let guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+    url: TEST_URL,
+  });
+  description = "Test description";
+  await PlacesUtils.history.update({ url: TEST_URL, guid, description });
+  descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    { url: TEST_URL }
+  );
+  Assert.equal(
+    description,
+    descriptionInDB,
+    "description should be updated via GUID as expected"
+  );
+
+  description = "Test descipriton".repeat(1000);
+  await PlacesUtils.history.update({ url: TEST_URL, description });
+  descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    { url: TEST_URL }
+  );
+  Assert.ok(
+    !!descriptionInDB.length < description.length,
+    "a long description should be truncated"
+  );
+
+  description = null;
+  await PlacesUtils.history.update({ url: TEST_URL, description });
+  descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    { url: TEST_URL }
+  );
+  Assert.strictEqual(
+    description,
+    descriptionInDB,
+    "a null description should set it to null in the database"
+  );
+});
+
+add_task(async function test_siteName_change_saved() {
+  await PlacesUtils.history.clear();
+
+  let TEST_URL = "http://mozilla.org/test_siteName_change_saved";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(await PlacesTestUtils.isPageInDB(TEST_URL));
+
+  let siteName = "Test site name";
+  await PlacesUtils.history.update({ url: TEST_URL, siteName });
+  let siteNameInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "site_name",
+    { url: TEST_URL }
+  );
+  Assert.equal(
+    siteName,
+    siteNameInDB,
+    "siteName should be updated via URL as expected"
+  );
+
+  siteName = "";
+  await PlacesUtils.history.update({ url: TEST_URL, siteName });
+  siteNameInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "site_name",
+    { url: TEST_URL }
+  );
+  Assert.strictEqual(
+    null,
+    siteNameInDB,
+    "an empty siteName should set it to null in the database"
+  );
+
+  let guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+    url: TEST_URL,
+  });
+  siteName = "Test site name";
+  await PlacesUtils.history.update({ url: TEST_URL, guid, siteName });
+  siteNameInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "site_name",
+    { url: TEST_URL }
+  );
+  Assert.equal(
+    siteName,
+    siteNameInDB,
+    "siteName should be updated via GUID as expected"
+  );
+
+  siteName = "Test site name".repeat(1000);
+  await PlacesUtils.history.update({ url: TEST_URL, siteName });
+  siteNameInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "site_name",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.ok(
+    !!siteNameInDB.length < siteName.length,
+    "a long siteName should be truncated"
+  );
+
+  siteName = null;
+  await PlacesUtils.history.update({ url: TEST_URL, siteName });
+  siteNameInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "site_name",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.strictEqual(
+    siteName,
+    siteNameInDB,
+    "a null siteName should set it to null in the database"
+  );
+});
+
+add_task(async function test_previewImageURL_change_saved() {
+  await PlacesUtils.history.clear();
+
+  let TEST_URL = "http://mozilla.org/test_previewImageURL_change_saved";
+  let IMAGE_URL = "http://mozilla.org/test_preview_image.png";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(await PlacesTestUtils.isPageInDB(TEST_URL));
+
+  let previewImageURL = IMAGE_URL;
+  await PlacesUtils.history.update({ url: TEST_URL, previewImageURL });
+  let previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.equal(
+    previewImageURL,
+    previewImageURLInDB,
+    "previewImageURL should be updated via URL as expected"
+  );
+
+  previewImageURL = null;
+  await PlacesUtils.history.update({ url: TEST_URL, previewImageURL });
+  previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.strictEqual(
+    null,
+    previewImageURLInDB,
+    "a null previewImageURL should set it to null in the database"
+  );
+
+  let guid = await PlacesTestUtils.getDatabaseValue("moz_places", "guid", {
+    url: TEST_URL,
+  });
+  previewImageURL = IMAGE_URL;
+  await PlacesUtils.history.update({ guid, previewImageURL });
+  previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.equal(
+    previewImageURL,
+    previewImageURLInDB,
+    "previewImageURL should be updated via GUID as expected"
+  );
+
+  previewImageURL = "";
+  await PlacesUtils.history.update({ url: TEST_URL, previewImageURL });
+  previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.strictEqual(
+    null,
+    previewImageURLInDB,
+    "an empty previewImageURL should set it to null in the database"
+  );
+});
+
+add_task(async function test_change_description_and_preview_saved() {
+  await PlacesUtils.history.clear();
+
+  let TEST_URL = "http://mozilla.org/test_change_both_saved";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(await PlacesTestUtils.isPageInDB(TEST_URL));
+
+  let description = "Test description";
+  let previewImageURL = "http://mozilla.org/test_preview_image.png";
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    description,
+    previewImageURL,
+  });
+  let descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    {
+      url: TEST_URL,
+    }
+  );
+  let previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.equal(
+    description,
+    descriptionInDB,
+    "description should be updated via URL as expected"
+  );
+  Assert.equal(
+    previewImageURL,
+    previewImageURLInDB,
+    "previewImageURL should be updated via URL as expected"
+  );
+
+  // Update description should not touch other fields
+  description = null;
+  await PlacesUtils.history.update({ url: TEST_URL, description });
+  descriptionInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "description",
+    {
+      url: TEST_URL,
+    }
+  );
+  previewImageURLInDB = await PlacesTestUtils.getDatabaseValue(
+    "moz_places",
+    "preview_image_url",
+    {
+      url: TEST_URL,
+    }
+  );
+  Assert.strictEqual(
+    description,
+    descriptionInDB,
+    "description should be updated via URL as expected"
+  );
+  Assert.equal(
+    previewImageURL,
+    previewImageURLInDB,
+    "previewImageURL should not be updated"
+  );
+});
+
+/**
+ * Gets annotation information from the database for the specified URL and
+ * annotation name.
+ *
+ * @param {String} pageUrl The URL to search for.
+ * @param {String} annoName The name of the annotation to search for.
+ * @return {Array} An array of objects containing the annotations found.
+ */
+async function getAnnotationInfoFromDB(pageUrl, annoName) {
+  let db = await PlacesUtils.promiseDBConnection();
+
+  let rows = await db.execute(
+    `
+    SELECT a.content, a.flags, a.expiration, a.type FROM moz_anno_attributes n
+    JOIN moz_annos a ON n.id = a.anno_attribute_id
+    JOIN moz_places h ON h.id = a.place_id
+    WHERE h.url_hash = hash(:pageUrl) AND h.url = :pageUrl
+      AND n.name = :annoName
+  `,
+    { annoName, pageUrl }
+  );
+
+  let result = rows.map(row => {
+    return {
+      content: row.getResultByName("content"),
+      flags: row.getResultByName("flags"),
+      expiration: row.getResultByName("expiration"),
+      type: row.getResultByName("type"),
+    };
+  });
+
+  return result;
+}
+
+add_task(async function test_simple_change_annotations() {
+  await PlacesUtils.history.clear();
+
+  const TEST_URL = "http://mozilla.org/test_change_both_saved";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL),
+    "Should have inserted the page into the database."
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/annotation", "testContent"]]),
+  });
+
+  let pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    1,
+    "Should have one annotation for the page"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    "testContent",
+    "Should have the correct annotation"
+  );
+
+  let annotationInfo = await getAnnotationInfoFromDB(
+    TEST_URL,
+    "test/annotation"
+  );
+  Assert.deepEqual(
+    {
+      content: "testContent",
+      flags: 0,
+      type: PlacesUtils.history.ANNOTATION_TYPE_STRING,
+      expiration: PlacesUtils.history.ANNOTATION_EXPIRE_NEVER,
+    },
+    annotationInfo[0],
+    "Should have stored the correct annotation data in the db"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/annotation2", "testAnno"]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    2,
+    "Should have two annotations for the page"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    "testContent",
+    "Should have the correct value for the first annotation"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    "testAnno",
+    "Should have the correct value for the second annotation"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/annotation", 1234]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    2,
+    "Should still have two annotations for the page"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    1234,
+    "Should have the updated the first annotation value"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    "testAnno",
+    "Should have kept the value for the second annotation"
+  );
+
+  annotationInfo = await getAnnotationInfoFromDB(TEST_URL, "test/annotation");
+  Assert.deepEqual(
+    {
+      content: 1234,
+      flags: 0,
+      type: PlacesUtils.history.ANNOTATION_TYPE_INT64,
+      expiration: PlacesUtils.history.ANNOTATION_EXPIRE_NEVER,
+    },
+    annotationInfo[0],
+    "Should have updated the annotation data in the db"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/annotation", null]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    1,
+    "Should have removed only the first annotation"
+  );
+  Assert.strictEqual(
+    pageInfo.annotations.get("test/annotation"),
+    undefined,
+    "Should have removed only the first annotation"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    "testAnno",
+    "Should have kept the value for the second annotation"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([["test/annotation2", null]]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(pageInfo.annotations.size, 0, "Should have no annotations left");
+
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(`
+    SELECT * FROM moz_annos
+  `);
+  Assert.equal(rows.length, 0, "Should be no annotations left in the db");
+});
+
+add_task(async function test_change_multiple_annotations() {
+  await PlacesUtils.history.clear();
+
+  const TEST_URL = "http://mozilla.org/test_change_both_saved";
+  await PlacesTestUtils.addVisits(TEST_URL);
+  Assert.ok(
+    await PlacesTestUtils.isPageInDB(TEST_URL),
+    "Should have inserted the page into the database."
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([
+      ["test/annotation", "testContent"],
+      ["test/annotation2", "testAnno"],
+    ]),
+  });
+
+  let pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    2,
+    "Should have inserted the two annotations for the page."
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    "testContent",
+    "Should have the correct value for the first annotation"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    "testAnno",
+    "Should have the correct value for the second annotation"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([
+      ["test/annotation", 123456],
+      ["test/annotation2", 135246],
+    ]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(
+    pageInfo.annotations.size,
+    2,
+    "Should have two annotations for the page"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation"),
+    123456,
+    "Should have the correct value for the first annotation"
+  );
+  Assert.equal(
+    pageInfo.annotations.get("test/annotation2"),
+    135246,
+    "Should have the correct value for the second annotation"
+  );
+
+  await PlacesUtils.history.update({
+    url: TEST_URL,
+    annotations: new Map([
+      ["test/annotation", null],
+      ["test/annotation2", null],
+    ]),
+  });
+
+  pageInfo = await PlacesUtils.history.fetch(TEST_URL, {
+    includeAnnotations: true,
+  });
+
+  Assert.equal(pageInfo.annotations.size, 0, "Should have no annotations left");
+});
+
+add_task(async function test_annotations_nonexisting_page() {
+  info("Adding annotations to a non existing page should be silent");
+  await PlacesUtils.history.update({
+    url: "http://nonexisting.moz/",
+    annotations: new Map([["test/annotation", null]]),
+  });
+});
+
+add_task(async function test_annotations_nonexisting_page() {
+  info("Adding annotations to a non existing page should be silent");
+  await PlacesUtils.history.update({
+    url: "http://nonexisting.moz/",
+    annotations: new Map([["test/annotation", null]]),
+  });
+});
diff --git a/toolkit/components/places/tests/history/test_updatePlaces_embed.js b/toolkit/components/places/tests/history/test_updatePlaces_embed.js
new file mode 100644
index 0000000000..a2831f2f58
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_updatePlaces_embed.js
@@ -0,0 +1,81 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Tests that updatePlaces properly handled callbacks for embed visits.
+
+"use strict";
+
+XPCOMUtils.defineLazyServiceGetter(
+  this,
+  "asyncHistory",
+  "@mozilla.org/browser/history;1",
+  "mozIAsyncHistory"
+);
+
+add_task(async function test_embed_visit() {
+  let place = {
+    uri: NetUtil.newURI("http://places.test/"),
+    visits: [
+      {
+        transitionType: PlacesUtils.history.TRANSITIONS.EMBED,
+        visitDate: PlacesUtils.toPRTime(new Date()),
+      },
+    ],
+  };
+  let errors = 0;
+  let results = 0;
+  let updated = await new Promise(resolve => {
+    asyncHistory.updatePlaces(place, {
+      ignoreErrors: true,
+      ignoreResults: true,
+      handleError(aResultCode, aPlace) {
+        errors++;
+      },
+      handleResult(aPlace) {
+        results++;
+      },
+      handleCompletion(resultCount) {
+        resolve(resultCount);
+      },
+    });
+  });
+  Assert.equal(errors, 0, "There should be no error callback");
+  Assert.equal(results, 0, "There should be no result callback");
+  Assert.equal(updated, 1, "The visit should have been added");
+});
+
+add_task(async function test_misc_visits() {
+  let place = {
+    uri: NetUtil.newURI("http://places.test/"),
+    visits: [
+      {
+        transitionType: PlacesUtils.history.TRANSITIONS.EMBED,
+        visitDate: PlacesUtils.toPRTime(new Date()),
+      },
+      {
+        transitionType: PlacesUtils.history.TRANSITIONS.LINK,
+        visitDate: PlacesUtils.toPRTime(new Date()),
+      },
+    ],
+  };
+  let errors = 0;
+  let results = 0;
+  let updated = await new Promise(resolve => {
+    asyncHistory.updatePlaces(place, {
+      ignoreErrors: true,
+      ignoreResults: true,
+      handleError(aResultCode, aPlace) {
+        errors++;
+      },
+      handleResult(aPlace) {
+        results++;
+      },
+      handleCompletion(resultCount) {
+        resolve(resultCount);
+      },
+    });
+  });
+  Assert.equal(errors, 0, "There should be no error callback");
+  Assert.equal(results, 0, "There should be no result callback");
+  Assert.equal(updated, 2, "The visit should have been added");
+});
diff --git a/toolkit/components/places/tests/history/xpcshell.ini b/toolkit/components/places/tests/history/xpcshell.ini
new file mode 100644
index 0000000000..b4a017e15d
--- /dev/null
+++ b/toolkit/components/places/tests/history/xpcshell.ini
@@ -0,0 +1,20 @@
+[DEFAULT]
+head = head_history.js
+
+[test_async_history_api.js]
+[test_bookmark_unhide.js]
+[test_fetch.js]
+[test_fetchAnnotatedPages.js]
+[test_fetchMany.js]
+[test_hasVisits.js]
+[test_insert.js]
+[test_insert_null_title.js]
+[test_insertMany.js]
+[test_remove.js]
+[test_removeMany.js]
+[test_removeVisits.js]
+[test_removeByFilter.js]
+[test_removeVisitsByFilter.js]
+[test_sameUri_titleChanged.js]
+[test_update.js]
+[test_updatePlaces_embed.js]