Quelle  nsNavHistoryResult.cpp   Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "nsNavHistory.h"
#include "nsNavBookmarks.h"
#include "nsFaviconService.h"
#include "nsDebug.h"
#include "nsNetUtil.h"
#include "nsString.h"
#include "nsReadableUtils.h"
#include "prtime.h"
#include "mozIStorageRow.h"
#include "mozIStorageResultSet.h"
#include "nsQueryObject.h"
#include "mozilla/dom/PlacesObservers.h"
#include "mozilla/dom/PlacesVisit.h"
#include "mozilla/dom/PlacesVisitRemoved.h"
#include "mozilla/dom/PlacesVisitTitle.h"
#include "mozilla/dom/PlacesBookmarkAddition.h"
#include "mozilla/dom/PlacesBookmarkRemoved.h"
#include "mozilla/dom/PlacesBookmarkMoved.h"
#include "mozilla/dom/PlacesBookmarkKeyword.h"
#include "mozilla/dom/PlacesBookmarkTags.h"
#include "mozilla/dom/PlacesBookmarkTime.h"
#include "mozilla/dom/PlacesBookmarkTitle.h"
#include "mozilla/dom/PlacesBookmarkUrl.h"
#include "mozilla/dom/PlacesFavicon.h"

#include "nsCycleCollectionParticipant.h"

// Thanks, Windows.h :(
#undef CompareString

#define TO_ICONTAINER(_node) \
  static_cast<nsINavHistoryContainerResultNode*>(_node)

#define TO_CONTAINER(_node) static_cast<nsNavHistoryContainerResultNode*>(_node)

#define NOTIFY_RESULT_OBSERVERS_RET(_result, _method, _ret)               \
  PR_BEGIN_MACRO                                                          \
  NS_ENSURE_TRUE(_result, _ret);                                          \
  if (!_result->mSuppressNotifications) {                                 \
    ENUMERATE_WEAKARRAY(_result->mObservers, nsINavHistoryResultObserver, \
                        _method)                                          \
  }                                                                       \
  PR_END_MACRO

#define NOTIFY_RESULT_OBSERVERS(_result, _method) \
  NOTIFY_RESULT_OBSERVERS_RET(_result, _method, NS_ERROR_UNEXPECTED)

// What we want is: NS_INTERFACE_MAP_ENTRY(self) for static IID accessors,
// but some of our classes (like nsNavHistoryResult) have an ambiguous base
// class of nsISupports which prevents this from working (the default macro
// converts it to nsISupports, then addrefs it, then returns it). Therefore, we
// expand the macro here and change it so that it works. Yuck.
#define NS_INTERFACE_MAP_STATIC_AMBIGUOUS(_class) \
  if (aIID.Equals(NS_GET_IID(_class))) {          \
    NS_ADDREF(this);                              \
    *aInstancePtr = this;                         \
    return NS_OK;                                 \
  } else

// Number of changes to handle separately in a batch.  If more changes are
// requested the node will switch to full refresh mode.
#define MAX_BATCH_CHANGES_BEFORE_REFRESH 5

// Number of Page_removed events to handle by simply refreshing all containers,
// because doing so is much faster than incremental updates.
#define MAX_PAGE_REMOVES_BEFORE_REFRESH 10

using namespace mozilla;
using namespace mozilla::dom;
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.
 *
 *  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();

  bool nonTimeBasedItems = false;
  bool domainBasedItems = false;

  if (aQuery->Parents().Length() > 0 || aQuery->Tags().Length() > 0 ||
      (aOptions->QueryType() ==
           nsINavHistoryQueryOptions::QUERY_TYPE_BOOKMARKS &&
       hasSearchTerms)) {
    return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
  }

  // Note: we don't currently have any complex non-bookmarked items, but these
  // are expected to be added. Put detection of these items here.
  if (hasSearchTerms || !aQuery->Domain().IsVoid() ||
      aQuery->Uri() != nullptr) {
    nonTimeBasedItems = true;
  }

  if (!aQuery->Domain().IsVoid()) {
    domainBasedItems = true;
  }

  if (aOptions->ResultType() ==
      nsINavHistoryQueryOptions::RESULTS_AS_TAGS_ROOT) {
    return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
  }

  if (aOptions->ResultType() ==
      nsINavHistoryQueryOptions::RESULTS_AS_ROOTS_QUERY) {
    return QUERYUPDATE_MOBILEPREF;
  }

  if (aOptions->ResultType() ==
      nsINavHistoryQueryOptions::RESULTS_AS_LEFT_PANE_QUERY) {
    return QUERYUPDATE_NONE;
  }

  // Whenever there is a maximum number of results,
  // and we are not a bookmark query we must requery. This
  // is because we can't generally know if any given addition/change causes
  // the item to be in the top N items in the database.
  uint16_t sortingMode = aOptions->SortingMode();
  if (aOptions->MaxResults() > 0 &&
      sortingMode != nsINavHistoryQueryOptions::SORT_BY_DATE_ASCENDING &&
      sortingMode != nsINavHistoryQueryOptions::SORT_BY_DATE_DESCENDING) {
    return QUERYUPDATE_COMPLEX;
  }

  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;
}

bool isQueryMatchingVisitDetails(
    const RefPtr<nsNavHistoryQuery>& query,
    const RefPtr<nsNavHistoryQueryOptions>& options, bool hidden,
    PRTime visitTime, uint32_t transition, nsIURI* uri) {
  if (hidden && !options->IncludeHidden()) {
    return false;
  }

  bool hasIt;
  if (NS_SUCCEEDED(query->GetHasBeginTime(&hasIt)) && hasIt) {
    PRTime beginTime = nsNavHistory::NormalizeTime(query->BeginTimeReference(),
                                                   query->BeginTime());
    if (visitTime < beginTime) {
      return false;
    }
  }
  if (NS_SUCCEEDED(query->GetHasEndTime(&hasIt)) && hasIt) {
    PRTime endTime = nsNavHistory::NormalizeTime(query->EndTimeReference(),
                                                 query->EndTime());
    if (visitTime > endTime) {
      return false;
    }
  }

  const nsTArray<uint32_t>& transitions = query->Transitions();
  if (transition > 0 && transitions.Length() &&
      !transitions.Contains(transition)) {
    return false;
  }

  if (!query->Domain().IsVoid()) {
    nsAutoCString asciiRequest;
    if (NS_FAILED(asciiHostNameFromHostString(query->Domain(), asciiRequest))) {
      return false;
    }
    if (query->DomainIsHost()) {
      // Exact domain match.
      nsAutoCString host;
      if (NS_FAILED(uri->GetAsciiHost(host)) || !asciiRequest.Equals(host)) {
        return false;
      }
    } else {
      // Wildcard domain match, subdomains are included.
      nsNavHistory* history = nsNavHistory::GetHistoryService();
      if (history) {
        nsAutoCString domain;
        history->DomainNameFromURI(uri, domain);
        if (!asciiRequest.Equals(domain)) {
          return false;
        }
      }
    }
  }

  if (query->Uri()) {
    bool equals;
    if (NS_FAILED(query->Uri()->Equals(uri, &equals)) || !equals) {
      return false;
    }
  }

  return true;
}

inline bool isTimeFilteredQuery(const RefPtr<nsNavHistoryQuery>& query) {
  bool hasIt;
  return (NS_SUCCEEDED(query->GetHasBeginTime(&hasIt)) && hasIt) ||
         (NS_SUCCEEDED(query->GetHasEndTime(&hasIt)) && hasIt);
}

