Add m-esr52 at 52.6.0

25 files changed, 6423 insertions, 0 deletions

diff --git a/toolkit/components/places/tests/queries/.eslintrc.js b/toolkit/components/places/tests/queries/.eslintrc.js
new file mode 100644
index 000000000..d35787cd2
--- /dev/null
+++ b/toolkit/components/places/tests/queries/.eslintrc.js
@@ -0,0 +1,7 @@
+"use strict";
+
+module.exports = {
+  "extends": [
+    "../../../../../testing/xpcshell/xpcshell.eslintrc.js"
+  ]
+};
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 000000000..d37b3365f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/head_queries.js
@@ -0,0 +1,370 @@
+/* -*- 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 Ci = Components.interfaces;
+var Cc = Components.classes;
+var Cr = Components.results;
+var Cu = Components.utils;
+
+Cu.import("resource://gre/modules/Services.jsm");
+
+// Import common head.
+{
+  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.
+ */
+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
+        yield 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.
+          let stmt = DBConn().createAsyncStatement(
+            "UPDATE moz_places SET visit_count = :vc WHERE url_hash = hash(:url) AND url = :url");
+          stmt.params.vc = qdata.visitCount;
+          stmt.params.url = qdata.uri;
+          try {
+            stmt.executeAsync();
+          }
+          catch (ex) {
+            print("Error while setting visit_count.");
+          }
+          finally {
+            stmt.finalize();
+          }
+        }
+      }
+
+      if (qdata.isRedirect) {
+        // This must be async to properly enqueue after the updateFrecency call
+        // done by the visit addition.
+        let stmt = DBConn().createAsyncStatement(
+          "UPDATE moz_places SET hidden = 1 WHERE url_hash = hash(:url) AND url = :url");
+        stmt.params.url = qdata.uri;
+        try {
+          stmt.executeAsync();
+        }
+        catch (ex) {
+          print("Error while setting hidden.");
+        }
+        finally {
+          stmt.finalize();
+        }
+      }
+
+      if (qdata.isDetails) {
+        // Then we add extraneous page details for testing
+        yield PlacesTestUtils.addVisits({
+          uri: uri(qdata.uri),
+          visitDate: qdata.lastVisit,
+          title: qdata.title
+        });
+      }
+
+      if (qdata.markPageAsTyped) {
+        PlacesUtils.history.markPageAsTyped(uri(qdata.uri));
+      }
+
+      if (qdata.isPageAnnotation) {
+        if (qdata.removeAnnotation)
+          PlacesUtils.annotations.removePageAnnotation(uri(qdata.uri),
+                                                       qdata.annoName);
+        else {
+          PlacesUtils.annotations.setPageAnnotation(uri(qdata.uri),
+                                                    qdata.annoName,
+                                                    qdata.annoVal,
+                                                    qdata.annoFlags,
+                                                    qdata.annoExpiration);
+        }
+      }
+
+      if (qdata.isItemAnnotation) {
+        if (qdata.removeAnnotation)
+          PlacesUtils.annotations.removeItemAnnotation(qdata.itemId,
+                                                       qdata.annoName);
+        else {
+          PlacesUtils.annotations.setItemAnnotation(qdata.itemId,
+                                                    qdata.annoName,
+                                                    qdata.annoVal,
+                                                    qdata.annoFlags,
+                                                    qdata.annoExpiration);
+        }
+      }
+
+      if (qdata.isFolder) {
+        yield PlacesUtils.bookmarks.insert({
+          parentGuid: qdata.parentGuid,
+          type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          title: qdata.title,
+          index: qdata.index
+        });
+      }
+
+      if (qdata.isLivemark) {
+        yield PlacesUtils.livemarks.addLivemark({ title: qdata.title
+                                                , parentId: (yield PlacesUtils.promiseItemId(qdata.parentGuid))
+                                                , index: qdata.index
+                                                , feedURI: uri(qdata.feedURI)
+                                                , siteURI: uri(qdata.uri)
+                                                });
+      }
+
+      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);
+        }
+
+        yield PlacesUtils.bookmarks.insert(data);
+
+        if (qdata.keyword) {
+          yield PlacesUtils.keywords.insert({ url: qdata.uri,
+                                              keyword: qdata.keyword });
+        }
+      }
+
+      if (qdata.isTag) {
+        PlacesUtils.tagging.tagURI(uri(qdata.uri), qdata.tagArray);
+      }
+
+      if (qdata.isSeparator) {
+        yield 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
+      do_print("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 ? true : false;
+  this.annoName = obj.annoName ? obj.annoName : "";
+  this.annoVal = obj.annoVal ? obj.annoVal : "";
+  this.annoFlags = obj.annoFlags ? obj.annoFlags : 0;
+  this.annoExpiration = obj.annoExpiration ? obj.annoExpiration : 0;
+  this.isItemAnnotation = obj.isItemAnnotation ? obj.isItemAnnotation : false;
+  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.isLivemark = obj.isLivemark ? obj.isLivemark : false;
+  this.parentGuid = obj.parentGuid || PlacesUtils.bookmarks.rootGuid;
+  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) {
+  do_print("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");
+    do_print("Found children:");
+    for (let i = 0; i < aRoot.childCount; i++) {
+      do_print(aRoot.getChild(i).uri);
+    }
+    do_print("Expected:");
+    for (let i = 0; i < aArray.length; i++) {
+      if (aArray[i].isInQuery)
+        do_print(aArray[i].uri);
+    }
+  }
+  do_check_eq(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) {
+        do_print("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;
+  do_print("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: True if item is in query set, and false if item is not in query set
+ *          If input is an array, returns True if FIRST object in array is in
+ *          query set.  To compare entire array, use the function above.
+ */
+function isInResult(aQueryData, aRoot) {
+  var rv = false;
+  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++) {
+    if (uri == aRoot.getChild(i).uri) {
+      rv = true;
+      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?
+    do_print("Result Set Empty");
+    return;
+  }
+
+  for (var i=0; i < aRoot.childCount; ++i) {
+    do_print("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 000000000..19414f96e
--- /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_415716.js b/toolkit/components/places/tests/queries/test_415716.js
new file mode 100644
index 000000000..754a73e7c
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_415716.js
@@ -0,0 +1,108 @@
+/* -*- 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/. */
+
+function modHistoryTypes(val) {
+  switch (val % 8) {
+    case 0:
+    case 1:
+      return TRANSITION_LINK;
+    case 2:
+      return TRANSITION_TYPED;
+    case 3:
+      return TRANSITION_BOOKMARK;
+    case 4:
+      return TRANSITION_EMBED;
+    case 5:
+      return TRANSITION_REDIRECT_PERMANENT;
+    case 6:
+      return TRANSITION_REDIRECT_TEMPORARY;
+    case 7:
+      return TRANSITION_DOWNLOAD;
+    case 8:
+      return TRANSITION_FRAMED_LINK;
+  }
+  return TRANSITION_TYPED;
+}
+
+function run_test()
+{
+  run_next_test();
+}
+
+/**
+ * Builds a test database by hand using various times, annotations and
+ * visit numbers for this test
+ */
+add_task(function* test_buildTestDatabase()
+{
+  // This is the set of visits that we will match - our min visit is 2 so that's
+  // why we add more visits to the same URIs.
+  let testURI = uri("http://www.foo.com");
+  let places = [];
+
+  for (let i = 0; i < 12; ++i) {
+    places.push({
+      uri: testURI,
+      transition: modHistoryTypes(i),
+      visitDate: today
+    });
+  }
+
+  testURI = uri("http://foo.com/youdontseeme.html");
+  let testAnnoName = "moz-test-places/testing123";
+  let testAnnoVal = "test";
+  for (let i = 0; i < 12; ++i) {
+    places.push({
+      uri: testURI,
+      transition: modHistoryTypes(i),
+      visitDate: today
+    });
+  }
+
+  yield PlacesTestUtils.addVisits(places);
+
+  PlacesUtils.annotations.setPageAnnotation(testURI, testAnnoName,
+                                            testAnnoVal, 0, 0);
+});
+
+/**
+ * This test will test Queries that use relative Time Range, minVists, maxVisits,
+ * annotation.
+ * The Query:
+ * Annotation == "moz-test-places/testing123" &&
+ * TimeRange == "now() - 2d" &&
+ * minVisits == 2 &&
+ * maxVisits == 10
+ */
+add_task(function test_execute()
+{
+  let query = PlacesUtils.history.getNewQuery();
+  query.annotation = "moz-test-places/testing123";
+  query.beginTime = daybefore * 1000;
+  query.beginTimeReference = PlacesUtils.history.TIME_RELATIVE_NOW;
+  query.endTime = today * 1000;
+  query.endTimeReference = PlacesUtils.history.TIME_RELATIVE_NOW;
+  query.minVisits = 2;
+  query.maxVisits = 10;
+
+  // Options
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_DATE_DESCENDING;
+  options.resultType = options.RESULTS_AS_VISIT;
+
+  // Results
+  let root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  let cc = root.childCount;
+  dump("----> cc is: " + cc + "\n");
+  for (let i = 0; i < root.childCount; ++i) {
+    let resultNode = root.getChild(i);
+    let accesstime = Date(resultNode.time / 1000);
+    dump("----> result: " + resultNode.uri + "   Date: " + accesstime.toLocaleString() + "\n");
+  }
+  do_check_eq(cc, 0);
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_abstime-annotation-domain.js b/toolkit/components/places/tests/queries/test_abstime-annotation-domain.js
new file mode 100644
index 000000000..199fc0865
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_abstime-annotation-domain.js
@@ -0,0 +1,210 @@
+/* -*- 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/. */
+
+const DAY_MSEC = 86400000;
+const MIN_MSEC = 60000;
+const HOUR_MSEC = 3600000;
+// Jan 6 2008 at 8am is our begin edge of the query
+var beginTimeDate = new Date(2008, 0, 6, 8, 0, 0, 0);
+// Jan 15 2008 at 9:30pm is our ending edge of the query
+var endTimeDate = new Date(2008, 0, 15, 21, 30, 0, 0);
+
+// These as millisecond values
+var beginTime = beginTimeDate.getTime();
+var endTime = endTimeDate.getTime();
+
+// Some range dates inside our query - mult by 1000 to convert to PRTIME
+var jan7_800 = (beginTime + DAY_MSEC) * 1000;
+var jan6_815 = (beginTime + (MIN_MSEC * 15)) * 1000;
+var jan11_800 = (beginTime + (DAY_MSEC * 5)) * 1000;
+var jan14_2130 = (endTime - DAY_MSEC) * 1000;
+var jan15_2045 = (endTime - (MIN_MSEC * 45)) * 1000;
+var jan12_1730 = (endTime - (DAY_MSEC * 3) - (HOUR_MSEC*4)) * 1000;
+
+// Dates outside our query - mult by 1000 to convert to PRTIME
+var jan6_700 = (beginTime - HOUR_MSEC) * 1000;
+var jan5_800 = (beginTime - DAY_MSEC) * 1000;
+var dec27_800 = (beginTime - (DAY_MSEC * 10)) * 1000;
+var jan15_2145 = (endTime + (MIN_MSEC * 15)) * 1000;
+var jan16_2130 = (endTime + (DAY_MSEC)) * 1000;
+var jan25_2130 = (endTime + (DAY_MSEC * 10)) * 1000;
+
+// So that we can easily use these too, convert them to PRTIME
+beginTime *= 1000;
+endTime *= 1000;
+
+/**
+ * Array of objects to build our test database
+ */
+var goodAnnoName = "moz-test-places/testing123";
+var val = "test";
+var badAnnoName = "text/foo";
+
+// 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
+  {isInQuery: true, isVisit: true, isDetails: true,
+   uri: "ftp://foo.com/ftp", lastVisit: jan12_1730,
+   title: "hugelongconfmozlagurationofwordswithasearchtermsinit whoo-hoo"},
+
+  // Test flat domain with annotation
+  {isInQuery: true, isVisit: true, isDetails: true, isPageAnnotation: true,
+   uri: "http://foo.com/", annoName: goodAnnoName, annoVal: val,
+   lastVisit: jan14_2130, title: "moz"},
+
+  // Test subdomain included with isRedirect=true, different transtype
+  {isInQuery: true, isVisit: true, isDetails: true, title: "moz",
+   isRedirect: true, uri: "http://mail.foo.com/redirect", lastVisit: jan11_800,
+   transType: PlacesUtils.history.TRANSITION_LINK},
+
+  // Test subdomain inclued at the leading time edge
+  {isInQuery: true, isVisit: true, isDetails: true,
+   uri: "http://mail.foo.com/yiihah", title: "moz", lastVisit: jan6_815},
+
+  // Test www. style URI is included, with an annotation
+  {isInQuery: true, isVisit: true, isDetails: true, isPageAnnotation: true,
+   uri: "http://www.foo.com/yiihah", annoName: goodAnnoName, annoVal: val,
+   lastVisit: jan7_800, title: "moz"},
+
+  // Test https protocol
+  {isInQuery: true, isVisit: true, isDetails: true, title: "moz",
+   uri: "https://foo.com/", lastVisit: jan15_2045},
+
+  // Test begin edge of time
+  {isInQuery: true, isVisit: true, isDetails: true, title: "moz mozilla",
+   uri: "https://foo.com/begin.html", lastVisit: beginTime},
+
+  // Test end edge of time
+  {isInQuery: true, isVisit: true, isDetails: true, title: "moz mozilla",
+   uri: "https://foo.com/end.html", lastVisit: endTime},
+
+  // Test an image link, with annotations
+  {isInQuery: true, isVisit: true, isDetails: true, isPageAnnotation: true,
+   title: "mozzie the dino", uri: "https://foo.com/mozzie.png",
+   annoName: goodAnnoName, annoVal: val, lastVisit: jan14_2130},
+
+  // Begin the invalid queries: Test too early
+  {isInQuery: false, isVisit:true, isDetails: true, title: "moz",
+   uri: "http://foo.com/tooearly.php", lastVisit: jan6_700},
+
+  // Test Bad Annotation
+  {isInQuery: false, isVisit:true, isDetails: true, isPageAnnotation: true,
+   title: "moz", uri: "http://foo.com/badanno.htm", lastVisit: jan12_1730,
+   annoName: badAnnoName, annoVal: val},
+
+  // Test bad URI
+  {isInQuery: false, isVisit:true, isDetails: true, title: "moz",
+   uri: "http://somefoo.com/justwrong.htm", lastVisit: jan11_800},
+
+  // Test afterward, one to update
+  {isInQuery: false, isVisit:true, isDetails: true, title: "changeme",
+   uri: "http://foo.com/changeme1.htm", lastVisit: jan12_1730},
+
+  // Test invalid title
+  {isInQuery: false, isVisit:true, isDetails: true, title: "changeme2",
+   uri: "http://foo.com/changeme2.htm", lastVisit: jan7_800},
+
+  // Test changing the lastVisit
+  {isInQuery: false, isVisit:true, isDetails: true, title: "moz",
+   uri: "http://foo.com/changeme3.htm", lastVisit: dec27_800}];
+
+/**
+ * This test will test a Query using several terms and do a bit of negative
+ * testing for items that should be ignored while querying over history.
+ * The Query:WHERE absoluteTime(matches) AND searchTerms AND URI
+ *                 AND annotationIsNot(match) GROUP BY Domain, Day SORT BY uri,ascending
+ *                 excludeITems(should be ignored)
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_abstime_annotation_domain()
+{
+  // Initialize database
+  yield task_populateDB(testData);
+
+  // Query
+  var query = PlacesUtils.history.getNewQuery();
+  query.beginTime = beginTime;
+  query.endTime = endTime;
+  query.beginTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.endTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.searchTerms = "moz";
+  query.domain = "foo.com";
+  query.domainIsHost = false;
+  query.annotation = "text/foo";
+  query.annotationIsNot = true;
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_URI_ASCENDING;
+  options.resultType = options.RESULTS_AS_URI;
+  // The next two options should be ignored
+  // can't use this one, breaks test - bug 419779
+  // options.excludeItems = true;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  // Ensure the result set is correct
+  compareArrayToResult(testData, root);
+
+  // Make some changes to the result set
+  // Let's add something first
+  var addItem = [{isInQuery: true, isVisit: true, isDetails: true, title: "moz",
+                 uri: "http://www.foo.com/i-am-added.html", lastVisit: jan11_800}];
+  yield task_populateDB(addItem);
+  do_print("Adding item foo.com/i-am-added.html");
+  do_check_eq(isInResult(addItem, root), true);
+
+  // Let's update something by title
+  var change1 = [{isDetails: true, uri: "http://foo.com/changeme1",
+                  lastVisit: jan12_1730, title: "moz moz mozzie"}];
+  yield task_populateDB(change1);
+  do_print("LiveUpdate by changing title");
+  do_check_eq(isInResult(change1, root), true);
+
+  // Let's update something by annotation
+  // Updating a page by removing an annotation does not cause it to join this
+  // query set.  I tend to think that it should cause that page to join this
+  // query set, because this visit fits all theother specified criteria once the
+  // annotation is removed. Uncommenting this will fail the test.
+  // Bug 424050
+  /* var change2 = [{isPageAnnotation: true, uri: "http://foo.com/badannotaion.html",
+                  annoName: "text/mozilla", annoVal: "test"}];
+  yield task_populateDB(change2);
+  do_print("LiveUpdate by removing annotation");
+  do_check_eq(isInResult(change2, root), true);*/
+
+  // Let's update by adding a visit in the time range for an existing URI
+  var change3 = [{isDetails: true, uri: "http://foo.com/changeme3.htm",
+                  title: "moz", lastVisit: jan15_2045}];
+  yield task_populateDB(change3);
+  do_print("LiveUpdate by adding visit within timerange");
+  do_check_eq(isInResult(change3, root), true);
+
+  // And delete something from the result set - using annotation
+  // Once again, bug 424050 prevents this from passing
+  /* var change4 = [{isPageAnnotation: true, uri: "ftp://foo.com/ftp",
+                  annoVal: "test", annoName: badAnnoName}];
+  yield task_populateDB(change4);
+  do_print("LiveUpdate by deleting item from set by adding annotation");
+  do_check_eq(isInResult(change4, root), false);*/
+
+  // Delete something by changing the title
+  var change5 = [{isDetails: true, uri: "http://foo.com/end.html", title: "deleted"}];
+  yield task_populateDB(change5);
+  do_print("LiveUpdate by deleting item by changing title");
+  do_check_eq(isInResult(change5, root), false);
+
+  root.containerOpen = false;
+});
diff --git a/toolkit/components/places/tests/queries/test_abstime-annotation-uri.js b/toolkit/components/places/tests/queries/test_abstime-annotation-uri.js
new file mode 100644
index 000000000..145d2cb59
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_abstime-annotation-uri.js
@@ -0,0 +1,162 @@
+/* -*- 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/. */
+
+const DAY_MSEC = 86400000;
+const MIN_MSEC = 60000;
+const HOUR_MSEC = 3600000;
+// Jan 6 2008 at 8am is our begin edge of the query
+var beginTimeDate = new Date(2008, 0, 6, 8, 0, 0, 0);
+// Jan 15 2008 at 9:30pm is our ending edge of the query
+var endTimeDate = new Date(2008, 0, 15, 21, 30, 0, 0);
+
+// These as millisecond values
+var beginTime = beginTimeDate.getTime();
+var endTime = endTimeDate.getTime();
+
+// Some range dates inside our query - mult by 1000 to convert to PRTIME
+var jan7_800 = (beginTime + DAY_MSEC) * 1000;
+var jan6_815 = (beginTime + (MIN_MSEC * 15)) * 1000;
+var jan11_800 = (beginTime + (DAY_MSEC * 5)) * 1000;
+var jan14_2130 = (endTime - DAY_MSEC) * 1000;
+var jan15_2045 = (endTime - (MIN_MSEC * 45)) * 1000;
+var jan12_1730 = (endTime - (DAY_MSEC * 3) - (HOUR_MSEC*4)) * 1000;
+
+// Dates outside our query - mult by 1000 to convert to PRTIME
+var jan6_700 = (beginTime - HOUR_MSEC) * 1000;
+var jan5_800 = (beginTime - DAY_MSEC) * 1000;
+var dec27_800 = (beginTime - (DAY_MSEC * 10)) * 1000;
+var jan15_2145 = (endTime + (MIN_MSEC * 15)) * 1000;
+var jan16_2130 = (endTime + (DAY_MSEC)) * 1000;
+var jan25_2130 = (endTime + (DAY_MSEC * 10)) * 1000;
+
+// So that we can easily use these too, convert them to PRTIME
+beginTime *= 1000;
+endTime *= 1000;
+
+/**
+ * Array of objects to build our test database
+ */
+var goodAnnoName = "moz-test-places/testing123";
+var val = "test";
+var badAnnoName = "text/foo";
+
+// 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
+  {isInQuery: true, isVisit: true, isDetails: true, isPageAnnotation: true,
+   uri: "http://foo.com/", annoName: goodAnnoName, annoVal: val,
+   lastVisit: jan14_2130, title: "moz"},
+
+  // Begin the invalid queries:
+  // Test www. style URI is not included, with an annotation
+  {isInQuery: false, isVisit: true, isDetails: true, isPageAnnotation: true,
+   uri: "http://www.foo.com/yiihah", annoName: goodAnnoName, annoVal: val,
+   lastVisit: jan7_800, title: "moz"},
+
+   // Test subdomain not inclued at the leading time edge
+   {isInQuery: false, isVisit: true, isDetails: true,
+    uri: "http://mail.foo.com/yiihah", title: "moz", lastVisit: jan6_815},
+
+  // Test https protocol
+  {isInQuery: false, isVisit: true, isDetails: true, title: "moz",
+   uri: "https://foo.com/", lastVisit: jan15_2045},
+
+   // Test ftp protocol
+   {isInQuery: false, isVisit: true, isDetails: true,
+    uri: "ftp://foo.com/ftp", lastVisit: jan12_1730,
+    title: "hugelongconfmozlagurationofwordswithasearchtermsinit whoo-hoo"},
+
+  // Test too early
+  {isInQuery: false, isVisit:true, isDetails: true, title: "moz",
+   uri: "http://foo.com/tooearly.php", lastVisit: jan6_700},
+
+  // Test Bad Annotation
+  {isInQuery: false, isVisit:true, isDetails: true, isPageAnnotation: true,
+   title: "moz", uri: "http://foo.com/badanno.htm", lastVisit: jan12_1730,
+   annoName: badAnnoName, annoVal: val},
+
+  // Test afterward, one to update
+  {isInQuery: false, isVisit:true, isDetails: true, title: "changeme",
+   uri: "http://foo.com/changeme1.htm", lastVisit: jan12_1730},
+
+  // Test invalid title
+  {isInQuery: false, isVisit:true, isDetails: true, title: "changeme2",
+   uri: "http://foo.com/changeme2.htm", lastVisit: jan7_800},
+
+  // Test changing the lastVisit
+  {isInQuery: false, isVisit:true, isDetails: true, title: "moz",
+   uri: "http://foo.com/changeme3.htm", lastVisit: dec27_800}];
+
+/**
+ * This test will test a Query using several terms and do a bit of negative
+ * testing for items that should be ignored while querying over history.
+ * The Query:WHERE absoluteTime(matches) AND searchTerms AND URI
+ *                 AND annotationIsNot(match) GROUP BY Domain, Day SORT BY uri,ascending
+ *                 excludeITems(should be ignored)
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_abstime_annotation_uri()
+{
+  // Initialize database
+  yield task_populateDB(testData);
+
+  // Query
+  var query = PlacesUtils.history.getNewQuery();
+  query.beginTime = beginTime;
+  query.endTime = endTime;
+  query.beginTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.endTimeReference = PlacesUtils.history.TIME_RELATIVE_EPOCH;
+  query.searchTerms = "moz";
+  query.uri = uri("http://foo.com");
+  query.annotation = "text/foo";
+  query.annotationIsNot = true;
+
+  // Options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = options.SORT_BY_URI_ASCENDING;
+  options.resultType = options.RESULTS_AS_URI;
+  // The next two options should be ignored
+  // can't use this one, breaks test - bug 419779
+  // options.excludeItems = true;
+
+  // Results
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+
+  // Ensure the result set is correct
+  compareArrayToResult(testData, root);
+
+  // live update.
+  do_print("change title");
+  var change1 = [{isDetails: true, uri:"http://foo.com/",
+                  title: "mo"}, ];
+  yield task_populateDB(change1);
+  do_check_false(isInResult({uri: "http://foo.com/"}, root));
+
+  var change2 = [{isDetails: true, uri:"http://foo.com/",
+                  title: "moz", lastvisit: endTime}, ];
+  yield task_populateDB(change2);
+  dump_table("moz_places");
+  do_check_false(isInResult({uri: "http://foo.com/"}, root));
+
+  // Let's delete something from the result set - using annotation
+  var change3 = [{isPageAnnotation: true,
+                  uri: "http://foo.com/",
+                  annoName: badAnnoName, annoVal: "test"}];
+  yield task_populateDB(change3);
+  do_print("LiveUpdate by removing annotation");
+  do_check_false(isInResult({uri: "http://foo.com/"}, root));
+
+  root.containerOpen = false;
+});
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 000000000..0ec99f8fc
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_async.js
@@ -0,0 +1,371 @@
+/* -*- 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: function (node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+    },
+
+    opened: function (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: function (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: function (node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkState("closed", 0);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+    },
+
+    opened: function (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: function (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: function (node, newState, oldState) {
+      this.checkStateChanged("loading", 1);
+      this.checkArgs("loading", node, oldState, node.STATE_CLOSED);
+      print("Closing container");
+      node.containerOpen = false;
+    },
+
+    opened: function (node, newState, oldState) {
+      do_throw("opened should not be called");
+    },
+
+    closed: function (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.defer();
+}
+
+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: function (aNewState, aNode, aOldState, aExpectOldState) {
+    print("Node passed on " + aNewState + " should be result.root");
+    do_check_eq(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.
+    do_check_true(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: function (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: function (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 + ")");
+    }
+    do_check_true(cnt >= aExpectedMin && cnt <= aExpectedMax);
+    return cnt;
+  },
+
+  /**
+   * Asynchronously opens the root of the test's result.
+   */
+  openContainer: function () {
+    // 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: function (container, oldState, newState) {
+        print("New state passed to containerStateChanged() should equal the " +
+              "container's current state");
+        do_check_eq(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, false);
+
+    print("Opening container");
+    this.result.root.containerOpen = true;
+  },
+
+  /**
+   * Starts the test and returns a promise resolved when the test completes.
+   */
+  run: function () {
+    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.
+   */
+  setup: function*() {
+    // 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" }
+    ]);
+    yield task_populateDB(this.data);
+
+    // Make a query.
+    this.query = PlacesUtils.history.getNewQuery();
+    this.query.setFolders([DataHelper.defaults.bookmark.parent], 1);
+    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: function () {
+    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: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder,
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+      uri: "http://example.com/",
+      title: "test bookmark"
+    },
+
+    folder: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder,
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+      title: "test folder"
+    },
+
+    separator: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder,
+      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;
+  }
+};
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_async()
+{
+  for (let test of tests) {
+    yield PlacesUtils.bookmarks.eraseEverything();
+
+    test.__proto__ = new Test();
+    yield test.setup();
+
+    print("------ Running test: " + test.desc);
+    yield test.run();
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  print("All tests done, exiting");
+});
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 000000000..ab9f2bf90
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_containersQueries_sorting.js
@@ -0,0 +1,411 @@
+/* -*- 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 hs = Cc["@mozilla.org/browser/nav-history-service;1"].
+         getService(Ci.nsINavHistoryService);
+var bh = hs.QueryInterface(Ci.nsIBrowserHistory);
+var tagging = Cc["@mozilla.org/browser/tagging-service;1"].
+              getService(Ci.nsITaggingService);
+
+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_TAG_QUERY, name: "RESULTS_AS_TAG_QUERY"},
+];
+
+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) {
+  do_check_eq(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_TAG_QUERY &&
+      (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_TAG_QUERY) {
+    // 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 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);
+
+      // 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;
+      }
+    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);
+    do_check_eq(sortedResults[i].title, results[i].title);
+  }
+}
+
+// Main
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(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 }));
+  yield task_populateDB(visits);
+
+  cartProd([resultTypes, sortingModes], test_query_callback);
+});
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 000000000..fbbacf6c9
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_history_queries_tags_liveUpdate.js
@@ -0,0 +1,200 @@
+/* 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;
+}
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_initialize()
+{
+  yield task_populateDB(gTestData);
+});
+
+add_task(function pages_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);
+      do_check_eq(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, null);
+    }
+  });
+});
+
+add_task(function visits_query()
+{
+  let [query, options] = newQueryWithOptions();
+  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);
+      do_check_eq(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, null);
+    }
+  });
+});
+
+add_task(function bookmarks_query()
+{
+  let [query, options] = newQueryWithOptions();
+  query.setFolders([PlacesUtils.unfiledBookmarksFolderId], 1);
+  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);
+      do_check_eq(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, null);
+    }
+  });
+});
+
+add_task(function pages_searchterm_query()
+{
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "example";
+  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);
+      do_check_eq(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, null);
+    }
+  });
+});
+
+add_task(function visits_searchterm_query()
+{
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "example";
+  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);
+      do_check_eq(node.tags, null);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, "test-tag");
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      do_check_eq(node.tags, null);
+    }
+  });
+});
+
+add_task(function pages_searchterm_is_tag_query()
+{
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "test-tag";
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([], root);
+    gTestData.forEach(function (data) {
+      let uri = NetUtil.newURI(data.uri);
+      PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
+                                           uri,
+                                           PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                           data.title);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      compareArrayToResult([data], root);
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      compareArrayToResult([], root);
+    });
+  });
+});
+
+add_task(function visits_searchterm_is_tag_query()
+{
+  let [query, options] = newQueryWithOptions();
+  query.searchTerms = "test-tag";
+  options.resultType = Ci.nsINavHistoryQueryOptions.RESULTS_AS_VISIT;
+  testQueryContents(query, options, function (root) {
+    compareArrayToResult([], root);
+    gTestData.forEach(function (data) {
+      let uri = NetUtil.newURI(data.uri);
+      PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
+                                           uri,
+                                           PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                           data.title);
+      PlacesUtils.tagging.tagURI(uri, ["test-tag"]);
+      compareArrayToResult([data], root);
+      PlacesUtils.tagging.untagURI(uri, ["test-tag"]);
+      compareArrayToResult([], root);
+    });
+  });
+});
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 000000000..eec87fe0e
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_history_queries_titles_liveUpdate.js
@@ -0,0 +1,210 @@
+/* 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() ];
+}
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* pages_query()
+{
+  yield 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);
+    do_check_eq(node.title, gTestData[i].title);
+    let uri = NetUtil.newURI(node.uri);
+    yield PlacesTestUtils.addVisits({uri: uri, title: "changedTitle"});
+    do_check_eq(node.title, "changedTitle");
+    yield PlacesTestUtils.addVisits({uri: uri, title: gTestData[i].title});
+    do_check_eq(node.title, gTestData[i].title);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* visits_query()
+{
+  yield 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);
+    do_check_eq(node.title, testData.title);
+    yield PlacesTestUtils.addVisits({uri: uri, title: "changedTitle"});
+    node = searchNodeHavingUrl(root, testData.uri);
+    do_check_eq(node.title, "changedTitle");
+    yield PlacesTestUtils.addVisits({uri: uri, title: testData.title});
+    node = searchNodeHavingUrl(root, testData.uri);
+    do_check_eq(node.title, testData.title);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* pages_searchterm_query()
+{
+  yield 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);
+    do_check_eq(node.title, gTestData[i].title);
+    yield PlacesTestUtils.addVisits({uri: uri, title: "changedTitle"});
+    do_check_eq(node.title, "changedTitle");
+    yield PlacesTestUtils.addVisits({uri: uri, title: gTestData[i].title});
+    do_check_eq(node.title, gTestData[i].title);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* visits_searchterm_query()
+{
+  yield 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);
+    do_check_eq(node.title, testData.title);
+    yield PlacesTestUtils.addVisits({uri: uri, title: "changedTitle"});
+    node = searchNodeHavingUrl(root, testData.uri);
+    do_check_eq(node.title, "changedTitle");
+    yield PlacesTestUtils.addVisits({uri: uri, title: testData.title});
+    node = searchNodeHavingUrl(root, testData.uri);
+    do_check_eq(node.title, testData.title);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* pages_searchterm_is_title_query()
+{
+  yield 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";
+    yield PlacesTestUtils.addVisits({ uri: uri, title: data.title,
+                                      visitDate: data.lastVisit });
+    compareArrayToResult([data], root);
+    data.title = origTitle;
+    yield PlacesTestUtils.addVisits({ uri: uri, title: data.title,
+                                      visitDate: data.lastVisit });
+    compareArrayToResult([], root);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* visits_searchterm_is_title_query()
+{
+  yield 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";
+    yield PlacesTestUtils.addVisits({ uri: uri, title: data.title,
+                                      visitDate: data.lastVisit });
+    compareArrayToResult([data], root);
+    data.title = origTitle;
+    yield PlacesTestUtils.addVisits({ uri: uri, title: data.title,
+                                      visitDate: data.lastVisit });
+    compareArrayToResult([], root);
+  }
+
+  root.containerOpen = false;
+  yield PlacesTestUtils.clearHistory();
+});
diff --git a/toolkit/components/places/tests/queries/test_onlyBookmarked.js b/toolkit/components/places/tests/queries/test_onlyBookmarked.js
new file mode 100644
index 000000000..45704c109
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_onlyBookmarked.js
@@ -0,0 +1,128 @@
+/* -*- 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 next thing we do is create a test database for us.  Each test runs with
+ * its own database (tail_queries.js will clear it after the run).  Take a look
+ * at the queryData object in head_queries.js, and you'll see how this object
+ * works.  You can call it anything you like, but I usually use "testData".
+ * I'll include a couple of example entries in the database.
+ *
+ * Note that to use the compareArrayToResult API, you need to put all the
+ * results that are in the query set at the top of the testData list, and those
+ * results MUST be in the same sort order as the items in the resulting query.
+ */
+
+var testData = [
+  // Add a bookmark that should be in the results
+  { isBookmark: true,
+    uri: "http://bookmarked.com/",
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    isInQuery: true },
+
+  // Add a bookmark that should not be in the results
+  { isBookmark: true,
+    uri: "http://bookmarked-elsewhere.com/",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    isInQuery: false },
+
+  // Add an un-bookmarked visit
+  { isVisit: true,
+    uri: "http://notbookmarked.com/",
+    isInQuery: false }
+];
+
+
+/**
+ * run_test is where the magic happens.  This is automatically run by the test
+ * harness.  It is where you do the work of creating the query, running it, and
+ * playing with the result set.
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_onlyBookmarked()
+{
+  // This function in head_queries.js creates our database with the above data
+  yield task_populateDB(testData);
+
+  // Query
+  var query = PlacesUtils.history.getNewQuery();
+  query.setFolders([PlacesUtils.toolbarFolderId], 1);
+  query.onlyBookmarked = true;
+
+  // query options
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.queryType = options.QUERY_TYPE_HISTORY;
+
+  // 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;
+
+  // You can use this to compare the data in the array with the result set,
+  // if the array's isInQuery: true items are sorted the same way as the result
+  // set.
+  do_print("begin first test");
+  compareArrayToResult(testData, root);
+  do_print("end first test");
+
+  // Test live-update
+  var liveUpdateTestData = [
+    // Add a bookmark that should show up
+    { isBookmark: true,
+      uri: "http://bookmarked2.com/",
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      isInQuery: true },
+
+    // Add a bookmark that should not show up
+    { isBookmark: true,
+      uri: "http://bookmarked-elsewhere2.com/",
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      isInQuery: false }
+  ];
+
+  yield task_populateDB(liveUpdateTestData); // add to the db
+
+  // add to the test data
+  testData.push(liveUpdateTestData[0]);
+  testData.push(liveUpdateTestData[1]);
+
+  // re-query and test
+  do_print("begin live-update test");
+  compareArrayToResult(testData, root);
+  do_print("end live-update test");
+/*
+  // we are actually not updating during a batch.
+  // see bug 432706 for details.
+
+  // Here's a batch update
+  var updateBatch = {
+    runBatched: function (aUserData) {
+      liveUpdateTestData[0].uri = "http://bookmarked3.com";
+      liveUpdateTestData[1].uri = "http://bookmarked-elsewhere3.com";
+      populateDB(liveUpdateTestData);
+      testData.push(liveUpdateTestData[0]);
+      testData.push(liveUpdateTestData[1]);
+    }
+  };
+
+  PlacesUtils.history.runInBatchMode(updateBatch, null);
+
+  // re-query and test
+  do_print("begin batched test");
+  compareArrayToResult(testData, root);
+  do_print("end batched test");
+*/
+  // Close the container when finished
+  root.containerOpen = false;
+});
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 000000000..694728a43
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_queryMultipleFolder.js
@@ -0,0 +1,65 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+function run_test() {
+  run_next_test();
+}
+
+add_task(function* test_queryMultipleFolders() {
+  // adding bookmarks in the folders
+  let folderIds = [];
+  let bookmarkIds = [];
+  for (let i = 0; i < 3; ++i) {
+    let folder = yield PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      title: `Folder${i}`
+    });
+    folderIds.push(yield PlacesUtils.promiseItemId(folder.guid));
+
+    for (let j = 0; j < 7; ++j) {
+      let bm = yield PlacesUtils.bookmarks.insert({
+        parentGuid: (yield PlacesUtils.promiseItemGuid(folderIds[i])),
+        url: `http://Bookmark${i}_${j}.com`,
+        title: ""
+      });
+      bookmarkIds.push(yield PlacesUtils.promiseItemId(bm.guid));
+    }
+  }
+
+  // using queryStringToQueries
+  let query = {};
+  let options = {};
+  let maxResults = 20;
+  let queryString = "place:" + folderIds.map((id) => {
+    return "folder=" + id;
+  }).join('&') + "&sort=5&maxResults=" + maxResults;
+  PlacesUtils.history.queryStringToQueries(queryString, query, {}, options);
+  let rootNode = PlacesUtils.history.executeQuery(query.value[0], 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(bookmarkIds[i], node.itemId, node.uri);
+  }
+  rootNode.containerOpen = false;
+
+  // using getNewQuery and getNewQueryOptions
+  query = PlacesUtils.history.getNewQuery();
+  options = PlacesUtils.history.getNewQueryOptions();
+  query.setFolders(folderIds, folderIds.length);
+  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(bookmarkIds[i], node.itemId, 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 000000000..24cf8aa9b
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_querySerialization.js
@@ -0,0 +1,797 @@
+/* -*- 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.
+ *
+ * Second, we need to also test serialization of multiple nsINavHistoryQuery
+ * objects at once.  To do this, we remember the previous NUM_MULTIPLE_QUERIES
+ * queries we tested individually and then serialize them together.  We do this
+ * each time we test an individual query.  Thus the set of queries we test
+ * together loses one query and gains another each time.
+ *
+ * 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.
+ *       - For each of the previous NUM_MULTIPLE_QUERIES
+ *         nsINavHistoryQueryOptions objects o we created:
+ *         - Serialize the previous NUM_MULTIPLE_QUERIES nsINavHistoryQuery
+ *           objects together with o.
+ *         - 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;
+
+const NUM_MULTIPLE_QUERIES        = 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");
+      },
+    ]
+  },
+  // hasAnnotation
+  {
+    flag:        "hasAnnotation",
+    subswitches: ["annotation", "annotationIsNot"],
+    desc:        "nsINavHistoryQuery.hasAnnotation",
+    matches:     flagSwitchMatches,
+    runs:        [
+      function (aQuery, aQueryOptions) {
+        aQuery.annotation = "bookmarks/toolbarFolder";
+        aQuery.annotationIsNot = false;
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.annotation = "bookmarks/toolbarFolder";
+        aQuery.annotationIsNot = true;
+      }
+    ]
+  },
+  // 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
+      }
+    ]
+  },
+  // onlyBookmarked
+  {
+    property: "onlyBookmarked",
+    desc:     "nsINavHistoryQuery.onlyBookmarked",
+    matches:  simplePropertyMatches,
+    runs:     [
+      function (aQuery, aQueryOptions) {
+        aQuery.onlyBookmarked = true;
+      }
+    ]
+  },
+  // getFolders
+  {
+    desc:    "nsINavHistoryQuery.getFolders",
+    matches: function (aQuery1, aQuery2) {
+      var q1Folders = aQuery1.getFolders();
+      var q2Folders = aQuery2.getFolders();
+      if (q1Folders.length !== q2Folders.length)
+        return false;
+      for (let i = 0; i < q1Folders.length; i++) {
+        if (q2Folders.indexOf(q1Folders[i]) < 0)
+          return false;
+      }
+      for (let i = 0; i < q2Folders.length; i++) {
+        if (q1Folders.indexOf(q2Folders[i]) < 0)
+          return false;
+      }
+      return true;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.setFolders([], 0);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setFolders([PlacesUtils.placesRootId], 1);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setFolders([PlacesUtils.placesRootId, PlacesUtils.tagsFolderId], 2);
+      }
+    ]
+  },
+  // tags
+  {
+    desc:    "nsINavHistoryQuery.getTags",
+    matches: function (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.indexOf(q1Tags[i]) < 0)
+          return false;
+      }
+      for (let i = 0; i < q2Tags.length; i++) {
+        if (q1Tags.indexOf(q2Tags[i]) < 0)
+          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: function (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.indexOf(q1Trans[i]) < 0)
+          return false;
+      }
+      for (let i = 0; i < q2Trans.length; i++) {
+        if (q1Trans.indexOf(q2Trans[i]) < 0)
+          return false;
+      }
+      return true;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([], 0);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([Ci.nsINavHistoryService.TRANSITION_DOWNLOAD],
+                              1);
+      },
+      function (aQuery, aQueryOptions) {
+        aQuery.setTransitions([Ci.nsINavHistoryService.TRANSITION_TYPED,
+                               Ci.nsINavHistoryService.TRANSITION_BOOKMARK], 2);
+      }
+    ]
+  },
+];
+
+// nsINavHistoryQueryOptions switches
+const queryOptionSwitches = [
+  // sortingMode
+  {
+    desc:    "nsINavHistoryQueryOptions.sortingMode",
+    matches: function (aOptions1, aOptions2) {
+      if (aOptions1.sortingMode === aOptions2.sortingMode) {
+        switch (aOptions1.sortingMode) {
+          case aOptions1.SORT_BY_ANNOTATION_ASCENDING:
+          case aOptions1.SORT_BY_ANNOTATION_DESCENDING:
+            return aOptions1.sortingAnnotation === aOptions2.sortingAnnotation;
+        }
+        return true;
+      }
+      return false;
+    },
+    runs: [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.sortingMode = aQueryOptions.SORT_BY_DATE_ASCENDING;
+      },
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.sortingMode = aQueryOptions.SORT_BY_ANNOTATION_ASCENDING;
+        aQueryOptions.sortingAnnotation = "bookmarks/toolbarFolder";
+      }
+    ]
+  },
+  // resultType
+  {
+    // property is used by function simplePropertyMatches.
+    property: "resultType",
+    desc:     "nsINavHistoryQueryOptions.resultType",
+    matches:  simplePropertyMatches,
+    runs:     [
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.resultType = aQueryOptions.RESULTS_AS_URI;
+      },
+      function (aQuery, aQueryOptions) {
+        aQueryOptions.resultType = aQueryOptions.RESULTS_AS_FULL_VISIT;
+      }
+    ]
+  },
+  // 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_UNIFIED;
+      }
+    ]
+  },
+];
+
+/**
+ * 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);
+  var prevQueries = [];
+  var prevOpts = [];
+
+  // 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);
+
+        // Test the previous NUM_MULTIPLE_QUERIES queries together.
+        prevQueries.push(query);
+        prevOpts.push(opts);
+        if (prevQueries.length >= NUM_MULTIPLE_QUERIES) {
+          // We can serialize multiple nsINavHistoryQuery objects together but
+          // only one nsINavHistoryQueryOptions object with them.  So, test each
+          // of the previous NUM_MULTIPLE_QUERIES nsINavHistoryQueryOptions.
+          for (let i = 0; i < prevOpts.length; i++) {
+            serializeDeserialize(prevQueries, prevOpts[i]);
+          }
+          prevQueries.shift();
+          prevOpts.shift();
+        }
+      });
+    });
+  }
+  print("\n");
+}
+
+/**
+ * Serializes the nsINavHistoryQuery objects in aQueryArr and the
+ * nsINavHistoryQueryOptions object aQueryOptions, de-serializes the
+ * serialization, and ensures (using do_check_* functions) that the
+ * de-serialized objects equal the originals.
+ *
+ * @param aQueryArr
+ *        an array containing nsINavHistoryQuery objects
+ * @param aQueryOptions
+ *        an nsINavHistoryQueryOptions object
+ */
+function serializeDeserialize(aQueryArr, aQueryOptions)
+{
+  var queryStr = PlacesUtils.history.queriesToQueryString(aQueryArr,
+                                                        aQueryArr.length,
+                                                        aQueryOptions);
+  print("  " + queryStr);
+  var queryArr2 = {};
+  var opts2 = {};
+  PlacesUtils.history.queryStringToQueries(queryStr, queryArr2, {}, opts2);
+  queryArr2 = queryArr2.value;
+  opts2 = opts2.value;
+
+  // The two sets of queries cannot be the same if their lengths differ.
+  do_check_eq(aQueryArr.length, queryArr2.length);
+
+  // Although the query serialization code as it is written now practically
+  // ensures that queries appear in the query string in the same order they
+  // appear in both the array to be serialized and the array resulting from
+  // de-serialization, the interface does not guarantee any ordering.  So, for
+  // each query in aQueryArr, find its equivalent in queryArr2 and delete it
+  // from queryArr2.  If queryArr2 is empty after looping through aQueryArr,
+  // the two sets of queries are equal.
+  for (let i = 0; i < aQueryArr.length; i++) {
+    let j = 0;
+    for (; j < queryArr2.length; j++) {
+      if (queryObjsEqual(querySwitches, aQueryArr[i], queryArr2[j]))
+        break;
+    }
+    if (j < queryArr2.length)
+      queryArr2.splice(j, 1);
+  }
+  do_check_eq(queryArr2.length, 0);
+
+  // Finally check the query options objects.
+  do_check_true(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_redirects.js b/toolkit/components/places/tests/queries/test_redirects.js
new file mode 100644
index 000000000..1be5a626f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_redirects.js
@@ -0,0 +1,311 @@
+/* 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.
+  do_check_eq(aSequence.length, 3);
+  let includeHidden = aSequence[0];
+  let maxResults = aSequence[1];
+  let sortingMode = aSequence[2];
+  print("\nTESTING: 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 == 0)
+        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;
+}
+
+function run_test()
+{
+  run_next_test();
+}
+
+/**
+ * Populate the visits array and add visits to the database.
+ * We will generate visit-chains like:
+ *   visit -> redirect_temp -> redirect_perm
+ */
+add_task(function* test_add_visits_to_database()
+{
+  yield 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.
+    // TODO: Bug 488966 could fix this behavior.
+    //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.
+  yield task_populateDB(visits);
+});
+
+add_task(function* test_redirects()
+{
+  // Frecency and hidden are updated asynchronously, wait for them.
+  yield 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 and most visited smart bookmark.
+  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);
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+
+  yield PlacesTestUtils.clearHistory();
+});
diff --git a/toolkit/components/places/tests/queries/test_results-as-tag-contents-query.js b/toolkit/components/places/tests/queries/test_results-as-tag-contents-query.js
new file mode 100644
index 000000000..f1cbfd4d8
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-tag-contents-query.js
@@ -0,0 +1,127 @@
+/* -*- 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 = [
+  { isInQuery: true,
+    isDetails: true,
+    title: "bmoz",
+    uri: "http://foo.com/",
+    isBookmark: true,
+    isTag: true,
+    tagArray: ["bugzilla"] },
+
+  { isInQuery: true,
+    isDetails: true,
+    title: "C Moz",
+    uri: "http://foo.com/changeme1.html",
+    isBookmark: true,
+    isTag: true,
+    tagArray: ["moz", "bugzilla"] },
+
+  { isInQuery: false,
+    isDetails: true,
+    title: "amo",
+    uri: "http://foo2.com/",
+    isBookmark: true,
+    isTag: true,
+    tagArray: ["moz"] },
+
+  { isInQuery: false,
+    isDetails: true,
+    title: "amo",
+    uri: "http://foo.com/changeme2.html",
+    isBookmark: true },
+];
+
+function getIdForTag(aTagName) {
+  var id = -1;
+  var query = PlacesUtils.history.getNewQuery();
+  query.setFolders([PlacesUtils.tagsFolderId], 1);
+  var options = PlacesUtils.history.getNewQueryOptions();
+  var root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+  var cc = root.childCount;
+  do_check_eq(root.childCount, 2);
+  for (let i = 0; i < cc; i++) {
+    let node = root.getChild(i);
+    if (node.title == aTagName) {
+      id = node.itemId;
+      break;
+    }
+  }
+  root.containerOpen = false;
+  return id;
+}
+
+ /**
+  * This test will test Queries that use relative search terms and URI options
+  */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_results_as_tag_contents_query()
+{
+  yield task_populateDB(testData);
+
+  // Get tag id.
+  let tagId = getIdForTag("bugzilla");
+  do_check_true(tagId > 0);
+
+  var options = PlacesUtils.history.getNewQueryOptions();
+  options.resultType = options.RESULTS_AS_TAG_CONTENTS;
+  var query = PlacesUtils.history.getNewQuery();
+  query.setFolders([tagId], 1);
+
+  var root = PlacesUtils.history.executeQuery(query, options).root;
+  root.containerOpen = true;
+
+  displayResultSet(root);
+  // Cannot use compare array to results, since results ordering is hardcoded
+  // and depending on lastModified (that could have VM timers issues).
+  testData.forEach(function(aEntry) {
+    if (aEntry.isInResult)
+      do_check_true(isInResult({uri: "http://foo.com/added.html"}, root));
+  });
+
+  // If that passes, check liveupdate
+  // Add to the query set
+  var change1 = { isVisit: true,
+                  isDetails: true,
+                  uri: "http://foo.com/added.html",
+                  title: "mozadded",
+                  isBookmark: true,
+                  isTag: true,
+                  tagArray: ["moz", "bugzilla"] };
+  do_print("Adding item to query");
+  yield task_populateDB([change1]);
+  do_print("These results should have been LIVE UPDATED with the new addition");
+  displayResultSet(root);
+  do_check_true(isInResult(change1, root));
+
+  // Add one by adding a tag, remove one by removing search term.
+  do_print("Updating items");
+  var change2 = [{ isDetails: true,
+                   uri: "http://foo3.com/",
+                   title: "foo"},
+                 { isDetails: true,
+                   uri: "http://foo.com/changeme2.html",
+                   title: "zydeco",
+                   isBookmark:true,
+                   isTag: true,
+                   tagArray: ["bugzilla", "moz"] }];
+  yield task_populateDB(change2);
+  do_check_false(isInResult({uri: "http://fooz.com/"}, root));
+  do_check_true(isInResult({uri: "http://foo.com/changeme2.html"}, root));
+
+  // Test removing a tag updates us.
+  do_print("Deleting item");
+  PlacesUtils.tagging.untagURI(uri("http://foo.com/changeme2.html"), ["bugzilla"]);
+  do_check_false(isInResult({uri: "http://foo.com/changeme2.html"}, root));
+
+  root.containerOpen = false;
+});
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 000000000..d0f270bd2
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_results-as-visit.js
@@ -0,0 +1,119 @@
+/* -*- 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 > 0,
+                      tagArray: aPage.tags });
+    }
+  }
+
+  var pages = [
+    { uri: "http://foo.com/", title: "amo", tags: ["moz"], visitCount: 3, inQuery: true },
+    { 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
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_results_as_visit()
+{
+   createTestData();
+   yield 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;
+
+   do_print("Number of items in result set: " + root.childCount);
+   for (let i=0; i < root.childCount; ++i) {
+     do_print("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
+   do_print("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" });
+   }
+   yield task_populateDB(tmp);
+   for (let i=0; i < 2; i++)
+     do_check_eq(root.getChild(i).title, "ab moz");
+
+   // Update an existing URI
+   do_print("Updating Item");
+   var change2 = [{ isVisit: true,
+                    title: "moz",
+                    uri: "http://foo.mail.com/changeme2.html" }];
+   yield task_populateDB(change2);
+   do_check_true(isInResult(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.
+   do_print("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"] }];
+   yield task_populateDB(change3);
+   do_check_false(isInResult({uri: "http://foo.mail.com/changeme1.html"}, root));
+   do_check_true(isInResult({uri: "http://foo.mail.com/changeme3.html"}, root));
+
+   // And now, delete one
+   do_print("Delete item outside of batch");
+   var change4 = [{ isVisit: true,
+                    lastVisit: newTimeInMicroseconds(),
+                    uri: "http://moilla.com/",
+                    title: "mo,z" }];
+   yield task_populateDB(change4);
+   do_check_false(isInResult(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 000000000..038367c0b
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js
@@ -0,0 +1,84 @@
+/* -*- 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
+  }
+];
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_initalize()
+{
+  yield task_populateDB(VISITS);
+});
+
+add_task(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.
+    yield task_populateDB(HIDDEN_VISITS);
+    let cc_update = root.childCount;
+
+    root.containerOpen = false;
+
+    do_check_eq(cc, data.expectedResults);
+    do_check_eq(cc_update, data.expectedResults + (data.includeHidden ? 1 : 0));
+
+    PlacesUtils.bhistory.removePage(uri("http://hidden.example.com/"));
+  }
+});
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 000000000..7bd91f057
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-bookmarklets.js
@@ -0,0 +1,70 @@
+/* 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');"
+  }
+];
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_initalize()
+{
+  yield 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 000000000..4f42e7000
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-domain.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 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: true, 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
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_searchterms_domain()
+{
+  yield 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;
+
+  do_print("Number of items in result set: " + root.childCount);
+  for (var i=0; i < root.childCount; ++i) {
+    do_print("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
+  do_print("Adding item to query");
+  var change1 = [{isVisit: true, isDetails: true, uri: "http://foo.com/added.htm",
+                  title: "moz", transType: PlacesUtils.history.TRANSITION_LINK}];
+  yield task_populateDB(change1);
+  do_check_true(isInResult(change1, root));
+
+  // Update an existing URI
+  do_print("Updating Item");
+  var change2 = [{isDetails: true, uri: "http://foo.com/changeme1.htm",
+                  title: "moz" }];
+  yield task_populateDB(change2);
+  do_check_true(isInResult(change2, root));
+
+  // Add one and take one out of query set, and simply change one so that it
+  // still applies to the query.
+  do_print("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"}];
+  yield task_populateDB(change3);
+  do_check_true(isInResult({uri: "http://foo.com/changeme2.htm"}, root));
+  do_check_true(isInResult({uri: "http://mail.foo.com/yiihah"}, root));
+  do_check_false(isInResult({uri: "ftp://foo.com/ftp"}, root));
+
+  // And now, delete one
+  do_print("Deleting items");
+  var change4 = [{isDetails: true, uri: "https://foo.com/",
+                  title: "mo,z"}];
+  yield task_populateDB(change4);
+  do_check_false(isInResult(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 000000000..af4efe196
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_searchterms-uri.js
@@ -0,0 +1,87 @@
+/* -*- 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
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_searchterms_uri()
+{
+  yield 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;
+
+   do_print("Number of items in result set: " + root.childCount);
+   for (var i=0; i < root.childCount; ++i) {
+     do_print("result: " + root.getChild(i).uri + " Title: " + root.getChild(i).title);
+   }
+
+   // Check our inital result set
+   compareArrayToResult(testData, root);
+
+   // live update.
+   do_print("change title");
+   var change1 = [{isDetails: true, uri:"http://foo.com/",
+                   title: "mo"}, ];
+   yield task_populateDB(change1);
+
+   do_check_false(isInResult({uri: "http://foo.com/"}, root));
+   var change2 = [{isDetails: true, uri:"http://foo.com/",
+                   title: "moz"}, ];
+   yield task_populateDB(change2);
+   do_check_true(isInResult({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 000000000..7ca50e6de
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_sort-date-site-grouping.js
@@ -0,0 +1,225 @@
+/* -*- 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 domainsInRange = [2, 3];
+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]
+  }
+];
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_sort_date_site_grouping()
+{
+  yield 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 Components.classes);
+  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.
+  do_check_eq(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) {
+    yield 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;
+
+    do_check_true(PlacesUtils.nodeIsDay(node));
+    PlacesUtils.asQuery(node);
+    let queries = node.getQueries();
+    let options = node.queryOptions;
+
+    do_check_eq(queries.length, 1);
+    let query = queries[0];
+
+    do_check_true(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;
+
+    do_check_eq(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 queries = child.getQueries();
+    let options = child.queryOptions;
+
+    do_check_eq(queries.length, 1);
+    let query = queries[0];
+
+    do_check_true(query.hasDomain);
+    do_check_true(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 000000000..4d8e1146d
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_sorting.js
@@ -0,0 +1,1265 @@
+/* -*- 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,
+
+  *setup() {
+    do_print("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",
+        keyword: "b",
+        isInQuery: true },
+
+      { isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "z",
+        keyword: "a",
+        isInQuery: true },
+
+      { isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "x",
+        keyword: "c",
+        isInQuery: true },
+    ];
+
+    this._sortedData = this._unsortedData;
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    // no reverse sorting for SORT BY NONE
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_URI_ASCENDING,
+
+  *setup() {
+    do_print("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: "a",
+        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: "a",
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[4],
+      this._unsortedData[6],
+      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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_URI_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+    // add visits to increase visit count
+    yield 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: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_KEYWORD_ASCENDING,
+
+  *setup() {
+    do_print("Sorting test 6: SORT BY KEYWORD");
+
+    this._unsortedData = [
+      { isBookmark: true,
+        uri: "http://example.com/a",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "z",
+        keyword: "a",
+        isInQuery: true },
+
+      { isBookmark: true,
+        uri: "http://example.com/c",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "x",
+        keyword: "c",
+        isInQuery: true },
+
+      { isBookmark: true,
+        uri: "http://example.com/b1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "y9",
+        keyword: "b",
+        isInQuery: true },
+
+      // without a keyword, should fall back to title
+      { isBookmark: true,
+        uri: "http://example.com/null2",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "null8",
+        keyword: null,
+        isInQuery: true },
+
+      // without a keyword, should fall back to title
+      { isBookmark: true,
+        uri: "http://example.com/null1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "null9",
+        keyword: null,
+        isInQuery: true },
+
+      // if keywords are equal, should fall back to title
+      { isBookmark: true,
+        uri: "http://example.com/b1",
+        parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+        title: "y8",
+        keyword: "b",
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[3],
+      this._unsortedData[4],
+      this._unsortedData[0],
+      this._unsortedData[5],
+      this._unsortedData[2],
+      this._unsortedData[1],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_KEYWORD_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_LASTMODIFIED_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_LASTMODIFIED_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_TAGS_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+    query.setFolders([PlacesUtils.bookmarks.toolbarFolder], 1);
+    query.onlyBookmarked = true;
+
+    // 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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_TAGS_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+// SORT_BY_ANNOTATION_* (int32)
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_ASCENDING,
+
+  *setup() {
+    do_print("Sorting test 10: SORT BY ANNOTATION (int32)");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      { isVisit: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds,
+        uri: "http://example.com/b1",
+        title: "y1",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 2,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds,
+        uri: "http://example.com/a",
+        title: "z",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 1,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds,
+        uri: "http://example.com/c",
+        title: "x",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 3,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      // if annotations are equal, should fall back to title
+      { isVisit: true,
+        isDetails: true,
+        lastVisit: timeInMicroseconds,
+        uri: "http://example.com/b2",
+        title: "y2",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 2,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[3],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingAnnotation = "sorting";
+    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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+// SORT_BY_ANNOTATION_* (int64)
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_ASCENDING,
+
+  *setup() {
+    do_print("Sorting test 11: SORT BY ANNOTATION (int64)");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: timeInMicroseconds,
+        title: "I",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 0xffffffff1,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://is.com/",
+        lastVisit: timeInMicroseconds,
+        title: "love",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 0xffffffff0,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://best.com/",
+        lastVisit: timeInMicroseconds,
+        title: "moz",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 0xffffffff2,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingAnnotation = "sorting";
+    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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+// SORT_BY_ANNOTATION_* (string)
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_ASCENDING,
+
+  *setup() {
+    do_print("Sorting test 12: SORT BY ANNOTATION (string)");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: timeInMicroseconds,
+        title: "I",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: "a",
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://is.com/",
+        lastVisit: timeInMicroseconds,
+        title: "love",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: "",
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://best.com/",
+        lastVisit: timeInMicroseconds,
+        title: "moz",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: "z",
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingAnnotation = "sorting";
+    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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+// SORT_BY_ANNOTATION_* (double)
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_ASCENDING,
+
+  *setup() {
+    do_print("Sorting test 13: SORT BY ANNOTATION (double)");
+
+    var timeInMicroseconds = Date.now() * 1000;
+    this._unsortedData = [
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://moz.com/",
+        lastVisit: timeInMicroseconds,
+        title: "I",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 1.2,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://is.com/",
+        lastVisit: timeInMicroseconds,
+        title: "love",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 1.1,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+
+      { isVisit: true,
+        isDetails: true,
+        uri: "http://best.com/",
+        lastVisit: timeInMicroseconds,
+        title: "moz",
+        isPageAnnotation: true,
+        annoName: "sorting",
+        annoVal: 1.3,
+        annoFlags: 0,
+        annoExpiration: Ci.nsIAnnotationService.EXPIRE_NEVER,
+        isInQuery: true },
+    ];
+
+    this._sortedData = [
+      this._unsortedData[1],
+      this._unsortedData[0],
+      this._unsortedData[2],
+    ];
+
+    // This function in head_queries.js creates our database with the above data
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    // Query
+    var query = PlacesUtils.history.getNewQuery();
+
+    // query options
+    var options = PlacesUtils.history.getNewQueryOptions();
+    options.sortingAnnotation = "sorting";
+    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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_ANNOTATION_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+// SORT_BY_FRECENCY_*
+
+tests.push({
+  _sortingMode: Ci.nsINavHistoryQueryOptions.SORT_BY_FRECENCY_ASCENDING,
+
+  *setup() {
+    do_print("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
+    yield task_populateDB(this._unsortedData);
+  },
+
+  check: function() {
+    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: function() {
+    this._sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_FRECENCY_DESCENDING;
+    this._sortedData.reverse();
+    this.check();
+  }
+});
+
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_sorting()
+{
+  for (let test of tests) {
+    yield test.setup();
+    yield PlacesTestUtils.promiseAsyncUpdates();
+    test.check();
+    // sorting reversed, usually SORT_BY have ASC and DESC
+    test.check_reverse();
+    // Execute cleanup tasks
+    yield PlacesUtils.bookmarks.eraseEverything();
+    yield PlacesTestUtils.clearHistory();
+  }
+});
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 000000000..afda3f03f
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_tags.js
@@ -0,0 +1,743 @@
+/* -*- 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 and history queries with tags.  See bug 399799.
+ */
+
+"use strict";
+
+add_task(function* tags_getter_setter() {
+  do_print("Tags getter/setter should work correctly");
+  do_print("Without setting tags, tags getter should return empty array");
+  var [query] = makeQuery();
+  do_check_eq(query.tags.length, 0);
+
+  do_print("Setting tags to an empty array, tags getter should return "+
+           "empty array");
+  [query] = makeQuery([]);
+  do_check_eq(query.tags.length, 0);
+
+  do_print("Setting a few tags, tags getter should return correct array");
+  var tags = ["bar", "baz", "foo"];
+  [query] = makeQuery(tags);
+  setsAreEqual(query.tags, tags, true);
+
+  do_print("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(function* invalid_setter_calls() {
+  do_print("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(function* not_setting_tags() {
+  do_print("Not setting tags at all should not affect query URI");
+  checkQueryURI();
+});
+
+add_task(function* empty_array_tags() {
+  do_print("Setting tags with an empty array should not affect query URI");
+  checkQueryURI([]);
+});
+
+add_task(function* set_tags() {
+  do_print("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(function* no_tags_tagsAreNot() {
+  do_print("Not setting tags at all but setting tagsAreNot should " +
+           "affect query URI");
+  checkQueryURI(null, true);
+});
+
+add_task(function* empty_array_tags_tagsAreNot() {
+  do_print("Setting tags with an empty array and setting tagsAreNot " +
+           "should affect query URI");
+  checkQueryURI([], true);
+});
+
+add_task(function* () {
+  do_print("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(function* tag_to_uri() {
+  do_print("Querying history on tag associated with a URI should return " +
+           "that URI");
+  yield task_doWithVisit(["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(function* tags_to_uri() {
+  do_print("Querying history on many tags associated with a URI should " +
+           "return that URI");
+  yield task_doWithVisit(["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(function* repeated_tag() {
+  do_print("Specifying the same tag multiple times in a history query " +
+           "should not matter");
+  yield task_doWithVisit(["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(function* many_tags_no_uri() {
+  do_print("Querying history on many tags associated with a URI and " +
+           "tags not associated with that URI should not return that URI");
+  yield task_doWithVisit(["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(function* nonexistent_tags() {
+  do_print("Querying history on nonexistent tags should return no results");
+  yield task_doWithVisit(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["bogus"]);
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["bogus", "gnarly"]);
+    executeAndCheckQueryResults(query, opts, []);
+  });
+});
+
+add_task(function* tag_to_bookmark() {
+  do_print("Querying bookmarks on tag associated with a URI should " +
+           "return that URI");
+  yield task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["bar"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["baz"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(function* many_tags_to_bookmark() {
+  do_print("Querying bookmarks on many tags associated with a URI " +
+           "should return that URI");
+  yield task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "bar"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "baz"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["bar", "baz"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "bar", "baz"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(function* repeated_tag_to_bookmarks() {
+  do_print("Specifying the same tag multiple times in a bookmark query " +
+           "should not matter");
+  yield task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "foo"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+    [query, opts] = makeQuery(["foo", "foo", "foo", "bar", "bar", "baz"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, [aURI.spec]);
+  });
+});
+
+add_task(function* many_tags_no_bookmark() {
+  do_print("Querying bookmarks on many tags associated with a URI and " +
+           "tags not associated with that URI should not return that URI");
+  yield task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["foo", "bogus"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["foo", "bar", "bogus"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["foo", "bar", "baz", "bogus"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, []);
+  });
+});
+
+add_task(function* nonexistent_tags_bookmark() {
+  do_print("Querying bookmarks on nonexistent tag should return no results");
+  yield task_doWithBookmark(["foo", "bar", "baz"], function (aURI) {
+    var [query, opts] = makeQuery(["bogus"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, []);
+    [query, opts] = makeQuery(["bogus", "gnarly"]);
+    opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+    executeAndCheckQueryResults(query, opts, []);
+  });
+});
+
+add_task(function* tagsAreNot_history() {
+  do_print("Querying history using tagsAreNot should work correctly");
+  var urisAndTags = {
+    "http://example.com/1": ["foo", "bar"],
+    "http://example.com/2": ["baz", "qux"],
+    "http://example.com/3": null
+  };
+
+  do_print("Add visits and tag the URIs");
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    yield PlacesTestUtils.addVisits(nsiuri);
+    if (tags)
+      PlacesUtils.tagging.tagURI(nsiuri, tags);
+  }
+
+  do_print('  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"]);
+
+  do_print('  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"]);
+
+  do_print('  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"]);
+
+  do_print('  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"]);
+
+  do_print('  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);
+  }
+  yield task_cleanDatabase();
+});
+
+add_task(function* tagsAreNot_bookmarks() {
+  do_print("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
+  };
+
+  do_print("Add bookmarks and tag the URIs");
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    yield addBookmark(nsiuri);
+    if (tags)
+      PlacesUtils.tagging.tagURI(nsiuri, tags);
+  }
+
+  do_print('  Querying for "foo" should match only /2 and /3');
+  var [query, opts] = makeQuery(["foo"], true);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root,
+                  ["http://example.com/2", "http://example.com/3"]);
+
+  do_print('  Querying for "foo" and "bar" should match only /2 and /3');
+  [query, opts] = makeQuery(["foo", "bar"], true);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root,
+                  ["http://example.com/2", "http://example.com/3"]);
+
+  do_print('  Querying for "foo" and "bogus" should match only /2 and /3');
+  [query, opts] = makeQuery(["foo", "bogus"], true);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root,
+                  ["http://example.com/2", "http://example.com/3"]);
+
+  do_print('  Querying for "foo" and "baz" should match only /3');
+  [query, opts] = makeQuery(["foo", "baz"], true);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root,
+                  ["http://example.com/3"]);
+
+  do_print('  Querying for "bogus" should match all');
+  [query, opts] = makeQuery(["bogus"], true);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  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);
+  }
+  yield task_cleanDatabase();
+});
+
+add_task(function* duplicate_tags() {
+  do_print("Duplicate existing tags (i.e., multiple tag folders with " +
+           "same name) should not throw off query results");
+  var tagName = "foo";
+
+  do_print("Add bookmark and tag it normally");
+  yield addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, [tagName]);
+
+  do_print("Manually create tag folder with same name as tag and insert " +
+           "bookmark");
+  let dupTag = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.tagsGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    title: tagName
+  });
+
+  yield PlacesUtils.bookmarks.insert({
+    parentGuid: dupTag.guid,
+    title: "title",
+    url: TEST_URI
+  });
+
+  do_print("Querying for tag should match URI");
+  var [query, opts] = makeQuery([tagName]);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [TEST_URI.spec]);
+
+  PlacesUtils.tagging.untagURI(TEST_URI, [tagName]);
+  yield task_cleanDatabase();
+});
+
+add_task(function* folder_named_as_tag() {
+  do_print("Regular folders with the same name as tag should not throw " +
+           "off query results");
+  var tagName = "foo";
+
+  do_print("Add bookmark and tag it");
+  yield addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, [tagName]);
+
+  do_print("Create folder with same name as tag");
+  yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    title: tagName
+  });
+
+  do_print("Querying for tag should match URI");
+  var [query, opts] = makeQuery([tagName]);
+  opts.queryType = opts.QUERY_TYPE_BOOKMARKS;
+  queryResultsAre(PlacesUtils.history.executeQuery(query, opts).root, [TEST_URI.spec]);
+
+  PlacesUtils.tagging.untagURI(TEST_URI, [tagName]);
+  yield task_cleanDatabase();
+});
+
+add_task(function* ORed_queries() {
+  do_print("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);
+  }
+
+  do_print("Add visits and tag the URIs");
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    yield PlacesTestUtils.addVisits(nsiuri);
+    if (tags)
+      PlacesUtils.tagging.tagURI(nsiuri, tags);
+  }
+
+  do_print("Query for /1 OR query for /2 should match both /1 and /2");
+  var [query1, opts] = makeQuery(urisAndTags["http://example.com/1"]);
+  var [query2] = makeQuery(urisAndTags["http://example.com/2"]);
+  var root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1", "http://example.com/2"]);
+
+  do_print("Query for /1 OR query on bogus tag should match only /1");
+  [query1, opts] = makeQuery(urisAndTags["http://example.com/1"]);
+  [query2] = makeQuery(["bogus"]);
+  root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1"]);
+
+  do_print("Query for /1 OR query for /1 should match only /1");
+  [query1, opts] = makeQuery(urisAndTags["http://example.com/1"]);
+  [query2] = makeQuery(urisAndTags["http://example.com/1"]);
+  root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1"]);
+
+  do_print("Query for /1 with tagsAreNot OR query for /2 with tagsAreNot " +
+           "should match both /1 and /2");
+  [query1, opts] = makeQuery(urisAndTags["http://example.com/1"], true);
+  [query2] = makeQuery(urisAndTags["http://example.com/2"], true);
+  root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1", "http://example.com/2"]);
+
+  do_print("Query for /1 OR query for /2 with tagsAreNot should match " +
+           "only /1");
+  [query1, opts] = makeQuery(urisAndTags["http://example.com/1"]);
+  [query2] = makeQuery(urisAndTags["http://example.com/2"], true);
+  root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1"]);
+
+  do_print("Query for /1 OR query for /1 with tagsAreNot should match " +
+           "both URIs");
+  [query1, opts] = makeQuery(urisAndTags["http://example.com/1"]);
+  [query2] = makeQuery(urisAndTags["http://example.com/1"], true);
+  root = PlacesUtils.history.executeQueries([query1, query2], 2, opts).root;
+  queryResultsAre(root, ["http://example.com/1", "http://example.com/2"]);
+
+  // Clean up.
+  for (let [pURI, tags] of Object.entries(urisAndTags)) {
+    let nsiuri = uri(pURI);
+    if (tags)
+      PlacesUtils.tagging.untagURI(nsiuri, tags);
+  }
+  yield task_cleanDatabase();
+});
+
+// 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.
+ */
+function* task_cleanDatabase(aCallback) {
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesTestUtils.clearHistory();
+}
+
+/**
+ * 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);
+  do_print("Query URI should be what we expect for the given tags");
+  do_check_eq(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
+ */
+function* task_doWithBookmark(aTags, aCallback) {
+  yield addBookmark(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, aTags);
+  yield aCallback(TEST_URI);
+  PlacesUtils.tagging.untagURI(TEST_URI, aTags);
+  yield task_cleanDatabase();
+}
+
+/**
+ * Asynchronous task that executes a callback function in a "scoped" database
+ * state.  A history visit is added and tagged before the callback is called,
+ * and afterward the database is cleared.
+ *
+ * @param aTags
+ *        A history visit will be added and tagged with this array of tags
+ * @param aCallback
+ *        A function that will be called after the visit has been tagged
+ */
+function* task_doWithVisit(aTags, aCallback) {
+  yield PlacesTestUtils.addVisits(TEST_URI);
+  PlacesUtils.tagging.tagURI(TEST_URI, aTags);
+  yield aCallback(TEST_URI);
+  PlacesUtils.tagging.untagURI(TEST_URI, aTags);
+  yield task_cleanDatabase();
+}
+
+/**
+ * queriesToQueryString() 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;
+  do_print("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.indexOf(t) < 0)
+        uniqueTags.push(t);
+    });
+    uniqueTags.sort();
+  }
+
+  do_print("Made query should be correct for tags and tagsAreNot");
+  if (uniqueTags)
+    setsAreEqual(query.tags, uniqueTags, true);
+  var expCount = uniqueTags ? uniqueTags.length : 0;
+  do_check_eq(query.tags.length, expCount);
+  do_check_eq(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.queriesToQueryString([aQuery], 1, aQueryOpts);
+}
+
+/**
+ * Ensures that the arrays contain the same elements and, optionally, in the
+ * same order.
+ */
+function setsAreEqual(aArr1, aArr2, aIsOrdered) {
+  do_check_eq(aArr1.length, aArr2.length);
+  if (aIsOrdered) {
+    for (let i = 0; i < aArr1.length; i++) {
+      do_check_eq(aArr1[i], aArr2[i]);
+    }
+  }
+  else {
+    aArr1.forEach(u => do_check_true(aArr2.indexOf(u) >= 0));
+    aArr2.forEach(u => do_check_true(aArr1.indexOf(u) >= 0));
+  }
+}
+
+function run_test() {
+  run_next_test();
+}
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 000000000..bbd4c9e01
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_transitions.js
@@ -0,0 +1,178 @@
+/* -*- 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 beginTime = Date.now();
+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];
+
+/**
+ * run_test is where the magic happens.  This is automatically run by the test
+ * harness.  It is where you do the work of creating the query, running it, and
+ * playing with the result set.
+ */
+function run_test()
+{
+  run_next_test();
+}
+
+add_task(function* test_transitions()
+{
+  let timeNow = Date.now();
+  for (let item of testData) {
+    yield 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.
+    queryStringToQueries("place:transition=" +
+                         Ci.nsINavHistoryService.TRANSITION_DOWNLOAD,
+                         query, {}, options);
+  query = (query.value)[0];
+  options = PlacesUtils.history.getNewQueryOptions();
+  var result = PlacesUtils.history.executeQuery(query, options);
+  var root = result.root;
+  root.containerOpen = true;
+  do_check_eq(testDataDownload.length, root.childCount);
+  yield PlacesTestUtils.addVisits({
+    uri: uri("http://getfirefox.com"),
+    transition: TRANSITION_DOWNLOAD
+  });
+  do_check_eq(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.queryStringToQueries(queryStr, query, {}, options);
+  query = query.value[0];
+  options = options.value;
+  var result = PlacesUtils.history.executeQuery(query, options);
+  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.ini b/toolkit/components/places/tests/queries/xpcshell.ini
new file mode 100644
index 000000000..7ff864679
--- /dev/null
+++ b/toolkit/components/places/tests/queries/xpcshell.ini
@@ -0,0 +1,34 @@
+[DEFAULT]
+head = head_queries.js
+tail =
+skip-if = toolkit == 'android'
+
+[test_415716.js]
+[test_abstime-annotation-domain.js]
+[test_abstime-annotation-uri.js]
+[test_async.js]
+[test_containersQueries_sorting.js]
+[test_history_queries_tags_liveUpdate.js]
+[test_history_queries_titles_liveUpdate.js]
+[test_onlyBookmarked.js]
+[test_queryMultipleFolder.js]
+[test_querySerialization.js]
+[test_redirects.js]
+# Bug 676989: test hangs consistently on Android
+skip-if = os == "android"
+[test_results-as-tag-contents-query.js]
+[test_results-as-visit.js]
+[test_searchterms-domain.js]
+[test_searchterms-uri.js]
+[test_searchterms-bookmarklets.js]
+[test_sort-date-site-grouping.js]
+[test_sorting.js]
+# Bug 676989: test hangs consistently on Android
+skip-if = os == "android" 
+[test_tags.js]
+# Bug 676989: test hangs consistently on Android
+skip-if = os == "android"
+[test_transitions.js]
+# Bug 676989: test hangs consistently on Android
+skip-if = os == "android"
+[test_searchTerms_includeHidden.js]