Adding upstream version 124.0.1.upstream/124.0.1

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

30 files changed, 6515 insertions, 0 deletions

diff --git a/toolkit/components/places/tests/queries/head_queries.js b/toolkit/components/places/tests/queries/head_queries.js
new file mode 100644
index 0000000000..ebb6eb4455
--- /dev/null
+++ b/toolkit/components/places/tests/queries/head_queries.js
@@ -0,0 +1,342 @@
+/* -*- 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);
+}
+
+// Put any other stuff relative to this test folder below.
+
+// Some Useful Date constants - PRTime uses microseconds, so convert
+const DAY_MICROSEC = 86400000000;
+const today = PlacesUtils.toPRTime(Date.now());
+const yesterday = today - DAY_MICROSEC;
+const lastweek = today - DAY_MICROSEC * 7;
+const daybefore = today - DAY_MICROSEC * 2;
+const old = today - DAY_MICROSEC * 3;
+const futureday = today + DAY_MICROSEC * 3;
+const olderthansixmonths = today - DAY_MICROSEC * 31 * 7;
+
+/**
+ * Generalized function to pull in an array of objects of data and push it into
+ * the database.  It does NOT do any checking to see that the input is
+ * appropriate.  This function is an asynchronous task, it can be called using
+ * "Task.spawn" or using the "yield" function inside another task.
+ */
+async function task_populateDB(aArray) {
+  // Iterate over aArray and execute all instructions.
+  for (let arrayItem of aArray) {
+    try {
+      // make the data object into a query data object in order to create proper
+      // default values for anything left unspecified
+      var qdata = new queryData(arrayItem);
+      if (qdata.isVisit) {
+        // Then we should add a visit for this node
+        await PlacesTestUtils.addVisits({
+          uri: uri(qdata.uri),
+          transition: qdata.transType,
+          visitDate: qdata.lastVisit,
+          referrer: qdata.referrer ? uri(qdata.referrer) : null,
+          title: qdata.title,
+        });
+        if (qdata.visitCount && !qdata.isDetails) {
+          // Set a fake visit_count, this is not a real count but can be used
+          // to test sorting by visit_count.
+          await PlacesTestUtils.updateDatabaseValues(
+            "moz_places",
+            { visit_count: qdata.visitCount },
+            { url: qdata.uri }
+          );
+        }
+      }
+
+      if (qdata.isRedirect) {
+        // This must be async to properly enqueue after the updateFrecency call
+        // done by the visit addition.
+        await PlacesTestUtils.updateDatabaseValues(
+          "moz_places",
+          { hidden: 1 },
+          { url: qdata.uri }
+        );
+      }
+
+      if (qdata.isDetails) {
+        // Then we add extraneous page details for testing
+        await PlacesTestUtils.addVisits({
+          uri: uri(qdata.uri),
+          visitDate: qdata.lastVisit,
+          title: qdata.title,
+        });
+      }
+
+      if (qdata.markPageAsTyped) {
+        PlacesUtils.history.markPageAsTyped(uri(qdata.uri));
+      }
+
+      if (qdata.isPageAnnotation) {
+        await PlacesUtils.history.update({
+          url: qdata.uri,
+          annotations: new Map([
+            [qdata.annoName, qdata.removeAnnotation ? null : qdata.annoVal],
+          ]),
+        });
+      }
+
+      if (qdata.isFolder) {
+        await PlacesUtils.bookmarks.insert({
+          parentGuid: qdata.parentGuid,
+          type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          title: qdata.title,
+          index: qdata.index,
+        });
+      }
+
+      if (qdata.isBookmark) {
+        let data = {
+          parentGuid: qdata.parentGuid,
+          index: qdata.index,
+          title: qdata.title,
+          url: qdata.uri,
+        };
+
+        if (qdata.dateAdded) {
+          data.dateAdded = new Date(qdata.dateAdded / 1000);
+        }
+
+        if (qdata.lastModified) {
+          data.lastModified = new Date(qdata.lastModified / 1000);
+        }
+
+        await PlacesUtils.bookmarks.insert(data);
+
+        if (qdata.keyword) {
+          await PlacesUtils.keywords.insert({
+            url: qdata.uri,
+            keyword: qdata.keyword,
+          });
+        }
+      }
+
+      if (qdata.isTag) {
+        PlacesUtils.tagging.tagURI(uri(qdata.uri), qdata.tagArray);
+      }
+
+      if (qdata.isSeparator) {
+        await PlacesUtils.bookmarks.insert({
+          parentGuid: qdata.parentGuid,
+          type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+          index: qdata.index,
+        });
+      }
+    } catch (ex) {
+      // use the arrayItem object here in case instantiation of qdata failed
+      info("Problem with this URI: " + arrayItem.uri);
+      do_throw("Error creating database: " + ex + "\n");
+    }
+  }
+}
+
+/**
+ * The Query Data Object - this object encapsulates data for our queries and is
+ * used to parameterize our calls to the Places APIs to put data into the
+ * database. It also has some interesting meta functions to determine which APIs
+ * should be called, and to determine if this object should show up in the
+ * resulting query.
+ * Its parameter is an object specifying which attributes you want to set.
+ * For ex:
+ * var myobj = new queryData({isVisit: true, uri:"http://mozilla.com", title="foo"});
+ * Note that it doesn't do any input checking on that object.
+ */
+function queryData(obj) {
+  this.isVisit = obj.isVisit ? obj.isVisit : false;
+  this.isBookmark = obj.isBookmark ? obj.isBookmark : false;
+  this.uri = obj.uri ? obj.uri : "";
+  this.lastVisit = obj.lastVisit ? obj.lastVisit : today;
+  this.referrer = obj.referrer ? obj.referrer : null;
+  this.transType = obj.transType
+    ? obj.transType
+    : Ci.nsINavHistoryService.TRANSITION_TYPED;
+  this.isRedirect = obj.isRedirect ? obj.isRedirect : false;
+  this.isDetails = obj.isDetails ? obj.isDetails : false;
+  this.title = obj.title ? obj.title : "";
+  this.markPageAsTyped = obj.markPageAsTyped ? obj.markPageAsTyped : false;
+  this.isPageAnnotation = obj.isPageAnnotation ? obj.isPageAnnotation : false;
+  this.removeAnnotation = !!obj.removeAnnotation;
+  this.annoName = obj.annoName ? obj.annoName : "";
+  this.annoVal = obj.annoVal ? obj.annoVal : "";
+  this.itemId = obj.itemId ? obj.itemId : 0;
+  this.annoMimeType = obj.annoMimeType ? obj.annoMimeType : "";
+  this.isTag = obj.isTag ? obj.isTag : false;
+  this.tagArray = obj.tagArray ? obj.tagArray : null;
+  this.parentGuid = obj.parentGuid || PlacesUtils.bookmarks.unfiledGuid;
+  this.feedURI = obj.feedURI ? obj.feedURI : "";
+  this.index = obj.index ? obj.index : PlacesUtils.bookmarks.DEFAULT_INDEX;
+  this.isFolder = obj.isFolder ? obj.isFolder : false;
+  this.contractId = obj.contractId ? obj.contractId : "";
+  this.lastModified = obj.lastModified ? obj.lastModified : null;
+  this.dateAdded = obj.dateAdded ? obj.dateAdded : null;
+  this.keyword = obj.keyword ? obj.keyword : "";
+  this.visitCount = obj.visitCount ? obj.visitCount : 0;
+  this.isSeparator = obj.hasOwnProperty("isSeparator") && obj.isSeparator;
+
+  // And now, the attribute for whether or not this object should appear in the
+  // resulting query
+  this.isInQuery = obj.isInQuery ? obj.isInQuery : false;
+}
+
+// All attributes are set in the constructor above
+queryData.prototype = {};
+
+/**
+ * Helper function to compare an array of query objects with a result set.
+ * It assumes the array of query objects contains the SAME SORT as the result
+ * set.  It checks the the uri, title, time, and bookmarkIndex properties of
+ * the results, where appropriate.
+ */
+function compareArrayToResult(aArray, aRoot) {
+  info("Comparing Array to Results");
+
+  var wasOpen = aRoot.containerOpen;
+  if (!wasOpen) {
+    aRoot.containerOpen = true;
+  }
+
+  // check expected number of results against actual
+  var expectedResultCount = aArray.filter(function (aEl) {
+    return aEl.isInQuery;
+  }).length;
+  if (expectedResultCount != aRoot.childCount) {
+    // Debugging code for failures.
+    dump_table("moz_places");
+    dump_table("moz_historyvisits");
+    info("Found children:");
+    for (let i = 0; i < aRoot.childCount; i++) {
+      info(aRoot.getChild(i).uri);
+    }
+    info("Expected:");
+    for (let i = 0; i < aArray.length; i++) {
+      if (aArray[i].isInQuery) {
+        info(aArray[i].uri);
+      }
+    }
+  }
+  Assert.equal(expectedResultCount, aRoot.childCount);
+
+  var inQueryIndex = 0;
+  for (var i = 0; i < aArray.length; i++) {
+    if (aArray[i].isInQuery) {
+      var child = aRoot.getChild(inQueryIndex);
+      // do_print("testing testData[" + i + "] vs result[" + inQueryIndex + "]");
+      if (!aArray[i].isFolder && !aArray[i].isSeparator) {
+        info(
+          "testing testData[" + aArray[i].uri + "] vs result[" + child.uri + "]"
+        );
+        if (aArray[i].uri != child.uri) {
+          dump_table("moz_places");
+          do_throw("Expected " + aArray[i].uri + " found " + child.uri);
+        }
+      }
+      if (!aArray[i].isSeparator && aArray[i].title != child.title) {
+        do_throw("Expected " + aArray[i].title + " found " + child.title);
+      }
+      if (
+        aArray[i].hasOwnProperty("lastVisit") &&
+        aArray[i].lastVisit != child.time
+      ) {
+        do_throw("Expected " + aArray[i].lastVisit + " found " + child.time);
+      }
+      if (
+        aArray[i].hasOwnProperty("index") &&
+        aArray[i].index != PlacesUtils.bookmarks.DEFAULT_INDEX &&
+        aArray[i].index != child.bookmarkIndex
+      ) {
+        do_throw(
+          "Expected " + aArray[i].index + " found " + child.bookmarkIndex
+        );
+      }
+
+      inQueryIndex++;
+    }
+  }
+
+  if (!wasOpen) {
+    aRoot.containerOpen = false;
+  }
+  info("Comparing Array to Results passes");
+}
+
+/**
+ * Helper function to check to see if one object either is or is not in the
+ * result set.  It can accept either a queryData object or an array of queryData
+ * objects.  If it gets an array, it only compares the first object in the array
+ * to see if it is in the result set.
+ * @returns {nsINavHistoryResultNode}: Either the node, if found, or null.
+ *          If input is an array, returns a result only for the first node.
+ *          To compare entire array, use the function above.
+ */
+function nodeInResult(aQueryData, aRoot) {
+  var rv = null;
+  var uri;
+  var wasOpen = aRoot.containerOpen;
+  if (!wasOpen) {
+    aRoot.containerOpen = true;
+  }
+
+  // If we have an array, pluck out the first item. If an object, pluc out the
+  // URI, we just compare URI's here.
+  if ("uri" in aQueryData) {
+    uri = aQueryData.uri;
+  } else {
+    uri = aQueryData[0].uri;
+  }
+
+  for (var i = 0; i < aRoot.childCount; i++) {
+    let node = aRoot.getChild(i);
+    if (uri == node.uri) {
+      rv = node;
+      break;
+    }
+  }
+  if (!wasOpen) {
+    aRoot.containerOpen = false;
+  }
+  return rv;
+}
+
+/**
+ * A nice helper function for debugging things. It prints the contents of a
+ * result set.
+ */
+function displayResultSet(aRoot) {
+  var wasOpen = aRoot.containerOpen;
+  if (!wasOpen) {
+    aRoot.containerOpen = true;
+  }
+
+  if (!aRoot.hasChildren) {
+    // Something wrong? Empty result set?
+    info("Result Set Empty");
+    return;
+  }
+
+  for (var i = 0; i < aRoot.childCount; ++i) {
+    info(
+      "Result Set URI: " +
+        aRoot.getChild(i).uri +
+        "   Title: " +
+        aRoot.getChild(i).title +
+        "   Visit Time: " +
+        aRoot.getChild(i).time
+    );
+  }
+  if (!wasOpen) {
+    aRoot.containerOpen = false;
+  }
+}
diff --git a/toolkit/components/places/tests/queries/readme.txt b/toolkit/components/places/tests/queries/readme.txt
new file mode 100644
index 0000000000..19414f96ed
--- /dev/null
+++ b/toolkit/components/places/tests/queries/readme.txt
@@ -0,0 +1,16 @@
+These are tests specific to the Places Query API.
+
+We are tracking the coverage of these tests here:
+http://wiki.mozilla.org/QA/TDAI/Projects/Places_Tests
+
+When creating one of these tests, you need to update those tables so that we
+know how well our test coverage is of this area.  Furthermore, when adding tests
+ensure to cover live update (changing the query set) by performing the following
+operations on the query set you get after running the query:
+* Adding a new item to the query set
+* Updating an existing item so that it matches the query set
+* Change an existing item so that it does not match the query set
+* Do multiple of the above inside an Update Batch transaction.
+* Try these transactions in different orders.
+
+Use the stub test to help you create a test with the proper structure.
diff --git a/toolkit/components/places/tests/queries/test_async.js b/toolkit/components/places/tests/queries/test_async.js
new file mode 100644
index 0000000000..8e895748ab
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_async.js
@@ -0,0 +1,379 @@
+/* -*- 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/. */
+
+var tests = [
+  {
+    desc:
+      "nsNavHistoryFolderResultNode: Basic test, asynchronously open and " +
+      "close container with a single child",
+
+    loading(node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+    },
+
+    opened(node, newState, oldState) {
+      this.checkStateChanged("opened", 1);
+      this.checkState("loading", 1);
+      this.checkArgs("opened", node, oldState, node.STATE_LOADING);
+
+      print("Checking node children");
+      compareArrayToResult(this.data, node);
+
+      print("Closing container");
+      node.containerOpen = false;
+    },
+
+    closed(node, newState, oldState) {
+      this.checkStateChanged("closed", 1);
+      this.checkState("opened", 1);
+      this.checkArgs("closed", node, oldState, node.STATE_OPENED);
+      this.success();
+    },
+  },
+
+  {
+    desc:
+      "nsNavHistoryFolderResultNode: After async open and no changes, " +
+      "second open should be synchronous",
+
+    loading(node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkState("closed", 0);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+    },
+
+    opened(node, newState, oldState) {
+      let cnt = this.checkStateChanged("opened", 1, 2);
+      let expectOldState = cnt === 1 ? node.STATE_LOADING : node.STATE_CLOSED;
+      this.checkArgs("opened", node, oldState, expectOldState);
+
+      print("Checking node children");
+      compareArrayToResult(this.data, node);
+
+      print("Closing container");
+      node.containerOpen = false;
+    },
+
+    closed(node, newState, oldState) {
+      let cnt = this.checkStateChanged("closed", 1, 2);
+      this.checkArgs("closed", node, oldState, node.STATE_OPENED);
+
+      switch (cnt) {
+        case 1:
+          node.containerOpen = true;
+          break;
+        case 2:
+          this.success();
+          break;
+      }
+    },
+  },
+
+  {
+    desc:
+      "nsNavHistoryFolderResultNode: After closing container in " +
+      "loading(), opened() should not be called",
+
+    loading(node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+      print("Closing container");
+      node.containerOpen = false;
+    },
+
+    opened(node, newState, oldState) {
+      do_throw("opened should not be called");
+    },
+
+    closed(node, newState, oldState) {
+      this.checkStateChanged("closed", 1);
+      this.checkState("loading", 1);
+      this.checkArgs("closed", node, oldState, node.STATE_LOADING);
+      this.success();
+    },
+  },
+];
+
+/**
+ * Instances of this class become the prototypes of the test objects above.
+ * Each test can therefore use the methods of this class, or they can override
+ * them if they want.  To run a test, call setup() and then run().
+ */
+function Test() {
+  // This maps a state name to the number of times it's been observed.
+  this.stateCounts = {};
+  // Promise object resolved when the next test can be run.
+  this.deferNextTest = Promise.withResolvers();
+}
+
+Test.prototype = {
+  /**
+   * Call this when an observer observes a container state change to sanity
+   * check the arguments.
+   *
+   * @param aNewState
+   *        The name of the new state.  Used only for printing out helpful info.
+   * @param aNode
+   *        The node argument passed to containerStateChanged.
+   * @param aOldState
+   *        The old state argument passed to containerStateChanged.
+   * @param aExpectOldState
+   *        The expected old state.
+   */
+  checkArgs(aNewState, aNode, aOldState, aExpectOldState) {
+    print("Node passed on " + aNewState + " should be result.root");
+    Assert.equal(this.result.root, aNode);
+    print("Old state passed on " + aNewState + " should be " + aExpectOldState);
+
+    // aOldState comes from xpconnect and will therefore be defined.  It may be
+    // zero, though, so use strict equality just to make sure aExpectOldState is
+    // also defined.
+    Assert.ok(aOldState === aExpectOldState);
+  },
+
+  /**
+   * Call this when an observer observes a container state change.  It registers
+   * the state change and ensures that it has been observed the given number
+   * of times.  See checkState for parameter explanations.
+   *
+   * @return The number of times aState has been observed, including the new
+   *         observation.
+   */
+  checkStateChanged(aState, aExpectedMin, aExpectedMax) {
+    print(aState + " state change observed");
+    if (!this.stateCounts.hasOwnProperty(aState)) {
+      this.stateCounts[aState] = 0;
+    }
+    this.stateCounts[aState]++;
+    return this.checkState(aState, aExpectedMin, aExpectedMax);
+  },
+
+  /**
+   * Ensures that the state has been observed the given number of times.
+   *
+   * @param  aState
+   *         The name of the state.
+   * @param  aExpectedMin
+   *         The state must have been observed at least this number of times.
+   * @param  aExpectedMax
+   *         The state must have been observed at most this number of times.
+   *         This parameter is optional.  If undefined, it's set to
+   *         aExpectedMin.
+   * @return The number of times aState has been observed, including the new
+   *         observation.
+   */
+  checkState(aState, aExpectedMin, aExpectedMax) {
+    let cnt = this.stateCounts[aState] || 0;
+    if (aExpectedMax === undefined) {
+      aExpectedMax = aExpectedMin;
+    }
+    if (aExpectedMin === aExpectedMax) {
+      print(
+        aState +
+          " should be observed only " +
+          aExpectedMin +
+          " times (actual = " +
+          cnt +
+          ")"
+      );
+    } else {
+      print(
+        aState +
+          " should be observed at least " +
+          aExpectedMin +
+          " times and at most " +
+          aExpectedMax +
+          " times (actual = " +
+          cnt +
+          ")"
+      );
+    }
+    Assert.ok(cnt >= aExpectedMin && cnt <= aExpectedMax);
+    return cnt;
+  },
+
+  /**
+   * Asynchronously opens the root of the test's result.
+   */
+  openContainer() {
+    // Set up the result observer.  It delegates to this object's callbacks and
+    // wraps them in a try-catch so that errors don't get eaten.
+    let self = this;
+    this.observer = {
+      containerStateChanged(container, oldState, newState) {
+        print(
+          "New state passed to containerStateChanged() should equal the " +
+            "container's current state"
+        );
+        Assert.equal(newState, container.state);
+
+        try {
+          switch (newState) {
+            case Ci.nsINavHistoryContainerResultNode.STATE_LOADING:
+              self.loading(container, newState, oldState);
+              break;
+            case Ci.nsINavHistoryContainerResultNode.STATE_OPENED:
+              self.opened(container, newState, oldState);
+              break;
+            case Ci.nsINavHistoryContainerResultNode.STATE_CLOSED:
+              self.closed(container, newState, oldState);
+              break;
+            default:
+              do_throw("Unexpected new state! " + newState);
+          }
+        } catch (err) {
+          do_throw(err);
+        }
+      },
+    };
+    this.result.addObserver(this.observer);
+
+    print("Opening container");
+    this.result.root.containerOpen = true;
+  },
+
+  /**
+   * Starts the test and returns a promise resolved when the test completes.
+   */
+  run() {
+    this.openContainer();
+    return this.deferNextTest.promise;
+  },
+
+  /**
+   * This must be called before run().  It adds a bookmark and sets up the
+   * test's result.  Override if need be.
+   */
+  async setup() {
+    // Populate the database with different types of bookmark items.
+    this.data = DataHelper.makeDataArray([
+      { type: "bookmark" },
+      { type: "separator" },
+      { type: "folder" },
+      { type: "bookmark", uri: "place:terms=foo" },
+    ]);
+    await task_populateDB(this.data);
+
+    // Make a query.
+    this.query = PlacesUtils.history.getNewQuery();
+    this.query.setParents([DataHelper.defaults.bookmark.parentGuid]);
+    this.opts = PlacesUtils.history.getNewQueryOptions();
+    this.opts.asyncEnabled = true;
+    this.result = PlacesUtils.history.executeQuery(this.query, this.opts);
+  },
+
+  /**
+   * Call this when the test has succeeded.  It cleans up resources and starts
+   * the next test.
+   */
+  success() {
+    this.result.removeObserver(this.observer);
+
+    // Resolve the promise object that indicates that the next test can be run.
+    this.deferNextTest.resolve();
+  },
+};
+
+/**
+ * This makes it a little bit easier to use the functions of head_queries.js.
+ */
+var DataHelper = {
+  defaults: {
+    bookmark: {
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+      uri: "http://example.com/",
+      title: "test bookmark",
+    },
+
+    folder: {
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+      title: "test folder",
+    },
+
+    separator: {
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    },
+  },
+
+  /**
+   * Converts an array of simple bookmark item descriptions to the more verbose
+   * format required by task_populateDB() in head_queries.js.
+   *
+   * @param  aData
+   *         An array of objects, each of which describes a bookmark item.
+   * @return An array of objects suitable for passing to populateDB().
+   */
+  makeDataArray: function DH_makeDataArray(aData) {
+    let self = this;
+    return aData.map(function (dat) {
+      let type = dat.type;
+      dat = self._makeDataWithDefaults(dat, self.defaults[type]);
+      switch (type) {
+        case "bookmark":
+          return {
+            isBookmark: true,
+            uri: dat.uri,
+            parentGuid: dat.parentGuid,
+            index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+            title: dat.title,
+            isInQuery: true,
+          };
+        case "separator":
+          return {
+            isSeparator: true,
+            parentGuid: dat.parentGuid,
+            index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+            isInQuery: true,
+          };
+        case "folder":
+          return {
+            isFolder: true,
+            parentGuid: dat.parentGuid,
+            index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+            title: dat.title,
+            isInQuery: true,
+          };
+        default:
+          do_throw("Unknown data type when populating DB: " + type);
+          return undefined;
+      }
+    });
+  },
+
+  /**
+   * Returns a copy of aData, except that any properties that are undefined but
+   * defined in aDefaults are set to the corresponding values in aDefaults.
+   *
+   * @param  aData
+   *         An object describing a bookmark item.
+   * @param  aDefaults
+   *         An object describing the default bookmark item.
+   * @return A copy of aData with defaults values set.
+   */
+  _makeDataWithDefaults: function DH__makeDataWithDefaults(aData, aDefaults) {
+    let dat = {};
+    for (let [prop, val] of Object.entries(aDefaults)) {
+      dat[prop] = aData.hasOwnProperty(prop) ? aData[prop] : val;
+    }
+    return dat;
+  },
+};
+
+add_task(async function test_async() {
+  for (let test of tests) {
+    await PlacesUtils.bookmarks.eraseEverything();
+
+    Object.setPrototypeOf(test, new Test());
+    await test.setup();
+
+    print("------ Running test: " + test.desc);
+    await test.run();
+  }
+
+  await PlacesUtils.bookmarks.eraseEverything();
+  print("All tests done, exiting");
+});
diff --git a/toolkit/components/places/tests/queries/test_bookmarks.js b/toolkit/components/places/tests/queries/test_bookmarks.js
new file mode 100644
index 0000000000..b5f2ef754f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_bookmarks.js
@@ -0,0 +1,105 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function test_eraseEverything() {
+  info("Test folder with eraseEverything");
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.unfiledGuid,
+    children: [
+      {
+        title: "remove-folder",
+        type: PlacesUtils.bookmarks.TYPE_FOLDER,
+        children: [
+          { url: "http://mozilla.org/", title: "title 1" },
+          { url: "http://mozilla.org/", title: "title 2" },
+          { title: "sub-folder", type: PlacesUtils.bookmarks.TYPE_FOLDER },
+          { type: PlacesUtils.bookmarks.TYPE_SEPARATOR },
+        ],
+      },
+    ],
+  });
+
+  let unfiled = PlacesUtils.getFolderContents(
+    PlacesUtils.bookmarks.unfiledGuid
+  ).root;
+  Assert.equal(unfiled.childCount, 1, "There should be 1 folder");
+  let folder = unfiled.getChild(0);
+  // Test dateAdded and lastModified properties.
+  Assert.equal(typeof folder.dateAdded, "number");
+  Assert.ok(folder.dateAdded > 0);
+  Assert.equal(typeof folder.lastModified, "number");
+  Assert.ok(folder.lastModified > 0);
+
+  let root = PlacesUtils.getFolderContents(folder.bookmarkGuid).root;
+  Assert.equal(root.childCount, 4, "The folder should have 4 children");
+  for (let i = 0; i < root.childCount; ++i) {
+    let node = root.getChild(i);
+    Assert.greater(node.itemId, 0, "The node should have an itemId");
+  }
+  Assert.equal(root.getChild(0).title, "title 1");
+  Assert.equal(root.getChild(1).title, "title 2");
+
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  // Refetch the guid to refresh the data.
+  unfiled = PlacesUtils.getFolderContents(
+    PlacesUtils.bookmarks.unfiledGuid
+  ).root;
+  Assert.equal(unfiled.childCount, 0);
+  unfiled.containerOpen = false;
+});
+
+add_task(async function test_search_title() {
+  let title = "ZZZXXXYYY";
+  let bm = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: "http://mozilla.org/",
+    title,
+  });
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "ZZZXXXYYY";
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 1);
+  let node = root.getChild(0);
+  Assert.equal(node.title, title);
+
+  // Test dateAdded and lastModified properties.
+  Assert.equal(typeof node.dateAdded, "number");
+  Assert.ok(node.dateAdded > 0);
+  Assert.equal(typeof node.lastModified, "number");
+  Assert.ok(node.lastModified > 0);
+  Assert.equal(node.bookmarkGuid, bm.guid);
+
+  await PlacesUtils.bookmarks.remove(bm);
+  Assert.equal(root.childCount, 0);
+  root.containerOpen = false;
+});
+
+add_task(async function test_long_title() {
+  let title = Array(TITLE_LENGTH_MAX + 5).join("A");
+  let bm = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: "http://mozilla.org/",
+    title,
+  });
+  let root = PlacesUtils.getFolderContents(
+    PlacesUtils.bookmarks.unfiledGuid
+  ).root;
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 1);
+  let node = root.getChild(0);
+  Assert.equal(node.title, title.substr(0, TITLE_LENGTH_MAX));
+
+  // Update with another long title.
+  let newTitle = Array(TITLE_LENGTH_MAX + 5).join("B");
+  bm.title = newTitle;
+  await PlacesUtils.bookmarks.update(bm);
+  Assert.equal(node.title, newTitle.substr(0, TITLE_LENGTH_MAX));
+
+  await PlacesUtils.bookmarks.remove(bm);
+  Assert.equal(root.childCount, 0);
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_containersQueries_sorting.js b/toolkit/components/places/tests/queries/test_containersQueries_sorting.js
new file mode 100644
index 0000000000..9cdc0f2a52
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_containersQueries_sorting.js
@@ -0,0 +1,492 @@
+/* -*- 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/. */
+
+/**
+ * Testing behavior of bug 473157
+ * "Want to sort history in container view without sorting the containers"
+ * and regression bug 488783
+ * Tags list no longer sorted (alphabetized).
+ * This test is for global testing sorting containers queries.
+ */
+
+// Globals and Constants
+
+var resultTypes = [
+  {
+    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY,
+    name: "RESULTS_AS_DATE_QUERY",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY,
+    name: "RESULTS_AS_SITE_QUERY",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY,
+    name: "RESULTS_AS_DATE_SITE_QUERY",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT,
+    name: "RESULTS_AS_TAGS_ROOT",
+  },
+];
+
+var sortingModes = [
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING,
+    name: "SORT_BY_TITLE_ASCENDING",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING,
+    name: "SORT_BY_TITLE_DESCENDING",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING,
+    name: "SORT_BY_DATE_ASCENDING",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING,
+    name: "SORT_BY_DATE_DESCENDING",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING,
+    name: "SORT_BY_DATEADDED_ASCENDING",
+  },
+  {
+    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING,
+    name: "SORT_BY_DATEADDED_DESCENDING",
+  },
+];
+
+// These pages will be added from newest to oldest and from less visited to most
+// visited.
+var pages = [
+  "http://www.mozilla.org/c/",
+  "http://www.mozilla.org/a/",
+  "http://www.mozilla.org/b/",
+  "http://www.mozilla.com/c/",
+  "http://www.mozilla.com/a/",
+  "http://www.mozilla.com/b/",
+];
+
+var tags = ["mozilla", "Development", "test"];
+
+// Test Runner
+
+/**
+ * Enumerates all the sequences of the cartesian product of the arrays contained
+ * in aSequences.  Examples:
+ *
+ *   cartProd([[1, 2, 3], ["a", "b"]], callback);
+ *   // callback is called 3 * 2 = 6 times with the following arrays:
+ *   // [1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]
+ *
+ *   cartProd([["a"], [1, 2, 3], ["X", "Y"]], callback);
+ *   // callback is called 1 * 3 * 2 = 6 times with the following arrays:
+ *   // ["a", 1, "X"], ["a", 1, "Y"], ["a", 2, "X"], ["a", 2, "Y"],
+ *   // ["a", 3, "X"], ["a", 3, "Y"]
+ *
+ *   cartProd([[1], [2], [3], [4]], callback);
+ *   // callback is called 1 * 1 * 1 * 1 = 1 time with the following array:
+ *   // [1, 2, 3, 4]
+ *
+ *   cartProd([], callback);
+ *   // callback is 0 times
+ *
+ *   cartProd([[1, 2, 3, 4]], callback);
+ *   // callback is called 4 times with the following arrays:
+ *   // [1], [2], [3], [4]
+ *
+ * @param  aSequences
+ *         an array that contains an arbitrary number of arrays
+ * @param  aCallback
+ *         a function that is passed each sequence of the product as it's
+ *         computed
+ * @return the total number of sequences in the product
+ */
+function cartProd(aSequences, aCallback) {
+  if (aSequences.length === 0) {
+    return 0;
+  }
+
+  // For each sequence in aSequences, we maintain a pointer (an array index,
+  // really) to the element we're currently enumerating in that sequence
+  var seqEltPtrs = aSequences.map(i => 0);
+
+  var numProds = 0;
+  var done = false;
+  while (!done) {
+    numProds++;
+
+    // prod = sequence in product we're currently enumerating
+    var prod = [];
+    for (var i = 0; i < aSequences.length; i++) {
+      prod.push(aSequences[i][seqEltPtrs[i]]);
+    }
+    aCallback(prod);
+
+    // The next sequence in the product differs from the current one by just a
+    // single element.  Determine which element that is.  We advance the
+    // "rightmost" element pointer to the "right" by one.  If we move past the
+    // end of that pointer's sequence, reset the pointer to the first element
+    // in its sequence and then try the sequence to the "left", and so on.
+
+    // seqPtr = index of rightmost input sequence whose element pointer is not
+    // past the end of the sequence
+    var seqPtr = aSequences.length - 1;
+    while (!done) {
+      // Advance the rightmost element pointer.
+      seqEltPtrs[seqPtr]++;
+
+      // The rightmost element pointer is past the end of its sequence.
+      if (seqEltPtrs[seqPtr] >= aSequences[seqPtr].length) {
+        seqEltPtrs[seqPtr] = 0;
+        seqPtr--;
+
+        // All element pointers are past the ends of their sequences.
+        if (seqPtr < 0) {
+          done = true;
+        }
+      } else {
+        break;
+      }
+    }
+  }
+  return numProds;
+}
+
+/**
+ * Test a query based on passed-in options.
+ *
+ * @param aSequence
+ *        array of options we will use to query.
+ */
+function test_query_callback(aSequence) {
+  Assert.equal(aSequence.length, 2);
+  var resultType = aSequence[0];
+  var sortingMode = aSequence[1];
+  print(
+    "\n\n*** Testing default sorting for resultType (" +
+      resultType.name +
+      ") and sortingMode (" +
+      sortingMode.name +
+      ")"
+  );
+
+  // Skip invalid combinations sorting queries by none.
+  if (
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT &&
+    (sortingMode.value == Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING ||
+      sortingMode.value == Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING)
+  ) {
+    // This is a bookmark query, we can't sort by visit date.
+    sortingMode.value = Ci.nsINavHistoryQueryOptions.SORT_BY_NONE;
+  }
+  if (
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY ||
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
+  ) {
+    // This is an history query, we can't sort by date added.
+    if (
+      sortingMode.value ==
+        Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING ||
+      sortingMode.value ==
+        Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING
+    ) {
+      sortingMode.value = Ci.nsINavHistoryQueryOptions.SORT_BY_NONE;
+    }
+  }
+
+  // Create a new query with required options.
+  var query = PlacesUtils.history.getNewQuery();
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.resultType = resultType.value;
+  options.sortingMode = sortingMode.value;
+
+  // Compare resultset with expectedData.
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  if (
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
+  ) {
+    // Date containers are always sorted by date descending.
+    check_children_sorting(
+      root,
+      Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING
+    );
+  } else {
+    check_children_sorting(root, sortingMode.value);
+  }
+
+  // Now Check sorting of the first child container.
+  var container = root
+    .getChild(0)
+    .QueryInterface(Ci.nsINavHistoryContainerResultNode);
+  container.containerOpen = true;
+
+  if (
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
+  ) {
+    // Has more than one level of containers, first we check the sorting of
+    // the first level (site containers), those won't inherit sorting...
+    check_children_sorting(
+      container,
+      Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
+    );
+    // ...then we check sorting of the contained urls, we can't inherit sorting
+    // since the above level does not inherit it, so they will be sorted by
+    // title ascending.
+    let innerContainer = container
+      .getChild(0)
+      .QueryInterface(Ci.nsINavHistoryContainerResultNode);
+    innerContainer.containerOpen = true;
+    check_children_sorting(
+      innerContainer,
+      Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
+    );
+    innerContainer.containerOpen = false;
+  } else if (
+    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT
+  ) {
+    // Sorting mode for tag contents is hardcoded for now, to allow for faster
+    // duplicates filtering.
+    check_children_sorting(
+      container,
+      Ci.nsINavHistoryQueryOptions.SORT_BY_NONE
+    );
+  } else {
+    check_children_sorting(container, sortingMode.value);
+  }
+
+  container.containerOpen = false;
+  root.containerOpen = false;
+
+  test_result_sortingMode_change(result, resultType, sortingMode);
+}
+
+/**
+ * Sets sortingMode on aResult and checks for correct sorting of children.
+ * Containers should not change their sorting, while contained uri nodes should.
+ *
+ * @param aResult
+ *        nsINavHistoryResult generated by our query.
+ * @param aResultType
+ *        required result type.
+ * @param aOriginalSortingMode
+ *        the sorting mode from query's options.
+ */
+function test_result_sortingMode_change(
+  aResult,
+  aResultType,
+  aOriginalSortingMode
+) {
+  var root = aResult.root;
+  // Now we set sortingMode on the result and check that containers are not
+  // sorted while children are.
+  sortingModes.forEach(function sortingModeChecker(aForcedSortingMode) {
+    print(
+      "\n* Test setting sortingMode (" +
+        aForcedSortingMode.name +
+        ") " +
+        "on result with resultType (" +
+        aResultType.name +
+        ") " +
+        "currently sorted as (" +
+        aOriginalSortingMode.name +
+        ")"
+    );
+
+    aResult.sortingMode = aForcedSortingMode.value;
+    root.containerOpen = true;
+
+    if (
+      aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
+      aResultType.value ==
+        Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
+    ) {
+      // Date containers are always sorted by date descending.
+      check_children_sorting(
+        root,
+        Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING
+      );
+    } else if (
+      aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY &&
+      (aOriginalSortingMode.value ==
+        Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING ||
+        aOriginalSortingMode.value ==
+          Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING)
+    ) {
+      // Site containers don't have a good time property to sort by.
+      check_children_sorting(root, Ci.nsINavHistoryQueryOptions.SORT_BY_NONE);
+    } else {
+      check_children_sorting(root, aOriginalSortingMode.value);
+    }
+
+    // Now Check sorting of the first child container.
+    var container = root
+      .getChild(0)
+      .QueryInterface(Ci.nsINavHistoryContainerResultNode);
+    container.containerOpen = true;
+
+    if (
+      aResultType.value ==
+      Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
+    ) {
+      // Has more than one level of containers, first we check the sorting of
+      // the first level (site containers), those won't be sorted...
+      check_children_sorting(
+        container,
+        Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
+      );
+      // ...then we check sorting of the second level of containers, result
+      // will sort them through recursiveSort.
+      let innerContainer = container
+        .getChild(0)
+        .QueryInterface(Ci.nsINavHistoryContainerResultNode);
+      innerContainer.containerOpen = true;
+      check_children_sorting(innerContainer, aForcedSortingMode.value);
+      innerContainer.containerOpen = false;
+    } else {
+      if (
+        aResultType.value ==
+          Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
+        aResultType.value ==
+          Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY ||
+        aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY
+      ) {
+        // Date containers are always sorted by date descending.
+        check_children_sorting(root, Ci.nsINavHistoryQueryOptions.SORT_BY_NONE);
+      } else {
+        check_children_sorting(root, aOriginalSortingMode.value);
+      }
+
+      // Children should always be sorted.
+      check_children_sorting(container, aForcedSortingMode.value);
+    }
+
+    container.containerOpen = false;
+    root.containerOpen = false;
+  });
+}
+
+/**
+ * Test if children of aRootNode are correctly sorted.
+ * @param aRootNode
+ *        already opened root node from our query's result.
+ * @param aExpectedSortingMode
+ *        The sortingMode we expect results to be.
+ */
+function check_children_sorting(aRootNode, aExpectedSortingMode) {
+  var results = [];
+  print("Found children:");
+  for (let i = 0; i < aRootNode.childCount; i++) {
+    results[i] = aRootNode.getChild(i);
+    print(i + " " + results[i].title);
+  }
+
+  // Helper for case insensitive string comparison.
+  function caseInsensitiveStringComparator(a, b) {
+    var aLC = a.toLowerCase();
+    var bLC = b.toLowerCase();
+    if (aLC < bLC) {
+      return -1;
+    }
+    if (aLC > bLC) {
+      return 1;
+    }
+    return 0;
+  }
+
+  // Get a comparator based on expected sortingMode.
+  var comparator;
+  switch (aExpectedSortingMode) {
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_NONE:
+      comparator = function (a, b) {
+        return 0;
+      };
+      break;
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING:
+      comparator = function (a, b) {
+        return caseInsensitiveStringComparator(a.title, b.title);
+      };
+      break;
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING:
+      comparator = function (a, b) {
+        return -caseInsensitiveStringComparator(a.title, b.title);
+      };
+      break;
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING:
+      comparator = function (a, b) {
+        return a.time - b.time;
+      };
+      break;
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING:
+      comparator = function (a, b) {
+        return b.time - a.time;
+      };
+    // fall through - we shouldn't do this, see bug 1572437.
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING:
+      comparator = function (a, b) {
+        return a.dateAdded - b.dateAdded;
+      };
+      break;
+    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING:
+      comparator = function (a, b) {
+        return b.dateAdded - a.dateAdded;
+      };
+      break;
+    default:
+      do_throw("Unknown sorting type: " + aExpectedSortingMode);
+  }
+
+  // Make an independent copy of the results array and sort it.
+  var sortedResults = results.slice();
+  sortedResults.sort(comparator);
+  // Actually compare returned children with our sorted array.
+  for (let i = 0; i < sortedResults.length; i++) {
+    if (sortedResults[i].title != results[i].title) {
+      print(
+        i +
+          " index wrong, expected " +
+          sortedResults[i].title +
+          " found " +
+          results[i].title
+      );
+    }
+    Assert.equal(sortedResults[i].title, results[i].title);
+  }
+}
+
+// Main
+
+add_task(async function test_containersQueries_sorting() {
+  // Add visits, bookmarks and tags to our database.
+  var timeInMilliseconds = Date.now();
+  var visitCount = 0;
+  var dayOffset = 0;
+  var visits = [];
+  pages.forEach(aPageUrl =>
+    visits.push({
+      isVisit: true,
+      isBookmark: true,
+      transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
+      uri: aPageUrl,
+      title: aPageUrl,
+      // subtract 5 hours per iteration, to expose more than one day container.
+      lastVisit: (timeInMilliseconds - 18000 * 1000 * dayOffset++) * 1000,
+      visitCount: visitCount++,
+      isTag: true,
+      tagArray: tags,
+      isInQuery: true,
+    })
+  );
+  await task_populateDB(visits);
+
+  cartProd([resultTypes, sortingModes], test_query_callback);
+});
diff --git a/toolkit/components/places/tests/queries/test_downloadHistory_liveUpdate.js b/toolkit/components/places/tests/queries/test_downloadHistory_liveUpdate.js
new file mode 100644
index 0000000000..ba0f528b62
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_downloadHistory_liveUpdate.js
@@ -0,0 +1,121 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that download history (filtered by transition) queries
+// don't invalidate (and requery) too often.
+
+function accumulateNotifications(result) {
+  let notifications = [];
+  let resultObserver = new Proxy(NavHistoryResultObserver, {
+    get(target, name) {
+      if (name == "check") {
+        result.removeObserver(resultObserver, false);
+        return expectedNotifications =>
+          Assert.deepEqual(notifications, expectedNotifications);
+      }
+      // ignore a few uninteresting notifications.
+      if (["QueryInterface", "containerStateChanged"].includes(name)) {
+        return () => {};
+      }
+      return () => {
+        notifications.push(name);
+      };
+    },
+  });
+  result.addObserver(resultObserver, false);
+  return resultObserver;
+}
+
+add_task(async function test_downloadhistory_query_notifications() {
+  const MAX_RESULTS = 5;
+  let query = PlacesUtils.history.getNewQuery();
+  query.setTransitions([PlacesUtils.history.TRANSITIONS.DOWNLOAD]);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+  options.maxResults = MAX_RESULTS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let notifications = accumulateNotifications(result);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+  // Add more maxResults downloads in order.
+  let transitions = Object.values(PlacesUtils.history.TRANSITIONS);
+  for (let transition of transitions) {
+    let uri = "http://fx-search.com/" + transition;
+    await PlacesTestUtils.addVisits({
+      uri,
+      transition,
+      title: "test " + transition,
+    });
+    // For each visit also set apart:
+    //  - a bookmark
+    //  - an annotation
+    //  - an icon
+    await PlacesUtils.bookmarks.insert({
+      url: uri,
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    });
+    await PlacesUtils.history.update({
+      url: uri,
+      annotations: new Map([["test/anno", "testValue"]]),
+    });
+    await PlacesTestUtils.addFavicons(new Map([[uri, SMALLPNG_DATA_URI.spec]]));
+  }
+  // Remove all the visits one by one.
+  for (let transition of transitions) {
+    let uri = Services.io.newURI("http://fx-search.com/" + transition);
+    await PlacesUtils.history.remove(uri);
+  }
+  root.containerOpen = false;
+  // We pretty much don't want to see invalidateContainer here, because that
+  // means we requeried.
+  // We also don't want to see changes caused by filtered-out transition types.
+  notifications.check([
+    "nodeHistoryDetailsChanged",
+    "nodeInserted",
+    "nodeTitleChanged",
+    "nodeIconChanged",
+    "nodeRemoved",
+  ]);
+});
+
+add_task(async function test_downloadhistory_query_filtering() {
+  const MAX_RESULTS = 3;
+  let query = PlacesUtils.history.getNewQuery();
+  query.setTransitions([PlacesUtils.history.TRANSITIONS.DOWNLOAD]);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+  options.maxResults = MAX_RESULTS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 0, "No visits found");
+  // Add more than maxResults downloads.
+  let uris = [];
+  // Define a monotonic visit date to ensure results order stability.
+  let visitDate = Date.now() * 1000;
+  for (let i = 0; i < MAX_RESULTS + 1; ++i, visitDate += 1000) {
+    let uri = `http://fx-search.com/download/${i}`;
+    await PlacesTestUtils.addVisits({
+      uri,
+      transition: PlacesUtils.history.TRANSITIONS.DOWNLOAD,
+      visitDate,
+    });
+    uris.push(uri);
+  }
+  // Add an older download visit out of the maxResults timeframe.
+  await PlacesTestUtils.addVisits({
+    uri: `http://fx-search.com/download/unordered`,
+    transition: PlacesUtils.history.TRANSITIONS.DOWNLOAD,
+    visitDate: new Date(Date.now() - 7200000),
+  });
+
+  Assert.equal(root.childCount, MAX_RESULTS, "Result should be limited");
+  // Invert the uris array because we are sorted by date descending.
+  uris.reverse();
+  for (let i = 0; i < root.childCount; ++i) {
+    let node = root.getChild(i);
+    Assert.equal(node.uri, uris[i], "Found the expected uri");
+  }
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_excludeQueries.js b/toolkit/components/places/tests/queries/test_excludeQueries.js
new file mode 100644
index 0000000000..c48f84c7f4
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_excludeQueries.js
@@ -0,0 +1,118 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+var bm;
+var fakeQuery;
+var folderShortcut;
+
+add_task(async function setup() {
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  bm = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: "http://example.com/",
+    title: "a bookmark",
+  });
+  fakeQuery = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: "place:terms=foo",
+    title: "a bookmark",
+  });
+  folderShortcut = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    url: `place:parent=${PlacesUtils.bookmarks.toolbarGuid}`,
+    title: "a bookmark",
+  });
+
+  checkBookmarkObject(bm);
+  checkBookmarkObject(fakeQuery);
+  checkBookmarkObject(folderShortcut);
+});
+
+add_task(async function test_bookmarks_url_query_implicit_exclusions() {
+  // When we run bookmarks url queries, we implicity filter out queries and
+  // folder shortcuts regardless of excludeQueries. They don't make sense to
+  // include in the results.
+  let expectedGuids = [bm.guid];
+  let query = PlacesUtils.history.getNewQuery();
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.excludeQueries = true;
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  Assert.equal(
+    root.childCount,
+    expectedGuids.length,
+    "Checking root child count"
+  );
+  for (let i = 0; i < expectedGuids.length; i++) {
+    Assert.equal(
+      root.getChild(i).bookmarkGuid,
+      expectedGuids[i],
+      "should have got the expected item"
+    );
+  }
+
+  root.containerOpen = false;
+});
+
+add_task(async function test_bookmarks_excludeQueries() {
+  // When excluding queries, we exclude actual queries, but not folder shortcuts.
+  let expectedGuids = [bm.guid, folderShortcut.guid];
+  let query = {},
+    options = {};
+  let queryString = `place:parent=${PlacesUtils.bookmarks.unfiledGuid}&excludeQueries=1`;
+  PlacesUtils.history.queryStringToQuery(queryString, query, options);
+
+  let root = PlacesUtils.history.executeQuery(query.value, options.value).root;
+  root.containerOpen = true;
+
+  Assert.equal(
+    root.childCount,
+    expectedGuids.length,
+    "Checking root child count"
+  );
+  for (let i = 0; i < expectedGuids.length; i++) {
+    Assert.equal(
+      root.getChild(i).bookmarkGuid,
+      expectedGuids[i],
+      "should have got the expected item"
+    );
+  }
+
+  root.containerOpen = false;
+});
+
+add_task(async function test_search_excludesQueries() {
+  // Searching implicity removes queries and folder shortcuts even if excludeQueries
+  // is not specified.
+  let expectedGuids = [bm.guid];
+
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "bookmark";
+
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  Assert.equal(
+    root.childCount,
+    expectedGuids.length,
+    "Checking root child count"
+  );
+  for (let i = 0; i < expectedGuids.length; i++) {
+    Assert.equal(
+      root.getChild(i).bookmarkGuid,
+      expectedGuids[i],
+      "should have got the expected item"
+    );
+  }
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_history_queries_tags_liveUpdate.js b/toolkit/components/places/tests/queries/test_history_queries_tags_liveUpdate.js
new file mode 100644
index 0000000000..aef45ff8f1
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_history_queries_tags_liveUpdate.js
@@ -0,0 +1,131 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that tags changes are correctly live-updated in a history
+// query.
+
+let timeInMicroseconds = PlacesUtils.toPRTime(Date.now() - 10000);
+
+function newTimeInMicroseconds() {
+  timeInMicroseconds = timeInMicroseconds + 1000;
+  return timeInMicroseconds;
+}
+
+var gTestData = [
+  {
+    isVisit: true,
+    uri: "http://example.com/1/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    isBookmark: true,
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    title: "example1",
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/2/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    isBookmark: true,
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    title: "example2",
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/3/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    isBookmark: true,
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    title: "example3",
+  },
+];
+
+function newQueryWithOptions() {
+  return [
+    PlacesUtils.history.getNewQuery(),
+    PlacesUtils.history.getNewQueryOptions(),
+  ];
+}
+
+function testQueryContents(aQuery, aOptions, aCallback) {
+  let root = PlacesUtils.history.executeQuery(aQuery, aOptions).root;
+  root.containerOpen = true;
+  aCallback(root);
+  root.containerOpen = false;
+}
+
+add_task(async function test_initialize() {
+  await task_populateDB(gTestData);
+});
+
+add_task(function pages_query() {
+  let [query, options] = newQueryWithOptions();
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+    for (let i = 0; i < root.childCount; i++) {
+      let node = root.getChild(i);
+      let uri = NetUtil.newURI(node.uri);
+      Assert.equal(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, null);
+    }
+  });
+});
+
+add_task(function visits_query() {
+  let [query, options] = newQueryWithOptions();
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_VISIT;
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+    for (let i = 0; i < root.childCount; i++) {
+      let node = root.getChild(i);
+      let uri = NetUtil.newURI(node.uri);
+      Assert.equal(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, null);
+    }
+  });
+});
+
+add_task(function bookmark_parent_query() {
+  let [query, options] = newQueryWithOptions();
+  query.setParents([PlacesUtils.bookmarks.unfiledGuid]);
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+    for (let i = 0; i < root.childCount; i++) {
+      let node = root.getChild(i);
+      let uri = NetUtil.newURI(node.uri);
+      Assert.equal(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, null);
+    }
+  });
+});
+
+add_task(function history_query() {
+  let [query, options] = newQueryWithOptions();
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+    for (let i = 0; i < root.childCount; i++) {
+      let node = root.getChild(i);
+      let uri = NetUtil.newURI(node.uri);
+      Assert.equal(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, null);
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      Assert.equal(node.tags, null);
+    }
+  });
+});
diff --git a/toolkit/components/places/tests/queries/test_history_queries_titles_liveUpdate.js b/toolkit/components/places/tests/queries/test_history_queries_titles_liveUpdate.js
new file mode 100644
index 0000000000..ac3931892f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_history_queries_titles_liveUpdate.js
@@ -0,0 +1,217 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that tags changes are correctly live-updated in a history
+// query.
+
+let timeInMicroseconds = PlacesUtils.toPRTime(Date.now() - 10000);
+
+function newTimeInMicroseconds() {
+  timeInMicroseconds = timeInMicroseconds + 1000;
+  return timeInMicroseconds;
+}
+
+var gTestData = [
+  {
+    isVisit: true,
+    uri: "http://example.com/1/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    title: "title1",
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/2/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    title: "title2",
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/3/",
+    lastVisit: newTimeInMicroseconds(),
+    isInQuery: true,
+    title: "title3",
+  },
+];
+
+function searchNodeHavingUrl(aRoot, aUrl) {
+  for (let i = 0; i < aRoot.childCount; i++) {
+    if (aRoot.getChild(i).uri == aUrl) {
+      return aRoot.getChild(i);
+    }
+  }
+  return undefined;
+}
+
+function newQueryWithOptions() {
+  return [
+    PlacesUtils.history.getNewQuery(),
+    PlacesUtils.history.getNewQueryOptions(),
+  ];
+}
+
+add_task(async function pages_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+  for (let i = 0; i < root.childCount; i++) {
+    let node = root.getChild(i);
+    Assert.equal(node.title, gTestData[i].title);
+    let uri = NetUtil.newURI(node.uri);
+    await PlacesTestUtils.addVisits({ uri, title: "changedTitle" });
+    Assert.equal(node.title, "changedTitle");
+    await PlacesTestUtils.addVisits({ uri, title: gTestData[i].title });
+    Assert.equal(node.title, gTestData[i].title);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function visits_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_VISIT;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+
+  for (let testData of gTestData) {
+    let uri = NetUtil.newURI(testData.uri);
+    let node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, testData.title);
+    await PlacesTestUtils.addVisits({ uri, title: "changedTitle" });
+    node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, "changedTitle");
+    await PlacesTestUtils.addVisits({ uri, title: testData.title });
+    node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, testData.title);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function pages_searchterm_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "example";
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+  for (let i = 0; i < root.childCount; i++) {
+    let node = root.getChild(i);
+    let uri = NetUtil.newURI(node.uri);
+    Assert.equal(node.title, gTestData[i].title);
+    await PlacesTestUtils.addVisits({ uri, title: "changedTitle" });
+    Assert.equal(node.title, "changedTitle");
+    await PlacesTestUtils.addVisits({ uri, title: gTestData[i].title });
+    Assert.equal(node.title, gTestData[i].title);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function visits_searchterm_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "example";
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_VISIT;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  compareArrayToResult([gTestData[0], gTestData[1], gTestData[2]], root);
+  for (let testData of gTestData) {
+    let uri = NetUtil.newURI(testData.uri);
+    let node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, testData.title);
+    await PlacesTestUtils.addVisits({ uri, title: "changedTitle" });
+    node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, "changedTitle");
+    await PlacesTestUtils.addVisits({ uri, title: testData.title });
+    node = searchNodeHavingUrl(root, testData.uri);
+    Assert.equal(node.title, testData.title);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function pages_searchterm_is_title_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "match";
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  compareArrayToResult([], root);
+  for (let data of gTestData) {
+    let uri = NetUtil.newURI(data.uri);
+    let origTitle = data.title;
+    data.title = "match";
+    await PlacesTestUtils.addVisits({
+      uri,
+      title: data.title,
+      visitDate: data.lastVisit,
+    });
+    compareArrayToResult([data], root);
+    data.title = origTitle;
+    await PlacesTestUtils.addVisits({
+      uri,
+      title: data.title,
+      visitDate: data.lastVisit,
+    });
+    compareArrayToResult([], root);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function visits_searchterm_is_title_query() {
+  await task_populateDB(gTestData);
+
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "match";
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_VISIT;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  compareArrayToResult([], root);
+  for (let data of gTestData) {
+    let uri = NetUtil.newURI(data.uri);
+    let origTitle = data.title;
+    data.title = "match";
+
+    info("Adding " + uri.spec);
+    await PlacesTestUtils.addVisits({
+      uri,
+      title: data.title,
+      visitDate: data.lastVisit,
+    });
+
+    compareArrayToResult([data], root);
+    data.title = origTitle;
+    info("Clobbering " + uri.spec);
+    await PlacesTestUtils.addVisits({
+      uri,
+      title: data.title,
+      visitDate: data.lastVisit,
+    });
+
+    compareArrayToResult([], root);
+  }
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
diff --git a/toolkit/components/places/tests/queries/test_options_inherit.js b/toolkit/components/places/tests/queries/test_options_inherit.js
new file mode 100644
index 0000000000..ae43350eda
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_options_inherit.js
@@ -0,0 +1,118 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+/**
+ * Tests inheritance of certain query options like:
+ * excludeItems, excludeQueries, expandQueries.
+ */
+
+"use strict";
+
+add_task(async function () {
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.unfiledGuid,
+    children: [
+      {
+        title: "folder",
+        type: PlacesUtils.bookmarks.TYPE_FOLDER,
+        children: [
+          {
+            title: "query",
+            url:
+              "place:queryType=" +
+              Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS,
+          },
+          { title: "bm", url: "http://example.com" },
+          {
+            type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+          },
+        ],
+      },
+      { title: "bm", url: "http://example.com" },
+      {
+        type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+      },
+    ],
+  });
+
+  await test_query({}, 3, 3, 2);
+  await test_query({ expandQueries: false }, 3, 3, 0);
+  await test_query({ excludeItems: true }, 1, 1, 0);
+  await test_query({ excludeItems: true, expandQueries: false }, 1, 1, 0);
+  await test_query({ excludeItems: true, excludeQueries: true }, 1, 0, 0);
+});
+
+async function test_query(
+  opts,
+  expectedRootCc,
+  expectedFolderCc,
+  expectedQueryCc
+) {
+  let query = PlacesUtils.history.getNewQuery();
+  query.setParents([PlacesUtils.bookmarks.unfiledGuid]);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  for (const [o, v] of Object.entries(opts)) {
+    info(`Setting ${o} to ${v}`);
+    options[o] = v;
+  }
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  Assert.equal(root.childCount, expectedRootCc, "Checking root child count");
+  if (root.childCount > 0) {
+    let folder = root.getChild(0);
+    Assert.equal(folder.title, "folder", "Found the expected folder");
+
+    // Check the folder uri doesn't reflect the root options, since those
+    // options are inherited and not part of this node declaration.
+    checkURIOptions(folder.uri);
+
+    PlacesUtils.asContainer(folder).containerOpen = true;
+    Assert.equal(
+      folder.childCount,
+      expectedFolderCc,
+      "Checking folder child count"
+    );
+    if (folder.childCount) {
+      let placeQuery = folder.getChild(0);
+      PlacesUtils.asQuery(placeQuery).containerOpen = true;
+      Assert.equal(
+        placeQuery.childCount,
+        expectedQueryCc,
+        "Checking query child count"
+      );
+      placeQuery.containerOpen = false;
+    }
+    folder.containerOpen = false;
+  }
+  let f = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+  });
+  checkURIOptions(root.getChild(root.childCount - 1).uri);
+  await PlacesUtils.bookmarks.remove(f);
+
+  root.containerOpen = false;
+}
+
+function checkURIOptions(uri) {
+  info("Checking options for uri " + uri);
+  let folderOptions = {};
+  PlacesUtils.history.queryStringToQuery(uri, {}, folderOptions);
+  folderOptions = folderOptions.value;
+  Assert.equal(
+    folderOptions.excludeItems,
+    false,
+    "ExcludeItems should not be changed"
+  );
+  Assert.equal(
+    folderOptions.excludeQueries,
+    false,
+    "ExcludeQueries should not be changed"
+  );
+  Assert.equal(
+    folderOptions.expandQueries,
+    true,
+    "ExpandQueries should not be changed"
+  );
+}
diff --git a/toolkit/components/places/tests/queries/test_queryMultipleFolder.js b/toolkit/components/places/tests/queries/test_queryMultipleFolder.js
new file mode 100644
index 0000000000..7c24bef74e
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_queryMultipleFolder.js
@@ -0,0 +1,106 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+var folderGuids = [];
+var bookmarkGuids = [];
+
+add_task(async function setup() {
+  // adding bookmarks in the folders
+  for (let i = 0; i < 3; ++i) {
+    let folder = await PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      title: `Folder${i}`,
+    });
+    folderGuids.push(folder.guid);
+
+    for (let j = 0; j < 7; ++j) {
+      let bm = await PlacesUtils.bookmarks.insert({
+        parentGuid: folderGuids[i],
+        url: `http://Bookmark${i}_${j}.com`,
+        title: "",
+      });
+      bookmarkGuids.push(bm.guid);
+    }
+  }
+});
+
+add_task(async function test_queryMultipleFolders_ids() {
+  // using queryStringToQuery
+  let query = {},
+    options = {};
+  let maxResults = 20;
+  let queryString = `place:${folderGuids
+    .map(guid => "parent=" + guid)
+    .join("&")}&sort=5&maxResults=${maxResults}`;
+  PlacesUtils.history.queryStringToQuery(queryString, query, options);
+  let rootNode = PlacesUtils.history.executeQuery(
+    query.value,
+    options.value
+  ).root;
+  rootNode.containerOpen = true;
+  let resultLength = rootNode.childCount;
+  Assert.equal(resultLength, maxResults);
+  for (let i = 0; i < resultLength; ++i) {
+    let node = rootNode.getChild(i);
+    Assert.equal(bookmarkGuids[i], node.bookmarkGuid, node.uri);
+  }
+  rootNode.containerOpen = false;
+
+  // using getNewQuery and getNewQueryOptions
+  query = PlacesUtils.history.getNewQuery();
+  options = PlacesUtils.history.getNewQueryOptions();
+  query.setParents(folderGuids);
+  options.sortingMode = options.SORT_BY_URI_ASCENDING;
+  options.maxResults = maxResults;
+  rootNode = PlacesUtils.history.executeQuery(query, options).root;
+  rootNode.containerOpen = true;
+  resultLength = rootNode.childCount;
+  Assert.equal(resultLength, maxResults);
+  for (let i = 0; i < resultLength; ++i) {
+    let node = rootNode.getChild(i);
+    Assert.equal(bookmarkGuids[i], node.bookmarkGuid, node.uri);
+  }
+  rootNode.containerOpen = false;
+});
+
+add_task(async function test_queryMultipleFolders_guids() {
+  // using queryStringToQuery
+  let query = {},
+    options = {};
+  let maxResults = 20;
+  let queryString = `place:${folderGuids
+    .map(guid => "parent=" + guid)
+    .join("&")}&sort=5&maxResults=${maxResults}`;
+  PlacesUtils.history.queryStringToQuery(queryString, query, options);
+  let rootNode = PlacesUtils.history.executeQuery(
+    query.value,
+    options.value
+  ).root;
+  rootNode.containerOpen = true;
+  let resultLength = rootNode.childCount;
+  Assert.equal(resultLength, maxResults);
+  for (let i = 0; i < resultLength; ++i) {
+    let node = rootNode.getChild(i);
+    Assert.equal(bookmarkGuids[i], node.bookmarkGuid, node.uri);
+  }
+  rootNode.containerOpen = false;
+
+  // using getNewQuery and getNewQueryOptions
+  query = PlacesUtils.history.getNewQuery();
+  options = PlacesUtils.history.getNewQueryOptions();
+  query.setParents(folderGuids);
+  options.sortingMode = options.SORT_BY_URI_ASCENDING;
+  options.maxResults = maxResults;
+  rootNode = PlacesUtils.history.executeQuery(query, options).root;
+  rootNode.containerOpen = true;
+  resultLength = rootNode.childCount;
+  Assert.equal(resultLength, maxResults);
+  for (let i = 0; i < resultLength; ++i) {
+    let node = rootNode.getChild(i);
+    Assert.equal(bookmarkGuids[i], node.bookmarkGuid, node.uri);
+  }
+  rootNode.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_querySerialization.js b/toolkit/components/places/tests/queries/test_querySerialization.js
new file mode 100644
index 0000000000..4c33854718
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_querySerialization.js
@@ -0,0 +1,718 @@
+/* -*- 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/. */
+
+/**
+ * Tests Places query serialization.  Associated bug is
+ * https://bugzilla.mozilla.org/show_bug.cgi?id=370197
+ *
+ * The simple idea behind this test is to try out different combinations of
+ * query switches and ensure that queries are the same before serialization
+ * as they are after de-serialization.
+ *
+ * In the code below, "switch" refers to a query option -- "option" in a broad
+ * sense, not nsINavHistoryQueryOptions specifically (which is why we refer to
+ * them as switches, not options).  Both nsINavHistoryQuery and
+ * nsINavHistoryQueryOptions allow you to specify switches that affect query
+ * strings.  nsINavHistoryQuery instances have attributes hasBeginTime,
+ * hasEndTime, hasSearchTerms, and so on.  nsINavHistoryQueryOptions instances
+ * have attributes sortingMode, resultType, excludeItems, etc.
+ *
+ * Ideally we would like to test all 2^N subsets of switches, where N is the
+ * total number of switches; switches might interact in erroneous or other ways
+ * we do not expect.  However, since N is large (21 at this time), that's
+ * impractical for a single test in a suite.
+ *
+ * Instead we choose all possible subsets of a certain, smaller size.  In fact
+ * we begin by choosing CHOOSE_HOW_MANY_SWITCHES_LO and ramp up to
+ * CHOOSE_HOW_MANY_SWITCHES_HI.
+ *
+ * There are two more wrinkles.  First, for some switches we'd like to be able to
+ * test multiple values.  For example, it seems like a good idea to test both an
+ * empty string and a non-empty string for switch nsINavHistoryQuery.searchTerms.
+ * When switches have more than one value for a test run, we use the Cartesian
+ * product of their values to generate all possible combinations of values.
+ *
+ * To summarize, here's how this test works:
+ *
+ * - For n = CHOOSE_HOW_MANY_SWITCHES_LO to CHOOSE_HOW_MANY_SWITCHES_HI:
+ *   - From the total set of switches choose all possible subsets of size n.
+ *     For each of those subsets s:
+ *     - Collect the test runs of each switch in subset s and take their
+ *       Cartesian product.  For each sequence in the product:
+ *       - Create nsINavHistoryQuery and nsINavHistoryQueryOptions objects
+ *         with the chosen switches and test run values.
+ *       - Serialize the query.
+ *       - De-serialize and ensure that the de-serialized query objects equal
+ *         the originals.
+ */
+
+const CHOOSE_HOW_MANY_SWITCHES_LO = 1;
+const CHOOSE_HOW_MANY_SWITCHES_HI = 2;
+
+// The switches are represented by objects below, in arrays querySwitches and
+// queryOptionSwitches.  Use them to set up test runs.
+//
+// Some switches have special properties (where noted), but all switches must
+// have the following properties:
+//
+//   matches: A function that takes two nsINavHistoryQuery objects (in the case
+//            of nsINavHistoryQuery switches) or two nsINavHistoryQueryOptions
+//            objects (for nsINavHistoryQueryOptions switches) and returns true
+//            if the values of the switch in the two objects are equal.  This is
+//            the foundation of how we determine if two queries are equal.
+//   runs:    An array of functions.  Each function takes an nsINavHistoryQuery
+//            object and an nsINavHistoryQueryOptions object.  The functions
+//            should set the attributes of one of the two objects as appropriate
+//            to their switches.  This is how switch values are set for each test
+//            run.
+//
+// The following properties are optional:
+//
+//   desc:    An informational string to print out during runs when the switch
+//            is chosen.  Hopefully helpful if the test fails.
+
+// nsINavHistoryQuery switches
+const querySwitches = [
+  // hasBeginTime
+  {
+    // flag and subswitches are used by the flagSwitchMatches function.  Several
+    // of the nsINavHistoryQuery switches (like this one) are really guard flags
+    // that indicate if other "subswitches" are enabled.
+    flag: "hasBeginTime",
+    subswitches: ["beginTime", "beginTimeReference", "absoluteBeginTime"],
+    desc: "nsINavHistoryQuery.hasBeginTime",
+    matches: flagSwitchMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.beginTime = Date.now() * 1000;
+        aQuery.beginTimeReference = Ci.nsINavHistoryQuery.TIME_RELATIVE_EPOCH;
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.beginTime = Date.now() * 1000;
+        aQuery.beginTimeReference = Ci.nsINavHistoryQuery.TIME_RELATIVE_TODAY;
+      },
+    ],
+  },
+  // hasEndTime
+  {
+    flag: "hasEndTime",
+    subswitches: ["endTime", "endTimeReference", "absoluteEndTime"],
+    desc: "nsINavHistoryQuery.hasEndTime",
+    matches: flagSwitchMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.endTime = Date.now() * 1000;
+        aQuery.endTimeReference = Ci.nsINavHistoryQuery.TIME_RELATIVE_EPOCH;
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.endTime = Date.now() * 1000;
+        aQuery.endTimeReference = Ci.nsINavHistoryQuery.TIME_RELATIVE_TODAY;
+      },
+    ],
+  },
+  // hasSearchTerms
+  {
+    flag: "hasSearchTerms",
+    subswitches: ["searchTerms"],
+    desc: "nsINavHistoryQuery.hasSearchTerms",
+    matches: flagSwitchMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.searchTerms = "shrimp and white wine";
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.searchTerms = "";
+      },
+    ],
+  },
+  // hasDomain
+  {
+    flag: "hasDomain",
+    subswitches: ["domain", "domainIsHost"],
+    desc: "nsINavHistoryQuery.hasDomain",
+    matches: flagSwitchMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.domain = "mozilla.com";
+        aQuery.domainIsHost = false;
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.domain = "www.mozilla.com";
+        aQuery.domainIsHost = true;
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.domain = "";
+      },
+    ],
+  },
+  // hasUri
+  {
+    flag: "hasUri",
+    subswitches: ["uri"],
+    desc: "nsINavHistoryQuery.hasUri",
+    matches: flagSwitchMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.uri = uri("http://mozilla.com");
+      },
+    ],
+  },
+  // minVisits
+  {
+    // property is used by function simplePropertyMatches.
+    property: "minVisits",
+    desc: "nsINavHistoryQuery.minVisits",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.minVisits = 0x7fffffff; // 2^31 - 1
+      },
+    ],
+  },
+  // maxVisits
+  {
+    property: "maxVisits",
+    desc: "nsINavHistoryQuery.maxVisits",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.maxVisits = 0x7fffffff; // 2^31 - 1
+      },
+    ],
+  },
+  // getFolders
+  {
+    desc: "nsINavHistoryQuery.getParents",
+    matches(aQuery1, aQuery2) {
+      var q1Parents = aQuery1.getParents();
+      var q2Parents = aQuery2.getParents();
+      if (q1Parents.length !== q2Parents.length) {
+        return false;
+      }
+      for (let i = 0; i < q1Parents.length; i++) {
+        if (!q2Parents.includes(q1Parents[i])) {
+          return false;
+        }
+      }
+      for (let i = 0; i < q2Parents.length; i++) {
+        if (!q1Parents.includes(q2Parents[i])) {
+          return false;
+        }
+      }
+      return true;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.setParents([]);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setParents([PlacesUtils.bookmarks.rootGuid]);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setParents([
+          PlacesUtils.bookmarks.rootGuid,
+          PlacesUtils.bookmarks.tagsGuid,
+        ]);
+      },
+    ],
+  },
+  // tags
+  {
+    desc: "nsINavHistoryQuery.getTags",
+    matches(aQuery1, aQuery2) {
+      if (aQuery1.tagsAreNot !== aQuery2.tagsAreNot) {
+        return false;
+      }
+      var q1Tags = aQuery1.tags;
+      var q2Tags = aQuery2.tags;
+      if (q1Tags.length !== q2Tags.length) {
+        return false;
+      }
+      for (let i = 0; i < q1Tags.length; i++) {
+        if (!q2Tags.includes(q1Tags[i])) {
+          return false;
+        }
+      }
+      for (let i = 0; i < q2Tags.length; i++) {
+        if (!q1Tags.includes(q2Tags[i])) {
+          return false;
+        }
+      }
+      return true;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.tags = [];
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.tags = [""];
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.tags = [
+          "foo",
+          "七難",
+          "",
+          "いっぱいおっぱい",
+          "Abracadabra",
+          "１２３",
+          "Here's a pretty long tag name with some = signs and 1 2 3s and spaces oh jeez will it work I hope so!",
+          "アスキーでございません",
+          "あいうえお",
+        ];
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.tags = [
+          "foo",
+          "七難",
+          "",
+          "いっぱいおっぱい",
+          "Abracadabra",
+          "１２３",
+          "Here's a pretty long tag name with some = signs and 1 2 3s and spaces oh jeez will it work I hope so!",
+          "アスキーでございません",
+          "あいうえお",
+        ];
+        aQuery.tagsAreNot = true;
+      },
+    ],
+  },
+  // transitions
+  {
+    desc: "tests nsINavHistoryQuery.getTransitions",
+    matches(aQuery1, aQuery2) {
+      var q1Trans = aQuery1.getTransitions();
+      var q2Trans = aQuery2.getTransitions();
+      if (q1Trans.length !== q2Trans.length) {
+        return false;
+      }
+      for (let i = 0; i < q1Trans.length; i++) {
+        if (!q2Trans.includes(q1Trans[i])) {
+          return false;
+        }
+      }
+      for (let i = 0; i < q2Trans.length; i++) {
+        if (!q1Trans.includes(q2Trans[i])) {
+          return false;
+        }
+      }
+      return true;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([]);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([Ci.nsINavHistoryService.TRANSITION_DOWNLOAD]);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([
+          Ci.nsINavHistoryService.TRANSITION_TYPED,
+          Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+        ]);
+      },
+    ],
+  },
+];
+
+// nsINavHistoryQueryOptions switches
+const queryOptionSwitches = [
+  // sortingMode
+  {
+    desc: "nsINavHistoryQueryOptions.sortingMode",
+    matches(aOptions1, aOptions2) {
+      if (aOptions1.sortingMode === aOptions2.sortingMode) {
+        return true;
+      }
+      return false;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.sortingMode = aQueryOptions.SORT_BY_DATE_ASCENDING;
+      },
+    ],
+  },
+  // resultType
+  {
+    // property is used by function simplePropertyMatches.
+    property: "resultType",
+    desc: "nsINavHistoryQueryOptions.resultType",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.resultType = aQueryOptions.RESULTS_AS_URI;
+      },
+    ],
+  },
+  // excludeItems
+  {
+    property: "excludeItems",
+    desc: "nsINavHistoryQueryOptions.excludeItems",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.excludeItems = true;
+      },
+    ],
+  },
+  // excludeQueries
+  {
+    property: "excludeQueries",
+    desc: "nsINavHistoryQueryOptions.excludeQueries",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.excludeQueries = true;
+      },
+    ],
+  },
+  // expandQueries
+  {
+    property: "expandQueries",
+    desc: "nsINavHistoryQueryOptions.expandQueries",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.expandQueries = true;
+      },
+    ],
+  },
+  // includeHidden
+  {
+    property: "includeHidden",
+    desc: "nsINavHistoryQueryOptions.includeHidden",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.includeHidden = true;
+      },
+    ],
+  },
+  // maxResults
+  {
+    property: "maxResults",
+    desc: "nsINavHistoryQueryOptions.maxResults",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.maxResults = 0xffffffff; // 2^32 - 1
+      },
+    ],
+  },
+  // queryType
+  {
+    property: "queryType",
+    desc: "nsINavHistoryQueryOptions.queryType",
+    matches: simplePropertyMatches,
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.queryType = aQueryOptions.QUERY_TYPE_HISTORY;
+      },
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.queryType = aQueryOptions.QUERY_TYPE_BOOKMARKS;
+      },
+    ],
+  },
+];
+
+/**
+ * Enumerates all the sequences of the cartesian product of the arrays contained
+ * in aSequences.  Examples:
+ *
+ *   cartProd([[1, 2, 3], ["a", "b"]], callback);
+ *   // callback is called 3 * 2 = 6 times with the following arrays:
+ *   // [1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]
+ *
+ *   cartProd([["a"], [1, 2, 3], ["X", "Y"]], callback);
+ *   // callback is called 1 * 3 * 2 = 6 times with the following arrays:
+ *   // ["a", 1, "X"], ["a", 1, "Y"], ["a", 2, "X"], ["a", 2, "Y"],
+ *   // ["a", 3, "X"], ["a", 3, "Y"]
+ *
+ *   cartProd([[1], [2], [3], [4]], callback);
+ *   // callback is called 1 * 1 * 1 * 1 = 1 time with the following array:
+ *   // [1, 2, 3, 4]
+ *
+ *   cartProd([], callback);
+ *   // callback is 0 times
+ *
+ *   cartProd([[1, 2, 3, 4]], callback);
+ *   // callback is called 4 times with the following arrays:
+ *   // [1], [2], [3], [4]
+ *
+ * @param  aSequences
+ *         an array that contains an arbitrary number of arrays
+ * @param  aCallback
+ *         a function that is passed each sequence of the product as it's
+ *         computed
+ * @return the total number of sequences in the product
+ */
+function cartProd(aSequences, aCallback) {
+  if (aSequences.length === 0) {
+    return 0;
+  }
+
+  // For each sequence in aSequences, we maintain a pointer (an array index,
+  // really) to the element we're currently enumerating in that sequence
+  var seqEltPtrs = aSequences.map(i => 0);
+
+  var numProds = 0;
+  var done = false;
+  while (!done) {
+    numProds++;
+
+    // prod = sequence in product we're currently enumerating
+    let prod = [];
+    for (let i = 0; i < aSequences.length; i++) {
+      prod.push(aSequences[i][seqEltPtrs[i]]);
+    }
+    aCallback(prod);
+
+    // The next sequence in the product differs from the current one by just a
+    // single element.  Determine which element that is.  We advance the
+    // "rightmost" element pointer to the "right" by one.  If we move past the
+    // end of that pointer's sequence, reset the pointer to the first element
+    // in its sequence and then try the sequence to the "left", and so on.
+
+    // seqPtr = index of rightmost input sequence whose element pointer is not
+    // past the end of the sequence
+    let seqPtr = aSequences.length - 1;
+    while (!done) {
+      // Advance the rightmost element pointer.
+      seqEltPtrs[seqPtr]++;
+
+      // The rightmost element pointer is past the end of its sequence.
+      if (seqEltPtrs[seqPtr] >= aSequences[seqPtr].length) {
+        seqEltPtrs[seqPtr] = 0;
+        seqPtr--;
+
+        // All element pointers are past the ends of their sequences.
+        if (seqPtr < 0) {
+          done = true;
+        }
+      } else {
+        break;
+      }
+    }
+  }
+  return numProds;
+}
+
+/**
+ * Enumerates all the subsets in aSet of size aHowMany.  There are
+ * C(aSet.length, aHowMany) such subsets.  aCallback will be passed each subset
+ * as it is generated.  Note that aSet and the subsets enumerated are -- even
+ * though they're arrays -- not sequences; the ordering of their elements is not
+ * important.  Example:
+ *
+ *   choose([1, 2, 3, 4], 2, callback);
+ *   // callback is called C(4, 2) = 6 times with the following sets (arrays):
+ *   // [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
+ *
+ * @param  aSet
+ *         an array from which to choose elements, aSet.length > 0
+ * @param  aHowMany
+ *         the number of elements to choose, > 0 and <= aSet.length
+ * @return the total number of sets chosen
+ */
+function choose(aSet, aHowMany, aCallback) {
+  // ptrs = indices of the elements in aSet we're currently choosing
+  var ptrs = [];
+  for (let i = 0; i < aHowMany; i++) {
+    ptrs.push(i);
+  }
+
+  var numFound = 0;
+  var done = false;
+  while (!done) {
+    numFound++;
+    aCallback(ptrs.map(p => aSet[p]));
+
+    // The next subset to be chosen differs from the current one by just a
+    // single element.  Determine which element that is.  Advance the "rightmost"
+    // pointer to the "right" by one.  If we move past the end of set, move the
+    // next non-adjacent rightmost pointer to the right by one, and reset all
+    // succeeding pointers so that they're adjacent to it.  When all pointers
+    // are clustered all the way to the right, we're done.
+
+    // Advance the rightmost pointer.
+    ptrs[ptrs.length - 1]++;
+
+    // The rightmost pointer has gone past the end of set.
+    if (ptrs[ptrs.length - 1] >= aSet.length) {
+      // Find the next rightmost pointer that is not adjacent to the current one.
+      let si = aSet.length - 2; // aSet index
+      let pi = ptrs.length - 2; // ptrs index
+      while (pi >= 0 && ptrs[pi] === si) {
+        pi--;
+        si--;
+      }
+
+      // All pointers are adjacent and clustered all the way to the right.
+      if (pi < 0) {
+        done = true;
+      } else {
+        // pi = index of rightmost pointer with a gap between it and its
+        // succeeding pointer.  Move it right and reset all succeeding pointers
+        // so that they're adjacent to it.
+        ptrs[pi]++;
+        for (let i = 0; i < ptrs.length - pi - 1; i++) {
+          ptrs[i + pi + 1] = ptrs[pi] + i + 1;
+        }
+      }
+    }
+  }
+  return numFound;
+}
+
+/**
+ * Convenience function for nsINavHistoryQuery switches that act as flags.  This
+ * is attached to switch objects.  See querySwitches array above.
+ *
+ * @param  aQuery1
+ *         an nsINavHistoryQuery object
+ * @param  aQuery2
+ *         another nsINavHistoryQuery object
+ * @return true if this switch is the same in both aQuery1 and aQuery2
+ */
+function flagSwitchMatches(aQuery1, aQuery2) {
+  if (aQuery1[this.flag] && aQuery2[this.flag]) {
+    for (let p in this.subswitches) {
+      if (p in aQuery1 && p in aQuery2) {
+        if (aQuery1[p] instanceof Ci.nsIURI) {
+          if (!aQuery1[p].equals(aQuery2[p])) {
+            return false;
+          }
+        } else if (aQuery1[p] !== aQuery2[p]) {
+          return false;
+        }
+      }
+    }
+  } else if (aQuery1[this.flag] || aQuery2[this.flag]) {
+    return false;
+  }
+
+  return true;
+}
+
+/**
+ * Tests if aObj1 and aObj2 are equal.  This function is general and may be used
+ * for either nsINavHistoryQuery or nsINavHistoryQueryOptions objects.  aSwitches
+ * determines which set of switches is used for comparison.  Pass in either
+ * querySwitches or queryOptionSwitches.
+ *
+ * @param  aSwitches
+ *         determines which set of switches applies to aObj1 and aObj2, either
+ *         querySwitches or queryOptionSwitches
+ * @param  aObj1
+ *         an nsINavHistoryQuery or nsINavHistoryQueryOptions object
+ * @param  aObj2
+ *         another nsINavHistoryQuery or nsINavHistoryQueryOptions object
+ * @return true if aObj1 and aObj2 are equal
+ */
+function queryObjsEqual(aSwitches, aObj1, aObj2) {
+  for (let i = 0; i < aSwitches.length; i++) {
+    if (!aSwitches[i].matches(aObj1, aObj2)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+/**
+ * This drives the test runs.  See the comment at the top of this file.
+ *
+ * @param aHowManyLo
+ *        the size of the switch subsets to start with
+ * @param aHowManyHi
+ *        the size of the switch subsets to end with (inclusive)
+ */
+function runQuerySequences(aHowManyLo, aHowManyHi) {
+  var allSwitches = querySwitches.concat(queryOptionSwitches);
+
+  // Choose aHowManyLo switches up to aHowManyHi switches.
+  for (let howMany = aHowManyLo; howMany <= aHowManyHi; howMany++) {
+    let numIters = 0;
+    print("CHOOSING " + howMany + " SWITCHES");
+
+    // Choose all subsets of size howMany from allSwitches.
+    choose(allSwitches, howMany, function (chosenSwitches) {
+      print(numIters);
+      numIters++;
+
+      // Collect the runs.
+      // runs = [ [runs from switch 1], ..., [runs from switch howMany] ]
+      var runs = chosenSwitches.map(function (s) {
+        if (s.desc) {
+          print("  " + s.desc);
+        }
+        return s.runs;
+      });
+
+      // cartProd(runs) => [
+      //   [switch 1 run 1, switch 2 run 1, ..., switch howMany run 1 ],
+      //   ...,
+      //   [switch 1 run 1, switch 2 run 1, ..., switch howMany run N ],
+      //   ..., ...,
+      //   [switch 1 run N, switch 2 run N, ..., switch howMany run 1 ],
+      //   ...,
+      //   [switch 1 run N, switch 2 run N, ..., switch howMany run N ],
+      // ]
+      cartProd(runs, function (runSet) {
+        // Create a new query, apply the switches in runSet, and test it.
+        var query = PlacesUtils.history.getNewQuery();
+        var opts = PlacesUtils.history.getNewQueryOptions();
+        for (let i = 0; i < runSet.length; i++) {
+          runSet[i](query, opts);
+        }
+        serializeDeserialize(query, opts);
+      });
+    });
+  }
+  print("\n");
+}
+
+/**
+ * Serializes the nsINavHistoryQuery objects in aQuery and the
+ * nsINavHistoryQueryOptions object aQueryOptions, de-serializes the
+ * serialization, and ensures (using do_check_* functions) that the
+ * de-serialized objects equal the originals.
+ *
+ * @param aQuery
+ *        an nsINavHistoryQuery object
+ * @param aQueryOptions
+ *        an nsINavHistoryQueryOptions object
+ */
+function serializeDeserialize(aQuery, aQueryOptions) {
+  let queryStr = PlacesUtils.history.queryToQueryString(aQuery, aQueryOptions);
+  print("  " + queryStr);
+  let query2 = {},
+    opts2 = {};
+  PlacesUtils.history.queryStringToQuery(queryStr, query2, opts2);
+  query2 = query2.value;
+  opts2 = opts2.value;
+
+  Assert.ok(queryObjsEqual(querySwitches, aQuery, query2));
+
+  // Finally check the query options objects.
+  Assert.ok(queryObjsEqual(queryOptionSwitches, aQueryOptions, opts2));
+}
+
+/**
+ * Convenience function for switches that have simple values.  This is attached
+ * to switch objects.  See querySwitches and queryOptionSwitches arrays above.
+ *
+ * @param  aObj1
+ *         an nsINavHistoryQuery or nsINavHistoryQueryOptions object
+ * @param  aObj2
+ *         another nsINavHistoryQuery or nsINavHistoryQueryOptions object
+ * @return true if this switch is the same in both aObj1 and aObj2
+ */
+function simplePropertyMatches(aObj1, aObj2) {
+  return aObj1[this.property] === aObj2[this.property];
+}
+
+function run_test() {
+  runQuerySequences(CHOOSE_HOW_MANY_SWITCHES_LO, CHOOSE_HOW_MANY_SWITCHES_HI);
+}
diff --git a/toolkit/components/places/tests/queries/test_query_uri_liveupdate.js b/toolkit/components/places/tests/queries/test_query_uri_liveupdate.js
new file mode 100644
index 0000000000..5ada4a84d4
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_query_uri_liveupdate.js
@@ -0,0 +1,45 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function test_results_as_tag_query() {
+  let bms = await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.unfiledGuid,
+    children: [
+      { url: "http://tag1.moz.com/", tags: ["tag1"] },
+      { url: "http://tag2.moz.com/", tags: ["tag2"] },
+      { url: "place:tag=tag1" },
+    ],
+  });
+
+  let root = PlacesUtils.getFolderContents(
+    PlacesUtils.bookmarks.unfiledGuid,
+    false,
+    true
+  ).root;
+  Assert.equal(root.childCount, 3, "We should get 3 results");
+  let queryRoot = root.getChild(2);
+  PlacesUtils.asContainer(queryRoot).containerOpen = true;
+
+  Assert.equal(queryRoot.uri, "place:tag=tag1", "Found the query");
+  Assert.equal(queryRoot.childCount, 1, "We should get 1 result");
+  Assert.equal(
+    queryRoot.getChild(0).uri,
+    "http://tag1.moz.com/",
+    "Found the tagged bookmark"
+  );
+
+  await PlacesUtils.bookmarks.update({
+    guid: bms[2].guid,
+    url: "place:tag=tag2",
+  });
+  Assert.equal(queryRoot.uri, "place:tag=tag2", "Found the query");
+  Assert.equal(queryRoot.childCount, 1, "We should get 1 result");
+  Assert.equal(
+    queryRoot.getChild(0).uri,
+    "http://tag2.moz.com/",
+    "Found the tagged bookmark"
+  );
+
+  queryRoot.containerOpen = false;
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_redirects.js b/toolkit/components/places/tests/queries/test_redirects.js
new file mode 100644
index 0000000000..b0e7c9b421
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_redirects.js
@@ -0,0 +1,351 @@
+/* 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/. */
+
+// Array of visits we will add to the database, will be populated later
+// in the test.
+var visits = [];
+
+/**
+ * Takes a sequence of query options, and compare query results obtained through
+ * them with a custom filtered array of visits, based on the values we are
+ * expecting from the query.
+ *
+ * @param  aSequence
+ *         an array that contains query options in the form:
+ *         [includeHidden, maxResults, sortingMode]
+ */
+function check_results_callback(aSequence) {
+  // Sanity check: we should receive 3 parameters.
+  Assert.equal(aSequence.length, 3);
+  let includeHidden = aSequence[0];
+  let maxResults = aSequence[1];
+  let sortingMode = aSequence[2];
+  info(" - - - ");
+  info(
+    "TESTING: includeHidden(" +
+      includeHidden +
+      ")," +
+      " maxResults(" +
+      maxResults +
+      ")," +
+      " sortingMode(" +
+      sortingMode +
+      ")."
+  );
+
+  function isHidden(aVisit) {
+    return (
+      aVisit.transType == Ci.nsINavHistoryService.TRANSITION_FRAMED_LINK ||
+      aVisit.isRedirect
+    );
+  }
+
+  // Build expectedData array.
+  let expectedData = visits.filter(function (aVisit, aIndex, aArray) {
+    // Embed visits never appear in results.
+    if (aVisit.transType == Ci.nsINavHistoryService.TRANSITION_EMBED) {
+      return false;
+    }
+
+    if (!includeHidden && isHidden(aVisit)) {
+      // If the page has any non-hidden visit, then it's visible.
+      if (
+        !visits.filter(function (refVisit) {
+          return refVisit.uri == aVisit.uri && !isHidden(refVisit);
+        }).length
+      ) {
+        return false;
+      }
+    }
+
+    return true;
+  });
+
+  // Remove duplicates, since queries are RESULTS_AS_URI (unique pages).
+  let seen = [];
+  expectedData = expectedData.filter(function (aData) {
+    if (seen.includes(aData.uri)) {
+      return false;
+    }
+    seen.push(aData.uri);
+    return true;
+  });
+
+  // Sort expectedData.
+  function getFirstIndexFor(aEntry) {
+    for (let i = 0; i < visits.length; i++) {
+      if (visits[i].uri == aEntry.uri) {
+        return i;
+      }
+    }
+    return undefined;
+  }
+  function comparator(a, b) {
+    if (sortingMode == Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING) {
+      return b.lastVisit - a.lastVisit;
+    }
+    if (
+      sortingMode == Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING
+    ) {
+      return b.visitCount - a.visitCount;
+    }
+    return getFirstIndexFor(a) - getFirstIndexFor(b);
+  }
+  expectedData.sort(comparator);
+
+  // Crop results to maxResults if it's defined.
+  if (maxResults) {
+    expectedData = expectedData.slice(0, maxResults);
+  }
+
+  // Create a new query with required options.
+  let query = PlacesUtils.history.getNewQuery();
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.includeHidden = includeHidden;
+  options.sortingMode = sortingMode;
+  if (maxResults) {
+    options.maxResults = maxResults;
+  }
+
+  // Compare resultset with expectedData.
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let root = result.root;
+  root.containerOpen = true;
+  compareArrayToResult(expectedData, root);
+  root.containerOpen = false;
+}
+
+/**
+ * Enumerates all the sequences of the cartesian product of the arrays contained
+ * in aSequences.  Examples:
+ *
+ *   cartProd([[1, 2, 3], ["a", "b"]], callback);
+ *   // callback is called 3 * 2 = 6 times with the following arrays:
+ *   // [1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]
+ *
+ *   cartProd([["a"], [1, 2, 3], ["X", "Y"]], callback);
+ *   // callback is called 1 * 3 * 2 = 6 times with the following arrays:
+ *   // ["a", 1, "X"], ["a", 1, "Y"], ["a", 2, "X"], ["a", 2, "Y"],
+ *   // ["a", 3, "X"], ["a", 3, "Y"]
+ *
+ *   cartProd([[1], [2], [3], [4]], callback);
+ *   // callback is called 1 * 1 * 1 * 1 = 1 time with the following array:
+ *   // [1, 2, 3, 4]
+ *
+ *   cartProd([], callback);
+ *   // callback is 0 times
+ *
+ *   cartProd([[1, 2, 3, 4]], callback);
+ *   // callback is called 4 times with the following arrays:
+ *   // [1], [2], [3], [4]
+ *
+ * @param  aSequences
+ *         an array that contains an arbitrary number of arrays
+ * @param  aCallback
+ *         a function that is passed each sequence of the product as it's
+ *         computed
+ * @return the total number of sequences in the product
+ */
+function cartProd(aSequences, aCallback) {
+  if (aSequences.length === 0) {
+    return 0;
+  }
+
+  // For each sequence in aSequences, we maintain a pointer (an array index,
+  // really) to the element we're currently enumerating in that sequence
+  let seqEltPtrs = aSequences.map(i => 0);
+
+  let numProds = 0;
+  let done = false;
+  while (!done) {
+    numProds++;
+
+    // prod = sequence in product we're currently enumerating
+    let prod = [];
+    for (let i = 0; i < aSequences.length; i++) {
+      prod.push(aSequences[i][seqEltPtrs[i]]);
+    }
+    aCallback(prod);
+
+    // The next sequence in the product differs from the current one by just a
+    // single element.  Determine which element that is.  We advance the
+    // "rightmost" element pointer to the "right" by one.  If we move past the
+    // end of that pointer's sequence, reset the pointer to the first element
+    // in its sequence and then try the sequence to the "left", and so on.
+
+    // seqPtr = index of rightmost input sequence whose element pointer is not
+    // past the end of the sequence
+    let seqPtr = aSequences.length - 1;
+    while (!done) {
+      // Advance the rightmost element pointer.
+      seqEltPtrs[seqPtr]++;
+
+      // The rightmost element pointer is past the end of its sequence.
+      if (seqEltPtrs[seqPtr] >= aSequences[seqPtr].length) {
+        seqEltPtrs[seqPtr] = 0;
+        seqPtr--;
+
+        // All element pointers are past the ends of their sequences.
+        if (seqPtr < 0) {
+          done = true;
+        }
+      } else {
+        break;
+      }
+    }
+  }
+  return numProds;
+}
+
+/**
+ * Populate the visits array and add visits to the database.
+ * We will generate visit-chains like:
+ *   visit -> redirect_temp -> redirect_perm
+ */
+add_task(async function test_add_visits_to_database() {
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  // We don't really bother on this, but we need a time to add visits.
+  let timeInMicroseconds = Date.now() * 1000;
+  let visitCount = 1;
+
+  // Array of all possible transition types we could be redirected from.
+  let t = [
+    Ci.nsINavHistoryService.TRANSITION_LINK,
+    Ci.nsINavHistoryService.TRANSITION_TYPED,
+    Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+    // Embed visits are not added to the database and we don't want redirects
+    // to them, thus just avoid addition.
+    // Ci.nsINavHistoryService.TRANSITION_EMBED,
+    Ci.nsINavHistoryService.TRANSITION_FRAMED_LINK,
+    // Would make hard sorting by visit date because last_visit_date is actually
+    // calculated excluding download transitions, but the query includes
+    // downloads.
+    // Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  ];
+
+  function newTimeInMicroseconds() {
+    timeInMicroseconds = timeInMicroseconds - 1000;
+    return timeInMicroseconds;
+  }
+
+  // we add a visit for each of the above transition types.
+  t.forEach(transition =>
+    visits.push({
+      isVisit: true,
+      transType: transition,
+      uri: "http://" + transition + ".example.com/",
+      title: transition + "-example",
+      isRedirect: true,
+      lastVisit: newTimeInMicroseconds(),
+      visitCount:
+        transition == Ci.nsINavHistoryService.TRANSITION_EMBED ||
+        transition == Ci.nsINavHistoryService.TRANSITION_FRAMED_LINK
+          ? 0
+          : visitCount++,
+      isInQuery: true,
+    })
+  );
+
+  // Add a REDIRECT_TEMPORARY layer of visits for each of the above visits.
+  t.forEach(transition =>
+    visits.push({
+      isVisit: true,
+      transType: Ci.nsINavHistoryService.TRANSITION_REDIRECT_TEMPORARY,
+      uri: "http://" + transition + ".redirect.temp.example.com/",
+      title: transition + "-redirect-temp-example",
+      lastVisit: newTimeInMicroseconds(),
+      isRedirect: true,
+      referrer: "http://" + transition + ".example.com/",
+      visitCount: visitCount++,
+      isInQuery: true,
+    })
+  );
+
+  // Add a REDIRECT_PERMANENT layer of visits for each of the above redirects.
+  t.forEach(transition =>
+    visits.push({
+      isVisit: true,
+      transType: Ci.nsINavHistoryService.TRANSITION_REDIRECT_PERMANENT,
+      uri: "http://" + transition + ".redirect.perm.example.com/",
+      title: transition + "-redirect-perm-example",
+      lastVisit: newTimeInMicroseconds(),
+      isRedirect: true,
+      referrer: "http://" + transition + ".redirect.temp.example.com/",
+      visitCount: visitCount++,
+      isInQuery: true,
+    })
+  );
+
+  // Add a REDIRECT_PERMANENT layer of visits that loop to the first visit.
+  // These entries should not change visitCount or lastVisit, otherwise
+  // guessing an order would be a nightmare.
+  function getLastValue(aURI, aProperty) {
+    for (let i = 0; i < visits.length; i++) {
+      if (visits[i].uri == aURI) {
+        return visits[i][aProperty];
+      }
+    }
+    do_throw("Unknown uri.");
+    return null;
+  }
+  t.forEach(transition =>
+    visits.push({
+      isVisit: true,
+      transType: Ci.nsINavHistoryService.TRANSITION_REDIRECT_PERMANENT,
+      uri: "http://" + transition + ".example.com/",
+      title: getLastValue("http://" + transition + ".example.com/", "title"),
+      lastVisit: getLastValue(
+        "http://" + transition + ".example.com/",
+        "lastVisit"
+      ),
+      isRedirect: true,
+      referrer: "http://" + transition + ".redirect.perm.example.com/",
+      visitCount: getLastValue(
+        "http://" + transition + ".example.com/",
+        "visitCount"
+      ),
+      isInQuery: true,
+    })
+  );
+
+  // Add an unvisited bookmark in the database, it should never appear.
+  visits.push({
+    isBookmark: true,
+    uri: "http://unvisited.bookmark.com/",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    title: "Unvisited Bookmark",
+    isInQuery: false,
+  });
+
+  // Put visits in the database.
+  await task_populateDB(visits);
+});
+
+add_task(async function test_redirects() {
+  // Frecency and hidden are updated asynchronously, wait for them.
+  await PlacesTestUtils.promiseAsyncUpdates();
+
+  // This array will be used by cartProd to generate a matrix of all possible
+  // combinations.
+  let includeHidden_options = [true, false];
+  let maxResults_options = [5, 10, 20, null];
+  // These sortingMode are choosen to toggle using special queries for history
+  // menu.
+  let sorting_options = [
+    Ci.nsINavHistoryQueryOptions.SORT_BY_NONE,
+    Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING,
+    Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING,
+  ];
+  // Will execute check_results_callback() for each generated combination.
+  cartProd(
+    [includeHidden_options, maxResults_options, sorting_options],
+    check_results_callback
+  );
+
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  await PlacesUtils.history.clear();
+});
diff --git a/toolkit/components/places/tests/queries/test_result_observeHistoryDetails.js b/toolkit/components/places/tests/queries/test_result_observeHistoryDetails.js
new file mode 100644
index 0000000000..83531ee2c4
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_result_observeHistoryDetails.js
@@ -0,0 +1,155 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that skipHistoryDetailsNotifications works as expected.
+
+function accumulateNotifications(
+  result,
+  skipHistoryDetailsNotifications = false
+) {
+  let notifications = [];
+  let resultObserver = new Proxy(NavHistoryResultObserver, {
+    get(target, name) {
+      if (name == "check") {
+        result.removeObserver(resultObserver, false);
+        return expectedNotifications =>
+          Assert.deepEqual(notifications, expectedNotifications);
+      }
+      if (name == "skipHistoryDetailsNotifications") {
+        return skipHistoryDetailsNotifications;
+      }
+      // ignore a few uninteresting notifications.
+      if (["QueryInterface", "containerStateChanged"].includes(name)) {
+        return () => {};
+      }
+      return () => {
+        notifications.push(name);
+      };
+    },
+  });
+  result.addObserver(resultObserver, false);
+  return resultObserver;
+}
+
+add_task(async function test_history_query_observe() {
+  let query = PlacesUtils.history.getNewQuery();
+  let options = PlacesUtils.history.getNewQueryOptions();
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let notifications = accumulateNotifications(result);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla.org",
+    title: "test",
+  });
+  notifications.check([
+    "nodeHistoryDetailsChanged",
+    "nodeInserted",
+    "nodeTitleChanged",
+  ]);
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function test_history_query_no_observe() {
+  let query = PlacesUtils.history.getNewQuery();
+  let options = PlacesUtils.history.getNewQueryOptions();
+  let result = PlacesUtils.history.executeQuery(query, options);
+  // Even if we opt-out of notifications, this is an history query, thus the
+  // setting is pretty much ignored.
+  let notifications = accumulateNotifications(result, true);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla.org",
+    title: "test",
+  });
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla2.org",
+    title: "test",
+  });
+
+  notifications.check([
+    "nodeHistoryDetailsChanged",
+    "nodeInserted",
+    "nodeTitleChanged",
+    "nodeHistoryDetailsChanged",
+    "nodeInserted",
+    "nodeTitleChanged",
+  ]);
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+});
+
+add_task(async function test_bookmarks_query_observe() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_BOOKMARKS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let notifications = accumulateNotifications(result);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+
+  await PlacesUtils.bookmarks.insert({
+    url: "http://mozilla.org",
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    title: "test",
+  });
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla.org",
+    title: "title",
+  });
+
+  notifications.check([
+    "nodeHistoryDetailsChanged",
+    "nodeInserted",
+    "nodeHistoryDetailsChanged",
+  ]);
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+  await PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(async function test_bookmarks_query_no_observe() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_BOOKMARKS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let notifications = accumulateNotifications(result, true);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+
+  await PlacesUtils.bookmarks.insert({
+    url: "http://mozilla.org",
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    title: "test",
+  });
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla.org",
+    title: "title",
+  });
+
+  notifications.check(["nodeInserted"]);
+
+  info("Change the sorting mode to one that is based on history");
+  notifications = accumulateNotifications(result, true);
+  result.sortingMode = options.SORT_BY_VISITCOUNT_DESCENDING;
+  notifications.check(["invalidateContainer"]);
+
+  notifications = accumulateNotifications(result, true);
+  await PlacesTestUtils.addVisits({
+    uri: "http://mozilla.org",
+    title: "title",
+  });
+  notifications.check(["nodeHistoryDetailsChanged"]);
+
+  root.containerOpen = false;
+  await PlacesUtils.bookmarks.eraseEverything();
+});
diff --git a/toolkit/components/places/tests/queries/test_results-as-left-pane.js b/toolkit/components/places/tests/queries/test_results-as-left-pane.js
new file mode 100644
index 0000000000..6cec733758
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-left-pane.js
@@ -0,0 +1,83 @@
+"use strict";
+
+const expectedRoots = [
+  {
+    title: "OrganizerQueryHistory",
+    uri: `place:sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING}&type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY}`,
+    guid: "history____v",
+  },
+  {
+    title: "OrganizerQueryDownloads",
+    uri: `place:transition=${Ci.nsINavHistoryService.TRANSITION_DOWNLOAD}&sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING}`,
+    guid: "downloads__v",
+  },
+  {
+    title: "TagsFolderTitle",
+    uri: `place:sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING}&type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT}`,
+    guid: "tags_______v",
+  },
+  {
+    title: "OrganizerQueryAllBookmarks",
+    uri: `place:type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_ROOTS_QUERY}`,
+    guid: "allbms_____v",
+  },
+];
+
+const placesStrings = Services.strings.createBundle(
+  "chrome://places/locale/places.properties"
+);
+
+function getLeftPaneQuery() {
+  var query = PlacesUtils.history.getNewQuery();
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.resultType = options.RESULTS_AS_LEFT_PANE_QUERY;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  return result.root;
+}
+
+function assertExpectedChildren(root, expectedChildren) {
+  Assert.equal(
+    root.childCount,
+    expectedChildren.length,
+    "Should have the expected number of children."
+  );
+
+  for (let i = 0; i < root.childCount; i++) {
+    Assert.ok(
+      PlacesTestUtils.ComparePlacesURIs(
+        root.getChild(i).uri,
+        expectedChildren[i].uri
+      ),
+      "Should have the correct uri for root ${i}"
+    );
+    Assert.equal(
+      root.getChild(i).title,
+      placesStrings.GetStringFromName(expectedChildren[i].title),
+      "Should have the correct title for root ${i}"
+    );
+    Assert.equal(root.getChild(i).bookmarkGuid, expectedChildren[i].guid);
+  }
+}
+
+/**
+ * This test will test the basic RESULTS_AS_ROOTS_QUERY, that simply returns,
+ * the existing bookmark roots.
+ */
+add_task(async function test_results_as_root() {
+  let root = getLeftPaneQuery();
+  root.containerOpen = true;
+
+  Assert.equal(
+    PlacesUtils.asQuery(root).queryOptions.queryType,
+    Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS,
+    "Should have a query type of QUERY_TYPE_BOOKMARKS"
+  );
+
+  assertExpectedChildren(root, expectedRoots);
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_results-as-roots.js b/toolkit/components/places/tests/queries/test_results-as-roots.js
new file mode 100644
index 0000000000..2f082d3e0b
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-roots.js
@@ -0,0 +1,114 @@
+"use strict";
+
+const MOBILE_BOOKMARKS_PREF = "browser.bookmarks.showMobileBookmarks";
+
+const expectedRoots = [
+  {
+    title: "BookmarksToolbarFolderTitle",
+    uri: `place:parent=${PlacesUtils.bookmarks.toolbarGuid}`,
+    guid: PlacesUtils.bookmarks.virtualToolbarGuid,
+  },
+  {
+    title: "BookmarksMenuFolderTitle",
+    uri: `place:parent=${PlacesUtils.bookmarks.menuGuid}`,
+    guid: PlacesUtils.bookmarks.virtualMenuGuid,
+  },
+  {
+    title: "OtherBookmarksFolderTitle",
+    uri: `place:parent=${PlacesUtils.bookmarks.unfiledGuid}`,
+    guid: PlacesUtils.bookmarks.virtualUnfiledGuid,
+  },
+];
+
+const expectedRootsWithMobile = [
+  ...expectedRoots,
+  {
+    title: "MobileBookmarksFolderTitle",
+    uri: `place:parent=${PlacesUtils.bookmarks.mobileGuid}`,
+    guid: PlacesUtils.bookmarks.virtualMobileGuid,
+  },
+];
+
+const placesStrings = Services.strings.createBundle(
+  "chrome://places/locale/places.properties"
+);
+
+function getAllBookmarksQuery() {
+  var query = PlacesUtils.history.getNewQuery();
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_VISITCOUNT_ASCENDING;
+  options.resultType = options.RESULTS_AS_ROOTS_QUERY;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  return result.root;
+}
+
+function assertExpectedChildren(root, expectedChildren) {
+  Assert.equal(
+    root.childCount,
+    expectedChildren.length,
+    "Should have the expected number of children."
+  );
+
+  for (let i = 0; i < root.childCount; i++) {
+    Assert.equal(
+      root.getChild(i).uri,
+      expectedChildren[i].uri,
+      "Should have the correct uri for root ${i}"
+    );
+    Assert.equal(
+      root.getChild(i).title,
+      placesStrings.GetStringFromName(expectedChildren[i].title),
+      "Should have the correct title for root ${i}"
+    );
+    Assert.equal(root.getChild(i).bookmarkGuid, expectedChildren[i].guid);
+  }
+}
+
+/**
+ * This test will test the basic RESULTS_AS_ROOTS_QUERY, that simply returns,
+ * the existing bookmark roots.
+ */
+add_task(async function test_results_as_root() {
+  let root = getAllBookmarksQuery();
+  root.containerOpen = true;
+
+  Assert.equal(
+    PlacesUtils.asQuery(root).queryOptions.queryType,
+    Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS,
+    "Should have a query type of QUERY_TYPE_BOOKMARKS"
+  );
+
+  assertExpectedChildren(root, expectedRoots);
+
+  root.containerOpen = false;
+});
+
+add_task(async function test_results_as_root_with_mobile() {
+  Services.prefs.setBoolPref(MOBILE_BOOKMARKS_PREF, true);
+
+  let root = getAllBookmarksQuery();
+  root.containerOpen = true;
+
+  assertExpectedChildren(root, expectedRootsWithMobile);
+
+  root.containerOpen = false;
+  Services.prefs.clearUserPref(MOBILE_BOOKMARKS_PREF);
+});
+
+add_task(async function test_results_as_root_remove_mobile_dynamic() {
+  Services.prefs.setBoolPref(MOBILE_BOOKMARKS_PREF, true);
+
+  let root = getAllBookmarksQuery();
+  root.containerOpen = true;
+
+  // Now un-set the pref, and poke the database to update the query.
+  Services.prefs.clearUserPref(MOBILE_BOOKMARKS_PREF);
+
+  assertExpectedChildren(root, expectedRoots);
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_results-as-tag-query.js b/toolkit/components/places/tests/queries/test_results-as-tag-query.js
new file mode 100644
index 0000000000..0d4670b658
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-tag-query.js
@@ -0,0 +1,63 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+const testData = {
+  "http://foo.com/": ["tag1", "tag 2", "Space ☺️ Between"].sort(),
+  "http://bar.com/": ["tag1", "tag 2"].sort(),
+  "http://baz.com/": ["tag 2", "Space ☺️ Between"].sort(),
+  "http://qux.com/": ["Space ☺️ Between"],
+};
+
+const formattedTestData = [];
+for (const [uri, tagArray] of Object.entries(testData)) {
+  formattedTestData.push({
+    title: `Title of ${uri}`,
+    uri,
+    isBookmark: true,
+    isTag: true,
+    tagArray,
+  });
+}
+
+add_task(async function test_results_as_tags_root() {
+  await task_populateDB(formattedTestData);
+
+  // Construct URL - tag mapping from tag query.
+  const actualData = {};
+  for (const uri in testData) {
+    if (testData.hasOwnProperty(uri)) {
+      actualData[uri] = [];
+    }
+  }
+
+  const options = PlacesUtils.history.getNewQueryOptions();
+  options.resultType = options.RESULTS_AS_TAGS_ROOT;
+  const query = PlacesUtils.history.getNewQuery();
+  const root = PlacesUtils.history.executeQuery(query, options).root;
+
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 3, "We should get as many results as tags.");
+  displayResultSet(root);
+
+  for (let i = 0; i < root.childCount; ++i) {
+    const node = root.getChild(i);
+    const tagName = node.title;
+    Assert.equal(
+      node.type,
+      node.RESULT_TYPE_QUERY,
+      "Result type should be RESULT_TYPE_QUERY."
+    );
+    const subRoot = node.QueryInterface(Ci.nsINavHistoryContainerResultNode);
+    subRoot.containerOpen = true;
+    for (let j = 0; j < subRoot.childCount; ++j) {
+      actualData[subRoot.getChild(j).uri].push(tagName);
+      actualData[subRoot.getChild(j).uri].sort();
+    }
+  }
+
+  Assert.deepEqual(
+    actualData,
+    testData,
+    "URI-tag mapping should be same from query and initial data."
+  );
+});
diff --git a/toolkit/components/places/tests/queries/test_results-as-visit.js b/toolkit/components/places/tests/queries/test_results-as-visit.js
new file mode 100644
index 0000000000..256e756c98
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-visit.js
@@ -0,0 +1,158 @@
+/* -*- 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/. */
+var testData = [];
+var timeInMicroseconds = PlacesUtils.toPRTime(Date.now() - 10000);
+
+function newTimeInMicroseconds() {
+  timeInMicroseconds = timeInMicroseconds + 1000;
+  return timeInMicroseconds;
+}
+
+function createTestData() {
+  function generateVisits(aPage) {
+    for (var i = 0; i < aPage.visitCount; i++) {
+      testData.push({
+        isInQuery: aPage.inQuery,
+        isVisit: true,
+        title: aPage.title,
+        uri: aPage.uri,
+        lastVisit: newTimeInMicroseconds(),
+        isTag: aPage.tags && !!aPage.tags.length,
+        tagArray: aPage.tags,
+      });
+    }
+  }
+
+  var pages = [
+    {
+      uri: "http://foo.com/",
+      title: "amo",
+      tags: ["moz"],
+      visitCount: 3,
+      inQuery: false,
+    },
+    {
+      uri: "http://moilla.com/",
+      title: "bMoz",
+      tags: ["bugzilla"],
+      visitCount: 5,
+      inQuery: true,
+    },
+    {
+      uri: "http://foo.mail.com/changeme1.html",
+      title: "c Moz",
+      visitCount: 7,
+      inQuery: true,
+    },
+    {
+      uri: "http://foo.mail.com/changeme2.html",
+      tags: ["moz"],
+      title: "",
+      visitCount: 1,
+      inQuery: false,
+    },
+    {
+      uri: "http://foo.mail.com/changeme3.html",
+      title: "zydeco",
+      visitCount: 5,
+      inQuery: false,
+    },
+  ];
+  pages.forEach(generateVisits);
+}
+
+/**
+ * This test will test Queries that use relative search terms and URI options
+ */
+add_task(async function test_results_as_visit() {
+  createTestData();
+  await task_populateDB(testData);
+  var query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "moz";
+  query.minVisits = 2;
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_VISITCOUNT_ASCENDING;
+  options.resultType = options.RESULTS_AS_VISIT;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  info("Number of items in result set: " + root.childCount);
+  for (let i = 0; i < root.childCount; ++i) {
+    info(
+      "result: " + root.getChild(i).uri + " Title: " + root.getChild(i).title
+    );
+  }
+
+  // Check our inital result set
+  compareArrayToResult(testData, root);
+
+  // If that passes, check liveupdate
+  // Add to the query set
+  info("Adding item to query");
+  var tmp = [];
+  for (let i = 0; i < 2; i++) {
+    tmp.push({
+      isVisit: true,
+      uri: "http://foo.com/added.html",
+      title: "ab moz",
+    });
+  }
+  await task_populateDB(tmp);
+  for (let i = 0; i < 2; i++) {
+    Assert.equal(root.getChild(i).title, "ab moz");
+  }
+
+  // Update an existing URI
+  info("Updating Item");
+  var change2 = [
+    { isVisit: true, title: "moz", uri: "http://foo.mail.com/changeme2.html" },
+  ];
+  await task_populateDB(change2);
+  Assert.ok(nodeInResult(change2, root));
+
+  // Update some visits - add one and take one out of query set, and simply
+  // change one so that it still applies to the query.
+  info("Updating More Items");
+  var change3 = [
+    {
+      isVisit: true,
+      lastVisit: newTimeInMicroseconds(),
+      uri: "http://foo.mail.com/changeme1.html",
+      title: "foo",
+    },
+    {
+      isVisit: true,
+      lastVisit: newTimeInMicroseconds(),
+      uri: "http://foo.mail.com/changeme3.html",
+      title: "moz",
+      isTag: true,
+      tagArray: ["foo", "moz"],
+    },
+  ];
+  await task_populateDB(change3);
+  Assert.ok(!nodeInResult({ uri: "http://foo.mail.com/changeme1.html" }, root));
+  Assert.ok(nodeInResult({ uri: "http://foo.mail.com/changeme3.html" }, root));
+
+  // And now, delete one
+  info("Delete item outside of batch");
+  var change4 = [
+    {
+      isVisit: true,
+      lastVisit: newTimeInMicroseconds(),
+      uri: "http://moilla.com/",
+      title: "mo,z",
+    },
+  ];
+  await task_populateDB(change4);
+  Assert.ok(!nodeInResult(change4, root));
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js b/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js
new file mode 100644
index 0000000000..224feb4f0c
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js
@@ -0,0 +1,74 @@
+/* -*- 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/. */
+
+// Tests the interaction of includeHidden and searchTerms search options.
+
+var timeInMicroseconds = Date.now() * 1000;
+
+const VISITS = [
+  {
+    isVisit: true,
+    transType: TRANSITION_TYPED,
+    uri: "http://redirect.example.com/",
+    title: "example",
+    isRedirect: true,
+    lastVisit: timeInMicroseconds--,
+  },
+  {
+    isVisit: true,
+    transType: TRANSITION_TYPED,
+    uri: "http://target.example.com/",
+    title: "example",
+    lastVisit: timeInMicroseconds--,
+  },
+];
+
+const HIDDEN_VISITS = [
+  {
+    isVisit: true,
+    transType: TRANSITION_FRAMED_LINK,
+    uri: "http://hidden.example.com/",
+    title: "red",
+    lastVisit: timeInMicroseconds--,
+  },
+];
+
+const TEST_DATA = [
+  { searchTerms: "example", includeHidden: true, expectedResults: 2 },
+  { searchTerms: "example", includeHidden: false, expectedResults: 1 },
+  { searchTerms: "red", includeHidden: true, expectedResults: 1 },
+];
+
+add_task(async function test_initalize() {
+  await task_populateDB(VISITS);
+});
+
+add_task(async function test_searchTerms_includeHidden() {
+  for (let data of TEST_DATA) {
+    let query = PlacesUtils.history.getNewQuery();
+    query.searchTerms = data.searchTerms;
+    let options = PlacesUtils.history.getNewQueryOptions();
+    options.includeHidden = data.includeHidden;
+
+    let root = PlacesUtils.history.executeQuery(query, options).root;
+    root.containerOpen = true;
+
+    let cc = root.childCount;
+    // Live update with hidden visits.
+    await task_populateDB(HIDDEN_VISITS);
+    let cc_update = root.childCount;
+
+    root.containerOpen = false;
+
+    Assert.equal(cc, data.expectedResults);
+    Assert.equal(
+      cc_update,
+      data.expectedResults + (data.includeHidden ? 1 : 0)
+    );
+
+    await PlacesUtils.history.remove("http://hidden.example.com/");
+  }
+});
diff --git a/toolkit/components/places/tests/queries/test_searchTerms_time.js b/toolkit/components/places/tests/queries/test_searchTerms_time.js
new file mode 100644
index 0000000000..39fd1353eb
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchTerms_time.js
@@ -0,0 +1,109 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that visitis are correctly live-updated in a history
+// query filtered on searchterms and time.
+
+const USEC_PER_DAY = 86400000000;
+const now = PlacesUtils.toPRTime(new Date());
+
+add_task(async function pages_query() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.beginTime = now - 15 * USEC_PER_DAY;
+  query.endTime = now - 5 * USEC_PER_DAY;
+  query.beginTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.endTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.searchTerms = "mo";
+
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_URI_ASCENDING;
+  options.resultType = options.RESULTS_AS_URI;
+  await testQuery(query, options);
+
+  options.sortingMode = options.SORT_BY_DATE_ASCENDING;
+  options.resultType = options.RESULTS_AS_VISITS;
+  await testQuery(query, options);
+});
+
+async function testQuery(query, options) {
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  Assert.equal(root.childCount, 0, "There should be zero results initially");
+
+  await PlacesTestUtils.addVisits([
+    // SearchTerms matching URL but out of the timeframe.
+    {
+      url: "https://test.moz.org",
+      title: "abc",
+      visitDate: now - 2 * USEC_PER_DAY,
+    },
+    // In the timeframe but no searchTerms match.
+    {
+      url: "https://test.def.org",
+      title: "def",
+      visitDate: now - 10 * USEC_PER_DAY,
+    },
+    // In the timeframe, matching title.
+    {
+      url: "https://test.ghi.org",
+      title: "amo",
+      visitDate: now - 10 * USEC_PER_DAY,
+    },
+  ]);
+
+  Assert.equal(root.childCount, 1, "Check matching results");
+  let node = root.getChild(0);
+  Assert.equal(node.title, "amo");
+
+  // Change title so it's no longer matching.
+  await PlacesTestUtils.addVisits({
+    url: "https://test.ghi.org",
+    title: "ghi",
+    visitDate: now - 10 * USEC_PER_DAY,
+  });
+
+  Assert.equal(root.childCount, 0, "Check matching results");
+
+  // Add visit in the timeframe.
+  await PlacesTestUtils.addVisits({
+    url: "https://test.moz.org",
+    title: "abc",
+    visitDate: now - 10 * USEC_PER_DAY,
+  });
+
+  Assert.equal(root.childCount, 1, "Check matching results");
+  node = root.getChild(0);
+  Assert.equal(node.title, "abc");
+
+  // Remove visit in the timeframe.
+  await PlacesUtils.history.removeVisitsByFilter({
+    beginDate: PlacesUtils.toDate(now - 15 * USEC_PER_DAY),
+    endDate: PlacesUtils.toDate(now - 5 * USEC_PER_DAY),
+  });
+  await PlacesTestUtils.dumpTable({
+    table: "moz_places",
+    columns: ["id", "url"],
+  });
+  await PlacesTestUtils.dumpTable({
+    table: "moz_historyvisits",
+    columns: ["place_id", "visit_date"],
+  });
+
+  Assert.equal(root.childCount, 0, "Check matching results");
+
+  // Add matching visit out of the timeframe.
+  await PlacesTestUtils.addVisits(
+    // SearchTerms matching URL but out of the timeframe.
+    {
+      url: "https://test.mozilla.org",
+      title: "mozilla",
+      visitDate: now - 2 * USEC_PER_DAY,
+    }
+  );
+
+  Assert.equal(root.childCount, 0, "Check matching results");
+
+  root.containerOpen = false;
+  await PlacesUtils.history.clear();
+}
diff --git a/toolkit/components/places/tests/queries/test_search_tags.js b/toolkit/components/places/tests/queries/test_search_tags.js
new file mode 100644
index 0000000000..4f8cface07
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_search_tags.js
@@ -0,0 +1,73 @@
+/* -*- 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/. */
+
+add_task(async function test_search_for_tagged_bookmarks() {
+  const testURI = "http://a1.com";
+
+  let folder = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    title: "bug 395101 test",
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+  });
+
+  let bookmark = await PlacesUtils.bookmarks.insert({
+    parentGuid: folder.guid,
+    title: "1 title",
+    url: testURI,
+  });
+
+  // tag the bookmarked URI
+  PlacesUtils.tagging.tagURI(uri(testURI), [
+    "elephant",
+    "walrus",
+    "giraffe",
+    "turkey",
+    "hiPPo",
+    "BABOON",
+    "alf",
+  ]);
+
+  // search for the bookmark, using a tag
+  var query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "elephant";
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS;
+  query.setParents([folder.guid]);
+
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var rootNode = result.root;
+  rootNode.containerOpen = true;
+
+  Assert.equal(rootNode.childCount, 1);
+  Assert.equal(rootNode.getChild(0).bookmarkGuid, bookmark.guid);
+  rootNode.containerOpen = false;
+
+  // partial matches are okay
+  query.searchTerms = "wal";
+  result = PlacesUtils.history.executeQuery(query, options);
+  rootNode = result.root;
+  rootNode.containerOpen = true;
+  Assert.equal(rootNode.childCount, 1);
+  rootNode.containerOpen = false;
+
+  // case insensitive search term
+  query.searchTerms = "WALRUS";
+  result = PlacesUtils.history.executeQuery(query, options);
+  rootNode = result.root;
+  rootNode.containerOpen = true;
+  Assert.equal(rootNode.childCount, 1);
+  Assert.equal(rootNode.getChild(0).bookmarkGuid, bookmark.guid);
+  rootNode.containerOpen = false;
+
+  // case insensitive tag
+  query.searchTerms = "baboon";
+  result = PlacesUtils.history.executeQuery(query, options);
+  rootNode = result.root;
+  rootNode.containerOpen = true;
+  Assert.equal(rootNode.childCount, 1);
+  Assert.equal(rootNode.getChild(0).bookmarkGuid, bookmark.guid);
+  rootNode.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_searchterms-bookmarklets.js b/toolkit/components/places/tests/queries/test_searchterms-bookmarklets.js
new file mode 100644
index 0000000000..8eebf68cad
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-bookmarklets.js
@@ -0,0 +1,63 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Check that bookmarklets are returned by searches with searchTerms.
+
+var testData = [
+  {
+    isInQuery: true,
+    isBookmark: true,
+    title: "bookmark 1",
+    uri: "http://mozilla.org/script/",
+  },
+
+  {
+    isInQuery: true,
+    isBookmark: true,
+    title: "bookmark 2",
+    uri: "javascript:alert('moz');",
+  },
+];
+
+add_task(async function test_initalize() {
+  await task_populateDB(testData);
+});
+
+add_test(function test_search_by_title() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "bookmark";
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_BOOKMARKS;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  compareArrayToResult(testData, root);
+  root.containerOpen = false;
+
+  run_next_test();
+});
+
+add_test(function test_search_by_schemeToken() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "script";
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_BOOKMARKS;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  compareArrayToResult(testData, root);
+  root.containerOpen = false;
+
+  run_next_test();
+});
+
+add_test(function test_search_by_uriAndTitle() {
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "moz";
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_BOOKMARKS;
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  compareArrayToResult(testData, root);
+  root.containerOpen = false;
+
+  run_next_test();
+});
diff --git a/toolkit/components/places/tests/queries/test_searchterms-domain.js b/toolkit/components/places/tests/queries/test_searchterms-domain.js
new file mode 100644
index 0000000000..45a0a7d542
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-domain.js
@@ -0,0 +1,197 @@
+/* -*- 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/. */
+
+// The test data for our database, note that the ordering of the results that
+// will be returned by the query (the isInQuery: true objects) is IMPORTANT.
+// see compareArrayToResult in head_queries.js for more info.
+var testData = [
+  // Test ftp protocol - vary the title length, embed search term
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    uri: "ftp://foo.com/ftp",
+    lastVisit: lastweek,
+    title: "hugelongconfmozlagurationofwordswithasearchtermsinit whoo-hoo",
+  },
+
+  // Test flat domain with annotation, search term in sentence
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    isPageAnnotation: true,
+    uri: "http://foo.com/",
+    annoName: "moz/test",
+    annoVal: "val",
+    lastVisit: lastweek,
+    title: "you know, moz is cool",
+  },
+
+  // Test subdomain included with isRedirect=true, different transtype
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    title: "amozzie",
+    isRedirect: true,
+    uri: "http://mail.foo.com/redirect",
+    lastVisit: old,
+    referrer: "http://myreferrer.com",
+    transType: PlacesUtils.history.TRANSITION_LINK,
+  },
+
+  // Test subdomain inclued, search term at end
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    uri: "http://mail.foo.com/yiihah",
+    title: "blahmoz",
+    lastVisit: daybefore,
+  },
+
+  // Test www. style URI is included, with a tag
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    isTag: true,
+    uri: "http://www.foo.com/yiihah",
+    tagArray: ["moz"],
+    lastVisit: yesterday,
+    title: "foo",
+  },
+
+  // Test https protocol
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    title: "moz",
+    uri: "https://foo.com/",
+    lastVisit: today,
+  },
+
+  // Begin the invalid queries: wrong search term
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m o z",
+    uri: "http://foo.com/tooearly.php",
+    lastVisit: today,
+  },
+
+  // Test bad URI
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "moz",
+    uri: "http://sffoo.com/justwrong.htm",
+    lastVisit: yesterday,
+  },
+
+  // Test what we do with escaping in titles
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m%0o%0z",
+    uri: "http://foo.com/changeme1.htm",
+    lastVisit: yesterday,
+  },
+
+  // Test another invalid title - for updating later
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m,oz",
+    uri: "http://foo.com/changeme2.htm",
+    lastVisit: yesterday,
+  },
+];
+
+/**
+ * This test will test Queries that use relative search terms and domain options
+ */
+add_task(async function test_searchterms_domain() {
+  await task_populateDB(testData);
+  var query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "moz";
+  query.domain = "foo.com";
+  query.domainIsHost = false;
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_DATE_ASCENDING;
+  options.resultType = options.RESULTS_AS_URI;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  info("Number of items in result set: " + root.childCount);
+  for (var i = 0; i < root.childCount; ++i) {
+    info(
+      "result: " + root.getChild(i).uri + " Title: " + root.getChild(i).title
+    );
+  }
+
+  // Check our inital result set
+  compareArrayToResult(testData, root);
+
+  // If that passes, check liveupdate
+  // Add to the query set
+  info("Adding item to query");
+  var change1 = [
+    {
+      isVisit: true,
+      isDetails: true,
+      uri: "http://foo.com/added.htm",
+      title: "moz",
+      transType: PlacesUtils.history.TRANSITION_LINK,
+    },
+  ];
+  await task_populateDB(change1);
+  Assert.ok(nodeInResult(change1, root));
+
+  // Update an existing URI
+  info("Updating Item");
+  var change2 = [
+    { isDetails: true, uri: "http://foo.com/changeme1.htm", title: "moz" },
+  ];
+  await task_populateDB(change2);
+  Assert.ok(nodeInResult(change2, root));
+
+  // Add one and take one out of query set, and simply change one so that it
+  // still applies to the query.
+  info("Updating More Items");
+  var change3 = [
+    { isDetails: true, uri: "http://foo.com/changeme2.htm", title: "moz" },
+    {
+      isDetails: true,
+      uri: "http://mail.foo.com/yiihah",
+      title: "moz now updated",
+    },
+    { isDetails: true, uri: "ftp://foo.com/ftp", title: "gone" },
+  ];
+  await task_populateDB(change3);
+  Assert.ok(nodeInResult({ uri: "http://foo.com/changeme2.htm" }, root));
+  Assert.ok(nodeInResult({ uri: "http://mail.foo.com/yiihah" }, root));
+  Assert.ok(!nodeInResult({ uri: "ftp://foo.com/ftp" }, root));
+
+  // And now, delete one
+  info("Deleting items");
+  var change4 = [{ isDetails: true, uri: "https://foo.com/", title: "mo,z" }];
+  await task_populateDB(change4);
+  Assert.ok(!nodeInResult(change4, root));
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_searchterms-uri.js b/toolkit/components/places/tests/queries/test_searchterms-uri.js
new file mode 100644
index 0000000000..27b9a28c71
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-uri.js
@@ -0,0 +1,125 @@
+/* -*- 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/. */
+
+// The test data for our database, note that the ordering of the results that
+// will be returned by the query (the isInQuery: true objects) is IMPORTANT.
+// see compareArrayToResult in head_queries.js for more info.
+var testData = [
+  // Test flat domain with annotation, search term in sentence
+  {
+    isInQuery: true,
+    isVisit: true,
+    isDetails: true,
+    isPageAnnotation: true,
+    uri: "http://foo.com/",
+    annoName: "moz/test",
+    annoVal: "val",
+    lastVisit: lastweek,
+    title: "you know, moz is cool",
+  },
+
+  // Test https protocol
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "moz",
+    uri: "https://foo.com/",
+    lastVisit: today,
+  },
+
+  // Begin the invalid queries: wrong search term
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m o z",
+    uri: "http://foo.com/wrongsearch.php",
+    lastVisit: today,
+  },
+
+  // Test subdomain inclued, search term at end
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    uri: "http://mail.foo.com/yiihah",
+    title: "blahmoz",
+    lastVisit: daybefore,
+  },
+
+  // Test ftp protocol - vary the title length, embed search term
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    uri: "ftp://foo.com/ftp",
+    lastVisit: lastweek,
+    title: "hugelongconfmozlagurationofwordswithasearchtermsinit whoo-hoo",
+  },
+
+  // Test what we do with escaping in titles
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m%0o%0z",
+    uri: "http://foo.com/changeme1.htm",
+    lastVisit: yesterday,
+  },
+
+  // Test another invalid title - for updating later
+  {
+    isInQuery: false,
+    isVisit: true,
+    isDetails: true,
+    title: "m,oz",
+    uri: "http://foo.com/changeme2.htm",
+    lastVisit: yesterday,
+  },
+];
+
+/**
+ * This test will test Queries that use relative search terms and URI options
+ */
+add_task(async function test_searchterms_uri() {
+  await task_populateDB(testData);
+  var query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = "moz";
+  query.uri = uri("http://foo.com");
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_DATE_ASCENDING;
+  options.resultType = options.RESULTS_AS_URI;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  info("Number of items in result set: " + root.childCount);
+  for (var i = 0; i < root.childCount; ++i) {
+    info(
+      "result: " + root.getChild(i).uri + " Title: " + root.getChild(i).title
+    );
+  }
+
+  // Check our inital result set
+  compareArrayToResult(testData, root);
+
+  // live update.
+  info("change title");
+  var change1 = [{ isDetails: true, uri: "http://foo.com/", title: "mo" }];
+  await task_populateDB(change1);
+
+  Assert.ok(!nodeInResult({ uri: "http://foo.com/" }, root));
+  var change2 = [{ isDetails: true, uri: "http://foo.com/", title: "moz" }];
+  await task_populateDB(change2);
+  Assert.ok(nodeInResult({ uri: "http://foo.com/" }, root));
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_sort-date-site-grouping.js b/toolkit/components/places/tests/queries/test_sort-date-site-grouping.js
new file mode 100644
index 0000000000..358ab45fdb
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_sort-date-site-grouping.js
@@ -0,0 +1,223 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* ***** BEGIN LICENSE BLOCK *****
+  Any copyright is dedicated to the Public Domain.
+  http://creativecommons.org/publicdomain/zero/1.0/
+ * ***** END LICENSE BLOCK ***** */
+
+// This test ensures that the date and site type of |place:| query maintains
+// its quantifications correctly. Namely, it ensures that the date part of the
+// query is not lost when the domain queries are made.
+
+// We specifically craft these entries so that if a by Date and Site sorting is
+// applied, we find one domain in the today range, and two domains in the older
+// than six months range.
+// The correspondence between item in |testData| and date range is stored in
+// leveledTestData.
+var testData = [
+  {
+    isVisit: true,
+    uri: "file:///directory/1",
+    lastVisit: today,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/1",
+    lastVisit: today,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/2",
+    lastVisit: today,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "file:///directory/2",
+    lastVisit: olderthansixmonths,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/3",
+    lastVisit: olderthansixmonths,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/4",
+    lastVisit: olderthansixmonths,
+    title: "test visit",
+    isInQuery: true,
+  },
+  {
+    isVisit: true,
+    uri: "http://example.net/1",
+    lastVisit: olderthansixmonths + 1000,
+    title: "test visit",
+    isInQuery: true,
+  },
+];
+var leveledTestData = [
+  // Today
+  [
+    [0], // Today, local files
+    [1, 2],
+  ], // Today, example.com
+  // Older than six months
+  [
+    [3], // Older than six months, local files
+    [4, 5], // Older than six months, example.com
+    [6], // Older than six months, example.net
+  ],
+];
+
+// This test data is meant for live updating. The |levels| property indicates
+// date range index and then domain index.
+var testDataAddedLater = [
+  {
+    isVisit: true,
+    uri: "http://example.com/5",
+    lastVisit: olderthansixmonths,
+    title: "test visit",
+    isInQuery: true,
+    levels: [1, 1],
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/6",
+    lastVisit: olderthansixmonths,
+    title: "test visit",
+    isInQuery: true,
+    levels: [1, 1],
+  },
+  {
+    isVisit: true,
+    uri: "http://example.com/7",
+    lastVisit: today,
+    title: "test visit",
+    isInQuery: true,
+    levels: [0, 1],
+  },
+  {
+    isVisit: true,
+    uri: "file:///directory/3",
+    lastVisit: today,
+    title: "test visit",
+    isInQuery: true,
+    levels: [0, 0],
+  },
+];
+
+add_task(async function test_sort_date_site_grouping() {
+  await task_populateDB(testData);
+
+  // On Linux, the (local files) folder is shown after sites unlike Mac/Windows.
+  // Thus, we avoid running this test on Linux but this should be re-enabled
+  // after bug 624024 is resolved.
+  let isLinux = "@mozilla.org/gnome-gconf-service;1" in Cc;
+  if (isLinux) {
+    return;
+  }
+
+  // In this test, there are three levels of results:
+  // 1st: Date queries. e.g., today, last week, or older than 6 months.
+  // 2nd: Domain queries restricted to a date. e.g. mozilla.com today.
+  // 3rd: Actual visits. e.g. mozilla.com/index.html today.
+  //
+  // We store all the third level result roots so that we can easily close all
+  // containers and test live updating into specific results.
+  let roots = [];
+
+  let query = PlacesUtils.history.getNewQuery();
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY;
+
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  // This corresponds to the number of date ranges.
+  Assert.equal(root.childCount, leveledTestData.length);
+
+  // We pass off to |checkFirstLevel| to check the first level of results.
+  for (let index = 0; index < leveledTestData.length; index++) {
+    let node = root.getChild(index);
+    checkFirstLevel(index, node, roots);
+  }
+
+  // Test live updating.
+  for (let visit of testDataAddedLater) {
+    await task_populateDB([visit]);
+    let oldLength = testData.length;
+    let i = visit.levels[0];
+    let j = visit.levels[1];
+    testData.push(visit);
+    leveledTestData[i][j].push(oldLength);
+    compareArrayToResult(
+      leveledTestData[i][j].map(x => testData[x]),
+      roots[i][j]
+    );
+  }
+
+  for (let i = 0; i < roots.length; i++) {
+    for (let j = 0; j < roots[i].length; j++) {
+      roots[i][j].containerOpen = false;
+    }
+  }
+
+  root.containerOpen = false;
+});
+
+function checkFirstLevel(index, node, roots) {
+  PlacesUtils.asContainer(node).containerOpen = true;
+
+  Assert.ok(PlacesUtils.nodeIsDay(node));
+  PlacesUtils.asQuery(node);
+  let query = node.query;
+  let options = node.queryOptions;
+
+  Assert.ok(query.hasBeginTime && query.hasEndTime);
+
+  // Here we check the second level of results.
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  roots.push([]);
+  root.containerOpen = true;
+
+  Assert.equal(root.childCount, leveledTestData[index].length);
+  for (var secondIndex = 0; secondIndex < root.childCount; secondIndex++) {
+    let child = PlacesUtils.asQuery(root.getChild(secondIndex));
+    checkSecondLevel(index, secondIndex, child, roots);
+  }
+  root.containerOpen = false;
+  node.containerOpen = false;
+}
+
+function checkSecondLevel(index, secondIndex, child, roots) {
+  let query = child.query;
+  let options = child.queryOptions;
+
+  Assert.ok(query.hasDomain);
+  Assert.ok(query.hasBeginTime && query.hasEndTime);
+
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  // We should now have that roots[index][secondIndex] is set to the second
+  // level's results root.
+  roots[index].push(root);
+
+  // We pass off to compareArrayToResult to check the third level of
+  // results.
+  root.containerOpen = true;
+  compareArrayToResult(
+    leveledTestData[index][secondIndex].map(x => testData[x]),
+    root
+  );
+  // We close |root|'s container later so that we can test live
+  // updates into it.
+}
diff --git a/toolkit/components/places/tests/queries/test_sorting.js b/toolkit/components/places/tests/queries/test_sorting.js
new file mode 100644
index 0000000000..41059c0823
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_sorting.js
@@ -0,0 +1,961 @@
+/* -*- 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/. */
+
+var tests = [];
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_NONE,
+
+  async setup() {
+    info("Sorting test 1: SORT BY NONE");
+
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://example.com/b",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "y",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "z",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "x",
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = this._unsortedData;
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    // no reverse sorting for SORT BY NONE
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING,
+
+  async setup() {
+    info("Sorting test 2: SORT BY TITLE");
+
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://example.com/b1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "y",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "z",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "x",
+        isInQuery: true,
+      },
+
+      // if titles are equal, should fall back to URI
+      {
+        isBookmark: true,
+        uri: "http://example.com/b2",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "y",
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[2],
+      this._unsortedData[0],
+      this._unsortedData[3],
+      this._unsortedData[1],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING,
+
+  async setup() {
+    info("Sorting test 3: SORT BY DATE");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      {
+        isVisit: true,
+        isDetails: true,
+        isBookmark: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 0,
+        uri: "http://example.com/c1",
+        lastVisit: timeInMicroseconds - 2000,
+        title: "x1",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        isBookmark: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 1,
+        uri: "http://example.com/a",
+        lastVisit: timeInMicroseconds - 1000,
+        title: "z",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        isBookmark: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 2,
+        uri: "http://example.com/b",
+        lastVisit: timeInMicroseconds - 3000,
+        title: "y",
+        isInQuery: true,
+      },
+
+      // if dates are equal, should fall back to title
+      {
+        isVisit: true,
+        isDetails: true,
+        isBookmark: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 3,
+        uri: "http://example.com/c2",
+        lastVisit: timeInMicroseconds - 2000,
+        title: "x2",
+        isInQuery: true,
+      },
+
+      // if dates and title are equal, should fall back to bookmark index
+      {
+        isVisit: true,
+        isDetails: true,
+        isBookmark: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 4,
+        uri: "http://example.com/c2",
+        lastVisit: timeInMicroseconds - 2000,
+        title: "x2",
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[2],
+      this._unsortedData[0],
+      this._unsortedData[3],
+      this._unsortedData[4],
+      this._unsortedData[1],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_URI_ASCENDING,
+
+  async setup() {
+    info("Sorting test 4: SORT BY URI");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds,
+        uri: "http://example.com/b",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 0,
+        title: "y",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 1,
+        title: "x",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 2,
+        title: "z",
+        isInQuery: true,
+      },
+
+      // if URIs are equal, should fall back to date
+      {
+        isBookmark: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds + 1000,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 3,
+        title: "x",
+        isInQuery: true,
+      },
+
+      // if no URI (e.g., node is a folder), should fall back to title
+      {
+        isFolder: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 4,
+        title: "y",
+        isInQuery: true,
+      },
+
+      // if URIs and dates are equal, should fall back to bookmark index
+      {
+        isBookmark: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds + 1000,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 5,
+        title: "x",
+        isInQuery: true,
+      },
+
+      // if no URI and titles are equal, should fall back to bookmark index
+      {
+        isFolder: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 6,
+        title: "y",
+        isInQuery: true,
+      },
+
+      // if no URI and titles are equal, should fall back to title
+      {
+        isFolder: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 7,
+        title: "z",
+        isInQuery: true,
+      },
+
+      // Separator should go after folders.
+      {
+        isSeparator: true,
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 8,
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[4],
+      this._unsortedData[6],
+      this._unsortedData[7],
+      this._unsortedData[8],
+      this._unsortedData[2],
+      this._unsortedData[0],
+      this._unsortedData[1],
+      this._unsortedData[3],
+      this._unsortedData[5],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_URI_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_ASCENDING,
+
+  async setup() {
+    info("Sorting test 5: SORT BY VISITCOUNT");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        lastVisit: timeInMicroseconds,
+        title: "z",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 0,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        lastVisit: timeInMicroseconds,
+        title: "x",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 1,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/b1",
+        lastVisit: timeInMicroseconds,
+        title: "y1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 2,
+        isInQuery: true,
+      },
+
+      // if visitCounts are equal, should fall back to date
+      {
+        isBookmark: true,
+        uri: "http://example.com/b2",
+        lastVisit: timeInMicroseconds + 1000,
+        title: "y2a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 3,
+        isInQuery: true,
+      },
+
+      // if visitCounts and dates are equal, should fall back to bookmark index
+      {
+        isBookmark: true,
+        uri: "http://example.com/b2",
+        lastVisit: timeInMicroseconds + 1000,
+        title: "y2b",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 4,
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[0],
+      this._unsortedData[2],
+      this._unsortedData[3],
+      this._unsortedData[4],
+      this._unsortedData[1],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+    // add visits to increase visit count
+    await PlacesTestUtils.addVisits([
+      {
+        uri: uri("http://example.com/a"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+      {
+        uri: uri("http://example.com/b1"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+      {
+        uri: uri("http://example.com/b1"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+      {
+        uri: uri("http://example.com/b2"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds + 1000,
+      },
+      {
+        uri: uri("http://example.com/b2"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds + 1000,
+      },
+      {
+        uri: uri("http://example.com/c"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+      {
+        uri: uri("http://example.com/c"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+      {
+        uri: uri("http://example.com/c"),
+        transition: TRANSITION_TYPED,
+        visitDate: timeInMicroseconds,
+      },
+    ]);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode =
+      Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING,
+
+  async setup() {
+    info("Sorting test 7: SORT BY DATEADDED");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://example.com/b1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 0,
+        title: "y1",
+        dateAdded: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 1,
+        title: "z",
+        dateAdded: timeInMicroseconds - 2000,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 2,
+        title: "x",
+        dateAdded: timeInMicroseconds,
+        isInQuery: true,
+      },
+
+      // if dateAddeds are equal, should fall back to title
+      {
+        isBookmark: true,
+        uri: "http://example.com/b2",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 3,
+        title: "y2",
+        dateAdded: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+
+      // if dateAddeds and titles are equal, should fall back to bookmark index
+      {
+        isBookmark: true,
+        uri: "http://example.com/b3",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 4,
+        title: "y3",
+        dateAdded: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[3],
+      this._unsortedData[4],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode =
+      Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_LASTMODIFIED_ASCENDING,
+
+  async setup() {
+    info("Sorting test 8: SORT BY LASTMODIFIED");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    var timeAddedInMicroseconds = timeInMicroseconds - 10000;
+
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://example.com/b1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 0,
+        title: "y1",
+        dateAdded: timeAddedInMicroseconds,
+        lastModified: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 1,
+        title: "z",
+        dateAdded: timeAddedInMicroseconds,
+        lastModified: timeInMicroseconds - 2000,
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 2,
+        title: "x",
+        dateAdded: timeAddedInMicroseconds,
+        lastModified: timeInMicroseconds,
+        isInQuery: true,
+      },
+
+      // if lastModifieds are equal, should fall back to title
+      {
+        isBookmark: true,
+        uri: "http://example.com/b2",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 3,
+        title: "y2",
+        dateAdded: timeAddedInMicroseconds,
+        lastModified: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+
+      // if lastModifieds and titles are equal, should fall back to bookmark
+      // index
+      {
+        isBookmark: true,
+        uri: "http://example.com/b3",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: 4,
+        title: "y3",
+        dateAdded: timeAddedInMicroseconds,
+        lastModified: timeInMicroseconds - 1000,
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[3],
+      this._unsortedData[4],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode =
+      Ci.nsINavHistoryQueryOptions.SORT_BY_LASTMODIFIED_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_TAGS_ASCENDING,
+
+  async setup() {
+    info("Sorting test 9: SORT BY TAGS");
+
+    this._unsortedData = [
+      {
+        isBookmark: true,
+        uri: "http://url2.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title x",
+        isTag: true,
+        tagArray: ["x", "y", "z"],
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://url1a.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title y1",
+        isTag: true,
+        tagArray: ["a", "b"],
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://url3a.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title w1",
+        isInQuery: true,
+      },
+
+      {
+        isBookmark: true,
+        uri: "http://url0.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title z",
+        isTag: true,
+        tagArray: ["a", "y", "z"],
+        isInQuery: true,
+      },
+
+      // if tags are equal, should fall back to title
+      {
+        isBookmark: true,
+        uri: "http://url1b.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title y2",
+        isTag: true,
+        tagArray: ["b", "a"],
+        isInQuery: true,
+      },
+
+      // if tags are equal, should fall back to title
+      {
+        isBookmark: true,
+        uri: "http://url3b.com/",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "title w2",
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[2],
+      this._unsortedData[5],
+      this._unsortedData[1],
+      this._unsortedData[4],
+      this._unsortedData[3],
+      this._unsortedData[0],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setParents([PlacesUtils.bookmarks.toolbarGuid]);
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    // Results - this gets the result set and opens it for reading and modification.
+    var result = PlacesUtils.history.executeQuery(query, options);
+    var root = result.root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_TAGS_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+// SORT_BY_FRECENCY_*
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_FRECENCY_ASCENDING,
+
+  async setup() {
+    info("Sorting test 13: SORT BY FRECENCY ");
+
+    let timeInMicroseconds = PlacesUtils.toPRTime(Date.now() - 10000);
+
+    function newTimeInMicroseconds() {
+      timeInMicroseconds = timeInMicroseconds + 1000;
+      return timeInMicroseconds;
+    }
+
+    this._unsortedData = [
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "I",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "I",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "I",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://is.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "love",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://best.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "moz",
+        isInQuery: true,
+      },
+
+      {
+        isVisit: true,
+        isDetails: true,
+        uri: "http://best.com/",
+        lastVisit: newTimeInMicroseconds(),
+        title: "moz",
+        isInQuery: true,
+      },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[3],
+      this._unsortedData[5],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    await task_populateDB(this._unsortedData);
+  },
+
+  check() {
+    var query = PlacesUtils.history.getNewQuery();
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingMode = this._sortingMode;
+
+    var root = PlacesUtils.history.executeQuery(query, options).root;
+    root.containerOpen = true;
+    compareArrayToResult(this._sortedData, root);
+    root.containerOpen = false;
+  },
+
+  check_reverse() {
+    this._sortingMode =
+      Ci.nsINavHistoryQueryOptions.SORT_BY_FRECENCY_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  },
+});
+
+add_task(async function test_sorting() {
+  for (let test of tests) {
+    await test.setup();
+    await PlacesTestUtils.promiseAsyncUpdates();
+    test.check();
+    // sorting reversed, usually SORT_BY have ASC and DESC
+    test.check_reverse();
+    // Execute cleanup tasks
+    await PlacesUtils.bookmarks.eraseEverything();
+    await PlacesUtils.history.clear();
+  }
+});
diff --git a/toolkit/components/places/tests/queries/test_tags.js b/toolkit/components/places/tests/queries/test_tags.js
new file mode 100644
index 0000000000..17ad3478ce
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_tags.js
@@ -0,0 +1,626 @@
+/* -*- 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/. */
+
+/**
+ * Tests bookmark queries with tags.  See bug 399799.
+ */
+
+"use strict";
+
+add_task(async function tags_getter_setter() {
+  info("Tags getter/setter should work correctly");
+  info("Without setting tags, tags getter should return empty array");
+  var [query] = makeQuery();
+  Assert.equal(query.tags.length, 0);
+
+  info("Setting tags to an empty array, tags getter should return empty array");
+  [query] = makeQuery([]);
+  Assert.equal(query.tags.length, 0);
+
+  info("Setting a few tags, tags getter should return correct array");
+  var tags = ["bar", "baz", "foo"];
+  [query] = makeQuery(tags);
+  setsAreEqual(query.tags, tags, true);
+
+  info("Setting some dupe tags, tags getter return unique tags");
+  [query] = makeQuery(["foo", "foo", "bar", "foo", "baz", "bar"]);
+  setsAreEqual(query.tags, ["bar", "baz", "foo"], true);
+});
+
+add_task(async function invalid_setter_calls() {
+  info("Invalid calls to tags setter should fail");
+  try {
+    var query = PlacesUtils.history.getNewQuery();
+    query.tags = null;
+    do_throw("Passing null to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    query = PlacesUtils.history.getNewQuery();
+    query.tags = "this should not work";
+    do_throw("Passing a string to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery([null]);
+    do_throw("Passing one-element array with null to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery([undefined]);
+    do_throw("Passing one-element array with undefined to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery(["foo", null, "bar"]);
+    do_throw("Passing mixture of tags and null to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery(["foo", undefined, "bar"]);
+    do_throw("Passing mixture of tags and undefined to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery([1, 2, 3]);
+    do_throw("Passing numbers to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery(["foo", 1, 2, 3]);
+    do_throw("Passing mixture of tags and numbers to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    var str = PlacesUtils.toISupportsString("foo");
+    query = PlacesUtils.history.getNewQuery();
+    query.tags = str;
+    do_throw("Passing nsISupportsString to SetTags should fail");
+  } catch (exc) {}
+
+  try {
+    makeQuery([str]);
+    do_throw("Passing array of nsISupportsStrings to SetTags should fail");
+  } catch (exc) {}
+});
+
+add_task(async function not_setting_tags() {
+  info("Not setting tags at all should not affect query URI");
+  checkQueryURI();
+});
+
+add_task(async function empty_array_tags() {
+  info("Setting tags with an empty array should not affect query URI");
+  checkQueryURI([]);
+});
+
+add_task(async function set_tags() {
+  info("Setting some tags should result in correct query URI");
+  checkQueryURI([
+    "foo",
+    "七難",
+    "",
+    "いっぱいおっぱい",
+    "Abracadabra",
+    "１２３",
+    "Here's a pretty long tag name with some = signs and 1 2 3s and spaces oh jeez will it work I hope so!",
+    "アスキーでございません",
+    "あいうえお",
+  ]);
+});
+
+add_task(async function no_tags_tagsAreNot() {
+  info(
+    "Not setting tags at all but setting tagsAreNot should " +
+      "affect query URI"
+  );
+  checkQueryURI(null, true);
+});
+
+add_task(async function empty_array_tags_tagsAreNot() {
+  info(
+    "Setting tags with an empty array and setting tagsAreNot " +
+      "should affect query URI"
+  );
+  checkQueryURI([], true);
+});
+
+add_task(async function () {
+  info(
+    "Setting some tags and setting tagsAreNot should result in " +
+      "correct query URI"
+  );
+  checkQueryURI(
+    [
+      "foo",
+      "七難",
+      "",
+      "いっぱいおっぱい",
+      "Abracadabra",
+      "１２３",
+      "Here's a pretty long tag name with some = signs and 1 2 3s and spaces oh jeez will it work I hope so!",
+      "アスキーでございません",
+      "あいうえお",
+    ],
+    true
+  );
+});
+
+add_task(async function tag() {
+  info("Querying on tag associated with a URI should return that URI");
+  await task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["bar"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["baz"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(async function many_tags() {
+  info("Querying on many tags associated with a URI should return that URI");
+  await task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "bar"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "baz"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["bar", "baz"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "bar", "baz"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(async function repeated_tag() {
+  info("Specifying the same tag multiple times should not matter");
+  await task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "foo"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "foo", "foo", "bar", "bar", "baz"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(async function many_tags_no_bookmark() {
+  info(
+    "Querying on many tags associated with a URI and tags not associated " +
+      "with that URI should not return that URI"
+  );
+  await task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "bogus"]);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["foo", "bar", "bogus"]);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["foo", "bar", "baz", "bogus"]);
+    executeAndCheckQueryResults(query, opts, []);
+  });
+});
+
+add_task(async function nonexistent_tags() {
+  info("Querying on nonexistent tag should return no results");
+  await task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["bogus"]);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["bogus", "gnarly"]);
+    executeAndCheckQueryResults(query, opts, []);
+  });
+});
+
+add_task(async function tagsAreNot() {
+  info("Querying bookmarks using tagsAreNot should work correctly");
+  var urisAndTags = {
+    "http://example.com/1": ["foo", "bar"],
+    "http://example.com/2": ["baz", "qux"],
+    "http://example.com/3": null,
+  };
+
+  info("Add bookmarks and tag the URIs");
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    await addBookmark(nsiuri);
+    if (tags) {
+      PlacesUtils.tagging.tagURI(nsiuri, tags);
+    }
+  }
+
+  info('  Querying for "foo" should match only /2 and /3');
+  var [query, opts] = makeQuery(["foo"], true);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    "http://example.com/2",
+    "http://example.com/3",
+  ]);
+
+  info('  Querying for "foo" and "bar" should match only /2 and /3');
+  [query, opts] = makeQuery(["foo", "bar"], true);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    "http://example.com/2",
+    "http://example.com/3",
+  ]);
+
+  info('  Querying for "foo" and "bogus" should match only /2 and /3');
+  [query, opts] = makeQuery(["foo", "bogus"], true);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    "http://example.com/2",
+    "http://example.com/3",
+  ]);
+
+  info('  Querying for "foo" and "baz" should match only /3');
+  [query, opts] = makeQuery(["foo", "baz"], true);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    "http://example.com/3",
+  ]);
+
+  info('  Querying for "bogus" should match all');
+  [query, opts] = makeQuery(["bogus"], true);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    "http://example.com/1",
+    "http://example.com/2",
+    "http://example.com/3",
+  ]);
+
+  // Clean up.
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    if (tags) {
+      PlacesUtils.tagging.untagURI(nsiuri, tags);
+    }
+  }
+  await task_cleanDatabase();
+});
+
+add_task(async function duplicate_tags() {
+  info(
+    "Duplicate existing tags (i.e., multiple tag folders with " +
+      "same name) should not throw off query results"
+  );
+  var tagName = "foo";
+
+  info("Add bookmark and tag it normally");
+  await addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, [tagName]);
+
+  info("Manually create tag folder with same name as tag and insert bookmark");
+  let dupTag = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.tagsGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    title: tagName,
+  });
+
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: dupTag.guid,
+    title: "title",
+    url: TEST_URI,
+  });
+
+  info("Querying for tag should match URI");
+  var [query, opts] = makeQuery([tagName]);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    TEST_URI.spec,
+  ]);
+
+  PlacesUtils.tagging.untagURI(TEST_URI, [tagName]);
+  await task_cleanDatabase();
+});
+
+add_task(async function folder_named_as_tag() {
+  info(
+    "Regular folders with the same name as tag should not throw " +
+      "off query results"
+  );
+  var tagName = "foo";
+
+  info("Add bookmark and tag it");
+  await addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, [tagName]);
+
+  info("Create folder with same name as tag");
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    title: tagName,
+  });
+
+  info("Querying for tag should match URI");
+  var [query, opts] = makeQuery([tagName]);
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [
+    TEST_URI.spec,
+  ]);
+
+  PlacesUtils.tagging.untagURI(TEST_URI, [tagName]);
+  await task_cleanDatabase();
+});
+
+add_task(async function ORed_queries() {
+  info("Multiple queries ORed together should work");
+  var urisAndTags = {
+    "http://example.com/1": [],
+    "http://example.com/2": [],
+  };
+
+  // Search with lots of tags to make sure tag parameter substitution in SQL
+  // can handle it with more than one query.
+  for (let i = 0; i < 11; i++) {
+    urisAndTags["http://example.com/1"].push("/1 tag " + i);
+    urisAndTags["http://example.com/2"].push("/2 tag " + i);
+  }
+
+  info("Add bookmarks and tag the URIs");
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    await addBookmark(nsiuri);
+    if (tags) {
+      PlacesUtils.tagging.tagURI(nsiuri, tags);
+    }
+  }
+
+  // Clean up.
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    if (tags) {
+      PlacesUtils.tagging.untagURI(nsiuri, tags);
+    }
+  }
+  await task_cleanDatabase();
+});
+
+add_task(async function tag_casing() {
+  info(
+    "Querying on associated tags should return " +
+      "correct results irrespective of casing of tags."
+  );
+  await task_doWithBookmark(["fOo", "bAr"], function (aURI) {
+    let [query, opts] = makeQuery(["Foo"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["Foo", "Bar"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["Foo"], true);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["Bogus"], true);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(async function tag_casing_l10n() {
+  info(
+    "Querying on associated tags should return " +
+      "correct results irrespective of casing of tags with international strings."
+  );
+  // \u041F is a lowercase \u043F
+  await task_doWithBookmark(
+    ["\u041F\u0442\u0438\u0446\u044B"],
+    function (aURI) {
+      let [query, opts] = makeQuery(["\u041F\u0442\u0438\u0446\u044B"]);
+      executeAndCheckQueryResults(query, opts, [aURI.spec]);
+      [query, opts] = makeQuery(["\u043F\u0442\u0438\u0446\u044B"]);
+      executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    }
+  );
+  await task_doWithBookmark(
+    ["\u043F\u0442\u0438\u0446\u044B"],
+    function (aURI) {
+      let [query, opts] = makeQuery(["\u041F\u0442\u0438\u0446\u044B"]);
+      executeAndCheckQueryResults(query, opts, [aURI.spec]);
+      [query, opts] = makeQuery(["\u043F\u0442\u0438\u0446\u044B"]);
+      executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    }
+  );
+});
+
+add_task(async function tag_special_char() {
+  info(
+    "Querying on associated tags should return " +
+      "correct results even if tags contain special characters."
+  );
+  await task_doWithBookmark(["Space ☺️ Between"], function (aURI) {
+    let [query, opts] = makeQuery(["Space ☺️ Between"]);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["Space ☺️ Between"], true);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["Bogus"], true);
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+// The tag keys in query URIs, i.e., "place:tag=foo&!tags=1"
+//                                          ---     -----
+const QUERY_KEY_TAG = "tag";
+const QUERY_KEY_NOT_TAGS = "!tags";
+
+const TEST_URI = uri("http://example.com/");
+
+/**
+ * Adds a bookmark.
+ *
+ * @param aURI
+ *        URI of the page (an nsIURI)
+ */
+function addBookmark(aURI) {
+  return PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    title: aURI.spec,
+    url: aURI,
+  });
+}
+
+/**
+ * Asynchronous task that removes all pages from history and bookmarks.
+ */
+async function task_cleanDatabase(aCallback) {
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesUtils.history.clear();
+}
+
+/**
+ * Sets up a query with the specified tags, converts it to a URI, and makes sure
+ * the URI is what we expect it to be.
+ *
+ * @param aTags
+ *        The query's tags will be set to those in this array
+ * @param aTagsAreNot
+ *        The query's tagsAreNot property will be set to this
+ */
+function checkQueryURI(aTags, aTagsAreNot) {
+  var pairs = (aTags || []).sort().map(t => QUERY_KEY_TAG + "=" + encodeTag(t));
+  if (aTagsAreNot) {
+    pairs.push(QUERY_KEY_NOT_TAGS + "=1");
+  }
+  var expURI = "place:" + pairs.join("&");
+  var [query, opts] = makeQuery(aTags, aTagsAreNot);
+  var actualURI = queryURI(query, opts);
+  info("Query URI should be what we expect for the given tags");
+  Assert.equal(actualURI, expURI);
+}
+
+/**
+ * Asynchronous task that executes a callback task in a "scoped" database state.
+ * A bookmark is added and tagged before the callback is called, and afterward
+ * the database is cleared.
+ *
+ * @param aTags
+ *        A bookmark will be added and tagged with this array of tags
+ * @param aCallback
+ *        A task function that will be called after the bookmark has been tagged
+ */
+async function task_doWithBookmark(aTags, aCallback) {
+  await addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, aTags);
+  await aCallback(TEST_URI);
+  PlacesUtils.tagging.untagURI(TEST_URI, aTags);
+  await task_cleanDatabase();
+}
+
+/**
+ * queryToQueryString() encodes every character in the query URI that doesn't
+ * match /[a-zA-Z]/.  There's no simple JavaScript function that does the same,
+ * but encodeURIComponent() comes close, only missing some punctuation.  This
+ * function takes care of all of that.
+ *
+ * @param  aTag
+ *         A tag name to encode
+ * @return A UTF-8 escaped string suitable for inclusion in a query URI
+ */
+function encodeTag(aTag) {
+  return encodeURIComponent(aTag).replace(
+    /[-_.!~*'()]/g, // '
+    s => "%" + s.charCodeAt(0).toString(16)
+  );
+}
+
+/**
+ * Executes the given query and compares the results to the given URIs.
+ * See queryResultsAre().
+ *
+ * @param aQuery
+ *        An nsINavHistoryQuery
+ * @param aQueryOpts
+ *        An nsINavHistoryQueryOptions
+ * @param aExpectedURIs
+ *        Array of URIs (as strings) that aResultRoot should contain
+ */
+function executeAndCheckQueryResults(aQuery, aQueryOpts, aExpectedURIs) {
+  var root = PlacesUtils.history.executeQuery(aQuery, aQueryOpts).root;
+  root.containerOpen = true;
+  queryResultsAre(root, aExpectedURIs);
+  root.containerOpen = false;
+}
+
+/**
+ * Returns new query and query options objects.  The query's tags will be
+ * set to aTags.  aTags may be null, in which case setTags() is not called at
+ * all on the query.
+ *
+ * @param  aTags
+ *         The query's tags will be set to those in this array
+ * @param  aTagsAreNot
+ *         The query's tagsAreNot property will be set to this
+ * @return [query, queryOptions]
+ */
+function makeQuery(aTags, aTagsAreNot) {
+  aTagsAreNot = !!aTagsAreNot;
+  info(
+    "Making a query " +
+      (aTags
+        ? "with tags " + aTags.toSource()
+        : "without calling setTags() at all") +
+      " and with tagsAreNot=" +
+      aTagsAreNot
+  );
+  var query = PlacesUtils.history.getNewQuery();
+  query.tagsAreNot = aTagsAreNot;
+  if (aTags) {
+    query.tags = aTags;
+    var uniqueTags = [];
+    aTags.forEach(function (t) {
+      if (typeof t === "string" && !uniqueTags.includes(t)) {
+        uniqueTags.push(t);
+      }
+    });
+    uniqueTags.sort();
+  }
+
+  info("Made query should be correct for tags and tagsAreNot");
+  if (uniqueTags) {
+    setsAreEqual(query.tags, uniqueTags, true);
+  }
+  var expCount = uniqueTags ? uniqueTags.length : 0;
+  Assert.equal(query.tags.length, expCount);
+  Assert.equal(query.tagsAreNot, aTagsAreNot);
+
+  return [query, PlacesUtils.history.getNewQueryOptions()];
+}
+
+/**
+ * Ensures that the URIs of aResultRoot are the same as those in aExpectedURIs.
+ *
+ * @param aResultRoot
+ *        The nsINavHistoryContainerResultNode root of an nsINavHistoryResult
+ * @param aExpectedURIs
+ *        Array of URIs (as strings) that aResultRoot should contain
+ */
+function queryResultsAre(aResultRoot, aExpectedURIs) {
+  var rootWasOpen = aResultRoot.containerOpen;
+  if (!rootWasOpen) {
+    aResultRoot.containerOpen = true;
+  }
+  var actualURIs = [];
+  for (let i = 0; i < aResultRoot.childCount; i++) {
+    actualURIs.push(aResultRoot.getChild(i).uri);
+  }
+  setsAreEqual(actualURIs, aExpectedURIs);
+  if (!rootWasOpen) {
+    aResultRoot.containerOpen = false;
+  }
+}
+
+/**
+ * Converts the given query into its query URI.
+ *
+ * @param  aQuery
+ *         An nsINavHistoryQuery
+ * @param  aQueryOpts
+ *         An nsINavHistoryQueryOptions
+ * @return The query's URI
+ */
+function queryURI(aQuery, aQueryOpts) {
+  return PlacesUtils.history.queryToQueryString(aQuery, aQueryOpts);
+}
+
+/**
+ * Ensures that the arrays contain the same elements and, optionally, in the
+ * same order.
+ */
+function setsAreEqual(aArr1, aArr2, aIsOrdered) {
+  Assert.equal(aArr1.length, aArr2.length);
+  if (aIsOrdered) {
+    for (let i = 0; i < aArr1.length; i++) {
+      Assert.equal(aArr1[i], aArr2[i]);
+    }
+  } else {
+    aArr1.forEach(u => Assert.ok(aArr2.includes(u)));
+    aArr2.forEach(u => Assert.ok(aArr1.includes(u)));
+  }
+}
diff --git a/toolkit/components/places/tests/queries/test_transitions.js b/toolkit/components/places/tests/queries/test_transitions.js
new file mode 100644
index 0000000000..3055f28e9f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_transitions.js
@@ -0,0 +1,175 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* ***** BEGIN LICENSE BLOCK *****
+  Any copyright is dedicated to the Public Domain.
+  http://creativecommons.org/publicdomain/zero/1.0/
+ * ***** END LICENSE BLOCK ***** */
+var testData = [
+  {
+    isVisit: true,
+    title: "page 0",
+    uri: "http://mozilla.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
+  },
+  {
+    isVisit: true,
+    title: "page 1",
+    uri: "http://google.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  },
+  {
+    isVisit: true,
+    title: "page 2",
+    uri: "http://microsoft.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  },
+  {
+    isVisit: true,
+    title: "page 3",
+    uri: "http://en.wikipedia.org/",
+    transType: Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+  },
+  {
+    isVisit: true,
+    title: "page 4",
+    uri: "http://fr.wikipedia.org/",
+    transType: Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  },
+  {
+    isVisit: true,
+    title: "page 5",
+    uri: "http://apple.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
+  },
+  {
+    isVisit: true,
+    title: "page 6",
+    uri: "http://campus-bike-store.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  },
+  {
+    isVisit: true,
+    title: "page 7",
+    uri: "http://uwaterloo.ca/",
+    transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
+  },
+  {
+    isVisit: true,
+    title: "page 8",
+    uri: "http://pugcleaner.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+  },
+  {
+    isVisit: true,
+    title: "page 9",
+    uri: "http://de.wikipedia.org/",
+    transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
+  },
+  {
+    isVisit: true,
+    title: "arewefastyet",
+    uri: "http://arewefastyet.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+  },
+  {
+    isVisit: true,
+    title: "arewefastyet",
+    uri: "http://arewefastyet.com/",
+    transType: Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+  },
+];
+// sets of indices of testData array by transition type
+var testDataTyped = [0, 5, 7, 9];
+var testDataDownload = [1, 2, 4, 6, 10];
+var testDataBookmark = [3, 8, 11];
+
+add_task(async function test_transitions() {
+  let timeNow = Date.now();
+  for (let item of testData) {
+    await PlacesTestUtils.addVisits({
+      uri: uri(item.uri),
+      transition: item.transType,
+      visitDate: timeNow++ * 1000,
+      title: item.title,
+    });
+  }
+
+  // dump_table("moz_places");
+  // dump_table("moz_historyvisits");
+
+  var numSortFunc = function (a, b) {
+    return a - b;
+  };
+  var arrs = testDataTyped
+    .concat(testDataDownload)
+    .concat(testDataBookmark)
+    .sort(numSortFunc);
+
+  // Four tests which compare the result of a query to an expected set.
+  var data = arrs.filter(function (index) {
+    return (
+      testData[index].uri.match(/arewefastyet\.com/) &&
+      testData[index].transType == Ci.nsINavHistoryService.TRANSITION_DOWNLOAD
+    );
+  });
+
+  compareQueryToTestData(
+    "place:domain=arewefastyet.com&transition=" +
+      Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+    data.slice()
+  );
+
+  compareQueryToTestData(
+    "place:transition=" + Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+    testDataDownload.slice()
+  );
+
+  compareQueryToTestData(
+    "place:transition=" + Ci.nsINavHistoryService.TRANSITION_TYPED,
+    testDataTyped.slice()
+  );
+
+  compareQueryToTestData(
+    "place:transition=" +
+      Ci.nsINavHistoryService.TRANSITION_DOWNLOAD +
+      "&transition=" +
+      Ci.nsINavHistoryService.TRANSITION_BOOKMARK,
+    data
+  );
+
+  // Tests the live update property of transitions.
+  var query = {};
+  var options = {};
+  PlacesUtils.history.queryStringToQuery(
+    "place:transition=" + Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+    query,
+    options
+  );
+  var result = PlacesUtils.history.executeQuery(query.value, options.value);
+  var root = result.root;
+  root.containerOpen = true;
+  Assert.equal(testDataDownload.length, root.childCount);
+  await PlacesTestUtils.addVisits({
+    uri: uri("http://getfirefox.com"),
+    transition: TRANSITION_DOWNLOAD,
+  });
+  Assert.equal(testDataDownload.length + 1, root.childCount);
+  root.containerOpen = false;
+});
+
+/*
+ * Takes a query and a set of indices. The indices correspond to elements
+ * of testData that are the result of the query.
+ */
+function compareQueryToTestData(queryStr, data) {
+  var query = {};
+  var options = {};
+  PlacesUtils.history.queryStringToQuery(queryStr, query, options);
+  var result = PlacesUtils.history.executeQuery(query.value, options.value);
+  var root = result.root;
+  for (var i = 0; i < data.length; i++) {
+    data[i] = testData[data[i]];
+    data[i].isInQuery = true;
+  }
+  compareArrayToResult(data, root);
+}
diff --git a/toolkit/components/places/tests/queries/xpcshell.toml b/toolkit/components/places/tests/queries/xpcshell.toml
new file mode 100644
index 0000000000..b171df8c00
--- /dev/null
+++ b/toolkit/components/places/tests/queries/xpcshell.toml
@@ -0,0 +1,57 @@
+[DEFAULT]
+head = "head_queries.js"
+skip-if = ["os == 'android'"]
+
+["test_async.js"]
+
+["test_bookmarks.js"]
+
+["test_containersQueries_sorting.js"]
+
+["test_downloadHistory_liveUpdate.js"]
+
+["test_excludeQueries.js"]
+
+["test_history_queries_tags_liveUpdate.js"]
+
+["test_history_queries_titles_liveUpdate.js"]
+
+["test_options_inherit.js"]
+
+["test_queryMultipleFolder.js"]
+
+["test_querySerialization.js"]
+
+["test_query_uri_liveupdate.js"]
+
+["test_redirects.js"]
+
+["test_result_observeHistoryDetails.js"]
+
+["test_results-as-left-pane.js"]
+
+["test_results-as-roots.js"]
+
+["test_results-as-tag-query.js"]
+
+["test_results-as-visit.js"]
+
+["test_searchTerms_includeHidden.js"]
+
+["test_searchTerms_time.js"]
+
+["test_search_tags.js"]
+
+["test_searchterms-bookmarklets.js"]
+
+["test_searchterms-domain.js"]
+
+["test_searchterms-uri.js"]
+
+["test_sort-date-site-grouping.js"]
+
+["test_sorting.js"]
+
+["test_tags.js"]
+
+["test_transitions.js"]