inline bool caseInsensitiveFind(const nsACString& aSearchTerms,
                                const nsACString& aTarget) {
  nsACString::const_iterator start, end;
  aTarget.BeginReading(start);
  aTarget.EndReading(end);
  return CaseInsensitiveFindInReadable(aSearchTerms, start, end);
}

bool isQuerySearchTermsMatching(const RefPtr<nsNavHistoryQuery>& aQuery,
                                const nsACString& aURI,
                                const nsACString& aTitle,
                                const nsAString& aTags) {
  nsAutoCString searchTerms = NS_ConvertUTF16toUTF8(aQuery->SearchTerms());
  if ((!aTitle.IsEmpty() && caseInsensitiveFind(searchTerms, aTitle)) ||
      (!aURI.IsEmpty() && caseInsensitiveFind(searchTerms, aURI))) {
    return true;
  }

  if (aTags.IsEmpty()) {
    return false;
  }
  for (const nsAString& tag : aTags.Split(',')) {
    if (caseInsensitiveFind(searchTerms, NS_ConvertUTF16toUTF8(tag))) {
      return true;
    }
  }
  return false;
}

bool isQuerySearchTermsMatching(const RefPtr<nsNavHistoryQuery>& aQuery,
                                const RefPtr<nsNavHistoryResultNode>& aNode) {
  return isQuerySearchTermsMatching(aQuery, aNode->mURI, aNode->mTitle,
                                    aNode->mTags);
}

// Emulate string comparison (used for sorting) for PRTime and int.
inline int32_t ComparePRTime(PRTime a, PRTime b) {
  if (a == b) {
    return 0;
  }
  return a < b ? -1 : 1;
}
inline int32_t CompareIntegers(uint32_t a, uint32_t b) {
  // These are unlikely to overflow, so just cast for now.
  return static_cast<int32_t>(a) - static_cast<int32_t>(b);
}

}  // anonymous namespace

NS_IMPL_CYCLE_COLLECTION(nsNavHistoryResultNode, mParent)

NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsNavHistoryResultNode)
  NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsINavHistoryResultNode)
  NS_INTERFACE_MAP_ENTRY(nsINavHistoryResultNode)
NS_INTERFACE_MAP_END

NS_IMPL_CYCLE_COLLECTING_ADDREF(nsNavHistoryResultNode)
NS_IMPL_CYCLE_COLLECTING_RELEASE(nsNavHistoryResultNode)

