--- a/toolkit/components/places/public/nsINavHistoryService.idl
+++ b/toolkit/components/places/public/nsINavHistoryService.idl
@@ -19,16 +19,17 @@
  * Portions created by the Initial Developer are Copyright (C) 2005
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *   Brett Wilson <brett@gmail.com>
  *   Dietrich Ayala <dietrich@mozilla.com>
  *   Marco Bonardo <mak77@bonardo.net>
  *   Asaf Romano <mano@mozilla.com>
+ *   Drew Willcoxon <adw@mozilla.com>
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either the GNU General Public License Version 2 or later (the "GPL"), or
  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
@@ -226,33 +227,43 @@ interface nsINavHistoryFullVisitResultNo
 };
 
 
 /**
  * Base class for container results. This includes all types of groupings.
  * Bookmark folders and places queries will be QueryResultNodes which extends
  * these items.
  */
-[scriptable, uuid(9e3f2f78-53ae-469a-9fb3-b0ef74b24a31)]
+[scriptable, uuid(55829318-0f6c-4503-8739-84231f3a6793)]
 interface nsINavHistoryContainerResultNode : nsINavHistoryResultNode
 {
 
   /**
    * Set this to allow descent into the container. When closed, attempting
    * to call getChildren or childCount will result in an error. You should
    * set this to false when you are done reading.
    *
    * For HOST and DAY groupings, doing this is free since the children have
    * been precomputed. For queries and bookmark folders, being open means they
    * will keep themselves up-to-date by listening for updates and re-querying
    * as needed.
    */
   attribute boolean containerOpen;
 
   /**
+   * Indicates whether the container is closed, loading, or opened.  Loading
+   * implies that the container has been opened asynchronously and has not yet
+   * fully opened.
+   */
+  readonly attribute unsigned short state;
+  const unsigned short STATE_CLOSED = 0;
+  const unsigned short STATE_LOADING = 1;
+  const unsigned short STATE_OPENED = 2;
+
+  /**
    * This indicates whether this node "may" have children, and can be used
    * when the container is open or closed. When the container is closed, it
    * will give you an exact answer if the node can easily be populated (for
    * example, a bookmark folder). If not (for example, a complex history query),
    * it will return true. When the container is open, it will always be
    * accurate. It is intended to be used to see if we should draw the "+" next
    * to a tree item.
    */
@@ -444,17 +455,17 @@ interface nsINavHistoryQueryResultNode :
 };
 
 
 /**
  * Allows clients to observe what is happening to a result as it updates itself
  * according to history and bookmark system events. Register this observer on a
  * result using nsINavHistoryResult::addObserver.
  */
