Bug 1391293 - Reduce Address Bar results flickering when typing additional chars. r=adw
authorMarco Bonardo <mbonardo@mozilla.com>
Fri, 08 Sep 2017 11:39:44 +0200
changeset 381642 33a41b9cf92a
parent 381641 2c920ffd1d7c
child 381643 a03036beafc0
push id51544
push usermak77@bonardo.net
push dateTue, 19 Sep 2017 13:40:11 +0000
treeherderautoland@a03036beafc0 [default view] [failures only]
reviewersadw
bugs1391293
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1391293 - Reduce Address Bar results flickering when typing additional chars. r=adw MozReview-Commit-ID: HaIK8YJho1y
toolkit/components/autocomplete/nsAutoCompleteSimpleResult.cpp
toolkit/components/autocomplete/nsIAutoCompleteSimpleResult.idl
toolkit/components/autocomplete/tests/unit/test_removeMatchAt.js
toolkit/components/autocomplete/tests/unit/xpcshell.ini
toolkit/components/places/UnifiedComplete.js
toolkit/components/places/tests/unifiedcomplete/test_search_suggestions.js
--- a/toolkit/components/autocomplete/nsAutoCompleteSimpleResult.cpp
+++ b/toolkit/components/autocomplete/nsAutoCompleteSimpleResult.cpp
@@ -194,16 +194,25 @@ nsAutoCompleteSimpleResult::AppendMatch(
                                         const nsAString& aFinalCompleteValue,
                                         const nsAString& aLabel)
 {
   return InsertMatchAt(mMatches.Length(), aValue, aComment, aImage, aStyle,
                        aFinalCompleteValue, aLabel);
 }
 
 NS_IMETHODIMP