nsNavHistoryResultNode::nsNavHistoryResultNode(const nsACString& aURI,
                                               const nsACString& aTitle,
                                               uint32_t aAccessCount,
                                               PRTime aTime)
    : mParent(nullptr),
      mURI(aURI),
      mTitle(aTitle),
      mAccessCount(aAccessCount),
      mTime(aTime),
      mBookmarkIndex(-1),
      mItemId(-1),
      mVisitId(-1),
      mDateAdded(0),
      mLastModified(0),
      mIndentLevel(-1),
      mFrecency(0),
      mHidden(false),
      mTransitionType(0) {
  mTags.SetIsVoid(true);
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetIcon(nsACString& aIcon) {
  if (this->IsContainer() || mURI.IsEmpty()) {
    return NS_OK;
  }

  aIcon.AppendLiteral("page-icon:");
  aIcon.Append(mURI);

  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetParent(nsINavHistoryContainerResultNode** aParent) {
  NS_IF_ADDREF(*aParent = mParent);
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetParentResult(nsINavHistoryResult** aResult) {
  *aResult = nullptr;
  if (IsContainer()) {
    NS_IF_ADDREF(*aResult = GetAsContainer()->mResult);
  } else if (mParent) {
    NS_IF_ADDREF(*aResult = mParent->mResult);
  }

  NS_ENSURE_STATE(*aResult);
  return NS_OK;
}

void nsNavHistoryResultNode::SetTags(const nsAString& aTags) {
  if (aTags.IsVoid()) {
    mTags.SetIsVoid(true);
    return;
  }

  mTags.Assign(aTags);
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetTags(nsAString& aTags) {
  if (mTags.IsVoid()) {
    aTags.SetIsVoid(true);
    return NS_OK;
  }

  aTags.Assign(mTags);
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetPageGuid(nsACString& aPageGuid) {
  aPageGuid = mPageGuid;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetBookmarkGuid(nsACString& aBookmarkGuid) {
  aBookmarkGuid = mBookmarkGuid;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetVisitId(int64_t* aVisitId) {
  *aVisitId = mVisitId;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryResultNode::GetVisitType(uint32_t* aVisitType) {
  *aVisitType = mTransitionType;
  return NS_OK;
}

void nsNavHistoryResultNode::OnRemoving() { mParent = nullptr; }

/**
 * This will find the result for this node.  We can ask the nearest container
 * for this value (either ourselves or our parents should be a container,
 * and all containers have result pointers).
 *
 * @note The result may be null, if the container is detached from the result
 *       who owns it.
 */
nsNavHistoryResult* nsNavHistoryResultNode::GetResult() {
  nsNavHistoryResultNode* node = this;
  do {
    if (node->IsContainer()) {
      nsNavHistoryContainerResultNode* container = TO_CONTAINER(node);
      return container->mResult;
    }
    node = node->mParent;
  } while (node);
  MOZ_ASSERT(false, "No container node found in hierarchy!");
  return nullptr;
}

NS_IMPL_CYCLE_COLLECTION_INHERITED(nsNavHistoryContainerResultNode,
                                   nsNavHistoryResultNode, mResult, mChildren)

NS_IMPL_ADDREF_INHERITED(nsNavHistoryContainerResultNode,
                         nsNavHistoryResultNode)
NS_IMPL_RELEASE_INHERITED(nsNavHistoryContainerResultNode,
                          nsNavHistoryResultNode)

NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsNavHistoryContainerResultNode)
  NS_INTERFACE_MAP_STATIC_AMBIGUOUS(nsNavHistoryContainerResultNode)
  NS_INTERFACE_MAP_ENTRY(nsINavHistoryContainerResultNode)
NS_INTERFACE_MAP_END_INHERITING(nsNavHistoryResultNode)

nsNavHistoryContainerResultNode::nsNavHistoryContainerResultNode(
    const nsACString& aURI, const nsACString& aTitle, PRTime aTime,
    uint32_t aContainerType, nsNavHistoryQueryOptions* aOptions)
    : nsNavHistoryResultNode(aURI, aTitle, 0, aTime),
      mResult(nullptr),
      mContainerType(aContainerType),
      mExpanded(false),
      mOptions(aOptions),
      mAsyncCanceledState(NOT_CANCELED) {
  MOZ_ASSERT(mOptions);
  MOZ_ALWAYS_SUCCEEDS(mOptions->Clone(getter_AddRefs(mOriginalOptions)));
}

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.
  mChildren.Clear();
}

/**
 * Containers should notify their children that they are being removed when the
 * container is being removed.
 */
void nsNavHistoryContainerResultNode::OnRemoving() {
  nsNavHistoryResultNode::OnRemoving();
  for (nsNavHistoryResultNode* child : mChildren) {
    child->OnRemoving();
  }
  mChildren.Clear();
  mResult = nullptr;
}

bool nsNavHistoryContainerResultNode::AreChildrenVisible() {
  nsNavHistoryResult* result = GetResult();
  if (!result) {
    MOZ_ASSERT_UNREACHABLE("Invalid result");
    return false;
  }

  if (!mExpanded) return false;

  // Now check if any ancestor is closed.
  nsNavHistoryContainerResultNode* ancestor = mParent;
  while (ancestor) {
    if (!ancestor->mExpanded) return false;

    ancestor = ancestor->mParent;
  }

  return true;
}

nsresult nsNavHistoryContainerResultNode::OnVisitsRemoved(nsIURI* aURI) {
  if (!AreChildrenVisible()) {
    return NS_OK;
  }

  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);
  if (result->CanSkipHistoryDetailsNotifications()) {
    return NS_OK;
  }

  nsAutoCString spec;
  nsresult rv = aURI->GetSpec(spec);
  NS_ENSURE_SUCCESS(rv, rv);

  nsCOMArray<nsNavHistoryResultNode> nodes;
  FindChildrenByURI(spec, &nodes);
  for (int32_t i = 0; i < nodes.Count(); i++) {
    nodes[i]->OnVisitsRemoved();
  }

  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetContainerOpen(bool* aContainerOpen) {
  *aContainerOpen = mExpanded;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryContainerResultNode::SetContainerOpen(bool aContainerOpen) {
  if (aContainerOpen) {
    if (!mExpanded) {
      if (mOptions->AsyncEnabled()) {
        OpenContainerAsync();
      } else {
        OpenContainer();
      }
    }
  } else {
    if (mExpanded) {
      CloseContainer();
    } else if (mAsyncPendingStmt) {
      CancelAsyncOpen(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(
    uint16_t aOldState) {
  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);

  nsresult rv;
  uint16_t currState;
  rv = GetState(&currState);
  NS_ENSURE_SUCCESS(rv, rv);

  // Notify via the new ContainerStateChanged observer method.
  NOTIFY_RESULT_OBSERVERS(result,
                          ContainerStateChanged(this, aOldState, currState));
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetState(uint16_t* _state) {
  NS_ENSURE_ARG_POINTER(_state);

  *_state = mExpanded           ? (uint16_t)STATE_OPENED
            : mAsyncPendingStmt ? (uint16_t)STATE_LOADING
                                : (uint16_t)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 not be expanded to open it");
  mExpanded = true;

  nsresult 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(
    bool aSuppressNotifications) {
  NS_ASSERTION(
      (mExpanded && !mAsyncPendingStmt) || (!mExpanded && mAsyncPendingStmt),
      "Container must be expanded or loading to close it");

  nsresult rv;
  uint16_t oldState;
  rv = GetState(&oldState);
  NS_ENSURE_SUCCESS(rv, rv);

  if (mExpanded) {
    // Recursively close all child containers.
    for (int32_t i = 0; i < mChildren.Count(); ++i) {
      if (mChildren[i]->IsContainer() &&
          mChildren[i]->GetAsContainer()->mExpanded) {
        mChildren[i]->GetAsContainer()->CloseContainer(true);
      }
    }

    mExpanded = false;
  }

  // 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 = nullptr;

  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(true);
    } else if (this->IsFolderOrShortcut()) {
      this->GetAsFolder()->ClearChildren(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(bool 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.
 */
void nsNavHistoryContainerResultNode::FillStats() {
  uint32_t accessCount = 0;
  PRTime newTime = 0;

  for (nsNavHistoryResultNode* node : mChildren) {
    SetAsParentOfNode(node);
    accessCount += node->mAccessCount;
    // this is how container nodes get sorted by date
    // The container gets the most recent time of the child nodes.
    if (node->mTime > newTime) {
      newTime = node->mTime;
    }
  }

  if (mExpanded) {
    mAccessCount = accessCount;
    if (!IsQuery() || newTime > mTime) {
      mTime = newTime;
    }
  }
}

void nsNavHistoryContainerResultNode::SetAsParentOfNode(
    nsNavHistoryResultNode* aNode) {
  aNode->mParent = this;
  aNode->mIndentLevel = mIndentLevel + 1;
  if (aNode->IsContainer()) {
    nsNavHistoryContainerResultNode* container = aNode->GetAsContainer();
    // Propagate some of the parent's options to this container.
    if (mOptions->ExcludeItems()) {
      container->mOptions->SetExcludeItems(true);
    }
    if (mOptions->ExcludeQueries()) {
      container->mOptions->SetExcludeQueries(true);
    }
    if (aNode->IsFolderOrShortcut() && mOptions->AsyncEnabled()) {
      container->mOptions->SetAsyncEnabled(true);
    }
    if (!mOptions->ExpandQueries()) {
      container->mOptions->SetExpandQueries(false);
    }
    container->mResult = mResult;
    container->FillStats();
  }
}

/**
 * This walks up the tree until we find a query result node or the root to get
 * the sorting type.
 */
uint16_t nsNavHistoryContainerResultNode::GetSortType() {
  if (mParent) return mParent->GetSortType();
  if (mResult) return mResult->mSortingMode;

  // This is a detached container, just use natural order.
  return nsINavHistoryQueryOptions::SORT_BY_NONE;
}

nsresult nsNavHistoryContainerResultNode::Refresh() {
  NS_WARNING(
      "Refresh() is supported by queries or folders, not generic containers.");
  return NS_OK;
}

/**
 * @return the sorting comparator function for the give sort type, or null if
 * there is no comparator.
 */
nsNavHistoryContainerResultNode::SortComparator
nsNavHistoryContainerResultNode::GetSortingComparator(uint16_t aSortType) {
  switch (aSortType) {
    case nsINavHistoryQueryOptions::SORT_BY_NONE:
      return &SortComparison_Bookmark;
    case nsINavHistoryQueryOptions::SORT_BY_TITLE_ASCENDING:
      return &SortComparison_TitleLess;
    case nsINavHistoryQueryOptions::SORT_BY_TITLE_DESCENDING:
      return &SortComparison_TitleGreater;
    case nsINavHistoryQueryOptions::SORT_BY_DATE_ASCENDING:
      return &SortComparison_DateLess;
    case nsINavHistoryQueryOptions::SORT_BY_DATE_DESCENDING:
      return &SortComparison_DateGreater;
    case nsINavHistoryQueryOptions::SORT_BY_URI_ASCENDING:
      return &SortComparison_URILess;
    case nsINavHistoryQueryOptions::SORT_BY_URI_DESCENDING:
      return &SortComparison_URIGreater;
    case nsINavHistoryQueryOptions::SORT_BY_VISITCOUNT_ASCENDING:
      return &SortComparison_VisitCountLess;
    case nsINavHistoryQueryOptions::SORT_BY_VISITCOUNT_DESCENDING:
      return &SortComparison_VisitCountGreater;
    case nsINavHistoryQueryOptions::SORT_BY_DATEADDED_ASCENDING:
      return &SortComparison_DateAddedLess;
    case nsINavHistoryQueryOptions::SORT_BY_DATEADDED_DESCENDING:
      return &SortComparison_DateAddedGreater;
    case nsINavHistoryQueryOptions::SORT_BY_LASTMODIFIED_ASCENDING:
      return &SortComparison_LastModifiedLess;
    case nsINavHistoryQueryOptions::SORT_BY_LASTMODIFIED_DESCENDING:
      return &SortComparison_LastModifiedGreater;
    case nsINavHistoryQueryOptions::SORT_BY_TAGS_ASCENDING:
      return &SortComparison_TagsLess;
    case nsINavHistoryQueryOptions::SORT_BY_TAGS_DESCENDING:
      return &SortComparison_TagsGreater;
    case nsINavHistoryQueryOptions::SORT_BY_FRECENCY_ASCENDING:
      return &SortComparison_FrecencyLess;
    case nsINavHistoryQueryOptions::SORT_BY_FRECENCY_DESCENDING:
      return &SortComparison_FrecencyGreater;
    default:
      MOZ_ASSERT_UNREACHABLE("Bad sorting type");
      return nullptr;
  }
}

/**
 * This is used by Result::SetSortingMode and QueryResultNode::FillChildren to
 * sort the child list.
 *
 * This does NOT update any visibility or tree information.  The caller will
 * have to completely rebuild the visible list after this.
 */
void nsNavHistoryContainerResultNode::RecursiveSort(
    SortComparator aComparator) {
  mChildren.Sort(aComparator);
  for (nsNavHistoryResultNode* child : mChildren) {
    if (child->IsContainer()) {
      child->GetAsContainer()->RecursiveSort(aComparator);
    }
  }
}

/**
 * @return the index that the given item would fall on if it were to be
 * inserted using the given sorting.
 */
int32_t nsNavHistoryContainerResultNode::FindInsertionPoint(
    nsNavHistoryResultNode* aNode, SortComparator aComparator,
    bool* aItemExists) {
  if (aItemExists) {
    (*aItemExists) = false;
  }

  if (mChildren.Count() == 0) return 0;

  // The common case is the beginning or the end because this is used to insert
  // new items that are added to history, which is usually sorted by date.
  int32_t res;
  res = aComparator(aNode, mChildren[0]);
  if (res <= 0) {
    if (aItemExists && res == 0) {
      (*aItemExists) = true;
    }
    return 0;
  }
  res = aComparator(aNode, mChildren[mChildren.Count() - 1]);
  if (res >= 0) {
    if (aItemExists && res == 0) {
      (*aItemExists) = true;
    }
    return mChildren.Count();
  }

  int32_t beginRange = 0;                // inclusive
  int32_t endRange = mChildren.Count();  // exclusive
  while (beginRange < endRange) {
    int32_t center = beginRange + (endRange - beginRange) / 2;
    int32_t res = aComparator(aNode, mChildren[center]);
    if (res <= 0) {
      endRange = center;  // left side
      if (aItemExists && res == 0) {
        (*aItemExists) = true;
      }
    } else {
      beginRange = center + 1;  // right site
    }
  }
  return endRange;
}

/**
 * This checks the child node at the given index to see if its sorting is
 * correct.  This is called when nodes are updated and we need to see whether
 * we need to move it.
 *
 * @returns true if not and it should be resorted.
 */
bool nsNavHistoryContainerResultNode::DoesChildNeedResorting(
    int32_t aIndex, SortComparator aComparator) {
  MOZ_ASSERT(aIndex < mChildren.Count(), "Input index out of range");
  MOZ_ASSERT(aIndex >= 0, "Input index out of range");
  if (aIndex < 0 || aIndex >= mChildren.Count() || mChildren.Count() == 1) {
    return false;
  }

  if (aIndex > 0) {
    // compare to previous item
    if (aComparator(mChildren[aIndex - 1], mChildren[aIndex]) > 0) {
      return true;
    }
  }
  if (aIndex < mChildren.Count() - 1) {
    // compare to next item
    if (aComparator(mChildren[aIndex], mChildren[aIndex + 1]) > 0) {
      return true;
    }
  }
  return false;
}

/* static */
int32_t nsNavHistoryContainerResultNode::SortComparison_StringLess(
    const nsAString& a, const nsAString& b) {
  nsNavHistory* history = nsNavHistory::GetHistoryService();
  NS_ENSURE_TRUE(history, 0);
  const mozilla::intl::Collator* collator = history->GetCollator();
  NS_ENSURE_TRUE(collator, 0);

  int32_t res = collator->CompareStrings(a, b);
  return res;
}

/**
 * When there are bookmark indices, we should never have ties, so we don't
 * need to worry about tiebreaking.  When there are no bookmark indices,
 * everything will be -1 and we don't worry about sorting.
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_Bookmark(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return a->mBookmarkIndex - b->mBookmarkIndex;
}

/**
 * These are a little more complicated because they do a localization
 * conversion.  If this is too slow, we can compute the sort keys once in
 * advance, sort that array, and then reorder the real array accordingly.
 * This would save some key generations.
 *
 * The collation object must be allocated before sorting on title!
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_TitleLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  uint32_t aType;
  a->GetType(&aType);

  int32_t value = SortComparison_StringLess(NS_ConvertUTF8toUTF16(a->mTitle),
                                            NS_ConvertUTF8toUTF16(b->mTitle));
  if (value == 0) {
    // resolve by URI
    if (a->IsURI()) {
      value = Compare(a->mURI, b->mURI);
    }
    if (value == 0) {
      // resolve by date
      value = ComparePRTime(a->mTime, b->mTime);
      if (value == 0) {
        value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
      }
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_TitleGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -SortComparison_TitleLess(a, b);
}

/**
 * Equal times will be very unusual, but it is important that there is some
 * deterministic ordering of the results so they don't move around.
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_DateLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = ComparePRTime(a->mTime, b->mTime);
  if (value == 0) {
    value = SortComparison_StringLess(NS_ConvertUTF8toUTF16(a->mTitle),
                                      NS_ConvertUTF8toUTF16(b->mTitle));
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_DateGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -nsNavHistoryContainerResultNode::SortComparison_DateLess(a, b);
}

int32_t nsNavHistoryContainerResultNode::SortComparison_DateAddedLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = ComparePRTime(a->mDateAdded, b->mDateAdded);
  if (value == 0) {
    value = SortComparison_StringLess(NS_ConvertUTF8toUTF16(a->mTitle),
                                      NS_ConvertUTF8toUTF16(b->mTitle));
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_DateAddedGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -nsNavHistoryContainerResultNode::SortComparison_DateAddedLess(a, b);
}

int32_t nsNavHistoryContainerResultNode::SortComparison_LastModifiedLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = ComparePRTime(a->mLastModified, b->mLastModified);
  if (value == 0) {
    value = SortComparison_StringLess(NS_ConvertUTF8toUTF16(a->mTitle),
                                      NS_ConvertUTF8toUTF16(b->mTitle));
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_LastModifiedGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -nsNavHistoryContainerResultNode::SortComparison_LastModifiedLess(a,
                                                                           b);
}

/**
 * Certain types of parent nodes are treated specially because URIs are not
 * valid (like days or hosts).
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_URILess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value;
  if (a->IsURI() && b->IsURI()) {
    // normal URI or visit
    value = Compare(a->mURI, b->mURI);
  } else if (a->IsContainer() && !b->IsContainer()) {
    // Containers appear before entries with a uri.
    return -1;
  } else if (b->IsContainer() && !a->IsContainer()) {
    return 1;
  } else {
    // For everything else, use title sorting.
    value = SortComparison_StringLess(NS_ConvertUTF8toUTF16(a->mTitle),
                                      NS_ConvertUTF8toUTF16(b->mTitle));
  }

  if (value == 0) {
    value = ComparePRTime(a->mTime, b->mTime);
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_URIGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -SortComparison_URILess(a, b);
}

/**
 * Fall back on dates for conflict resolution
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_VisitCountLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = CompareIntegers(a->mAccessCount, b->mAccessCount);
  if (value == 0) {
    value = ComparePRTime(a->mTime, b->mTime);
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_VisitCountGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -nsNavHistoryContainerResultNode::SortComparison_VisitCountLess(a, b);
}

int32_t nsNavHistoryContainerResultNode::SortComparison_TagsLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = 0;
  nsAutoString aTags, bTags;

  nsresult rv = a->GetTags(aTags);
  NS_ENSURE_SUCCESS(rv, 0);

  rv = b->GetTags(bTags);
  NS_ENSURE_SUCCESS(rv, 0);

  value = SortComparison_StringLess(aTags, bTags);

  // fall back to title sorting
  if (value == 0) {
    value = SortComparison_TitleLess(a, b);
  }

  return value;
}

int32_t nsNavHistoryContainerResultNode::SortComparison_TagsGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -SortComparison_TagsLess(a, b);
}

/**
 * Fall back on date and bookmarked status, for conflict resolution.
 */
int32_t nsNavHistoryContainerResultNode::SortComparison_FrecencyLess(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  int32_t value = CompareIntegers(a->mFrecency, b->mFrecency);
  if (value == 0) {
    value = ComparePRTime(a->mTime, b->mTime);
    if (value == 0) {
      value = nsNavHistoryContainerResultNode::SortComparison_Bookmark(a, b);
    }
  }
  return value;
}
int32_t nsNavHistoryContainerResultNode::SortComparison_FrecencyGreater(
    nsNavHistoryResultNode* a, nsNavHistoryResultNode* b) {
  return -nsNavHistoryContainerResultNode::SortComparison_FrecencyLess(a, b);
}

/**
 * Searches this folder for a node with the given URI.  Returns null if not
 * found.
 *
 * @note Does not addref the node!
 */
nsNavHistoryResultNode* nsNavHistoryContainerResultNode::FindChildByURI(
    const nsACString& aSpec, uint32_t* aNodeIndex) {
  for (int32_t i = 0; i < mChildren.Count(); ++i) {
    if (mChildren[i]->IsURI()) {
      if (aSpec.Equals(mChildren[i]->mURI)) {
        *aNodeIndex = i;
        return mChildren[i];
      }
    }
  }
  return nullptr;
}

/**
 * Searches for matches for the given URI.
 */
void nsNavHistoryContainerResultNode::FindChildrenByURI(
    const nsCString& aSpec, nsCOMArray<nsNavHistoryResultNode>* aMatches) {
  for (int32_t i = 0; i < mChildren.Count(); ++i) {
    if (mChildren[i]->IsURI()) {
      if (aSpec.Equals(mChildren[i]->mURI)) {
        aMatches->AppendObject(mChildren[i]);
      }
    }
  }
}

/**
 * Searches this folder for a node with the given guid/target-folder-guid.
 *
 * @return the node if found, null otherwise.
 * @note Does not addref the node!
 */
nsNavHistoryResultNode* nsNavHistoryContainerResultNode::FindChildByGuid(
    const nsACString& guid, int32_t* nodeIndex) {
  *nodeIndex = -1;
  for (int32_t i = 0; i < mChildren.Count(); ++i) {
    if (mChildren[i]->mBookmarkGuid == guid ||
        mChildren[i]->mPageGuid == guid ||
        (mChildren[i]->IsFolderOrShortcut() &&
         mChildren[i]->GetAsFolder()->mTargetFolderGuid == guid)) {
      *nodeIndex = i;
      return mChildren[i];
    }
  }
  return nullptr;
}

/**
 * Searches this folder for a node with the given id/target-folder-id.
 *
 * @return the node if found, null otherwise.
 * @note Does not addref the node!
 */
nsNavHistoryResultNode* nsNavHistoryContainerResultNode::FindChildById(
    int64_t aItemId, int32_t* aNodeIndex) {
  for (int32_t i = 0; i < mChildren.Count(); ++i) {
    if (mChildren[i]->mItemId == aItemId ||
        (mChildren[i]->IsFolderOrShortcut() &&
         mChildren[i]->GetAsFolder()->mTargetFolderItemId == aItemId)) {
      *aNodeIndex = i;
      return mChildren[i];
    }
  }
  *aNodeIndex = -1;
  return nullptr;
}

/**
 * This does the work of adding a child to the container.  The child can be
 * either a container or or a single item that may even be collapsed with the
 * adjacent ones.
 */
nsresult nsNavHistoryContainerResultNode::InsertChildAt(
    nsNavHistoryResultNode* aNode, int32_t aIndex) {
  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);

  SetAsParentOfNode(aNode);

  if (!mChildren.InsertObjectAt(aNode, aIndex)) return NS_ERROR_OUT_OF_MEMORY;

  // Update our stats and notify the result's observers.
  uint32_t oldAccessCount = mAccessCount;
  PRTime oldTime = mTime;

  mAccessCount += aNode->mAccessCount;
  if (mTime < aNode->mTime) {
    mTime = aNode->mTime;
  }
  if ((!mParent || mParent->AreChildrenVisible()) &&
      !result->CanSkipHistoryDetailsNotifications()) {
    NOTIFY_RESULT_OBSERVERS(
        result, NodeHistoryDetailsChanged(TO_ICONTAINER(this), oldTime,
                                          oldAccessCount));
  }

  // Update tree if we are visible.  Note that we could be here and not
  // expanded, like when there is a bookmark folder being updated because its
  // parent is visible.
  if (AreChildrenVisible()) {
    NOTIFY_RESULT_OBSERVERS(result, NodeInserted(this, aNode, aIndex));
  }

  return NS_OK;
}

/**
 * This locates the proper place for insertion according to the current sort
 * and calls InsertChildAt
 */
nsresult nsNavHistoryContainerResultNode::InsertSortedChild(
    nsNavHistoryResultNode* aNode, bool aIgnoreDuplicates) {
  if (mChildren.Count() == 0) return InsertChildAt(aNode, 0);

  SortComparator comparator = GetSortingComparator(GetSortType());
  if (comparator) {
    // When inserting a new node, it must have proper statistics because we use
    // them to find the correct insertion point.  The insert function will then
    // recompute these statistics and fill in the proper parents and hierarchy
    // level.  Doing this twice shouldn't be a large performance penalty because
    // when we are inserting new containers, they typically contain only one
    // item (because we've browsed a new page).
    if (aNode->IsContainer()) {
      // need to update all the new item's children
      nsNavHistoryContainerResultNode* container = aNode->GetAsContainer();
      container->mResult = mResult;
      container->FillStats();
    }

    bool itemExists;
    int32_t position = FindInsertionPoint(aNode, comparator, &itemExists);
    if (aIgnoreDuplicates && itemExists) {
      return NS_OK;
    }

    return InsertChildAt(aNode, position);
  }
  return InsertChildAt(aNode, mChildren.Count());
}

/**
 * This checks if the item at aIndex is located correctly given the sorting
 * move.  If it's not, the item is moved, and the result's observers are
 * notified.
 *
 * @return true if the item position has been changed, false otherwise.
 */
bool nsNavHistoryContainerResultNode::EnsureItemPosition(int32_t aIndex) {
  NS_ASSERTION(aIndex < mChildren.Count(), "Invalid index");
  if (aIndex >= mChildren.Count()) {
    return false;
  }

  SortComparator comparator = GetSortingComparator(GetSortType());
  if (!comparator) {
    return false;
  }

  if (!DoesChildNeedResorting(aIndex, comparator)) {
    return false;
  }

  RefPtr<nsNavHistoryResultNode> node(mChildren[aIndex]);
  mChildren.RemoveObjectAt(aIndex);

  int32_t newIndex = FindInsertionPoint(node, comparator, nullptr);
  mChildren.InsertObjectAt(node.get(), newIndex);

  if (AreChildrenVisible()) {
    nsNavHistoryResult* result = GetResult();
    NOTIFY_RESULT_OBSERVERS_RET(
        result, NodeMoved(node, this, aIndex, this, newIndex), false);
  }

  return true;
}

/**
 * This does all the work of removing a child from this container, including
 * updating the tree if necessary.  Note that we do not need to be open for
 * this to work.
 */
nsresult nsNavHistoryContainerResultNode::RemoveChildAt(int32_t aIndex) {
  NS_ASSERTION(aIndex >= 0 && aIndex < mChildren.Count(), "Invalid index");

  // Hold an owning reference to keep from expiring while we work with it.
  RefPtr<nsNavHistoryResultNode> oldNode = mChildren[aIndex];

  // Update stats.
  // XXX This assertion does not reliably pass -- investigate!! (bug 1049797)
  // MOZ_ASSERT(mAccessCount >= mChildren[aIndex]->mAccessCount,
  //            "Invalid access count while updating!");
  mAccessCount -= mChildren[aIndex]->mAccessCount;

  // Remove it from our list and notify the result's observers.
  mChildren.RemoveObjectAt(aIndex);
  if (AreChildrenVisible()) {
    nsNavHistoryResult* result = GetResult();
    NOTIFY_RESULT_OBSERVERS(result, NodeRemoved(this, oldNode, aIndex));
  }

  oldNode->OnRemoving();
  return NS_OK;
}

/**
 * Searches for matches for the given URI.  If aOnlyOne is set, it will
 * terminate as soon as it finds a single match.  This would be used when there
 * are URI results so there will only ever be one copy of any URI.
 *
 * When aOnlyOne is false, it will check all elements.  This is for non-history
 * or visit style results that may have multiple copies of any given URI.
 */
void nsNavHistoryContainerResultNode::RecursiveFindURIs(
    bool aOnlyOne, nsNavHistoryContainerResultNode* aContainer,
    const nsCString& aSpec, nsCOMArray<nsNavHistoryResultNode>* aMatches) {
  for (int32_t i = 0; i < aContainer->mChildren.Count(); ++i) {
    auto* node = aContainer->mChildren[i];
    if (node->IsURI()) {
      if (node->mURI.Equals(aSpec)) {
        aMatches->AppendObject(node);
        if (aOnlyOne) {
          return;
        }
      }
    } else if (node->IsContainer() && node->GetAsContainer()->mExpanded) {
      RecursiveFindURIs(aOnlyOne, node->GetAsContainer(), aSpec, aMatches);
    }
  }
}

/**
 * If aUpdateSort is true, we will also update the sorting of this item.
 * Normally you want this to be true, but it can be false if the thing you are
 * changing can not affect sorting (like favicons).
 *
 * You should NOT change any child lists as part of the callback function.
 */
bool nsNavHistoryContainerResultNode::UpdateURIs(
    bool aRecursive, bool aOnlyOne, bool aUpdateSort, const nsCString& aSpec,
    nsresult (*aCallback)(nsNavHistoryResultNode*, const void*,
                          const nsNavHistoryResult*),
    const void* aClosure) {
  const nsNavHistoryResult* result = GetResult();
  if (!result) {
    MOZ_ASSERT(false, "Should have a result");
    return false;
  }

  // this needs to be owning since sometimes we remove and re-insert nodes
  // in their parents and we don't want them to go away.
  nsCOMArray<nsNavHistoryResultNode> matches;

  if (aRecursive) {
    RecursiveFindURIs(aOnlyOne, this, aSpec, &matches);
  } else if (aOnlyOne) {
    uint32_t nodeIndex;
    nsNavHistoryResultNode* node = FindChildByURI(aSpec, &nodeIndex);
    if (node) {
      matches.AppendObject(node);
    }
  } else {
    MOZ_ASSERT(
        false,
        "UpdateURIs does not handle nonrecursive updates of multiple items.");
    // this case easy to add if you need it, just find all the matching URIs
    // at this level.  However, this isn't currently used. History uses
    // recursive, Bookmarks uses one level and knows that the match is unique.
    return false;
  }

  if (matches.Count() == 0) return false;

  // PERFORMANCE: This updates each container for each child in it that
  // changes.  In some cases, many elements have changed inside the same
  // container.  It would be better to compose a list of containers, and
  // update each one only once for all the items that have changed in it.
  for (int32_t i = 0; i < matches.Count(); ++i) {
    nsNavHistoryResultNode* node = matches[i];
    nsNavHistoryContainerResultNode* parent = node->mParent;
    if (!parent) {
      MOZ_ASSERT(false, "All URI nodes being updated must have parents");
      continue;
    }

    aCallback(node, aClosure, result);

    if (aUpdateSort) {
      int32_t childIndex = parent->FindChild(node);
      MOZ_ASSERT(childIndex >= 0,
                 "Could not find child we just got a reference to");
      if (childIndex >= 0) {
        parent->EnsureItemPosition(childIndex);
      }
    }
  }

  return true;
}

/**
 * This is used to update the titles in the tree.  This is called from both
 * query and bookmark folder containers to update the tree.  Bookmark folders
 * should be sure to set recursive to false, since child folders will have
 * their own callbacks registered.
 */
static nsresult setTitleCallback(nsNavHistoryResultNode* aNode,
                                 const void* aClosure,
                                 const nsNavHistoryResult* aResult) {
  const nsACString* newTitle = static_cast<const nsACString*>(aClosure);
  aNode->mTitle = *newTitle;

  if (aResult && (!aNode->mParent || aNode->mParent->AreChildrenVisible())) {
    NOTIFY_RESULT_OBSERVERS(aResult, NodeTitleChanged(aNode, *newTitle));
  }

  return NS_OK;
}
nsresult nsNavHistoryContainerResultNode::ChangeTitles(
    nsIURI* aURI, const nsACString& aNewTitle, bool aRecursive, bool aOnlyOne) {
  // uri string
  nsAutoCString uriString;
  nsresult rv = aURI->GetSpec(uriString);
  NS_ENSURE_SUCCESS(rv, rv);

  // The recursive function will update the result's tree nodes, but only if we
  // give it a non-null pointer.  So if there isn't a tree, just pass nullptr
  // so it doesn't bother trying to call the result.
  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);

  uint16_t sortType = GetSortType();
  bool updateSorting =
      (sortType == nsINavHistoryQueryOptions::SORT_BY_TITLE_ASCENDING ||
       sortType == nsINavHistoryQueryOptions::SORT_BY_TITLE_DESCENDING);

  UpdateURIs(aRecursive, aOnlyOne, updateSorting, uriString, setTitleCallback,
             static_cast<const void*>(&aNewTitle));

  return NS_OK;
}

/**
 * Complex containers (folders and queries) will override this.  Here, we
 * handle the case of simple containers (like host groups) where the children
 * are always stored.
 */
NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetHasChildren(bool* aHasChildren) {
  *aHasChildren = (mChildren.Count() > 0);
  return NS_OK;
}

/**
 * @throws if this node is closed.
 */
NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetChildCount(uint32_t* aChildCount) {
  if (!mExpanded) return NS_ERROR_NOT_AVAILABLE;
  *aChildCount = mChildren.Count();
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetChild(uint32_t aIndex,
                                          nsINavHistoryResultNode** _child) {
  if (!mExpanded) return NS_ERROR_NOT_AVAILABLE;
  if (aIndex >= mChildren.Length()) return NS_ERROR_INVALID_ARG;
  nsCOMPtr<nsINavHistoryResultNode> child = mChildren.ElementAt(aIndex);
  child.forget(_child);
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryContainerResultNode::GetChildIndex(nsINavHistoryResultNode* aNode,
                                               uint32_t* _retval) {
  if (!mExpanded) return NS_ERROR_NOT_AVAILABLE;

  int32_t nodeIndex = FindChild(static_cast<nsNavHistoryResultNode*>(aNode));
  if (nodeIndex == -1) return NS_ERROR_INVALID_ARG;

  *_retval = nodeIndex;
  return NS_OK;
}

/**
 * HOW QUERY UPDATING WORKS
 *
 * Queries are different than bookmark folders in that we can not always do
 * dynamic updates (easily) and updates are more expensive.  Therefore, we do
 * NOT query if we are not open and want to see if we have any children (for
 * drawing a twisty) and always assume we will.
 *
 * When the container is opened, we execute the query and register the
 * listeners.  Like bookmark folders, we stay registered even when closed, and
 * clear ourselves as soon as a message comes in.  This lets us respond quickly
 * if the user closes and reopens the container.
 *
 * We try to handle the most common notifications for the most common query
 * types dynamically, that is, figuring out what should happen in response to
 * a message without doing a requery.  For complex changes or complex queries,
 * we give up and requery.
 */
NS_IMPL_ISUPPORTS_INHERITED(nsNavHistoryQueryResultNode,
                            nsNavHistoryContainerResultNode,
                            nsINavHistoryQueryResultNode)

nsNavHistoryQueryResultNode::nsNavHistoryQueryResultNode(
    const nsACString& aTitle, PRTime aTime, const nsACString& aQueryURI,
    const RefPtr<nsNavHistoryQuery>& aQuery,
    const RefPtr<nsNavHistoryQueryOptions>& aOptions)
    : nsNavHistoryContainerResultNode(aQueryURI, aTitle, aTime,
                                      nsNavHistoryResultNode::RESULT_TYPE_QUERY,
                                      aOptions),
      mQuery(aQuery),
      mHasSearchTerms(false),
      mLiveUpdate(getUpdateRequirements(aQuery, aOptions, &mHasSearchTerms)),
      mContentsValid(false),
      mBatchChanges(0),
      mTransitions(aQuery->Transitions().Clone()) {}

nsNavHistoryQueryResultNode::~nsNavHistoryQueryResultNode() {
  // Remove this node from result's observers.  We don't need to be notified
  // anymore.
  if (mResult && mResult->mAllBookmarksObservers.Contains(this)) {
    mResult->RemoveAllBookmarksObserver(this);
  }
  if (mResult && mResult->mHistoryObservers.Contains(this)) {
    mResult->RemoveHistoryObserver(this);
  }
  if (mResult && mResult->mMobilePrefObservers.Contains(this)) {
    mResult->RemoveMobilePrefsObserver(this);
  }
}

/**
 * Whoever made us may want non-expanding queries. However, we always expand
 * when we are the root node, or else asking for non-expanding queries would be
 * useless.  A query node is not expandable if excludeItems is set or if
 * expandQueries is unset.
 */
bool nsNavHistoryQueryResultNode::CanExpand() {
  // The root node and containersQueries can always expand;
  if ((mResult && mResult->mRootNode == this) || IsContainersQuery()) {
    return true;
  }

  if (mOptions->ExcludeItems()) {
    return false;
  }
  if (mOptions->ExpandQueries()) {
    return true;
  }

  return false;
}

/**
 * Some query with a particular result type can contain other queries.  They
 * must be always expandable
 */
bool nsNavHistoryQueryResultNode::IsContainersQuery() {
  uint16_t resultType = Options()->ResultType();
  return resultType == nsINavHistoryQueryOptions::RESULTS_AS_DATE_QUERY ||
         resultType == nsINavHistoryQueryOptions::RESULTS_AS_DATE_SITE_QUERY ||
         resultType == nsINavHistoryQueryOptions::RESULTS_AS_TAGS_ROOT ||
         resultType == nsINavHistoryQueryOptions::RESULTS_AS_SITE_QUERY ||
         resultType == nsINavHistoryQueryOptions::RESULTS_AS_ROOTS_QUERY ||
         resultType == nsINavHistoryQueryOptions::RESULTS_AS_LEFT_PANE_QUERY;
}

/**
 * Here we do not want to call ContainerResultNode::OnRemoving since our own
 * ClearChildren will do the same thing and more (unregister the observers).
 * The base ResultNode::OnRemoving will clear some regular node stats, so it is
 * OK.
 */
void nsNavHistoryQueryResultNode::OnRemoving() {
  nsNavHistoryResultNode::OnRemoving();
  ClearChildren(true);
  mResult = nullptr;
}

/**
 * Marks the container as open, rebuilding results if they are invalid.  We
 * may still have valid results if the container was previously open and
 * nothing happened since closing it.
 *
 * We do not handle CloseContainer specially.  The default one just marks the
 * container as closed, but doesn't actually mark the results as invalid.
 * The results will be invalidated by the next history or bookmark
 * notification that comes in.  This means if you open and close the item
 * 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 = true;

  nsresult rv;

  if (!CanExpand()) return NS_OK;
  if (!mContentsValid) {
    rv = FillChildren();
    NS_ENSURE_SUCCESS(rv, rv);
  }

  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
 * don't matter.
 */
NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetHasChildren(bool* aHasChildren) {
  *aHasChildren = false;

  if (!CanExpand()) {
    return NS_OK;
  }

  uint16_t resultType = mOptions->ResultType();

  // Tags are always populated, otherwise they are removed.
  if (mQuery->Tags().Length() == 1 && mParent &&
      mParent->mOptions->ResultType() ==
          nsINavHistoryQueryOptions::RESULTS_AS_TAGS_ROOT) {
    *aHasChildren = true;
    return NS_OK;
  }

  // AllBookmarks and the left pane folder also always have children.
  if (resultType == nsINavHistoryQueryOptions::RESULTS_AS_ROOTS_QUERY ||
      resultType == nsINavHistoryQueryOptions::RESULTS_AS_LEFT_PANE_QUERY) {
    *aHasChildren = true;
    return NS_OK;
  }

  // For history containers query we must check if we have any history
  if (resultType == nsINavHistoryQueryOptions::RESULTS_AS_DATE_QUERY ||
      resultType == nsINavHistoryQueryOptions::RESULTS_AS_DATE_SITE_QUERY ||
      resultType == nsINavHistoryQueryOptions::RESULTS_AS_SITE_QUERY) {
    nsNavHistory* history = nsNavHistory::GetHistoryService();
    NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
    *aHasChildren = history->hasHistoryEntries();
    return NS_OK;
  }

  // TODO (Bug 1477934): We don't have a good synchronous way to fetch whether
  // we have tags or not, to properly reply to the hasChildren request on the
  // tags root. Potentially we could pass this information when we create the
  // container.

  // If the container is open and populated, this is trivial.
  if (mContentsValid) {
    *aHasChildren = (mChildren.Count() > 0);
    return NS_OK;
  }

  // Fallback to assume we have children.
  *aHasChildren = true;
  return NS_OK;
}

/**
 * This doesn't just return mURI because in the case of queries that may
 * be lazily constructed from the query objects.
 */
NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetUri(nsACString& aURI) {
  aURI = mURI;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetFolderItemId(int64_t* aItemId) {
  *aItemId = -1;
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetTargetFolderGuid(nsACString& aGuid) {
  aGuid.Truncate();
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetQuery(nsINavHistoryQuery** _query) {
  RefPtr<nsNavHistoryQuery> query = mQuery;
  query.forget(_query);
  return NS_OK;
}

NS_IMETHODIMP
nsNavHistoryQueryResultNode::GetQueryOptions(
    nsINavHistoryQueryOptions** _options) {
  MOZ_ASSERT(mOptions, "Options should be valid");
  RefPtr<nsNavHistoryQueryOptions> options = mOptions;
  options.forget(_options);
  return NS_OK;
}

/**
 * Safe options getter, ensures query is parsed first.
 */
nsNavHistoryQueryOptions* nsNavHistoryQueryResultNode::Options() {
  MOZ_ASSERT(mOptions, "Options invalid, cannot generate from URI");
  return mOptions;
}

nsresult nsNavHistoryQueryResultNode::FillChildren() {
  MOZ_ASSERT(!mContentsValid,
             "Don't call FillChildren when contents are valid");
  MOZ_ASSERT(mChildren.Count() == 0,
             "We are trying to fill children when there already are some");
  NS_ENSURE_STATE(mQuery && mOptions);

  // get the results from the history service
  nsNavHistory* history = nsNavHistory::GetHistoryService();
  NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
  nsresult rv = history->GetQueryResults(this, mQuery, mOptions, &mChildren);
  NS_ENSURE_SUCCESS(rv, rv);

  // it is important to call FillStats to fill in the parents on all
  // nodes and the result node pointers on the containers
  FillStats();

  uint16_t sortType = GetSortType();

  if (mResult && 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 if (mOptions->QueryType() !=
                 nsINavHistoryQueryOptions::QUERY_TYPE_HISTORY ||
             sortType != nsINavHistoryQueryOptions::SORT_BY_NONE) {
    // The default SORT_BY_NONE sorts by the bookmark index (position),
    // which we do not have for history queries.
    // Once we've computed all tree stats, we can sort, because containers will
    // then have proper visit counts and dates.
    SortComparator comparator = GetSortingComparator(GetSortType());
    if (comparator) {
      // Usually containers queries results comes already sorted from the
      // database, but some locales could have special rules to sort by title.
      // RecursiveSort won't apply these rules to containers in containers
      // queries because when setting sortingMode on the result we want to sort
      // contained items (bug 473157).
      // Base container RecursiveSort will sort both our children and all
      // descendants, and is used in this case because we have to do manual
      // title sorting.
      // Query RecursiveSort will instead only sort descendants if we are a
      // constinaersQuery, e.g. a grouped query that will return other queries.
      // For other type of queries it will act as the base one.
      if (IsContainersQuery() && sortType == mOptions->SortingMode() &&
          (sortType == nsINavHistoryQueryOptions::SORT_BY_TITLE_ASCENDING ||
           sortType == nsINavHistoryQueryOptions::SORT_BY_TITLE_DESCENDING)) {
        nsNavHistoryContainerResultNode::RecursiveSort(comparator);
      } else {
        RecursiveSort(comparator);
      }
    }
  }

  // if we are limiting our results remove items from the end of the
  // 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 (mChildren.Length() > mOptions->MaxResults()) {
      mChildren.RemoveObjectAt(mChildren.Count() - 1);
    }
  }

  // If we're not updating the query, we don't need to add listeners, so bail
  // out early.
  if (mLiveUpdate == QUERYUPDATE_NONE) {
    mContentsValid = true;
    return NS_OK;
  }

  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);

  // Ensure to add history observer before bookmarks observer, because the
  // latter wants to know if an history observer was added.

  if (mOptions->QueryType() == nsINavHistoryQueryOptions::QUERY_TYPE_HISTORY) {
    // Date containers that contain site containers have no reason to observe
    // history, if the inside site container is expanded it will update,
    // otherwise we are going to refresh the parent query.
    if (!mParent || mParent->mOptions->ResultType() !=
                        nsINavHistoryQueryOptions::RESULTS_AS_DATE_SITE_QUERY) {
      // register with the result for history updates
      result->AddHistoryObserver(this);
    }
  }

  if (mOptions->QueryType() ==
          nsINavHistoryQueryOptions::QUERY_TYPE_BOOKMARKS ||
      mLiveUpdate == QUERYUPDATE_COMPLEX_WITH_BOOKMARKS || mHasSearchTerms) {
    // register with the result for bookmark updates
    result->AddAllBookmarksObserver(this);
  }

  if (mLiveUpdate == QUERYUPDATE_MOBILEPREF) {
    result->AddMobilePrefsObserver(this);
  }

  mContentsValid = true;
  return NS_OK;
}

/**
 * Call with unregister = false when we are going to update the children (for
 * example, when the container is open).  This will clear the list and notify
 * all the children that they are going away.
 *
 * When the results are becoming invalid and we are not going to refresh them,
 * set unregister = true, which will unregister the listener from the
 * result if any.  We use unregister = false when we are refreshing the list
 * immediately so want to stay a notifier.
 */
void nsNavHistoryQueryResultNode::ClearChildren(bool aUnregister) {
  for (int32_t i = 0; i < mChildren.Count(); ++i) mChildren[i]->OnRemoving();
  mChildren.Clear();

  if (aUnregister && mContentsValid) {
    nsNavHistoryResult* result = GetResult();
    if (result) {
      result->RemoveHistoryObserver(this);
      result->RemoveAllBookmarksObserver(this);
      result->RemoveMobilePrefsObserver(this);
    }
  }
  mContentsValid = false;
}

/**
 * This is called to update the result when something has changed that we
 * can not incrementally update.
 */
nsresult nsNavHistoryQueryResultNode::Refresh() {
  nsNavHistoryResult* result = GetResult();
  NS_ENSURE_STATE(result);
  if (result->IsBatching()) {
    result->requestRefresh(this);
    return NS_OK;
  }

  // This is not a root node but it does not have a parent - this means that
  // the node has already been cleared and it is now called, because it was
  // left in a local copy of the observers array.
  if (mIndentLevel > -1 && !mParent) return NS_OK;

  // Do not refresh if we are not expanded or if we are child of a query
  // containing other queries.  In this case calling Refresh for each child
  // query could cause a major slowdown.  We should not refresh nested
  // queries, since we will already refresh the parent one.
  // The only exception to this, is if the parent query is of QUERYUPDATE_NONE,
  // this can be the case for the RESULTS_AS_TAGS_ROOT
  // under RESULTS_AS_LEFT_PANE_QUERY.
  if (!mExpanded) {
    ClearChildren(true);
    return NS_OK;
  }

  if (mParent && mParent->IsQuery()) {
    nsNavHistoryQueryResultNode* parent = mParent->GetAsQuery();
    if (parent->IsContainersQuery() &&
        parent->mLiveUpdate != QUERYUPDATE_NONE) {
      // Don't update, just invalidate and unhook
      ClearChildren(true);
      return NS_OK;  // no updates in tree state
    }
  }

  if (mLiveUpdate == QUERYUPDATE_COMPLEX_WITH_BOOKMARKS) {
    ClearChildren(true);
  } else {
    ClearChildren(false);
  }

  // Ignore errors from FillChildren, since we will still want to refresh
  // the tree (there just might not be anything in it on error).
  (void)FillChildren();

  NOTIFY_RESULT_OBSERVERS(result, InvalidateContainer(TO_CONTAINER(this)));
  return NS_OK;
}

/**
 * Here, we override GetSortType to return the current sorting for this
 * query.  GetSortType is used when dynamically inserting query results so we
 * can see which comparator we should use to find the proper insertion point
 * (it shouldn't be called from folder containers which maintain their own
 * sorting).
 *
 * Normally, the container just forwards it up the chain.  This is what we want
 * for host groups, for example.  For queries, we often want to use the query's
 * sorting mode.
 *
 * However, we only use this query node's sorting when it is not the root.
 * When it is the root, we use the result's sorting mode.  This is because
 * there are two cases:
 *   - You are looking at a bookmark hierarchy that contains an embedded
 *     result.  We should always use the query's sort ordering since the result
 *     node's headers have nothing to do with us (and are disabled).
 *   - You are looking at a query in the tree.  In this case, we want the
--> --------------------

--> maximum size reached

--> --------------------