--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -758,155 +758,16 @@ nsNavHistory::NormalizeTime(uint32_t aRe
       break;
     default:
       NS_NOTREACHED("Invalid relative time");
       return 0;
   }
   return ref + aOffset;
 }
 
-// nsNavHistory::EvaluateQueryForNode
-//
-//    This runs the node through the given query to see if satisfies the
-//    query conditions. Not every query parameters are handled by this code,
-//    but we handle the most common ones so that performance is better.
-//
-//    We assume that the time on the node is the time that we want to compare.
-//    This is not necessarily true because URL nodes have the last access time,
-//    which is not necessarily the same. However, since this is being called
-//    to update the list, we assume that the last access time is the current
-//    access time that we are being asked to compare so it works out.
-//
-//    Returns true if node matches the query, false if not.
-
-bool
-nsNavHistory::EvaluateQueryForNode(const RefPtr<nsNavHistoryQuery>& aQuery,
-                                   nsNavHistoryQueryOptions* aOptions,
-                                   nsNavHistoryResultNode* aNode)
-{
-  // lazily created from the node's string when we need to match URIs
-  nsCOMPtr<nsIURI> nodeUri;
-
-  // --- hidden ---
-  if (aNode->mHidden && !aOptions->IncludeHidden())
-    return false;
-
-  bool hasIt;
-  // --- begin time ---
-  aQuery->GetHasBeginTime(&hasIt);
-  if (hasIt) {
-    PRTime beginTime = NormalizeTime(aQuery->BeginTimeReference(),
-                                     aQuery->BeginTime());
-    if (aNode->mTime < beginTime)
-      return false;
-  }
-
-  // --- end time ---
-  aQuery->GetHasEndTime(&hasIt);
-  if (hasIt) {
-    PRTime endTime = NormalizeTime(aQuery->EndTimeReference(),
-                                   aQuery->EndTime());
-    if (aNode->mTime > endTime)
-      return false;
-  }
-
-  // --- search terms ---
-  if (!aQuery->SearchTerms().IsEmpty()) {
-    // we can use the existing filtering code, just give it our one object in
-    // an array.
-    nsCOMArray<nsNavHistoryResultNode> inputSet;
-    inputSet.AppendObject(aNode);
-    nsCOMArray<nsNavHistoryResultNode> filteredSet;
-    nsresult rv = FilterResultSet(nullptr, inputSet, &filteredSet, aQuery, aOptions);
-    if (NS_FAILED(rv))
-      return false;
-    if (!filteredSet.Count())
-      return false;
-  }
-
-  // --- domain/host matching ---
-  if (!aQuery->Domain().IsVoid()) {
-    if (!nodeUri) {
-      // lazy creation of nodeUri, which might be checked for multiple queries
-      if (NS_FAILED(NS_NewURI(getter_AddRefs(nodeUri), aNode->mURI)))
-        return false;
-    }
-    nsAutoCString asciiRequest;
-    if (NS_FAILED(AsciiHostNameFromHostString(aQuery->Domain(), asciiRequest)))
-      return false;
-
-    if (aQuery->DomainIsHost()) {
-      nsAutoCString host;
-      if (NS_FAILED(nodeUri->GetAsciiHost(host)))
-        return false;
-
-      if (!asciiRequest.Equals(host))
-        return false;
-    }
-    // check domain names
-    nsAutoCString domain;
-    DomainNameFromURI(nodeUri, domain);
-    if (!asciiRequest.Equals(domain))
-      return false;
-  }
-
-  // --- URI matching ---
-  if (aQuery->Uri()) {
-    if (!nodeUri) { // lazy creation of nodeUri
-      if (NS_FAILED(NS_NewURI(getter_AddRefs(nodeUri), aNode->mURI)))
-        return false;
-    }
-
-    bool equals;
-    nsresult rv = aQuery->Uri()->Equals(nodeUri, &equals);
-    NS_ENSURE_SUCCESS(rv, false);
-    if (!equals)
-      return false;
-  }
-
-  // Transitions matching.
-  const nsTArray<uint32_t>& transitions = aQuery->Transitions();
-  if (aNode->mTransitionType > 0 &&
-      transitions.Length() &&
-      !transitions.Contains(aNode->mTransitionType)) {
-    return false;
-  }
-
-  // If we ever make it to the bottom, that means it passed all the tests for
-  // the given query.
-  return true;
-}
-
-
-// nsNavHistory::AsciiHostNameFromHostString
-//
-//    We might have interesting encodings and different case in the host name.
-//    This will convert that host name into an ASCII host name by sending it
-//    through the URI canonicalization. The result can be used for comparison
-//    with other ASCII host name strings.
-nsresult // static
-nsNavHistory::AsciiHostNameFromHostString(const nsACString& aHostName,
-                                          nsACString& aAscii)
-{
-  aAscii.Truncate();
-  if (aHostName.IsEmpty()) {
-    return NS_OK;
-  }
-  // To properly generate a uri we must provide a protocol.
-  nsAutoCString fakeURL("http://");
-  fakeURL.Append(aHostName);
-  nsCOMPtr<nsIURI> uri;
-  nsresult rv = NS_NewURI(getter_AddRefs(uri), fakeURL);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = uri->GetAsciiHost(aAscii);
-  NS_ENSURE_SUCCESS(rv, rv);
-  return NS_OK;
-}
-
-
 // nsNavHistory::DomainNameFromURI
 //
 //    This does the www.mozilla.org -> mozilla.org and
 //    foo.theregister.co.uk -> theregister.co.uk conversion
 void
 nsNavHistory::DomainNameFromURI(nsIURI *aURI,
                                 nsACString& aDomainName)
 {
@@ -3434,27 +3295,24 @@ nsNavHistory::GetTagsFolder()
 //
 // This does some post-query-execution filtering:
 //   - searching on title, url and tags
 //   - limit count
 //
 // Note:  changes to filtering in FilterResultSet()
 // may require changes to NeedToFilterResultSet()
 
+// static
 nsresult
 nsNavHistory::FilterResultSet(nsNavHistoryQueryResultNode* aQueryNode,
                               const nsCOMArray<nsNavHistoryResultNode>& aSet,
                               nsCOMArray<nsNavHistoryResultNode>* aFiltered,
                               const RefPtr<nsNavHistoryQuery>& aQuery,
                               nsNavHistoryQueryOptions *aOptions)
 {
-  // get the bookmarks service
-  nsNavBookmarks *bookmarks = nsNavBookmarks::GetBookmarksService();
-  NS_ENSURE_TRUE(bookmarks, NS_ERROR_OUT_OF_MEMORY);
-
   // parse the search terms
   nsTArray<nsString> terms;
   ParseSearchTermsFromQuery(aQuery, &terms);
 
   uint16_t resultType = aOptions->ResultType();
   bool excludeQueries = aOptions->ExcludeQueries();
   for (int32_t nodeIndex = 0; nodeIndex < aSet.Count(); nodeIndex++) {
     if (excludeQueries && aSet[nodeIndex]->IsQuery()) {

--- a/toolkit/components/places/nsNavHistory.h
+++ b/toolkit/components/places/nsNavHistory.h
@@ -292,22 +292,16 @@ public:
                                    const nsAString& aValue,
                                    const nsACString& aGUID);
 
   /**
    * Returns current number of days stored in history.
    */
   int32_t GetDaysOfHistory();
 
-  bool EvaluateQueryForNode(const RefPtr<nsNavHistoryQuery>& aQuery,
-                              nsNavHistoryQueryOptions* aOptions,
-                              nsNavHistoryResultNode* aNode);
-
-  static nsresult AsciiHostNameFromHostString(const nsACString& aHostName,
-                                              nsACString& aAscii);
   void DomainNameFromURI(nsIURI* aURI,
                          nsACString& aDomainName);
   static PRTime NormalizeTime(uint32_t aRelative, PRTime aOffset);
 
   // Don't use these directly, inside nsNavHistory use UpdateBatchScoper,
   // else use nsINavHistoryService::RunInBatchMode
   nsresult BeginUpdateBatch();
   nsresult EndUpdateBatch();
@@ -490,16 +484,23 @@ public:
    */
   nsresult GetCryptoProvider(HCRYPTPROV& aCryptoProvider) const {
     NS_ENSURE_STATE(mCryptoProviderInitialized);
     aCryptoProvider = mCryptoProvider;
     return NS_OK;
   }
 #endif
 
+
+  static nsresult FilterResultSet(nsNavHistoryQueryResultNode *aParentNode,
+                                  const nsCOMArray<nsNavHistoryResultNode>& aSet,
+                                  nsCOMArray<nsNavHistoryResultNode>* aFiltered,
+                                  const RefPtr<nsNavHistoryQuery>& aQuery,
+                                  nsNavHistoryQueryOptions* aOptions);
+
 private:
   ~nsNavHistory();
 
   // used by GetHistoryService
   static nsNavHistory *gHistoryService;
 
 protected:
 
@@ -549,22 +550,16 @@ protected:
                                      const RefPtr<nsNavHistoryQueryOptions>& aOptions);
 
   nsresult ResultsAsList(mozIStorageStatement* statement,
                          nsNavHistoryQueryOptions* aOptions,
                          nsCOMArray<nsNavHistoryResultNode>* aResults);
 
   void TitleForDomain(const nsCString& domain, nsACString& aTitle);
 
-  nsresult FilterResultSet(nsNavHistoryQueryResultNode *aParentNode,
-                           const nsCOMArray<nsNavHistoryResultNode>& aSet,
-                           nsCOMArray<nsNavHistoryResultNode>* aFiltered,
-                           const RefPtr<nsNavHistoryQuery>& aQuery,
-                           nsNavHistoryQueryOptions* aOptions);
-
   // observers
   nsMaybeWeakPtrArray<nsINavHistoryObserver> mObservers;
 
   // effective tld service
   nsCOMPtr<nsIEffectiveTLDService> mTLDService;
   nsCOMPtr<nsIIDNService>          mIDNService;
 
   // localization

--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -61,37 +61,37 @@
 
 using namespace mozilla;
 using namespace mozilla::places;
 
 namespace {
 
 /**
  * Returns conditions for query update.
- *    QUERYUPDATE_TIME:
- *      This query is only limited by an inclusive time range on the first
- *      query object. The caller can quickly evaluate the time itself if it
- *      chooses. This is even simpler than "simple" below.
- *    QUERYUPDATE_SIMPLE:
- *      This query is evaluatable using EvaluateQueryForNode to do live
- *      updating.
- *    QUERYUPDATE_COMPLEX:
- *      This query is not evaluatable using EvaluateQueryForNode. When something
- *      happens that this query updates, you will need to re-run the query.
- *    QUERYUPDATE_COMPLEX_WITH_BOOKMARKS:
- *      A complex query that additionally has dependence on bookmarks. All
- *      bookmark-dependent queries fall under this category.
- *    QUERYUPDATE_MOBILEPREF:
- *      A complex query but only updates when the mobile preference changes.
- *    QUERYUPDATE_NONE:
- *      A query that never updates, e.g. the left-pane root query.
+ *  QUERYUPDATE_TIME:
+ *    This query is only limited by an inclusive time range on the first
+ *    query object. The caller can quickly evaluate the time itself if it
+ *    chooses. This is even simpler than "simple" below.
+ *  QUERYUPDATE_SIMPLE:
+ *    This query is evaluatable using evaluateQueryForNode to do live
+ *    updating.
+ *  QUERYUPDATE_COMPLEX:
+ *    This query is not evaluatable using evaluateQueryForNode. When something
+ *    happens that this query updates, you will need to re-run the query.
+ *  QUERYUPDATE_COMPLEX_WITH_BOOKMARKS:
+ *    A complex query that additionally has dependence on bookmarks. All
+ *    bookmark-dependent queries fall under this category.
+ *  QUERYUPDATE_MOBILEPREF:
+ *    A complex query but only updates when the mobile preference changes.
+ *  QUERYUPDATE_NONE:
+ *    A query that never updates, e.g. the left-pane root query.
  *
- *    aHasSearchTerms will be set to true if the query has any dependence on
- *    keywords. When there is no dependence on keywords, we can handle title
- *    change operations as simple instead of complex.
+ *  aHasSearchTerms will be set to true if the query has any dependence on
+ *  keywords. When there is no dependence on keywords, we can handle title
+ *  change operations as simple instead of complex.
  */
 uint32_t
 getUpdateRequirements(const RefPtr<nsNavHistoryQuery>& aQuery,
                       const RefPtr<nsNavHistoryQueryOptions>& aOptions,
                       bool* aHasSearchTerms)
 {
   // first check if there are search terms
   bool hasSearchTerms = *aHasSearchTerms = !aQuery->SearchTerms().IsEmpty();
@@ -139,16 +139,145 @@ getUpdateRequirements(const RefPtr<nsNav
   if (domainBasedItems)
     return QUERYUPDATE_HOST;
   if (!nonTimeBasedItems)
     return QUERYUPDATE_TIME;
 
   return QUERYUPDATE_SIMPLE;
 }
 
+/**
+ * We might have interesting encodings and different case in the host name.
+ * This will convert that host name into an ASCII host name by sending it
+ * through the URI canonicalization. The result can be used for comparison
+ * with other ASCII host name strings.
+ */
+nsresult
+asciiHostNameFromHostString(const nsACString& aHostName,
+                                          nsACString& aAscii)
+{
+  aAscii.Truncate();
+  if (aHostName.IsEmpty()) {
+    return NS_OK;
+  }
+  // To properly generate a uri we must provide a protocol.
+  nsAutoCString fakeURL("http://");
+  fakeURL.Append(aHostName);
+  nsCOMPtr<nsIURI> uri;
+  nsresult rv = NS_NewURI(getter_AddRefs(uri), fakeURL);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = uri->GetAsciiHost(aAscii);
+  NS_ENSURE_SUCCESS(rv, rv);
+  return NS_OK;
+}
+
+/**
+ * This runs the node through the given query to see if satisfies the
+ * query conditions. Not every query parameters are handled by this code,
+ * but we handle the most common ones so that performance is better.
+ * We assume that the time on the node is the time that we want to compare.
+ * This is not necessarily true because URL nodes have the last access time,
+ * which is not necessarily the same. However, since this is being called
+ * to update the list, we assume that the last access time is the current
+ * access time that we are being asked to compare so it works out.
+ * Returns true if node matches the query, false if not.
+ */
+bool
+evaluateQueryForNode(const RefPtr<nsNavHistoryQuery>& aQuery,
+                     const RefPtr<nsNavHistoryQueryOptions>& aOptions,
+                     const RefPtr<nsNavHistoryResultNode>& aNode)
+{
+  // Hidden
+  if (aNode->mHidden && !aOptions->IncludeHidden())
+    return false;
+
+  bool hasIt;
+  // Begin time
+  aQuery->GetHasBeginTime(&hasIt);
+  if (hasIt) {
+    PRTime beginTime = nsNavHistory::NormalizeTime(aQuery->BeginTimeReference(),
+                                                   aQuery->BeginTime());
+    if (aNode->mTime < beginTime)
+      return false;
+  }
+
+  // End time
+  aQuery->GetHasEndTime(&hasIt);
+  if (hasIt) {
+    PRTime endTime = nsNavHistory::NormalizeTime(aQuery->EndTimeReference(),
+                                                 aQuery->EndTime());
+    if (aNode->mTime > endTime)
+      return false;
+  }
+
+  // Search terms
+  if (!aQuery->SearchTerms().IsEmpty()) {
+    // we can use the existing filtering code, just give it our one object in
+    // an array.
+    nsCOMArray<nsNavHistoryResultNode> inputSet;
+    inputSet.AppendObject(aNode);
+    nsCOMArray<nsNavHistoryResultNode> filteredSet;
+    nsresult rv = nsNavHistory::FilterResultSet(nullptr, inputSet, &filteredSet, aQuery, aOptions);
+    if (NS_FAILED(rv))
+      return false;
+    if (!filteredSet.Count())
+      return false;
+  }
+
+  // Domain/host
+  if (!aQuery->Domain().IsVoid()) {
+    nsCOMPtr<nsIURI> nodeUri;
+    if (NS_FAILED(NS_NewURI(getter_AddRefs(nodeUri), aNode->mURI)))
+      return false;
+    nsAutoCString asciiRequest;
+    if (NS_FAILED(asciiHostNameFromHostString(aQuery->Domain(), asciiRequest)))
+      return false;
+    if (aQuery->DomainIsHost()) {
+      nsAutoCString host;
+      if (NS_FAILED(nodeUri->GetAsciiHost(host)))
+        return false;
+
+      if (!asciiRequest.Equals(host))
+        return false;
+    }
+    // check domain names.
+    nsNavHistory* history = nsNavHistory::GetHistoryService();
+    if (!history)
+      return false;
+    nsAutoCString domain;
+    history->DomainNameFromURI(nodeUri, domain);
+    if (!asciiRequest.Equals(domain))
+      return false;
+  }
+
+  // URI
+  if (aQuery->Uri()) {
+    nsCOMPtr<nsIURI> nodeUri;
+    if (NS_FAILED(NS_NewURI(getter_AddRefs(nodeUri), aNode->mURI)))
+      return false;
+     bool equals;
+    nsresult rv = aQuery->Uri()->Equals(nodeUri, &equals);
+    NS_ENSURE_SUCCESS(rv, false);
+    if (!equals)
+      return false;
+  }
+
+  // Transitions
+  const nsTArray<uint32_t>& transitions = aQuery->Transitions();
+  if (aNode->mTransitionType > 0 &&
+      transitions.Length() &&
+      !transitions.Contains(aNode->mTransitionType)) {
+    return false;
+  }
+
+  // If we ever make it to the bottom, that means it passed all the tests for
+  // the given query.
+  return true;
+}
+
 // Emulate string comparison (used for sorting) for PRTime and int.
 inline int32_t ComparePRTime(PRTime a, PRTime b)
 {
   if (a < b)
     return -1;
   else if (a > b)
     return 1;
   return 0;
@@ -2373,17 +2502,17 @@ nsNavHistoryQueryResultNode::OnVisit(nsI
       nsresult rv = history->VisitIdToResultNode(aVisitId, mOptions,
                                                  getter_AddRefs(addition));
       NS_ENSURE_SUCCESS(rv, rv);
       if (!addition) {
         // Certain result types manage the nodes by themselves.
         return NS_OK;
       }
       addition->mTransitionType = aTransitionType;
-      if (!history->EvaluateQueryForNode(mQuery, mOptions, addition))
+      if (!evaluateQueryForNode(mQuery, mOptions, addition))
         return NS_OK; // don't need to include in our query
 
       if (mOptions->ResultType() == nsNavHistoryQueryOptions::RESULTS_AS_VISIT) {
         // If this is a visit type query, just insert the new visit.  We never
         // update visits, only add or remove them.
         rv = InsertSortedChild(addition);
         NS_ENSURE_SUCCESS(rv, rv);
       } else {
@@ -2475,32 +2604,32 @@ nsNavHistoryQueryResultNode::OnTitleChan
     if (matches.Count() == 0) {
       // This could be a new node matching the query, thus we could need
       // to add it to the result.
       RefPtr<nsNavHistoryResultNode> node;
       nsNavHistory* history = nsNavHistory::GetHistoryService();
       NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
       rv = history->URIToResultNode(aURI, mOptions, getter_AddRefs(node));
       NS_ENSURE_SUCCESS(rv, rv);
-      if (history->EvaluateQueryForNode(mQuery, mOptions, node)) {
+      if (evaluateQueryForNode(mQuery, mOptions, node)) {
         rv = InsertSortedChild(node);
         NS_ENSURE_SUCCESS(rv, rv);
       }
     }
     for (int32_t i = 0; i < matches.Count(); ++i) {
       // For each matched node we check if it passes the query filter, if not
       // we remove the node from the result, otherwise we'll update the title
       // later.
       nsNavHistoryResultNode* node = matches[i];
       // We must check the node with the new title.
       node->mTitle = newTitle;
 
       nsNavHistory* history = nsNavHistory::GetHistoryService();
       NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-      if (!history->EvaluateQueryForNode(mQuery, mOptions, node)) {
+      if (!evaluateQueryForNode(mQuery, mOptions, node)) {
         nsNavHistoryContainerResultNode* parent = node->mParent;
         // URI nodes should always have parents
         NS_ENSURE_TRUE(parent, NS_ERROR_UNEXPECTED);
         int32_t childIndex = parent->FindChild(node);
         NS_ASSERTION(childIndex >= 0, "Child not found in parent");
         parent->RemoveChildAt(childIndex);
       }
     }
@@ -2684,33 +2813,33 @@ nsNavHistoryQueryResultNode::NotifyIfTag
   nsCOMArray<nsNavHistoryResultNode> matches;
   RecursiveFindURIs(onlyOneEntry, this, spec, &matches);
 
   if (matches.Count() == 0 && mHasSearchTerms) {
     // A new tag has been added, it's possible it matches our query.
     NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
     rv = history->URIToResultNode(aURI, mOptions, getter_AddRefs(node));
     NS_ENSURE_SUCCESS(rv, rv);
-    if (history->EvaluateQueryForNode(mQuery, mOptions, node)) {
+    if (evaluateQueryForNode(mQuery, mOptions, node)) {
       rv = InsertSortedChild(node);
       NS_ENSURE_SUCCESS(rv, rv);
     }
   }
 
   for (int32_t i = 0; i < matches.Count(); ++i) {
     nsNavHistoryResultNode* node = matches[i];
     // Force a tags update before checking the node.
     node->mTags.SetIsVoid(true);
     nsAutoString tags;
     rv = node->GetTags(tags);
     NS_ENSURE_SUCCESS(rv, rv);
     // It's possible now this node does not respect anymore the conditions.
     // In such a case it should be removed.
     if (mHasSearchTerms &&
-        !history->EvaluateQueryForNode(mQuery, mOptions, node)) {
+        !evaluateQueryForNode(mQuery, mOptions, node)) {
       nsNavHistoryContainerResultNode* parent = node->mParent;
       // URI nodes should always have parents
       NS_ENSURE_TRUE(parent, NS_ERROR_UNEXPECTED);
       int32_t childIndex = parent->FindChild(node);
       NS_ASSERTION(childIndex >= 0, "Child not found in parent");
       parent->RemoveChildAt(childIndex);
     }
     else {