--- a/toolkit/components/autocomplete/nsAutoCompleteController.cpp
+++ b/toolkit/components/autocomplete/nsAutoCompleteController.cpp
@@ -66,17 +66,17 @@ nsAutoCompleteController::nsAutoComplete
   mProhibitAutoFill(false),
   mUserClearedAutoFill(false),
   mClearingAutoFillSearchesAgain(false),
   mCompositionState(eCompositionState_None),
   mSearchStatus(nsAutoCompleteController::STATUS_NONE),
   mRowCount(0),
   mSearchesOngoing(0),
   mSearchesFailed(0),
-  mFirstSearchResult(false),
+  mDelayedRowCountDelta(0),
   mImmediateSearchesCount(0),
   mCompletedSelectionIndex(-1)
 {
 }
 
 nsAutoCompleteController::~nsAutoCompleteController()
 {
   SetInput(nullptr);
@@ -211,16 +211,17 @@ nsAutoCompleteController::ResetInternalS
     mSearchString = value;
   }
 
   mPlaceholderCompletionString.Truncate();
   mDefaultIndexCompleted = false;
   mProhibitAutoFill = false;
   mSearchStatus = nsIAutoCompleteController::STATUS_NONE;
   mRowCount = 0;
+  mDelayedRowCountDelta = 0;
   mCompletedSelectionIndex = -1;
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsAutoCompleteController::StartSearch(const nsAString &aSearchString)
 {
@@ -867,35 +868,24 @@ nsAutoCompleteController::HandleSearchRe
   }
 }
 
 
 ////////////////////////////////////////////////////////////////////////
 //// nsIAutoCompleteObserver
 
 NS_IMETHODIMP