-[scriptable, uuid(9a229620-1faf-11df-8a39-0800200c9a66)]
+[scriptable, uuid(d746da3c-f698-48bc-ad73-2d428b23b0c6)]
 interface nsINavHistoryResultObserver : nsISupports
 {
   /**
    * Called when 'aItem' is inserted into 'aParent' at index 'aNewIndex'.
    * The item previously at index (if any) and everything below it will have
    * been shifted down by one. The item may be a container or a leaf.
    */
   void nodeInserted(in nsINavHistoryContainerResultNode aParent,
@@ -604,32 +615,52 @@ interface nsINavHistoryResultObserver : 
   void nodeReplaced(in nsINavHistoryContainerResultNode aParentNode,
                     in nsINavHistoryResultNode aOldNode,
                     in nsINavHistoryResultNode aNewNode,
                     in unsigned long aIndex);
 
   /**
    * Called after a container node went from closed to opened.
    *
+   * @note  This method is DEPRECATED.  In the future only containerStateChanged
+   *        will notify when a container is opened.
+   *
    * @param aContainerNode
    *        the container node which was opened
    */
   void containerOpened(in nsINavHistoryContainerResultNode aContainerNode);
 
   /**
    * Called after a container node went from opened to closed. This will be
    * called for the topmost container that is closing, and implies that any
    * child containers have closed as well.
    *
+   * @note  This method is DEPRECATED.  In the future only containerStateChanged
+   *        will notify when a container is closed.
+   *
    * @param aContainerNode
    *        the container node which was closed
    */
   void containerClosed(in nsINavHistoryContainerResultNode aContainerNode);
 
   /**
+   * Called after a container changes state.
+   *
+   * @param aContainerNode
+   *        The container that has changed state.
+   * @param aOldState
+   *        The state that aContainerNode has transitioned out of.
+   * @param aNewState
+   *        The state that aContainerNode has transitioned into.
+   */
+  void containerStateChanged(in nsINavHistoryContainerResultNode aContainerNode,
+                             in unsigned long aOldState,
+                             in unsigned long aNewState);
+
+  /**
    * Called when something significant has happened within the container. The
    * contents of the container should be re-built.
    *
    * @param aContainerNode
    *        the container node to invalidate
    */
   void invalidateContainer(in nsINavHistoryContainerResultNode aContainerNode);
 
@@ -1031,17 +1062,17 @@ interface nsINavHistoryQuery : nsISuppor
    * Creates a new query item with the same parameters of this one.
    */
   nsINavHistoryQuery clone();
 };
 
 /**
  * This object represents the global options for executing a query.
  */
-[scriptable, uuid(c6831388-fd4c-46a8-85f3-952917b66d72)]
+[scriptable, uuid(2d8ff86b-f8c2-451c-8a1a-1ff0749a074e)]
 interface nsINavHistoryQueryOptions : nsISupports
 {
   /**
    * You can ask for the results to be pre-sorted. Since the DB has indices
    * of many items, it can produce sorted results almost for free. These should
    * be self-explanatory.
    *
    * Note: re-sorting is slower, as is sorting by title or when you have a
@@ -1257,16 +1288,26 @@ interface nsINavHistoryQueryOptions : ns
 
   /**
    * The type of search to use when querying the DB; This attribute is only
    * honored by query nodes. It is silently ignored for simple folder queries.
    */
   attribute unsigned short queryType;
 
   /**
+   * When this is true, the root container node generated by these options and
+   * its descendant containers will be opened asynchronously if they support it.
+   * This is false by default.
+   *
+   * @note Currently only bookmark folder containers support being opened
+   *       asynchronously.
+   */
+  attribute boolean asyncEnabled;
+
+  /**
    * Creates a new options item with the same parameters of this one.
    */
   nsINavHistoryQueryOptions clone();
 };
 
 [scriptable, uuid(437f539b-d541-4a0f-a200-6f9a6d45cce2)]
 interface nsINavHistoryService : nsISupports
 {

--- a/toolkit/components/places/src/nsNavBookmarks.cpp
+++ b/toolkit/components/places/src/nsNavBookmarks.cpp
@@ -2279,99 +2279,145 @@ nsNavBookmarks::ResultNodeForContainer(P
   NS_ENSURE_SUCCESS(rv, rv);
 
   NS_ADDREF(*aNode);
   return NS_OK;
 }
 
 
 nsresult
-nsNavBookmarks::QueryFolderChildren(PRInt64 aFolderId,
-                                    nsNavHistoryQueryOptions* aOptions,
-                                    nsCOMArray<nsNavHistoryResultNode>* aChildren)
+nsNavBookmarks::QueryFolderChildren(
+  PRInt64 aFolderId,
+  nsNavHistoryQueryOptions* aOptions,
+  nsCOMArray<nsNavHistoryResultNode>* aChildren)
 {
+  NS_ENSURE_ARG_POINTER(aOptions);
+  NS_ENSURE_ARG_POINTER(aChildren);
+
   DECLARE_AND_ASSIGN_SCOPED_LAZY_STMT(stmt, mDBGetChildren);
   nsresult rv = stmt->BindInt64Parameter(0, aFolderId);
   NS_ENSURE_SUCCESS(rv, rv);
 
-  nsCOMPtr<nsNavHistoryQueryOptions> options = do_QueryInterface(aOptions, &rv);
+  nsCOMPtr<mozIStorageValueArray> row = do_QueryInterface(stmt, &rv);
   NS_ENSURE_SUCCESS(rv, rv);
 
   PRInt32 index = -1;
   PRBool hasResult;
   while (NS_SUCCEEDED(stmt->ExecuteStep(&hasResult)) && hasResult) {
-
-    // The results will be in order of index. Even if we don't add a node
-    // because it was excluded, we need to count its index, so do that
-    // before doing anything else. Index was initialized to -1 above, so
-    // it will start counting at 0 the first time through the loop.
-    index ++;
-
-    PRInt32 itemType;
-    rv = stmt->GetInt32(kGetChildrenIndex_Type, &itemType);
-    NS_ENSURE_SUCCESS(rv, rv);
-    PRInt64 id;
-    rv = stmt->GetInt64(nsNavHistory::kGetInfoIndex_ItemId, &id);
+    rv = ProcessFolderNodeRow(row, aOptions, aChildren, index);
     NS_ENSURE_SUCCESS(rv, rv);
-    nsRefPtr<nsNavHistoryResultNode> node;
-    if (itemType == TYPE_BOOKMARK) {
-      nsNavHistory* history = nsNavHistory::GetHistoryService();
-      NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-      rv = history->RowToResult(stmt, options, getter_AddRefs(node));
-      NS_ENSURE_SUCCESS(rv, rv);
-
-      PRUint32 nodeType;
-      node->GetType(&nodeType);
-      if ((nodeType == nsINavHistoryResultNode::RESULT_TYPE_QUERY &&
-           aOptions->ExcludeQueries()) ||
-          (nodeType != nsINavHistoryResultNode::RESULT_TYPE_QUERY &&
-           nodeType != nsINavHistoryResultNode::RESULT_TYPE_FOLDER_SHORTCUT &&
-           aOptions->ExcludeItems())) {
-        continue;
+  }
+
+  return NS_OK;
+}
+
+
+nsresult
+nsNavBookmarks::ProcessFolderNodeRow(
+  mozIStorageValueArray* aRow,
+  nsNavHistoryQueryOptions* aOptions,
+  nsCOMArray<nsNavHistoryResultNode>* aChildren,
+  PRInt32& aCurrentIndex)
+{
+  NS_ENSURE_ARG_POINTER(aRow);
+  NS_ENSURE_ARG_POINTER(aOptions);
+  NS_ENSURE_ARG_POINTER(aChildren);
+
+  // The results will be in order of aCurrentIndex. Even if we don't add a node
+  // because it was excluded, we need to count its index, so do that before
+  // doing anything else.
+  aCurrentIndex++;
+
+  PRInt32 itemType;
+  nsresult rv = aRow->GetInt32(kGetChildrenIndex_Type, &itemType);
+  NS_ENSURE_SUCCESS(rv, rv);
+  PRInt64 id;
+  rv = aRow->GetInt64(nsNavHistory::kGetInfoIndex_ItemId, &id);
+  NS_ENSURE_SUCCESS(rv, rv);
+  nsRefPtr<nsNavHistoryResultNode> node;
+  if (itemType == TYPE_BOOKMARK) {
+    nsNavHistory* history = nsNavHistory::GetHistoryService();
+    NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
+    rv = history->RowToResult(aRow, aOptions, getter_AddRefs(node));
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    PRUint32 nodeType;
+    node->GetType(&nodeType);
+    if ((nodeType == nsINavHistoryResultNode::RESULT_TYPE_QUERY &&
+         aOptions->ExcludeQueries()) ||
+        (nodeType != nsINavHistoryResultNode::RESULT_TYPE_QUERY &&
+         nodeType != nsINavHistoryResultNode::RESULT_TYPE_FOLDER_SHORTCUT &&
+         aOptions->ExcludeItems())) {
+      return NS_OK;
+    }
+  }
+  else if (itemType == TYPE_FOLDER || itemType == TYPE_DYNAMIC_CONTAINER) {
+    if (aOptions->ExcludeReadOnlyFolders()) {
+      // If the folder is read-only, skip it.
+      PRBool readOnly;
+      if (itemType == TYPE_DYNAMIC_CONTAINER) {
+        readOnly = PR_TRUE;
       }
-    } else if (itemType == TYPE_FOLDER || itemType == TYPE_DYNAMIC_CONTAINER) {
-      if (options->ExcludeReadOnlyFolders()) {
-        // see if it's read only and skip it
-        PRBool readOnly = PR_FALSE;
+      else {
+        readOnly = PR_FALSE;
         GetFolderReadonly(id, &readOnly);
-        if (readOnly)
-          continue; // skip
       }
-
-      rv = ResultNodeForContainer(id, aOptions, getter_AddRefs(node));
-      if (NS_FAILED(rv))
-        continue;
-    } else {
-      // separator
-      if (aOptions->ExcludeItems()) {
-        continue;
-      }
-      node = new nsNavHistorySeparatorResultNode();
-      NS_ENSURE_TRUE(node, NS_ERROR_OUT_OF_MEMORY);
-
-      // add the item identifier (RowToResult does so for bookmark items in
-      // the next else block);
-      rv = stmt->GetInt64(nsNavHistory::kGetInfoIndex_ItemId,
-                                    &node->mItemId);
-      NS_ENSURE_SUCCESS(rv, rv);
-      // date-added and last-modified
-      rv = stmt->GetInt64(nsNavHistory::kGetInfoIndex_ItemDateAdded,
-                          &node->mDateAdded);
-      NS_ENSURE_SUCCESS(rv, rv);
-      rv = stmt->GetInt64(nsNavHistory::kGetInfoIndex_ItemLastModified,
-                          &node->mLastModified);
-      NS_ENSURE_SUCCESS(rv, rv);
+      if (readOnly)
+        return NS_OK;
+    }
+    rv = ResultNodeForContainer(id, aOptions, getter_AddRefs(node));
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+  else {
+    // This is a separator.
+    if (aOptions->ExcludeItems()) {
+      return NS_OK;
     }
-
-    // this method fills all bookmark queries, so we store the index of the
-    // item in its parent
-    node->mBookmarkIndex = index;
-
-    NS_ENSURE_TRUE(aChildren->AppendObject(node), NS_ERROR_OUT_OF_MEMORY);
+    node = new nsNavHistorySeparatorResultNode();
+    NS_ENSURE_TRUE(node, NS_ERROR_OUT_OF_MEMORY);
+
+    rv = aRow->GetInt64(nsNavHistory::kGetInfoIndex_ItemId, &node->mItemId);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = aRow->GetInt64(nsNavHistory::kGetInfoIndex_ItemDateAdded,
+                        &node->mDateAdded);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = aRow->GetInt64(nsNavHistory::kGetInfoIndex_ItemLastModified,
+                        &node->mLastModified);
+    NS_ENSURE_SUCCESS(rv, rv);
   }
+
+  // Store the index of the node within this container.  Note that this is not
+  // moz_bookmarks.position.
+  node->mBookmarkIndex = aCurrentIndex;
+
+  NS_ENSURE_TRUE(aChildren->AppendObject(node), NS_ERROR_OUT_OF_MEMORY);
+
+  return NS_OK;
+}
+
+
+nsresult
+nsNavBookmarks::QueryFolderChildrenAsync(
+  nsNavHistoryFolderResultNode* aNode,
+  PRInt64 aFolderId,
+  mozIStoragePendingStatement** _pendingStmt)
+{
+  NS_ENSURE_ARG_POINTER(aNode);
+  NS_ENSURE_ARG_POINTER(_pendingStmt);
+
+  mozStorageStatementScoper scope(mDBGetChildren);
+
+  nsresult rv = mDBGetChildren->BindInt64Parameter(0, aFolderId);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr<mozIStoragePendingStatement> pendingStmt;
+  rv = mDBGetChildren->ExecuteAsync(aNode, getter_AddRefs(pendingStmt));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  NS_IF_ADDREF(*_pendingStmt = pendingStmt);
   return NS_OK;
 }
 
 
 nsresult
 nsNavBookmarks::FolderCount(PRInt64 aFolderId, PRInt32* _folderCount)
 {
   *_folderCount = 0;

--- a/toolkit/components/places/src/nsNavBookmarks.h
+++ b/toolkit/components/places/src/nsNavBookmarks.h
@@ -18,16 +18,17 @@
  * Google Inc.
  * Portions created by the Initial Developer are Copyright (C) 2005
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *   Brian Ryner <bryner@brianryner.com> (original author)
  *   Dietrich Ayala <dietrich@mozilla.com>
  *   Marco Bonardo <mak77@bonardo.net>
+ *   Drew Willcoxon <adw@mozilla.com>
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either the GNU General Public License Version 2 or later (the "GPL"), or
  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
@@ -103,16 +104,49 @@ public:
 
   // Find all the children of a folder, using the given query and options.
   // For each child, a ResultNode is created and added to |children|.
   // The results are ordered by folder position.
   nsresult QueryFolderChildren(PRInt64 aFolderId,
                                nsNavHistoryQueryOptions* aOptions,
                                nsCOMArray<nsNavHistoryResultNode>* children);
 
+  /**
+   * Turns aRow into a node and appends it to aChildren if it is appropriate to
+   * do so.
+   *
+   * @param aRow
+   *        A Storage statement (in the case of synchronous execution) or row of
+   *        a result set (in the case of asynchronous execution).
+   * @param aOptions
+   *        The options of the parent folder node.
+   * @param aChildren
+   *        The children of the parent folder node.
+   * @param aCurrentIndex
+   *        The index of aRow within the results.  When called on the first row,
+   *        this should be set to -1.
+   */
+  nsresult ProcessFolderNodeRow(mozIStorageValueArray* aRow,
+                                nsNavHistoryQueryOptions* aOptions,
+                                nsCOMArray<nsNavHistoryResultNode>* aChildren,
+                                PRInt32& aCurrentIndex);
+
+  /**
+   * The async version of QueryFolderChildren.
+   *
+   * @param aNode
+   *        The folder node that will receive the children.
+   * @param _pendingStmt
+   *        The Storage pending statement that will be used to control async
+   *        execution.
+   */
+  nsresult QueryFolderChildrenAsync(nsNavHistoryFolderResultNode* aNode,
+                                    PRInt64 aFolderId,
+                                    mozIStoragePendingStatement** _pendingStmt);
+
   // If aFolder is -1, uses the autoincrement id for folder index. Returns
   // the index of the new folder in aIndex, whether it was passed in or
   // generated by autoincrement.
   nsresult CreateContainerWithID(PRInt64 aId, PRInt64 aParent,
                                  const nsACString& aName,
                                  const nsAString& aContractId,
                                  PRBool aIsBookmarkFolder,
                                  PRInt32* aIndex,

--- a/toolkit/components/places/src/nsNavHistory.cpp
+++ b/toolkit/components/places/src/nsNavHistory.cpp
@@ -6476,21 +6476,23 @@ nsNavHistory::BindQueryClauseParameters(
 //
 
 nsresult
 nsNavHistory::ResultsAsList(mozIStorageStatement* statement,
                             nsNavHistoryQueryOptions* aOptions,
                             nsCOMArray<nsNavHistoryResultNode>* aResults)
 {
   nsresult rv;
+  nsCOMPtr<mozIStorageValueArray> row = do_QueryInterface(statement, &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
 
   PRBool hasMore = PR_FALSE;
   while (NS_SUCCEEDED(statement->ExecuteStep(&hasMore)) && hasMore) {
     nsRefPtr<nsNavHistoryResultNode> result;
-    rv = RowToResult(statement, aOptions, getter_AddRefs(result));
+    rv = RowToResult(row, aOptions, getter_AddRefs(result));
     NS_ENSURE_SUCCESS(rv, rv);
     aResults->AppendObject(result);
   }
   return NS_OK;
 }
 
 static PRInt64
 GetAgeInDays(PRTime aNormalizedNow, PRTime aDate)
@@ -6867,17 +6869,17 @@ nsNavHistory::GetRedirectFor(const nsACS
 
 
 // nsNavHistory::RowToResult
 //
 //    Here, we just have a generic row. It could be a query, URL, visit,
 //    or full visit.
 
 nsresult
-nsNavHistory::RowToResult(mozIStorageStatement* aRow,
+nsNavHistory::RowToResult(mozIStorageValueArray* aRow,
                           nsNavHistoryQueryOptions* aOptions,
                           nsNavHistoryResultNode** aResult)
 {
   *aResult = nsnull;
   NS_ASSERTION(aRow && aOptions && aResult, "Null pointer in RowToResult");
 
   // URL
   nsCAutoString url;
@@ -7092,17 +7094,20 @@ nsNavHistory::VisitIdToResultNode(PRInt6
   PRBool hasMore = PR_FALSE;
   rv = statement->ExecuteStep(&hasMore);
   NS_ENSURE_SUCCESS(rv, rv);
   if (! hasMore) {
     NS_NOTREACHED("Trying to get a result node for an invalid visit");
     return NS_ERROR_INVALID_ARG;
   }
 
-  return RowToResult(statement, aOptions, aResult);
+  nsCOMPtr<mozIStorageValueArray> row = do_QueryInterface(statement, &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return RowToResult(row, aOptions, aResult);
 }
 
 nsresult
 nsNavHistory::BookmarkIdToResultNode(PRInt64 aBookmarkId, nsNavHistoryQueryOptions* aOptions,
                                      nsNavHistoryResultNode** aResult)
 {
   mozIStorageStatement *stmt = GetDBBookmarkToUrlResult();
   NS_ENSURE_STATE(stmt);
@@ -7113,17 +7118,20 @@ nsNavHistory::BookmarkIdToResultNode(PRI
   PRBool hasMore = PR_FALSE;
   rv = stmt->ExecuteStep(&hasMore);
   NS_ENSURE_SUCCESS(rv, rv);
   if (!hasMore) {
     NS_NOTREACHED("Trying to get a result node for an invalid bookmark identifier");
     return NS_ERROR_INVALID_ARG;
   }
 
-  return RowToResult(stmt, aOptions, aResult);
+  nsCOMPtr<mozIStorageValueArray> row = do_QueryInterface(stmt, &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return RowToResult(row, aOptions, aResult);
 }
 
 void
 nsNavHistory::SendPageChangedNotification(nsIURI* aURI, PRUint32 aWhat,
                                           const nsAString& aValue)
 {
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavHistoryObserver, OnPageChanged(aURI, aWhat, aValue));

--- a/toolkit/components/places/src/nsNavHistory.h
+++ b/toolkit/components/places/src/nsNavHistory.h
@@ -262,17 +262,17 @@ public:
   // nsNavHistoryQueryResultNode
   nsresult GetQueryResults(nsNavHistoryQueryResultNode *aResultNode,
                            const nsCOMArray<nsNavHistoryQuery>& aQueries,
                            nsNavHistoryQueryOptions *aOptions,
                            nsCOMArray<nsNavHistoryResultNode>* aResults);
 
   // Take a row of kGetInfoIndex_* columns and construct a ResultNode.
   // The row must contain the full set of columns.
-  nsresult RowToResult(mozIStorageStatement* aRow,
+  nsresult RowToResult(mozIStorageValueArray* aRow,
                        nsNavHistoryQueryOptions* aOptions,
                        nsNavHistoryResultNode** aResult);
   nsresult QueryRowToResult(PRInt64 aItemId, const nsACString& aURI,
                             const nsACString& aTitle,
                             PRUint32 aAccessCount, PRTime aTime,
                             const nsACString& aFavicon,
                             nsNavHistoryResultNode** aNode);
 

--- a/toolkit/components/places/src/nsNavHistoryQuery.cpp
+++ b/toolkit/components/places/src/nsNavHistoryQuery.cpp
@@ -169,16 +169,17 @@ static void SetOptionsKeyUint32(const ns
 #define QUERYKEY_EXPAND_QUERIES "expandQueries"
 #define QUERYKEY_FORCE_ORIGINAL_TITLE "originalTitle"
 #define QUERYKEY_INCLUDE_HIDDEN "includeHidden"
 #define QUERYKEY_REDIRECTS_MODE "redirectsMode"
 #define QUERYKEY_MAX_RESULTS "maxResults"
 #define QUERYKEY_QUERY_TYPE "queryType"
 #define QUERYKEY_TAG "tag"
 #define QUERYKEY_NOTTAGS "!tags"
+#define QUERYKEY_ASYNC_ENABLED "asyncEnabled"
 
 inline void AppendAmpersandIfNonempty(nsACString& aString)
 {
   if (! aString.IsEmpty())
     aString.Append('&');
 }
 inline void AppendInt16(nsACString& str, PRInt16 i)
 {
@@ -610,16 +611,22 @@ nsNavHistory::QueriesToQueryString(nsINa
 
   // queryType
   if (options->QueryType() !=  nsINavHistoryQueryOptions::QUERY_TYPE_HISTORY) {
     AppendAmpersandIfNonempty(queryString);
     queryString += NS_LITERAL_CSTRING(QUERYKEY_QUERY_TYPE "=");
     AppendInt16(queryString, options->QueryType());
   }
 
+  // async enabled
+  if (options->AsyncEnabled()) {
+    AppendAmpersandIfNonempty(queryString);
+    queryString += NS_LITERAL_CSTRING(QUERYKEY_ASYNC_ENABLED "=1");
+  }
+
   aQueryString.Assign(NS_LITERAL_CSTRING("place:") + queryString);
   return NS_OK;
 }
 
 
 // TokenizeQueryString
 
 nsresult
@@ -865,16 +872,20 @@ nsNavHistory::TokensToQueries(const nsTA
     // max results
     } else if (kvp.key.EqualsLiteral(QUERYKEY_MAX_RESULTS)) {
       SetOptionsKeyUint32(kvp.value, aOptions,
                           &nsINavHistoryQueryOptions::SetMaxResults);
     // query type
     } else if (kvp.key.EqualsLiteral(QUERYKEY_QUERY_TYPE)) {
       SetOptionsKeyUint16(kvp.value, aOptions,
                           &nsINavHistoryQueryOptions::SetQueryType);
+    // async enabled
+    } else if (kvp.key.EqualsLiteral(QUERYKEY_ASYNC_ENABLED)) {
+      SetOptionsKeyBool(kvp.value, aOptions,
+                        &nsINavHistoryQueryOptions::SetAsyncEnabled);
     // unknown key
     } else {
       NS_WARNING("TokensToQueries(), ignoring unknown key: ");
       NS_WARNING(kvp.key.get());
     }
   }
 
   if (folders.Length() != 0)
@@ -1515,16 +1526,31 @@ nsNavHistoryQueryOptions::SetQueryType(P
   // resultType is set.
   if (mResultType == RESULTS_AS_TAG_CONTENTS ||
       mResultType == RESULTS_AS_TAG_QUERY)
    return NS_OK;
   mQueryType = aQueryType;
   return NS_OK;
 }
 
+// asyncEnabled
+NS_IMETHODIMP
+nsNavHistoryQueryOptions::GetAsyncEnabled(PRBool* _asyncEnabled)
+{
+  *_asyncEnabled = mAsyncEnabled;
+  return NS_OK;
+}
+NS_IMETHODIMP
+nsNavHistoryQueryOptions::SetAsyncEnabled(PRBool aAsyncEnabled)
+{
+  mAsyncEnabled = aAsyncEnabled;
+  return NS_OK;
+}
+
+
 NS_IMETHODIMP
 nsNavHistoryQueryOptions::Clone(nsINavHistoryQueryOptions** aResult)
 {
   nsNavHistoryQueryOptions *clone = nsnull;
   nsresult rv = Clone(&clone);
   *aResult = clone;
   return rv;
 }
@@ -1541,16 +1567,17 @@ nsNavHistoryQueryOptions::Clone(nsNavHis
   result->mSort = mSort;
   result->mResultType = mResultType;
   result->mExcludeItems = mExcludeItems;
   result->mExcludeQueries = mExcludeQueries;
   result->mExpandQueries = mExpandQueries;
   result->mMaxResults = mMaxResults;
   result->mQueryType = mQueryType;
   result->mParentAnnotationToExclude = mParentAnnotationToExclude;
+  result->mAsyncEnabled = mAsyncEnabled;
 
   resultHolder.swap(*aResult);
   return NS_OK;
 }
 
 
 // AppendBoolKeyValueIfTrue
 

--- a/toolkit/components/places/src/nsNavHistoryQuery.h
+++ b/toolkit/components/places/src/nsNavHistoryQuery.h
@@ -117,25 +117,28 @@ NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHisto
 // nsNavHistoryQueryOptions
 
 #define NS_NAVHISTORYQUERYOPTIONS_IID \
 {0x95f8ba3b, 0xd681, 0x4d89, {0xab, 0xd1, 0xfd, 0xae, 0xf2, 0xa3, 0xde, 0x18}}
 
 class nsNavHistoryQueryOptions : public nsINavHistoryQueryOptions
 {
 public:
-  nsNavHistoryQueryOptions() : mSort(0), mResultType(0),
-                               mExcludeItems(PR_FALSE),
-                               mExcludeQueries(PR_FALSE),
-                               mExcludeReadOnlyFolders(PR_FALSE),
-                               mExpandQueries(PR_TRUE),
-                               mIncludeHidden(PR_FALSE),
-                               mRedirectsMode(nsINavHistoryQueryOptions::REDIRECTS_MODE_ALL),
-                               mMaxResults(0),
-                               mQueryType(nsINavHistoryQueryOptions::QUERY_TYPE_HISTORY)
+  nsNavHistoryQueryOptions()
+  : mSort(0)
+  , mResultType(0)
+  , mExcludeItems(PR_FALSE)
+  , mExcludeQueries(PR_FALSE)
+  , mExcludeReadOnlyFolders(PR_FALSE)
+  , mExpandQueries(PR_TRUE)
+  , mIncludeHidden(PR_FALSE)
+  , mRedirectsMode(nsINavHistoryQueryOptions::REDIRECTS_MODE_ALL)
+  , mMaxResults(0)
+  , mQueryType(nsINavHistoryQueryOptions::QUERY_TYPE_HISTORY)
+  , mAsyncEnabled(PR_FALSE)
   { }
 
   NS_DECLARE_STATIC_IID_ACCESSOR(NS_NAVHISTORYQUERYOPTIONS_IID)
 
   NS_DECL_ISUPPORTS
   NS_DECL_NSINAVHISTORYQUERYOPTIONS
 
   PRUint16 SortingMode() const { return mSort; }
@@ -143,16 +146,17 @@ public:
   PRBool ExcludeItems() const { return mExcludeItems; }
   PRBool ExcludeQueries() const { return mExcludeQueries; }
   PRBool ExcludeReadOnlyFolders() const { return mExcludeReadOnlyFolders; }
   PRBool ExpandQueries() const { return mExpandQueries; }
   PRBool IncludeHidden() const { return mIncludeHidden; }
   PRUint16 RedirectsMode() const { return mRedirectsMode; }
   PRUint32 MaxResults() const { return mMaxResults; }
   PRUint16 QueryType() const { return mQueryType; }
+  PRBool AsyncEnabled() const { return mAsyncEnabled; }
 
   nsresult Clone(nsNavHistoryQueryOptions **aResult);
 
 private:
   nsNavHistoryQueryOptions(const nsNavHistoryQueryOptions& other) {} // no copy
 
   // IF YOU ADD MORE ITEMS:
   //  * Add a new getter for C++ above if it makes sense
@@ -167,14 +171,14 @@ private:
   PRPackedBool mExcludeItems;
   PRPackedBool mExcludeQueries;
   PRPackedBool mExcludeReadOnlyFolders;
   PRPackedBool mExpandQueries;
   PRPackedBool mIncludeHidden;
   PRUint16 mRedirectsMode;
   PRUint32 mMaxResults;
   PRUint16 mQueryType;
+  PRBool mAsyncEnabled;
 };
 
 NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHistoryQueryOptions, NS_NAVHISTORYQUERYOPTIONS_IID)
 
 #endif // nsNavHistoryQuery_h_
-

--- a/toolkit/components/places/src/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/src/nsNavHistoryResult.cpp
@@ -19,16 +19,17 @@
  * Portions created by the Initial Developer are Copyright (C) 2005
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *   Brett Wilson <brettw@gmail.com> (original author)
  *   Dietrich Ayala <dietrich@mozilla.com>
  *   Asaf Romano <mano@mozilla.com>
  *   Marco Bonardo <mak77@bonardo.net>
+ *   Drew Willcoxon <adw@mozilla.com>
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either the GNU General Public License Version 2 or later (the "GPL"), or
  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
@@ -50,17 +51,16 @@
 #include "nsNetUtil.h"
 #include "nsPrintfCString.h"
 #include "nsString.h"
 #include "nsUnicharUtils.h"
 #include "prtime.h"
 #include "prprf.h"
 
 #include "nsIDynamicContainer.h"
-#include "mozStorageHelper.h"
 #include "nsCycleCollectionParticipant.h"
 #include "nsIClassInfo.h"
 #include "nsIProgrammingLanguage.h"
 #include "nsIXPCScriptable.h"
 
 #define TO_ICONTAINER(_node)                                                  \
     static_cast<nsINavHistoryContainerResultNode*>(_node)                      
 
@@ -386,26 +386,27 @@ nsNavHistoryResultNode::GetGeneratingOpt
     // generating options.
     if (IsContainer())
       return GetAsContainer()->mOptions;
 
     NS_NOTREACHED("Can't find a generating node for this container, perhaps FillStats has not been called on this tree yet?");
     return nsnull;
   }
 
+  // Look up the tree.  We want the options that were used to create this node,
+  // and since it has a parent, it's the options of an ancestor, not of the node
+  // itself.  So start at the parent.
   nsNavHistoryContainerResultNode* cur = mParent;
   while (cur) {
-    if (cur->IsFolder())
-      return cur->GetAsFolder()->mOptions;
-    else if (cur->IsQuery())
-      return cur->GetAsQuery()->mOptions;
+    if (cur->IsContainer())
+      return cur->GetAsContainer()->mOptions;
     cur = cur->mParent;
   }
 
-  // We should always find a folder or query node as an ancestor.
+  // We should always find a container node as an ancestor.
   NS_NOTREACHED("Can't find a generating node for this container, the tree seemes corrupted.");
   return nsnull;
 }
 
 
 NS_IMPL_ISUPPORTS_INHERITED1(nsNavHistoryVisitResultNode,
                              nsNavHistoryResultNode,
                              nsINavHistoryVisitResultNode)
@@ -461,33 +462,35 @@ nsNavHistoryContainerResultNode::nsNavHi
     const nsACString& aIconURI, PRUint32 aContainerType, PRBool aReadOnly,
     const nsACString& aDynamicContainerType, nsNavHistoryQueryOptions* aOptions) :
   nsNavHistoryResultNode(aURI, aTitle, 0, 0, aIconURI),
   mResult(nsnull),
   mContainerType(aContainerType),
   mExpanded(PR_FALSE),
   mChildrenReadOnly(aReadOnly),
   mOptions(aOptions),
-  mDynamicContainerType(aDynamicContainerType)
+  mDynamicContainerType(aDynamicContainerType),
+  mAsyncCanceledState(NOT_CANCELED)
 {
 }
 
 nsNavHistoryContainerResultNode::nsNavHistoryContainerResultNode(
     const nsACString& aURI, const nsACString& aTitle,
     PRTime aTime,
     const nsACString& aIconURI, PRUint32 aContainerType, PRBool aReadOnly,
     const nsACString& aDynamicContainerType, 
     nsNavHistoryQueryOptions* aOptions) :
   nsNavHistoryResultNode(aURI, aTitle, 0, aTime, aIconURI),
   mResult(nsnull),
   mContainerType(aContainerType),
   mExpanded(PR_FALSE),
   mChildrenReadOnly(aReadOnly),
   mOptions(aOptions),
-  mDynamicContainerType(aDynamicContainerType)
+  mDynamicContainerType(aDynamicContainerType),
+  mAsyncCanceledState(NOT_CANCELED)
 {
 }
 
 
 nsNavHistoryContainerResultNode::~nsNavHistoryContainerResultNode()
 {
   // Explicitly clean up array of children of this container.  We must ensure
   // all references are gone and all of their destructors are called.
@@ -540,108 +543,216 @@ nsNavHistoryContainerResultNode::GetCont
   *aContainerOpen = mExpanded;
   return NS_OK;
 }
 
 
 NS_IMETHODIMP
 nsNavHistoryContainerResultNode::SetContainerOpen(PRBool aContainerOpen)
 {
-  if (mExpanded && !aContainerOpen)
-    CloseContainer(PR_FALSE);
-  else if (!mExpanded && aContainerOpen)
-    OpenContainer();
+  if (aContainerOpen) {
+    if (!mExpanded) {
+      nsNavHistoryQueryOptions* options = GetGeneratingOptions();
+      if (options && options->AsyncEnabled())
+        OpenContainerAsync();
+      else
+        OpenContainer();
+    }
+  }
+  else {
+    if (mExpanded)
+      CloseContainer();
+    else if (mAsyncPendingStmt)
+      CancelAsyncOpen(PR_FALSE);
+  }
+
+  return NS_OK;
+}
+
+
+/**
+ * Notifies the result's observers of a change in the container's state.  The
+ * notification includes both the old and new states:  The old is aOldState, and
+ * the new is the container's current state.
+ *
+ * @param aOldState
+ *        The state being transitioned out of.
+ */
+nsresult
+nsNavHistoryContainerResultNode::NotifyOnStateChange(PRUint16 aOldState)
+{
+  nsNavHistoryResult* result = GetResult();
+  NS_ENSURE_STATE(result);
+
+  nsresult rv;
+  PRUint16 currState;
+  rv = GetState(&currState);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Notify via the new ContainerStateChanged observer method.
+  NOTIFY_RESULT_OBSERVERS(result,
+                          ContainerStateChanged(this, aOldState, currState));
+
+  // Notify via the deprecated observer methods.
+  if (currState == STATE_OPENED)
+    NOTIFY_RESULT_OBSERVERS(result, ContainerOpened(this));
+  else if (currState == STATE_CLOSED)
+    NOTIFY_RESULT_OBSERVERS(result, ContainerClosed(this));
+
+  return NS_OK;
+}
+
+
+NS_IMETHODIMP
+nsNavHistoryContainerResultNode::GetState(PRUint16* _state)
+{
+  NS_ENSURE_ARG_POINTER(_state);
+
+  *_state = mExpanded ? STATE_OPENED :
+            mAsyncPendingStmt ? STATE_LOADING :
+            STATE_CLOSED;
+
   return NS_OK;
 }
 
 
 /**
  * This handles the generic container case.  Other container types should
  * override this to do their own handling.
  */
 nsresult
 nsNavHistoryContainerResultNode::OpenContainer()
 {
-  NS_ASSERTION(!mExpanded, "Container must be expanded to close it");
+  NS_ASSERTION(!mExpanded, "Container must not be expanded to open it");
   mExpanded = PR_TRUE;
 
+  nsresult rv;
+
   if (IsDynamicContainer()) {
     // dynamic container API may want to fill us
-    nsresult rv;
     nsCOMPtr<nsIDynamicContainer> svc = do_GetService(mDynamicContainerType.get(), &rv);
     if (NS_SUCCEEDED(rv)) {
       svc->OnContainerNodeOpening(this, GetGeneratingOptions());
     } else {
       NS_WARNING("Unable to get dynamic container for ");
       NS_WARNING(mDynamicContainerType.get());
     }
     PRInt32 oldAccessCount = mAccessCount;
     FillStats();
     rv = ReverseUpdateStats(mAccessCount - oldAccessCount);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
-  nsNavHistoryResult* result = GetResult();
-  NOTIFY_RESULT_OBSERVERS(result, ContainerOpened(this));
+  rv = NotifyOnStateChange(STATE_CLOSED);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 /**
  * Unset aSuppressNotifications to notify observers on this change.  That is
  * the normal operation.  This is set to false for the recursive calls since the
  * root container that is being closed will handle recomputation of the visible
  * elements for its entire subtree.
  */
 nsresult
 nsNavHistoryContainerResultNode::CloseContainer(PRBool aSuppressNotifications)
 {
-  NS_ASSERTION(mExpanded, "Container must be expanded to close it");
-
-  // Recursively close all child containers.
-  for (PRInt32 i = 0; i < mChildren.Count(); ++i) {
-    if (mChildren[i]->IsContainer() &&
-        mChildren[i]->GetAsContainer()->mExpanded)
-      mChildren[i]->GetAsContainer()->CloseContainer(PR_TRUE);
-  }
-
-  mExpanded = PR_FALSE;
+  NS_ASSERTION((mExpanded && !mAsyncPendingStmt) ||
+               (!mExpanded && mAsyncPendingStmt),
+               "Container must be expanded or loading to close it");
 
   nsresult rv;
-  if (IsDynamicContainer()) {
-    // Notify dynamic containers that we are closing.
-    nsCOMPtr<nsIDynamicContainer> svc =
-      do_GetService(mDynamicContainerType.get(), &rv);
-    if (NS_SUCCEEDED(rv))
-      svc->OnContainerNodeClosed(this);
+  PRUint16 oldState;
+  rv = GetState(&oldState);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (mExpanded) {
+    // Recursively close all child containers.
+    for (PRInt32 i = 0; i < mChildren.Count(); ++i) {
+      if (mChildren[i]->IsContainer() &&
+          mChildren[i]->GetAsContainer()->mExpanded)
+        mChildren[i]->GetAsContainer()->CloseContainer(PR_TRUE);
+    }
+
+    mExpanded = PR_FALSE;
+
+    if (IsDynamicContainer()) {
+      // Notify dynamic containers that we are closing.
+      nsCOMPtr<nsIDynamicContainer> svc =
+        do_GetService(mDynamicContainerType.get());
+      if (svc)
+        svc->OnContainerNodeClosed(this);
+    }
   }
 
-  nsNavHistoryResult* result = GetResult();
-  if (!aSuppressNotifications)
-    NOTIFY_RESULT_OBSERVERS(result, ContainerClosed(TO_CONTAINER(this)));
+  // Be sure to set this to null before notifying observers.  It signifies that
+  // the container is no longer loading (if it was in the first place).
+  mAsyncPendingStmt = nsnull;
+
+  if (!aSuppressNotifications) {
+    rv = NotifyOnStateChange(oldState);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
 
   // If this is the root container of a result, we can tell the result to stop
   // observing changes, otherwise the result will stay in memory and updates
   // itself till it is cycle collected.
+  nsNavHistoryResult* result = GetResult();
+  NS_ENSURE_STATE(result);
   if (result->mRootNode == this) {
     result->StopObserving();
     // When reopening this node its result will be out of sync.
     // We must clear our children to ensure we will call FillChildren
     // again in such a case.
     if (this->IsQuery())
       this->GetAsQuery()->ClearChildren(PR_TRUE);
     else if (this->IsFolder())
       this->GetAsFolder()->ClearChildren(PR_TRUE);
   }
 
   return NS_OK;
 }
 
 
 /**
+ * The async version of OpenContainer.
+ */
+nsresult
+nsNavHistoryContainerResultNode::OpenContainerAsync()
+{
+  return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+
+/**
+ * Cancels the pending asynchronous Storage execution triggered by
+ * FillChildrenAsync, if it exists.  This method doesn't do much, because after
+ * cancelation Storage will call this node's HandleCompletion callback, where
+ * the real work is done.
+ *
+ * @param aRestart
+ *        If true, async execution will be restarted by HandleCompletion.
+ */
+void
+nsNavHistoryContainerResultNode::CancelAsyncOpen(PRBool aRestart)
+{
+  NS_ASSERTION(mAsyncPendingStmt, "Async execution canceled but not pending");
+
+  mAsyncCanceledState = aRestart ? CANCELED_RESTART_NEEDED : CANCELED;
+
+  // Cancel will fail if the pending statement has already been canceled.
+  // That's OK since this method may be called multiple times, and multiple
+  // cancels don't harm anything.
+  (void)mAsyncPendingStmt->Cancel();
+}
+
+
+/**
  * This builds up tree statistics from the bottom up.  Call with a container
  * and the indent level of that container.  To init the full tree, call with
  * the root container.  The default indent level is -1, which is appropriate
  * for the root level.
  *
  * CALL THIS AFTER FILLING ANY CONTAINER to update the parent and result node
  * pointers, even if you don't care about visit counts and last visit dates.
  */
@@ -2253,25 +2364,29 @@ nsNavHistoryQueryResultNode::OnRemoving(
  * without anything happening in between, it will be fast (this actually
  * happens when results are used as menus).
  */
 nsresult
 nsNavHistoryQueryResultNode::OpenContainer()
 {
   NS_ASSERTION(!mExpanded, "Container must be closed to open it");
   mExpanded = PR_TRUE;
+
+  nsresult rv;
+
   if (!CanExpand())
     return NS_OK;
   if (!mContentsValid) {
-    nsresult rv = FillChildren();
+    rv = FillChildren();
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
-  nsNavHistoryResult* result = GetResult();
-  NOTIFY_RESULT_OBSERVERS(result, ContainerOpened(TO_CONTAINER(this)));
+  rv = NotifyOnStateChange(STATE_CLOSED);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 /**
  * When we have valid results we can always give an exact answer.  When we
  * don't we just assume we'll have results, since actually doing the query
  * might be hard.  This is used to draw twisties on the tree, so precise results
@@ -3167,18 +3282,43 @@ nsNavHistoryFolderResultNode::OpenContai
       } else {
         NS_WARNING("Unable to get dynamic container for ");
         NS_WARNING(mDynamicContainerType.get());
       }
     }
   }
   mExpanded = PR_TRUE;
 
-  nsNavHistoryResult* result = GetResult();
-  NOTIFY_RESULT_OBSERVERS(result, ContainerOpened(TO_CONTAINER(this)));
+  rv = NotifyOnStateChange(STATE_CLOSED);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+
+/**
+ * The async version of OpenContainer.
+ */
+nsresult
+nsNavHistoryFolderResultNode::OpenContainerAsync()
+{
+  NS_ASSERTION(!mExpanded, "Container already expanded when opening it");
+
+  // If the children are valid, open the container synchronously.  This will be
+  // the case when the container has already been opened and any other time
+  // FillChildren or FillChildrenAsync has previously been called.
+  if (mContentsValid)
+    return OpenContainer();
+
+  nsresult rv = FillChildrenAsync();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = NotifyOnStateChange(STATE_CLOSED);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 /**
  * @see nsNavHistoryQueryResultNode::HasChildren.  The semantics here are a
  * little different.  Querying the contents of a bookmark folder is relatively
  * fast and it is common to have empty folders.  Therefore, we always want to
@@ -3323,18 +3463,29 @@ nsNavHistoryFolderResultNode::FillChildr
   NS_ENSURE_SUCCESS(rv, rv);
 
   // PERFORMANCE: it may be better to also fill any child folders at this point
   // so that we can draw tree twisties without doing a separate query later.
   // If we don't end up drawing twisties a lot, it doesn't matter. If we do
   // this, we should wrap everything in a transaction here on the bookmark
   // service's connection.
 
-  // it is important to call FillStats to fill in the parents on all
-  // nodes and the result node pointers on the containers
+  return OnChildrenFilled();
+}
+
+
+/**
+ * Performs some tasks after all the children of the container have been added.
+ * The container's contents are not valid until this method has been called.
+ */
+nsresult
+nsNavHistoryFolderResultNode::OnChildrenFilled()
+{
+  // It is important to call FillStats to fill in the parents on all
+  // nodes and the result node pointers on the containers.
   FillStats();
 
   if (mResult->mNeedsToApplySortingMode) {
     // We should repopulate container and then apply sortingMode.  To avoid
     // sorting 2 times we simply do that here.
     mResult->SetSortingMode(mResult->mSortingMode);
   }
   else {
@@ -3352,38 +3503,171 @@ nsNavHistoryFolderResultNode::FillChildr
   // mChildren array after sorting.  This is done for root node only.
   // Note, if count < max results, we won't do anything.
   if (!mParent && mOptions->MaxResults()) {
     while ((PRUint32)mChildren.Count() > mOptions->MaxResults())
       mChildren.RemoveObjectAt(mChildren.Count() - 1);
   }
 
   // Register with the result for updates.
-  nsNavHistoryResult* result = GetResult();
-  NS_ENSURE_STATE(result);
-  result->AddBookmarkFolderObserver(this, mItemId);
-  mIsRegisteredFolderObserver = PR_TRUE;
+  EnsureRegisteredAsFolderObserver();
 
   mContentsValid = PR_TRUE;
   return NS_OK;
 }
 
 
+/**
+ * Registers the node with its result as a folder observer if it is not already
+ * registered.
+ */
+void
+nsNavHistoryFolderResultNode::EnsureRegisteredAsFolderObserver()
+{
+  if (!mIsRegisteredFolderObserver && mResult) {
+    mResult->AddBookmarkFolderObserver(this, mItemId);
+    mIsRegisteredFolderObserver = PR_TRUE;
+  }
+}
+
+
+/**
+ * The async version of FillChildren.  This begins asynchronous execution by
+ * calling nsNavBookmarks::QueryFolderChildrenAsync.  During execution, this
+ * node's async Storage callbacks, HandleResult and HandleCompletion, will be
+ * called.
+ */
+nsresult
+nsNavHistoryFolderResultNode::FillChildrenAsync()
+{
+  NS_ASSERTION(!mContentsValid, "FillChildrenAsync when contents are valid");
+  NS_ASSERTION(mChildren.Count() == 0, "FillChildrenAsync when children exist");
+
+  // ProcessFolderNodeChild, called in HandleResult, increments this for every
+  // result row it processes.  Initialize it here as we begin async execution.
+  mAsyncBookmarkIndex = -1;
+
+  nsNavBookmarks* bmSvc = nsNavBookmarks::GetBookmarksService();
+  NS_ENSURE_TRUE(bmSvc, NS_ERROR_OUT_OF_MEMORY);
+  nsresult rv =
+    bmSvc->QueryFolderChildrenAsync(this, mItemId,
+                                    getter_AddRefs(mAsyncPendingStmt));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Register with the result for updates.  All updates during async execution
+  // will cause it to be restarted.
+  EnsureRegisteredAsFolderObserver();
+
+  return NS_OK;
+}
+
+
+/**
+ * A mozIStorageStatementCallback method.  Called during the async execution
+ * begun by FillChildrenAsync.
+ *
+ * @param aResultSet
+ *        The result set containing the data from the database.
+ */
+NS_IMETHODIMP
+nsNavHistoryFolderResultNode::HandleResult(mozIStorageResultSet* aResultSet)
+{
+  NS_ENSURE_ARG_POINTER(aResultSet);
+
+  nsNavBookmarks* bmSvc = nsNavBookmarks::GetBookmarksService();
+  if (!bmSvc) {
+    CancelAsyncOpen(PR_FALSE);
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  // Consume all the currently available rows of the result set.
+  nsCOMPtr<mozIStorageRow> row;
+  while (NS_SUCCEEDED(aResultSet->GetNextRow(getter_AddRefs(row))) && row) {
+    nsresult rv = bmSvc->ProcessFolderNodeRow(row, mOptions, &mChildren,
+                                              mAsyncBookmarkIndex);
+    if (NS_FAILED(rv)) {
+      CancelAsyncOpen(PR_FALSE);
+      return rv;
+    }
+  }
+
+  return NS_OK;
+}
+
+
+/**
+ * A mozIStorageStatementCallback method.  Called during the async execution
+ * begun by FillChildrenAsync.
+ *
+ * @param aReason
+ *        Indicates the final state of execution.
+ */
+NS_IMETHODIMP
+nsNavHistoryFolderResultNode::HandleCompletion(PRUint16 aReason)
+{
+  if (aReason == mozIStorageStatementCallback::REASON_FINISHED &&
+      mAsyncCanceledState == NOT_CANCELED) {
+    // Async execution successfully completed.  The container is ready to open.
+
+    nsresult rv = OnChildrenFilled();
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    if (IsDynamicContainer()) {
+      // The dynamic container service may want to change the bookmarks of this
+      // folder.
+      nsCOMPtr<nsIDynamicContainer> svc =
+        do_GetService(mDynamicContainerType.get(), &rv);
+      if (NS_SUCCEEDED(rv)) {
+        svc->OnContainerNodeOpening(
+          static_cast<nsNavHistoryContainerResultNode*>(this), mOptions);
+      }
+      else {
+        NS_WARNING("Unable to get dynamic container for ");
+        NS_WARNING(mDynamicContainerType.get());
+      }
+    }
+
+    mExpanded = PR_TRUE;
+    mAsyncPendingStmt = nsnull;
+
+    // Notify observers only after mExpanded and mAsyncPendingStmt are set.
+    rv = NotifyOnStateChange(STATE_LOADING);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  else if (mAsyncCanceledState == CANCELED_RESTART_NEEDED) {
+    // Async execution was canceled and needs to be restarted.
+    mAsyncCanceledState = NOT_CANCELED;
+    ClearChildren(PR_FALSE);
+    FillChildrenAsync();
+  }
+
+  else {
+    // Async execution failed or was canceled without restart.  Remove all
+    // children and close the container, notifying observers.
+    mAsyncCanceledState = NOT_CANCELED;
+    ClearChildren(PR_TRUE);
+    CloseContainer();
+  }
+
+  return NS_OK;
+}
+
+
 void
 nsNavHistoryFolderResultNode::ClearChildren(PRBool unregister)
 {
   for (PRInt32 i = 0; i < mChildren.Count(); ++i)
     mChildren[i]->OnRemoving();
   mChildren.Clear();
 
-  if (unregister && mContentsValid) {
-    if (mResult) {
-      mResult->RemoveBookmarkFolderObserver(this, mItemId);
-      mIsRegisteredFolderObserver = PR_FALSE;
-    }
+  PRBool needsUnregister = unregister && (mContentsValid || mAsyncPendingStmt);
+  if (needsUnregister && mResult && mIsRegisteredFolderObserver) {
+    mResult->RemoveBookmarkFolderObserver(this, mItemId);
+    mIsRegisteredFolderObserver = PR_FALSE;
   }
   mContentsValid = PR_FALSE;
 }
 
 
 /**
  * This is called to update the result when something has changed that we
  * can not incrementally update.
@@ -3484,16 +3768,26 @@ nsNavHistoryFolderResultNode::FindChildB
       *aNodeIndex = i;
       return mChildren[i];
     }
   }
   return nsnull;
 }
 
 
+// Used by nsNavHistoryFolderResultNode's nsINavBookmarkObserver methods below.
+// If the container is notified of a bookmark event while asynchronous execution
+// is pending, this restarts it and returns.
+#define RESTART_AND_RETURN_IF_ASYNC_PENDING() \
+  if (mAsyncPendingStmt) { \
+    CancelAsyncOpen(PR_TRUE); \
+    return NS_OK; \
+  }
+
+
 NS_IMETHODIMP
 nsNavHistoryFolderResultNode::OnBeginUpdateBatch()
 {
   return NS_OK;
 }
 
 
 NS_IMETHODIMP
@@ -3524,16 +3818,18 @@ nsNavHistoryFolderResultNode::OnItemAdde
   else if (aIndex > mChildren.Count()) {
     if (!excludeItems) {
       // Something wrong happened while updating indexes.
       NS_NOTREACHED("Invalid index for item adding: greater than count");
     }
     aIndex = mChildren.Count();
   }
 
+  RESTART_AND_RETURN_IF_ASYNC_PENDING();
+
   nsNavBookmarks* bookmarks = nsNavBookmarks::GetBookmarksService();
   NS_ENSURE_TRUE(bookmarks, NS_ERROR_OUT_OF_MEMORY);
 
   nsresult rv;
 
   // Check for query URIs, which are bookmarks, but treated as containers
   // in results and views.
   PRBool isQuery = PR_FALSE;
@@ -3610,16 +3906,18 @@ nsNavHistoryFolderResultNode::OnItemRemo
   // We only care about notifications when a child changes.  When the deleted
   // item is us, our parent should also be registered and will remove us from
   // its list.
   if (mItemId == aItemId)
     return NS_OK;
 
   NS_ASSERTION(aParentFolder == mItemId, "Got wrong bookmark update");
 
+  RESTART_AND_RETURN_IF_ASYNC_PENDING();
+
   PRBool excludeItems = (mResult && mResult->mRootNode->mOptions->ExcludeItems()) ||
                         (mParent && mParent->mOptions->ExcludeItems()) ||
                         mOptions->ExcludeItems();
 
   // don't trust the index from the bookmark service, find it ourselves.  The
   // sorting could be different, or the bookmark services indices and ours might
   // be out of sync somehow.
   PRUint32 index;
@@ -3745,16 +4043,18 @@ nsNavHistoryFolderResultNode::OnItemChan
   if (mQueryItemId != -1) {
     PRBool isTitleChange = aProperty.EqualsLiteral("title");
     if ((mQueryItemId == aItemId && !isTitleChange) ||
         (mQueryItemId != aItemId && isTitleChange)) {
       return NS_OK;
     }
   }
 
+  RESTART_AND_RETURN_IF_ASYNC_PENDING();
+
   return nsNavHistoryResultNode::OnItemChanged(aItemId, aProperty,
                                                aIsAnnotationProperty,
                                                aNewValue,
                                                aLastModified,
                                                aItemType);
 }
 
 /**
@@ -3764,16 +4064,19 @@ NS_IMETHODIMP
 nsNavHistoryFolderResultNode::OnItemVisited(PRInt64 aItemId,
                                             PRInt64 aVisitId, PRTime aTime)
 {
   PRBool excludeItems = (mResult && mResult->mRootNode->mOptions->ExcludeItems()) ||
                         (mParent && mParent->mOptions->ExcludeItems()) ||
                         mOptions->ExcludeItems();
   if (excludeItems)
     return NS_OK; // don't update items when we aren't displaying them
+
+  RESTART_AND_RETURN_IF_ASYNC_PENDING();
+
   if (!StartIncrementalUpdate())
     return NS_OK;
 
   PRUint32 nodeIndex;
   nsNavHistoryResultNode* node = FindChildById(aItemId, &nodeIndex);
   if (!node)
     return NS_ERROR_FAILURE;
 
@@ -3815,16 +4118,19 @@ nsNavHistoryFolderResultNode::OnItemVisi
 
 NS_IMETHODIMP
 nsNavHistoryFolderResultNode::OnItemMoved(PRInt64 aItemId, PRInt64 aOldParent,
                                           PRInt32 aOldIndex, PRInt64 aNewParent,
                                           PRInt32 aNewIndex, PRUint16 aItemType)
 {
   NS_ASSERTION(aOldParent == mItemId || aNewParent == mItemId,
                "Got a bookmark message that doesn't belong to us");
+
+  RESTART_AND_RETURN_IF_ASYNC_PENDING();
+
   if (!StartIncrementalUpdate())
     return NS_OK; // entire container was refreshed for us
 
   if (aOldParent == aNewParent) {
     // getting moved within the same folder, we don't want to do a remove and
     // an add because that will lose your tree state.
 
     // adjust bookmark indices

--- a/toolkit/components/places/src/nsNavHistoryResult.h
+++ b/toolkit/components/places/src/nsNavHistoryResult.h
@@ -44,16 +44,18 @@
 
 #ifndef nsNavHistoryResult_h_
 #define nsNavHistoryResult_h_
 
 #include "nsTArray.h"
 #include "nsInterfaceHashtable.h"
 #include "nsDataHashtable.h"
 #include "nsCycleCollectionParticipant.h"
+#include "mozilla/storage.h"
+#include "Helpers.h"
 
 class nsNavHistory;
 class nsNavHistoryQuery;
 class nsNavHistoryQueryOptions;
 
 class nsNavHistoryContainerResultNode;
 class nsNavHistoryFolderResultNode;
 class nsNavHistoryQueryResultNode;
@@ -451,16 +453,18 @@ public:
 //    This is the base class for all nodes that can have children. It is
 //    overridden for nodes that are dynamically populated such as queries and
 //    folders. It is used directly for simple containers such as host groups
 //    in history views.
 
 // derived classes each provide their own implementation of has children and
 // forward the rest to us using this macro
 #define NS_FORWARD_CONTAINERNODE_EXCEPT_HASCHILDREN_AND_READONLY \
+  NS_IMETHOD GetState(PRUint16* _state) \
+    { return nsNavHistoryContainerResultNode::GetState(_state); } \
   NS_IMETHOD GetContainerOpen(PRBool *aContainerOpen) \
     { return nsNavHistoryContainerResultNode::GetContainerOpen(aContainerOpen); } \
   NS_IMETHOD SetContainerOpen(PRBool aContainerOpen) \
     { return nsNavHistoryContainerResultNode::SetContainerOpen(aContainerOpen); } \
   NS_IMETHOD GetChildCount(PRUint32 *aChildCount) \
     { return nsNavHistoryContainerResultNode::GetChildCount(aChildCount); } \
   NS_IMETHOD GetChild(PRUint32 index, nsINavHistoryResultNode **_retval) \
     { return nsNavHistoryContainerResultNode::GetChild(index, _retval); } \
@@ -527,16 +531,18 @@ public:
   virtual void OnRemoving();
 
   PRBool AreChildrenVisible();
 
   // Overridded by descendents to populate.
   virtual nsresult OpenContainer();
   nsresult CloseContainer(PRBool aSuppressNotifications = PR_FALSE);
 
+  virtual nsresult OpenContainerAsync();
+
   // This points to the result that owns this container. All containers have
   // their result pointer set so we can quickly get to the result without having
   // to walk the tree. Yet, this also saves us from storing a million pointers
   // for every leaf node to the result.
   nsRefPtr<nsNavHistoryResult> mResult;
 
   // For example, RESULT_TYPE_QUERY. Query and Folder results override GetType
   // so this is not used, but is still kept in sync.
@@ -644,16 +650,29 @@ public:
                          const nsCString& aSpec,
                          nsCOMArray<nsNavHistoryResultNode>* aMatches);
   nsresult UpdateURIs(PRBool aRecursive, PRBool aOnlyOne, PRBool aUpdateSort,
                       const nsCString& aSpec,
                       nsresult (*aCallback)(nsNavHistoryResultNode*,void*, nsNavHistoryResult*),
                       void* aClosure);
   nsresult ChangeTitles(nsIURI* aURI, const nsACString& aNewTitle,
                         PRBool aRecursive, PRBool aOnlyOne);
+
+protected:
+
+  enum AsyncCanceledState {
+    NOT_CANCELED, CANCELED, CANCELED_RESTART_NEEDED
+  };
+
+  void CancelAsyncOpen(PRBool aRestart);
+  nsresult NotifyOnStateChange(PRUint16 aOldState);
+
+  PRBool mAsyncEnabled;
+  nsCOMPtr<mozIStoragePendingStatement> mAsyncPendingStmt;
+  PRBool mAsyncCanceledState;
 };
 
 NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHistoryContainerResultNode,
                               NS_NAVHISTORYCONTAINERRESULTNODE_IID)
 
 // nsNavHistoryQueryResultNode
 //
 //    Overridden container type for complex queries over history and/or
@@ -731,17 +750,18 @@ public:
 
 
 // nsNavHistoryFolderResultNode
 //
 //    Overridden container type for bookmark folders. It will keep the contents
 //    of the folder in sync with the bookmark service.
 
 class nsNavHistoryFolderResultNode : public nsNavHistoryContainerResultNode,
-                                     public nsINavHistoryQueryResultNode
+                                     public nsINavHistoryQueryResultNode,
+                                     public mozilla::places::AsyncStatementCallback
 {
 public:
   nsNavHistoryFolderResultNode(const nsACString& aTitle,
                                nsNavHistoryQueryOptions* options,
                                PRInt64 aFolderId,
                                const nsACString& aDynamicContainerType);
 
   virtual ~nsNavHistoryFolderResultNode();
@@ -760,23 +780,25 @@ public:
   NS_FORWARD_CONTAINERNODE_EXCEPT_HASCHILDREN_AND_READONLY
   NS_IMETHOD GetHasChildren(PRBool* aHasChildren);
   NS_IMETHOD GetChildrenReadOnly(PRBool *aChildrenReadOnly);
   NS_IMETHOD GetItemId(PRInt64 *aItemId);
   NS_DECL_NSINAVHISTORYQUERYRESULTNODE
 
   virtual nsresult OpenContainer();
 
+  virtual nsresult OpenContainerAsync();
+  NS_DECL_ASYNCSTATEMENTCALLBACK
+
   // This object implements a bookmark observer interface without deriving from
   // the bookmark observers. This is called from the result's actual observer
   // and it knows all observers are FolderResultNodes
   NS_DECL_NSINAVBOOKMARKOBSERVER
 
   virtual void OnRemoving();
-public:
 
   // this indicates whether the folder contents are valid, they don't go away
   // after the container is closed until a notification comes in
   PRBool mContentsValid;
 
   // If the node is generated from a place:folder=X query, this is the query's
   // itemId.
   PRInt64 mQueryItemId;
@@ -788,17 +810,22 @@ public:
   PRBool StartIncrementalUpdate();
   void ReindexRange(PRInt32 aStartIndex, PRInt32 aEndIndex, PRInt32 aDelta);
 
   nsNavHistoryResultNode* FindChildById(PRInt64 aItemId,
                                         PRUint32* aNodeIndex);
 
 private:
 
+  nsresult OnChildrenFilled();
+  void EnsureRegisteredAsFolderObserver();
+  nsresult FillChildrenAsync();
+
   PRBool mIsRegisteredFolderObserver;
+  PRInt32 mAsyncBookmarkIndex;
 };
 
 // nsNavHistorySeparatorResultNode
 //
 // Separator result nodes do not hold any data.
 class nsNavHistorySeparatorResultNode : public nsNavHistoryResultNode
 {
 public:

--- a/toolkit/components/places/tests/queries/head_queries.js
+++ b/toolkit/components/places/tests/queries/head_queries.js
@@ -234,16 +234,19 @@ function populateDB(aArray) {
       }
 
       if (qdata.isDynContainer) {
         PlacesUtils.bookmarks.createDynamicContainer(qdata.parentFolder,
                                                      qdata.title,
                                                      qdata.contractId,
                                                      qdata.index);
       }
+
+      if (qdata.isSeparator)
+        PlacesUtils.bookmarks.insertSeparator(qdata.parentFolder, qdata.index);
     } catch (ex) {
       // use the data object here in case instantiation of qdata failed
       LOG("Problem with this URI: " + data.uri);
       do_throw("Error creating database: " + ex + "\n");
     }
   }); // End of function and array
 }
 
@@ -302,16 +305,17 @@ function queryData(obj) {
   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 : today;
   this.dateAdded = obj.dateAdded ? obj.dateAdded : today;
   this.keyword = obj.keyword ? obj.keyword : "";
   this.visitCount = obj.visitCount ? obj.visitCount : 0;
   this.readOnly = obj.readOnly ? obj.readOnly : false;
+  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 = { }
@@ -334,22 +338,22 @@ function compareArrayToResult(aArray, aR
   var expectedResultCount = aArray.filter(function(aEl) { return aEl.isInQuery; }).length;
   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);
       LOG("testing testData[" + i + "] vs result[" + inQueryIndex + "]");
-      if(!aArray[i].isFolder) {
+      if (!aArray[i].isFolder && !aArray[i].isSeparator) {
         LOG("testing testData[" + aArray[i].uri + "] vs result[" + child.uri + "]");
         if (aArray[i].uri != child.uri)
           do_throw("Expected " + aArray[i].uri + " found " + child.uri);
       }
-      if (aArray[i].title != child.title)
+      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);

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_async.js
@@ -0,0 +1,395 @@
+/* -*- Mode: Java; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Places.
+ *
+ * The Initial Developer of the Original Code is
+ * the Mozilla Foundation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Drew Willcoxon <adw@mozilla.com> (Original Author)
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+let gTests = [
+  {
+    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 = {};
+}
+
+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.
+    this.observer = let (self = this) {
+      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);
+        }
+      },
+      containerOpened: function (container) {},
+      containerClosed: function (container) {}
+    };
+    this.result.addObserver(this.observer, false);
+
+    print("Opening container");
+    this.result.root.containerOpen = true;
+  },
+
+  /**
+   * Override this if need be.
+   */
+  run: function () {
+    this.openContainer();
+  },
+
+  /**
+   * 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" }
+    ]);
+    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);
+    doNextTest();
+  }
+};
+
+/**
+ * This makes it a little bit easier to use the functions of head_queries.js.
+ */
+let DataHelper = {
+  defaults: {
+    bookmark: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder,
+      uri: "http://example.com/",
+      title: "test bookmark"
+    },
+
+    folder: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder,
+      title: "test folder"
+    },
+
+    separator: {
+      parent: PlacesUtils.bookmarks.unfiledBookmarksFolder
+    }
+  },
+
+  /**
+   * Converts an array of simple bookmark item descriptions to the more verbose
+   * format required by 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) {
+    return let (self = this) 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,
+          parentFolder: dat.parent,
+          index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+          title: dat.title,
+          isInQuery: true
+        };
+      case "separator":
+        return {
+          isSeparator: true,
+          parentFolder: dat.parent,
+          index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+          isInQuery: true
+        };
+      case "folder":
+        return {
+          isFolder: true,
+          readOnly: false,
+          parentFolder: dat.parent,
+          index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+          title: dat.title,
+          isInQuery: true
+        };
+      default:
+        do_throw("Unknown data type when populating DB: " + type);
+      }
+    });
+  },
+
+  /**
+   * 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] in Iterator(aDefaults)) {
+      dat[prop] = aData.hasOwnProperty(prop) ? aData[prop] : val;
+    }
+    return dat;
+  }
+};
+
+function doNextTest() {
+  remove_all_bookmarks();
+  if (gTests.length === 0) {
+    print("All tests done, exiting");
+    do_test_finished();
+  }
+  else {
+    let test = gTests.shift();
+    test.__proto__ = new Test();
+    test.setup();
+    print("------ Running test: " + test.desc);
+    test.run();
+  }
+}
+
+function run_test() {
+  do_test_pending();
+  doNextTest();
+}