+nsAutoCompleteSimpleResult::RemoveMatchAt(int32_t aIndex)
+{
+  CHECK_MATCH_INDEX(aIndex, false);
+
+  mMatches.RemoveElementAt(aIndex);
+  return NS_OK;
+}
+
+NS_IMETHODIMP
 nsAutoCompleteSimpleResult::GetMatchCount(uint32_t *aMatchCount)
 {
   *aMatchCount = mMatches.Length();
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsAutoCompleteSimpleResult::GetValueAt(int32_t aIndex, nsAString& _retval)
--- a/toolkit/components/autocomplete/nsIAutoCompleteSimpleResult.idl
+++ b/toolkit/components/autocomplete/nsIAutoCompleteSimpleResult.idl
@@ -84,16 +84,23 @@ interface nsIAutoCompleteSimpleResult : 
   void appendMatch(in AString aValue,
                    in AString aComment,
                    [optional] in AString aImage,
                    [optional] in AString aStyle,
                    [optional] in AString aFinalCompleteValue,
                    [optional] in AString aLabel);
 
   /**
+   * Removes an existing match.
+   * @note this is different from removeValueAt, since it's not a consequence of
+   * a user action, and as such it won't notify onValueRemoved.
+   */
+  void removeMatchAt(in long aIndex);
+
+  /**
    * Gets the listener for changes in the result.
    */
   nsIAutoCompleteSimpleResultListener getListener();
 
   /**
    * Sets a listener for changes in the result.
    */
   void setListener(in nsIAutoCompleteSimpleResultListener aListener);
new file mode 100644
--- /dev/null
+++ b/toolkit/components/autocomplete/tests/unit/test_removeMatchAt.js
@@ -0,0 +1,15 @@
+function run_test() {
+  let result = Cc["@mozilla.org/autocomplete/simple-result;1"]
+                 .createInstance(Ci.nsIAutoCompleteSimpleResult);
+  result.appendMatch("a", "");
+  result.appendMatch("b", "");
+  result.removeMatchAt(0);
+  Assert.equal(result.matchCount, 1);
+  Assert.equal(result.getValueAt(0), "b");
+  result.appendMatch("c", "");
+  result.removeMatchAt(1);
+  Assert.equal(result.matchCount, 1);
+  Assert.equal(result.getValueAt(0), "b");
+  result.removeMatchAt(0);
+  Assert.equal(result.matchCount, 0);
+}
--- a/toolkit/components/autocomplete/tests/unit/xpcshell.ini
+++ b/toolkit/components/autocomplete/tests/unit/xpcshell.ini
@@ -15,9 +15,10 @@ head = head_autocomplete.js
 [test_finalCompleteValue.js]
 [test_finalCompleteValue_defaultIndex.js]
 [test_finalCompleteValue_forceComplete.js]
 [test_finalCompleteValueSelectedIndex.js]
 [test_finalDefaultCompleteValue.js]
 [test_immediate_search.js]
 [test_insertMatchAt.js]
 [test_previousResult.js]
+[test_removeMatchAt.js]
 [test_stopSearch.js]
--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -17,16 +17,23 @@ const MS_PER_DAY = 86400000; // 24 * 60 
 const {
   MATCH_ANYWHERE,
   MATCH_BOUNDARY_ANYWHERE,
   MATCH_BOUNDARY,
   MATCH_BEGINNING,
   MATCH_BEGINNING_CASE_SENSITIVE,
 } = Ci.mozIPlacesAutoComplete;
 
+// Values for browser.urlbar.insertMethod
+const INSERTMETHOD = {
+  APPEND: 0, // Just append new results.
+  MERGE_RELATED: 1, // Merge previous and current results if search strings are related
+  MERGE: 2 // Always merge previous and current results
+};
+
 // Prefs are defined as [pref name, default value].
 const PREF_URLBAR_BRANCH = "browser.urlbar.";
 const PREF_URLBAR_DEFAULTS = new Map([
   ["autocomplete.enabled", true],
   ["autoFill", true],
   ["autoFill.typed", true],
   ["autoFill.searchEngines", false],
   ["restyleSearches", false],
@@ -40,16 +47,17 @@ const PREF_URLBAR_DEFAULTS = new Map([
   ["suggest.history.onlyTyped", false],
   ["suggest.searches", false],
   ["maxCharsForSearchSuggestions", 20],
   ["maxHistoricalSearchSuggestions", 0],
   ["usepreloadedtopurls.enabled", true],
   ["usepreloadedtopurls.expire_days", 14],
   ["matchBuckets", "general:5,suggestion:Infinity"],
   ["matchBucketsSearch", ""],
+  ["insertMethod", INSERTMETHOD.MERGE_RELATED],
 ]);
 const PREF_OTHER_DEFAULTS = new Map([
   ["keyword.enabled", true],
 ]);
 
 // AutoComplete query type constants.
 // Describes the various types of queries that we can process rows for.
 const QUERYTYPE_FILTERED            = 0;
@@ -781,19 +789,22 @@ function looksLikeUrl(str, ignoreAlphanu
  * @param autocompleteListener
  *        An nsIAutoCompleteObserver.
  * @param resultListener
  *        An nsIAutoCompleteSimpleResultListener.
  * @param autocompleteSearch
  *        An nsIAutoCompleteSearch.
  * @param prohibitSearchSuggestions
  *        Whether search suggestions are allowed for this search.
+ * @param [optional] previousResult
+ *        The result object from the previous search. if available.
  */
 function Search(searchString, searchParam, autocompleteListener,
-                resultListener, autocompleteSearch, prohibitSearchSuggestions) {
+                resultListener, autocompleteSearch, prohibitSearchSuggestions,
+                previousResult) {
   // We want to store the original string for case sensitive searches.
   this._originalSearchString = searchString;
   this._trimmedOriginalSearchString = searchString.trim();
   let strippedOriginalSearchString =
     stripPrefix(this._trimmedOriginalSearchString.toLowerCase());
   this._searchString =
     textURIService.unEscapeURIForUI("UTF-8", strippedOriginalSearchString);
 
@@ -824,31 +835,48 @@ function Search(searchString, searchPara
 
   this._prohibitSearchSuggestions = prohibitSearchSuggestions;
 
   this._listener = autocompleteListener;
   this._autocompleteSearch = autocompleteSearch;
 
   // Create a new result to add eventual matches.  Note we need a result
   // regardless having matches.
-  let result = Cc["@mozilla.org/autocomplete/simple-result;1"]
+  let result = previousResult ||
+               Cc["@mozilla.org/autocomplete/simple-result;1"]
                  .createInstance(Ci.nsIAutoCompleteSimpleResult);
   result.setSearchString(searchString);
   result.setListener(resultListener);
   // Will be set later, if needed.
   result.setDefaultIndex(-1);
   this._result = result;
 
+  this._previousSearchMatchTypes = [];
+  for (let i = 0; previousResult && i < previousResult.matchCount; ++i) {
+    let style = previousResult.getStyleAt(i);
+    if (style.includes("heuristic")) {
+      this._previousSearchMatchTypes.push(MATCHTYPE.HEURISTIC);
+    } else if (style.includes("suggestion")) {
+      this._previousSearchMatchTypes.push(MATCHTYPE.SUGGESTION);
+    } else if (style.includes("extension")) {
+      this._previousSearchMatchTypes.push(MATCHTYPE.EXTENSION);
+    } else {
+      this._previousSearchMatchTypes.push(MATCHTYPE.GENERAL);
+    }
+  }
+
+  // This is a replacement for this._result.matchCount, to be used when you need
+  // to check how many "current" matches have been inserted.
+  // Indeed this._result.matchCount may include matches from the previous search.
+  this._currentMatchCount = 0;
+
   // These are used to avoid adding duplicate entries to the results.
   this._usedURLs = new Set();
   this._usedPlaceIds = new Set();
 
-  // Resolved when all the matches providers have been fetched.
-  this._allMatchesPromises = [];
-
   // Counters for the number of matches per MATCHTYPE.
   this._counts = Object.values(MATCHTYPE)
                        .reduce((o, p) => { o[p] = 0; return o; }, {});
 
   this._searchStringHasWWW = this._strippedPrefix.endsWith("www.");
   this._searchStringWWW = this._searchStringHasWWW ? "www." : "";
   this._searchStringFromWWW = this._searchStringWWW + this._searchString;
 
@@ -950,16 +978,19 @@ Search.prototype = {
   },
 
   /**
    * Stop this search.
    * After invoking this method, we won't run any more searches or heuristics,
    * and no new matches may be added to the current result.
    */
   stop() {
+    // Avoid multiple calls or re-entrance.
+    if (!this.pending)
+      return;
     if (this._sleepTimer)
       this._sleepTimer.cancel();
     if (this._sleepResolve) {
       this._sleepResolve();
       this._sleepResolve = null;
     }
     if (this._searchSuggestionController) {
       this._searchSuggestionController.stop();
@@ -990,18 +1021,17 @@ Search.prototype = {
     this.interrupt = () => {
       // Interrupt any ongoing statement to run the search sooner.
       if (!SwitchToTabStorage.updating) {
         conn.interrupt();
       }
     }
 
     TelemetryStopwatch.start(TELEMETRY_1ST_RESULT, this);
-    if (this._searchString)
-      TelemetryStopwatch.start(TELEMETRY_6_FIRST_RESULTS, this);
+    TelemetryStopwatch.start(TELEMETRY_6_FIRST_RESULTS, this);
 
     // Since we call the synchronous parseSubmissionURL function later, we must
     // wait for the initialization of PlacesSearchAutocompleteProvider first.
     await PlacesSearchAutocompleteProvider.ensureInitialized();
     if (!this.pending)
       return;
 
     // For any given search, we run many queries/heuristics:
@@ -1041,60 +1071,87 @@ Search.prototype = {
     await this._checkPreloadedSitesExpiry();
 
     // Add the first heuristic result, if any.  Set _addingHeuristicFirstMatch
     // to true so that when the result is added, "heuristic" can be included in
     // its style.
     this._addingHeuristicFirstMatch = true;
     let hasHeuristic = await this._matchFirstHeuristicResult(conn);
     this._addingHeuristicFirstMatch = false;
+    this._cleanUpNonCurrentMatches(MATCHTYPE.HEURISTIC);
     if (!this.pending)
       return;
 
     // We sleep a little between adding the heuristicFirstMatch and matching
     // any other searches so we aren't kicking off potentially expensive
     // searches on every keystroke.
     // Though, if there's no heuristic result, we start searching immediately,
     // since autocomplete may be waiting for us.
     if (hasHeuristic) {
       await this._sleep(Prefs.get("delay"));
       if (!this.pending)
         return;
     }
 
     // Only add extension suggestions if the first token is a registered keyword
     // and the search string has characters after the first token.
+    let extensionsCompletePromise = Promise.resolve();
     if (this._searchTokens.length > 0 &&
         ExtensionSearchHandler.isKeywordRegistered(this._searchTokens[0]) &&
         this._originalSearchString.length > this._searchTokens[0].length) {
-      await this._matchExtensionSuggestions();
-      if (!this.pending)
-        return;
+      // Do not await on this, since extensions cannot notify when they are done
+      // adding results, it may take too long.
+      extensionsCompletePromise = this._matchExtensionSuggestions();
     } else if (ExtensionSearchHandler.hasActiveInputSession()) {
       ExtensionSearchHandler.handleInputCancelled();
     }
 
+    let searchSuggestionsCompletePromise = Promise.resolve();
     if (this._enableActions && this._searchTokens.length > 0) {
-      await this._matchSearchSuggestions();
-      if (!this.pending)
-        return;
+      // Limit the string sent for search suggestions to a maximum length.
+      let searchString = this._searchTokens.join(" ")
+                             .substr(0, Prefs.get("maxCharsForSearchSuggestions"));
+      // Avoid fetching suggestions if they are not required, private browsing
+      // mode is enabled, or the search string may expose sensitive information.
+      if (this.hasBehavior("searches") && !this._inPrivateWindow &&
+          !this._prohibitSearchSuggestionsFor(searchString)) {
+        searchSuggestionsCompletePromise = this._matchSearchSuggestions(searchString);
+        if (this.hasBehavior("restrict")) {
+          // Wait for the suggestions to be added.
+          await searchSuggestionsCompletePromise;
+          this._cleanUpNonCurrentMatches(MATCHTYPE.SUGGESTION);
+          // We're done if we're restricting to search suggestions.
+          // Notify the result completion then stop the search.
+          this._autocompleteSearch.finishSearch(true);
+          this.stop();
+          return;
+        }
+      }
     }
+    // In any case, clear previous suggestions.
+    searchSuggestionsCompletePromise.then(() => {
+      this._cleanUpNonCurrentMatches(MATCHTYPE.SUGGESTION);
+    });
 
     for (let [query, params] of queries) {
       await conn.executeCached(query, params, this._onResultRow.bind(this));
       if (!this.pending)
         return;
     }
 
     if (this._enableActions && this.hasBehavior("openpage")) {
       await this._matchRemoteTabs();
       if (!this.pending)
         return;
     }
 
+    // Ideally we should wait until MATCH_BOUNDARY_ANYWHERE, but that query
+    // may be really slow and we may end up showing old results for too long.
+    this._cleanUpNonCurrentMatches(MATCHTYPE.GENERAL);
+
     // If we do not have enough results, and our match type is
     // MATCH_BOUNDARY_ANYWHERE, search again with MATCH_ANYWHERE to get more
     // results.
     let count = this._counts[MATCHTYPE.GENERAL] + this._counts[MATCHTYPE.HEURISTIC];
     if (this._matchBehavior == MATCH_BOUNDARY_ANYWHERE &&
         count < Prefs.get("maxRichResults")) {
       this._matchBehavior = MATCH_ANYWHERE;
       for (let [query, params] of [ this._adaptiveQuery,
@@ -1102,22 +1159,21 @@ Search.prototype = {
         await conn.executeCached(query, params, this._onResultRow.bind(this));
         if (!this.pending)
           return;
       }
     }
 
     this._matchPreloadedSites();
 
-    // Ensure to fill any remaining space. Suggestions which come from extensions are
-    // inserted at the beginning, so any suggestions
-    await Promise.all(this._allMatchesPromises);
+    // Ensure to fill any remaining space.
+    await searchSuggestionsCompletePromise;
+    await extensionsCompletePromise;
   },
 
-
   async _checkPreloadedSitesExpiry() {
     if (!Prefs.get("usepreloadedtopurls.enabled"))
       return;
     let profileCreationDate = await ProfileAgeCreatedPromise;
     let daysSinceProfileCreation = (Date.now() - profileCreationDate) / MS_PER_DAY;
     if (daysSinceProfileCreation > Prefs.get("usepreloadedtopurls.expire_days"))
       Services.prefs.setBoolPref("browser.urlbar.usepreloadedtopurls.enabled", false);
   },
@@ -1313,65 +1369,46 @@ Search.prototype = {
       if (matched) {
         return true;
       }
     }
 
     return false;
   },
 
-  async _matchSearchSuggestions() {
-    // Limit the string sent for search suggestions to a maximum length.
-    let searchString = this._searchTokens.join(" ")
-                           .substr(0, Prefs.get("maxCharsForSearchSuggestions"));
-    // Avoid fetching suggestions if they are not required, private browsing
-    // mode is enabled, or the search string may expose sensitive information.
-    if (!this.hasBehavior("searches") || this._inPrivateWindow ||
-        this._prohibitSearchSuggestionsFor(searchString)) {
-      return;
-    }
-
+  _matchSearchSuggestions(searchString) {
     this._searchSuggestionController =
       PlacesSearchAutocompleteProvider.getSuggestionController(
         searchString,
         this._inPrivateWindow,
         Prefs.get("maxHistoricalSearchSuggestions"),
         Prefs.get("maxRichResults") - Prefs.get("maxHistoricalSearchSuggestions"),
         this._userContextId
       );
-    let promise = this._searchSuggestionController.fetchCompletePromise
-      .then(() => {
-        // The search has been canceled already.
-        if (!this._searchSuggestionController)
-          return;
-        if (this._searchSuggestionController.resultsCount >= 0 &&
-            this._searchSuggestionController.resultsCount < 2) {
-          // The original string is used to properly compare with the next search.
-          this._lastLowResultsSearchSuggestion = this._originalSearchString;
+    return this._searchSuggestionController.fetchCompletePromise.then(() => {
+      // The search has been canceled already.
+      if (!this._searchSuggestionController)
+        return;
+      if (this._searchSuggestionController.resultsCount >= 0 &&
+          this._searchSuggestionController.resultsCount < 2) {
+        // The original string is used to properly compare with the next search.
+        this._lastLowResultsSearchSuggestion = this._originalSearchString;
+      }
+      while (this.pending) {
+        let result = this._searchSuggestionController.consume();
+        if (!result)
+          break;
+        let { match, suggestion, historical } = result;
+        if (!looksLikeUrl(suggestion)) {
+          // Don't include the restrict token, if present.
+          let searchString = this._searchTokens.join(" ");
+          this._addSearchEngineMatch(match, searchString, suggestion, historical);
         }
-        while (this.pending) {
-          let result = this._searchSuggestionController.consume();
-          if (!result)
-            break;
-          let { match, suggestion, historical } = result;
-          if (!looksLikeUrl(suggestion)) {
-            // Don't include the restrict token, if present.
-            let searchString = this._searchTokens.join(" ");
-            this._addSearchEngineMatch(match, searchString, suggestion, historical);
-          }
-        }
-      });
-
-    if (this.hasBehavior("restrict")) {
-      // We're done if we're restricting to search suggestions.
-      await promise;
-      this.stop();
-    } else {
-      this._allMatchesPromises.push(promise);
-    }
+      }
+    }).catch(Cu.reportError);
   },
 
   _prohibitSearchSuggestionsFor(searchString) {
     if (this._prohibitSearchSuggestions)
       return true;
 
     // Suggestions for a single letter are unlikely to be useful.
     if (searchString.length < 2)
@@ -1594,38 +1631,46 @@ Search.prototype = {
     let value = PlacesUtils.mozActionURI("searchengine", actionURLParams);
     let match = {
       value,
       comment: searchMatch.engineName,
       icon: searchMatch.iconUrl,
       style: "action searchengine",
       frecency: FRECENCY_DEFAULT
     };
-    if (suggestion)
+    if (suggestion) {
+      match.style += " suggestion";
       match.type = MATCHTYPE.SUGGESTION;
+    }
 
     this._addMatch(match);
   },
 
   _matchExtensionSuggestions() {
     let promise = ExtensionSearchHandler.handleSearch(this._searchTokens[0], this._originalSearchString,
       suggestions => {
         for (let suggestion of suggestions) {
           let content = `${this._searchTokens[0]} ${suggestion.content}`;
           this._addExtensionMatch(content, suggestion.description);
         }
       }
     );
+    // Remove previous search matches sooner than the maximum timeout, otherwise
+    // matches may appear stale for a long time.
+    // This is necessary because WebExtensions don't have a method to notify
+    // that they are done providing results, so they could be pending forever.
+    setTimeout(() => this._cleanUpNonCurrentMatches(MATCHTYPE.EXTENSION), 100);
+
     // Since the extension has no way to signale when it's done pushing
     // results, we add a timeout racing with the addition.
     let timeoutPromise = new Promise((resolve, reject) => {
       setTimeout(() => reject(new Error("timeout waiting for the extension to add its results to the location bar")),
                  MAXIMUM_ALLOWED_EXTENSION_TIME_MS);
     });
-    this._allMatchesPromises.push(Promise.race([timeoutPromise, promise]).catch(Cu.reportError));
+    return Promise.race([timeoutPromise, promise]).catch(Cu.reportError);
   },
 
   async _matchRemoteTabs() {
     let matches = await PlacesRemoteTabsAutocompleteProvider.getMatches(this._originalSearchString);
     for (let {url, title, icon, deviceName} of matches) {
       // It's rare that Sync supplies the icon for the page (but if it does, it
       // is a string URL)
       if (!icon) {
@@ -1836,59 +1881,149 @@ Search.prototype = {
 
     if (this._addingHeuristicFirstMatch) {
       match.style += " heuristic";
     }
 
     match.icon = match.icon || "";
     match.finalCompleteValue = match.finalCompleteValue || "";
 
-    this._result.insertMatchAt(this._getInsertIndexForMatch(match),
+    let {index, replace} = this._getInsertIndexForMatch(match);
+    if (replace) { // Replacing an existing match from the previous search.
+      this._result.removeMatchAt(index);
+    }
+    this._result.insertMatchAt(index,
                                match.value,
                                match.comment,
                                match.icon,
                                match.style,
                                match.finalCompleteValue);
+    this._currentMatchCount++;
     this._counts[match.type]++;
 
-    if (this._result.matchCount == 1)
+    if (this._currentMatchCount == 1)
       TelemetryStopwatch.finish(TELEMETRY_1ST_RESULT, this);
-    if (this._result.matchCount == 6)
+    if (this._currentMatchCount == 6)
       TelemetryStopwatch.finish(TELEMETRY_6_FIRST_RESULTS, this);
-
     this.notifyResults(true);
   },
 
   _getInsertIndexForMatch(match) {
     let index = 0;
     // The buckets change depending on the context, that is currently decided by
     // the first added match (the heuristic one).
     if (!this._buckets) {
       // Convert the buckets to readable objects with a count property.
-      let buckets = match.style.includes("searchengine") ? Prefs.get("matchBucketsSearch")
+      let buckets = match.type == MATCHTYPE.HEURISTIC &&
+                    match.style.includes("searchengine") ? Prefs.get("matchBucketsSearch")
                                                          : Prefs.get("matchBuckets");
+      // - available is the number of available slots in the bucket
+      // - insertIndex is the index of the first available slot in the bucket
+      // - count is the number of matches in the bucket, note that it also
+      //   account for matches from the previous search, while available and
+      //   insertIndex don't.
       this._buckets = buckets.map(([type, available]) => ({ type,
                                                             available,
-                                                            count: 0,
+                                                            insertIndex: 0,
+                                                            count: 0
                                                           }));
+
+      // If we have matches from the previous search, we want to replace them
+      // in-place to reduce flickering.
+      // This requires walking the previous matches and marking their existence
+      // into the current buckets, so that, when we'll add the new matches to
+      // the buckets, we can either append or replace a match.
+      if (this._previousSearchMatchTypes.length > 0) {
+        for (let type of this._previousSearchMatchTypes) {
+          for (let bucket of this._buckets) {
+            if (type == bucket.type && bucket.count < bucket.available) {
+              bucket.count++;
+              break;
+            }
+          }
+        }
+      }
     }
+
+    let replace = false;
     for (let bucket of this._buckets) {
       // Move to the next bucket if the match type is incompatible, or if there
       // is no available space or if the frecency is below the threshold.
       if (match.type != bucket.type || !bucket.available) {
         index += bucket.count;
         continue;
       }
 
-      index += bucket.count;
+      index += bucket.insertIndex;
       bucket.available--;
-      bucket.count++;
+      if (bucket.insertIndex < bucket.count) {
+        replace = true;
+      } else {
+        bucket.count++;
+      }
+      bucket.insertIndex++;
       break;
     }
-    return index;
+    return { index, replace };
+  },
+
+  /**
+   * Removes matches from a previous search, that are no more returned by the
+   * current search
+   * @param type
+   *        The MATCHTYPE to clean up.
+   * @param [optional] notify
+   *        Whether to notify a result change.
+   */
+  _cleanUpNonCurrentMatches(type, notify = true) {
+    if (this._previousSearchMatchTypes.length == 0 || !this.pending)
+      return;
+
+    let index = 0;
+    let changed = false;
+    if (!this._buckets) {
+      // No match arrived yet, so any match of the given type should be removed
+      // from the top.
+      while (this._previousSearchMatchTypes[0] == type) {
+        this._previousSearchMatchTypes.shift();
+        this._result.removeMatchAt(0);
+        changed = true;
+      }
+    } else {
+      for (let bucket of this._buckets) {
+        if (bucket.type != type) {
+          index += bucket.count;
+          continue;
+        }
+        index += bucket.insertIndex;
+
+        while (bucket.count > bucket.insertIndex) {
+          this._result.removeMatchAt(index);
+          changed = true;
+          bucket.count--;
+        }
+      }
+    }
+    if (changed && notify) {
+      this.notifyResults(true);
+    }
+  },
+
+  /**
+   * If in restrict mode, cleanups non current matches for all the empty types.
+   */
+  cleanUpRestrictNonCurrentMatches() {
+    if (this.hasBehavior("restrict") && this._previousSearchMatchTypes.length > 0) {
+      for (let type of new Set(this._previousSearchMatchTypes)) {
+        if (this._counts[type] == 0) {
+          // Don't notify, since we are about to notify completion.
+          this._cleanUpNonCurrentMatches(type, false);
+        }
+      }
+    }
   },
 
   _processHostRow(row) {
     let match = {};
     let strippedHost = row.getResultByIndex(QUERYINDEX_URL);
     let url = row.getResultByIndex(QUERYINDEX_TITLE);
     let unstrippedHost = stripHttpAndTrim(url, false);
     let frecency = row.getResultByIndex(QUERYINDEX_FRECENCY);
@@ -2226,22 +2361,28 @@ Search.prototype = {
  /**
    * Notifies the listener about results.
    *
    * @param searchOngoing
    *        Indicates whether the search is ongoing.
    */
   notifyResults(searchOngoing) {
     let result = this._result;
-    let resultCode = result.matchCount ? "RESULT_SUCCESS" : "RESULT_NOMATCH";
+    let resultCode = this._currentMatchCount ? "RESULT_SUCCESS" : "RESULT_NOMATCH";
     if (searchOngoing) {
       resultCode += "_ONGOING";
     }
     result.setSearchResult(Ci.nsIAutoCompleteResult[resultCode]);
     this._listener.onSearchResult(this._autocompleteSearch, result);
+    if (!searchOngoing) {
+      // Break possible cycles.
+      this._result.setListener(null);
+      this._listener = null;
+      this._autocompleteSearch = null;
+    }
   },
 }
 
 // UnifiedComplete class
 // component @mozilla.org/autocomplete/search;1?name=unifiedcomplete
 
 function UnifiedComplete() {
   // Make sure the preferences are initialized as soon as possible.
@@ -2276,25 +2417,29 @@ UnifiedComplete.prototype = {
    * Gets a Sqlite database handle.
    *
    * @return {Promise}
    * @resolves to the Sqlite database handle (according to Sqlite.jsm).
    * @rejects javascript exception.
    */
   getDatabaseHandle() {
     if (Prefs.get("autocomplete.enabled") && !this._promiseDatabase) {
-      this._promiseDatabase = (async function() {
+      this._promiseDatabase = (async () => {
         let conn = await Sqlite.cloneStorageConnection({
           connection: PlacesUtils.history.DBConnection,
           readOnly: true
         });
 
         try {
            Sqlite.shutdown.addBlocker("Places UnifiedComplete.js clone closing",
-                                      async function() {
+                                      async () => {
+                                        // Break a possible cycle through the
+                                        // previous result, the controller and
+                                        // ourselves.
+                                        this._currentSearch = null;
                                         SwitchToTabStorage.shutdown();
                                         await conn.close();
                                       });
         } catch (ex) {
           // It's too late to block shutdown, just close the connection.
           await conn.close();
           throw ex;
         }
@@ -2327,34 +2472,65 @@ UnifiedComplete.prototype = {
   },
 
   populatePreloadedSiteStorage(json) {
     PreloadedSiteStorage.populate(json);
   },
 
   // nsIAutoCompleteSearch
 
-  startSearch(searchString, searchParam, previousResult, listener) {
+  startSearch(searchString, searchParam, acPreviousResult, listener) {
     // Stop the search in case the controller has not taken care of it.
     if (this._currentSearch) {
       this.stopSearch();
     }
 
-    // Note: We don't use previousResult to make sure ordering of results are
-    //       consistent.  See bug 412730 for more details.
-
     // If the previous search didn't fetch enough search suggestions, it's
     // unlikely a longer text would do.
     let prohibitSearchSuggestions =
       !!this._lastLowResultsSearchSuggestion &&
       searchString.length > this._lastLowResultsSearchSuggestion.length &&
       searchString.startsWith(this._lastLowResultsSearchSuggestion);
 
+
+    // We don't directly reuse the controller provided previousResult because:
+    //  * it is only populated when the new searchString is an extension of the
+    //    previous one. We want to handle the backspace case too.
+    //  * Bookmarks may be titled differently than history and we want to show
+    //    the right title.  For example a "foo" titled page could be bookmarked
+    //    as "foox", typing "foo" followed by "x" would show the history result
+    //    from the previous search (See bug 412730).
+    //  * Adaptive History means a result may appear even if the previous string
+    //    didn't match it.
+    // What we can do is reuse the previous result along with the bucketing
+    // system to avoid flickering. Since we know where a new match should be
+    // positioned, we  wait for a new match to arrive before replacing the
+    // previous one. This may leave stale matches from the previous search that
+    // would not be returned by the current one, thus once the current search is
+    // complete, we remove those stale matches with _cleanUpNonCurrentMatches().
+    let previousResult = null;
+    let insertMethod = Prefs.get("insertMethod");
+    if (this._currentSearch && insertMethod != INSERTMETHOD.APPEND) {
+      let result = this._currentSearch._result;
+      // Only reuse the previous result when one of the search strings is an
+      // extension of the other one.  We could expand this to any case, but
+      // that may leave exposed unrelated matches for a longer time.
+      let previousSearchString = result.searchString;
+      let stringsRelated = previousSearchString.length > 0 &&
+                           searchString.length > 0 &&
+                           (previousSearchString.includes(searchString) ||
+                            searchString.includes(previousSearchString));
+      if (insertMethod == INSERTMETHOD.MERGE || stringsRelated) {
+        previousResult = result;
+      }
+    }
+
     this._currentSearch = new Search(searchString, searchParam, listener,
-                                     this, this, prohibitSearchSuggestions);
+                                     this, this, prohibitSearchSuggestions,
+                                     previousResult);
 
     // If we are not enabled, we need to return now.  Notice we need an empty
     // result regardless, so we still create the Search object.
     if (!Prefs.get("autocomplete.enabled")) {
       this.finishSearch(true);
       return;
     }
 
@@ -2390,20 +2566,25 @@ UnifiedComplete.prototype = {
   finishSearch(notify = false) {
     TelemetryStopwatch.cancel(TELEMETRY_1ST_RESULT, this);
     TelemetryStopwatch.cancel(TELEMETRY_6_FIRST_RESULTS, this);
     // Clear state now to avoid race conditions, see below.
     let search = this._currentSearch;
     if (!search)
       return;
     this._lastLowResultsSearchSuggestion = search._lastLowResultsSearchSuggestion;
-    delete this._currentSearch;
+
+    if (!notify || !search.pending)
+      return;
+
 
-    if (!notify)
-      return;
+    // If we are in restrict mode and we reused the previous search results,
+    // it's possible we didn't go through all the cleanup methods due to early
+    // bailouts. Thus we could still have nonmatching results to remove.
+    search.cleanUpRestrictNonCurrentMatches();
 
     // There is a possible race condition here.
     // When a search completes it calls finishSearch that notifies results
     // here.  When the controller gets the last result it fires
     // onSearchComplete.
     // If onSearchComplete immediately starts a new search it will set a new
     // _currentSearch, and on return the execution will continue here, after
     // notifyResults.
--- a/toolkit/components/places/tests/unifiedcomplete/test_search_suggestions.js
+++ b/toolkit/components/places/tests/unifiedcomplete/test_search_suggestions.js
@@ -105,27 +105,27 @@ add_task(async function singleWordQuery(
       makeSearchMatch("hello", { engineName: ENGINE_NAME, heuristic: true }),
       { uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello foo",
         searchQuery: "hello",
         searchSuggestion: "hello foo",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello bar",
         searchQuery: "hello",
         searchSuggestion: "hello bar",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }],
   });
 
   await cleanUpSuggestions();
 });
 
 add_task(async function multiWordQuery() {
@@ -139,27 +139,27 @@ add_task(async function multiWordQuery()
       makeSearchMatch("hello world", { engineName: ENGINE_NAME, heuristic: true }),
       { uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello world foo",
         searchQuery: "hello world",
         searchSuggestion: "hello world foo",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello world bar",
         searchQuery: "hello world",
         searchSuggestion: "hello world bar",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }],
   });
 
   await cleanUpSuggestions();
 });
 
 add_task(async function suffixMatch() {
@@ -178,27 +178,27 @@ add_task(async function suffixMatch() {
       makeSearchMatch("hello", { engineName: ENGINE_NAME, heuristic: true }),
       { uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "baz hello",
         searchQuery: "hello",
         searchSuggestion: "baz hello",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "quux hello",
         searchQuery: "hello",
         searchSuggestion: "quux hello",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }],
   });
 
   await cleanUpSuggestions();
 });
 
 add_task(async function queryIsNotASubstring() {
@@ -215,27 +215,27 @@ add_task(async function queryIsNotASubst
       makeSearchMatch("hello", { engineName: ENGINE_NAME, heuristic: true }),
       { uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "aaa",
         searchQuery: "hello",
         searchSuggestion: "aaa",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "bbb",
         searchQuery: "hello",
         searchSuggestion: "bbb",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }],
   });
 
   await cleanUpSuggestions();
 });
 
 add_task(async function restrictToken() {
@@ -280,28 +280,28 @@ add_task(async function restrictToken() 
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "hello foo",
           searchQuery: "hello",
           searchSuggestion: "hello foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "hello bar",
           searchQuery: "hello",
           searchSuggestion: "hello bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   // Now do a restricted search to make sure only suggestions appear.
   await check_autocomplete({
     search: SUGGEST_RESTRICT_TOKEN + " hello",
@@ -312,28 +312,28 @@ add_task(async function restrictToken() 
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "hello foo",
           searchQuery: "hello",
           searchSuggestion: "hello foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "hello bar",
           searchQuery: "hello",
           searchSuggestion: "hello bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       }
     ],
   });
 
   await cleanUpSuggestions();
 });
 
@@ -413,28 +413,28 @@ add_task(async function mixup_frecency()
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency foo",
           searchQuery: "frecency",
           searchSuggestion: "frecency foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency bar",
           searchQuery: "frecency",
           searchSuggestion: "frecency bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       { uri: NetUtil.newURI("http://example.com/lo3"),
         title: "low frecency 3" },
       { uri: NetUtil.newURI("http://example.com/lo2"),
         title: "low frecency 2" },
       { uri: NetUtil.newURI("http://example.com/lo1"),
         title: "low frecency 1" },
@@ -458,17 +458,17 @@ add_task(async function mixup_frecency()
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency foo",
           searchQuery: "frecency",
           searchSuggestion: "frecency foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       { uri: NetUtil.newURI("http://example.com/hi3"),
         title: "high frecency 3",
         style: [ "bookmark" ] },
       { uri: NetUtil.newURI("http://example.com/hi2"),
         title: "high frecency 2",
         style: [ "bookmark" ] },
@@ -483,17 +483,17 @@ add_task(async function mixup_frecency()
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency bar",
           searchQuery: "frecency",
           searchSuggestion: "frecency bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       { uri: NetUtil.newURI("http://example.com/lo3"),
         title: "low frecency 3" },
       { uri: NetUtil.newURI("http://example.com/lo2"),
         title: "low frecency 2" },
       { uri: NetUtil.newURI("http://example.com/lo1"),
         title: "low frecency 1" },
@@ -515,28 +515,28 @@ add_task(async function mixup_frecency()
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency foo",
           searchQuery: "frecency",
           searchSuggestion: "frecency foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "frecency bar",
           searchQuery: "frecency",
           searchSuggestion: "frecency bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       { uri: NetUtil.newURI("http://example.com/hi3"),
         title: "high frecency 3",
         style: [ "bookmark" ] },
       { uri: NetUtil.newURI("http://example.com/hi2"),
         title: "high frecency 2",
         style: [ "bookmark" ] },
@@ -575,28 +575,28 @@ add_task(async function prohibit_suggest
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost foo",
           searchQuery: "localhost",
           searchSuggestion: "localhost foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost bar",
           searchQuery: "localhost",
           searchSuggestion: "localhost bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
   Services.prefs.setBoolPref("browser.fixup.domainwhitelist.localhost", true);
   do_register_cleanup(() => {
     Services.prefs.clearUserPref("browser.fixup.domainwhitelist.localhost");
   });
@@ -618,28 +618,28 @@ add_task(async function prohibit_suggest
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost other foo",
           searchQuery: "localhost other",
           searchSuggestion: "localhost other foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost other bar",
           searchQuery: "localhost other",
           searchSuggestion: "localhost other bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   // Clear the whitelist for localhost, and try preferring DNS for any single
   // word instead:
   Services.prefs.clearUserPref("browser.fixup.domainwhitelist.localhost");
@@ -675,28 +675,28 @@ add_task(async function prohibit_suggest
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost other foo",
           searchQuery: "localhost other",
           searchSuggestion: "localhost other foo",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "localhost other bar",
           searchQuery: "localhost other",
           searchSuggestion: "localhost other bar",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   Services.prefs.clearUserPref("browser.fixup.dns_first_for_single_words");
 
   await check_autocomplete({
@@ -762,17 +762,17 @@ add_task(async function avoid_url_sugges
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "test. com",
           searchQuery: "test",
           searchSuggestion: "test. com",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   await cleanUpSuggestions();
 });
 
@@ -791,17 +791,17 @@ add_task(async function avoid_http_url_s
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "htted",
           searchQuery: "htt",
           searchSuggestion: "htted",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   await check_autocomplete({
     search: "ftp",
     searchParam: "enable-actions",
@@ -834,17 +834,17 @@ add_task(async function avoid_http_url_s
       {
         uri: makeActionURI(("searchengine"), {
           engineName: ENGINE_NAME,
           input: "httpded",
           searchQuery: "httpd",
           searchSuggestion: "httpded",
         }),
         title: ENGINE_NAME,
-        style: ["action", "searchengine"],
+        style: ["action", "searchengine", "suggestion"],
         icon: "",
       },
     ],
   });
 
   await check_autocomplete({
     search: "http:",
     searchParam: "enable-actions",
@@ -1029,37 +1029,37 @@ add_task(async function historicalSugges
     {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello Barney!",
         searchQuery: "hello",
         searchSuggestion: "hello Barney!",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello foo",
         searchQuery: "hello",
         searchSuggestion: "hello foo",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }, {
       uri: makeActionURI(("searchengine"), {
         engineName: ENGINE_NAME,
         input: "hello bar",
         searchQuery: "hello",
         searchSuggestion: "hello bar",
       }),
       title: ENGINE_NAME,
-      style: ["action", "searchengine"],
+      style: ["action", "searchengine", "suggestion"],
       icon: "",
     }],
   });
 
   await cleanUpSuggestions();
   Services.prefs.clearUserPref("browser.urlbar.maxHistoricalSearchSuggestions");
 });