-nsAutoCompleteController::OnUpdateSearchResult(nsIAutoCompleteSearch *aSearch, nsIAutoCompleteResult* aResult)
-{
-  MOZ_ASSERT(mSearches.Contains(aSearch));
-
-  ClearResults();
-  HandleSearchResult(aSearch, aResult);
-  return NS_OK;
-}
-
-NS_IMETHODIMP
 nsAutoCompleteController::OnSearchResult(nsIAutoCompleteSearch *aSearch, nsIAutoCompleteResult* aResult)
 {
   MOZ_ASSERT(mSearchesOngoing > 0 && mSearches.Contains(aSearch));
 
-  // If this is the first search result we are processing
-  // we should clear out the previously cached results.
-  if (mFirstSearchResult) {
-    ClearResults();
-    mFirstSearchResult = false;
+  // Update the tree if necessary.
+  if (mTree && mDelayedRowCountDelta != 0) {
+    mTree->RowCountChanged(0, mDelayedRowCountDelta);
+    mDelayedRowCountDelta = 0;
   }
 
   uint16_t result = 0;
   if (aResult) {
     aResult->GetSearchResult(&result);
   }
 
   // If our results are incremental, the search is still ongoing.
@@ -1215,26 +1205,28 @@ nsAutoCompleteController::ClosePopup()
 nsresult
 nsAutoCompleteController::BeforeSearches()
 {
   NS_ENSURE_STATE(mInput);
 
   mSearchStatus = nsIAutoCompleteController::STATUS_SEARCHING;
   mDefaultIndexCompleted = false;
 
-  // The first search result will clear mResults array, though we should pass
-  // the previous result to each search to allow them to reuse it.  So we
-  // temporarily cache current results till AfterSearches().
+  // ClearResults will clear the mResults array, but we should pass the previous
+  // result to each search to allow reusing it.  So we temporarily cache the
+  // current results until AfterSearches().
   if (!mResultCache.AppendObjects(mResults)) {
     return NS_ERROR_OUT_OF_MEMORY;
   }
-
+  // The rowCountChanged notification is sent later, when the first result
+  // from the search arrives, to avoid flickering in the tree contents.
+  mDelayedRowCountDelta = 0;
+  ClearResults(true);
   mSearchesOngoing = mSearches.Length();
   mSearchesFailed = 0;
-  mFirstSearchResult = true;
 
   // notify the input that the search is beginning
   mInput->OnSearchBegin();
 
   return NS_OK;
 }
 
 nsresult
@@ -1726,16 +1718,22 @@ nsresult
 nsAutoCompleteController::PostSearchCleanup()
 {
   NS_ENSURE_STATE(mInput);
   nsCOMPtr<nsIAutoCompleteInput> input(mInput);
 
   uint32_t minResults;
   input->GetMinResultsForPopup(&minResults);
 
+  // Apply a pending rowCountChanged.
+  if (mTree && mDelayedRowCountDelta != 0) {
+    mTree->RowCountChanged(0, mDelayedRowCountDelta);
+    // mDelayedRowCountDelta will be reset by the next search.
+  }
+
   if (mRowCount || minResults == 0) {
     OpenPopup();
     if (mRowCount)
       mSearchStatus = nsIAutoCompleteController::STATUS_COMPLETE_MATCH;
     else
       mSearchStatus = nsIAutoCompleteController::STATUS_COMPLETE_NO_MATCH;
   } else {
     mSearchStatus = nsIAutoCompleteController::STATUS_COMPLETE_NO_MATCH;
@@ -1744,25 +1742,32 @@ nsAutoCompleteController::PostSearchClea
 
   // notify the input that the search is complete
   input->OnSearchComplete();
 
   return NS_OK;
 }
 
 nsresult
-nsAutoCompleteController::ClearResults()
+nsAutoCompleteController::ClearResults(bool aIsSearching)
 {
   int32_t oldRowCount = mRowCount;
   mRowCount = 0;
   mResults.Clear();
   if (oldRowCount != 0) {
-    if (mTree)
-      mTree->RowCountChanged(0, -oldRowCount);
-    else if (mInput) {
+    if (mTree) {
+      if (aIsSearching) {
+        // Delay the notification, so the tree provides a smoother transition to
+        // the new result. It will be handled as soon as we add the first result.
+        mDelayedRowCountDelta = -oldRowCount;
+      } else {
+        // Notify immediately.
+        mTree->RowCountChanged(0, -oldRowCount);
+      }
+    } else if (mInput) {
       nsCOMPtr<nsIAutoCompletePopup> popup;
       mInput->GetPopup(getter_AddRefs(popup));
       NS_ENSURE_TRUE(popup != nullptr, NS_ERROR_FAILURE);
       // if we had a tree, RowCountChanged() would have cleared the selection
       // when the selected row was removed.  But since we don't have a tree,
       // we need to clear the selection manually.
       popup->SetSelectedIndex(-1);
     }

--- a/toolkit/components/autocomplete/nsAutoCompleteController.h
+++ b/toolkit/components/autocomplete/nsAutoCompleteController.h
@@ -112,17 +112,17 @@ protected:
    * This happens because we don't want to replace text if the user backspaces
    * just before Enter.
    *
    * @param _retval
    *        The value to be completed.
    */
   nsresult GetFinalDefaultCompleteValue(nsAString &_retval);
 
-  nsresult ClearResults();
+  nsresult ClearResults(bool aIsSearching = false);
 
   nsresult RowIndexToSearch(int32_t aRowIndex,
                             int32_t *aSearchIndex, int32_t *aItemIndex);
 
   // members //////////////////////////////////////////
 
   nsCOMPtr<nsIAutoCompleteInput> mInput;
 
@@ -159,17 +159,17 @@ protected:
     eCompositionState_Composing,
     eCompositionState_Committing
   };
   CompositionState mCompositionState;
   uint16_t mSearchStatus;
   uint32_t mRowCount;
   uint32_t mSearchesOngoing;
   uint32_t mSearchesFailed;
-  bool mFirstSearchResult;
+  int32_t mDelayedRowCountDelta;
   uint32_t mImmediateSearchesCount;
   // The index of the match on the popup that was selected using the keyboard,
   // if the completeselectedindex attribute is set.
   // This is used to distinguish that selection (which would have been put in
   // the input on being selected) from a moused-over selectedIndex value. This
   // distinction is used to prevent mouse moves from inadvertently changing
   // what happens once the user hits Enter on the keyboard.
   // See bug 1043584 for more details.

--- a/toolkit/components/autocomplete/nsIAutoCompleteSearch.idl
+++ b/toolkit/components/autocomplete/nsIAutoCompleteSearch.idl
@@ -35,24 +35,16 @@ interface nsIAutoCompleteObserver : nsIS
 { 
   /*
    * Called when a search is complete and the results are ready
    *
    * @param search - The search object that processed this search
    * @param result - The search result object
    */
   void onSearchResult(in nsIAutoCompleteSearch search, in nsIAutoCompleteResult result);
-
-  /*
-   * Called to update with new results
-   *
-   * @param search - The search object that processed this search
-   * @param result - The search result object
-   */
-  void onUpdateSearchResult(in nsIAutoCompleteSearch search, in nsIAutoCompleteResult result);
 };
 
 [scriptable, uuid(4c3e7462-fbfb-4310-8f4b-239238392b75)]
 interface nsIAutoCompleteSearchDescriptor : nsISupports
 {
   // The search is started after the timeout specified by the corresponding
   // nsIAutoCompleteInput implementation.
   const unsigned short SEARCH_TYPE_DELAYED = 0;

--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -2379,16 +2379,18 @@ Search.prototype = {
    * @param searchOngoing
    *        Indicates whether the search result should be marked as ongoing.
    * @param skipDelay
    *        Whether to notify immediately.
    */
   _notifyDelaysCount: 0,
   notifyResult(searchOngoing, skipDelay = false) {
     let notify = () => {
+      if (!this.pending)
+        return;
       this._notifyDelaysCount = 0;
       let resultCode = this._currentMatchCount ? "RESULT_SUCCESS" : "RESULT_NOMATCH";
       if (searchOngoing) {
         resultCode += "_ONGOING";
       }
       let result = this._result;
       result.setSearchResult(Ci.nsIAutoCompleteResult[resultCode]);
       this._listener.onSearchResult(this._autocompleteSearch, result);