Bug 1391293 - Reduce Address Bar results flickering when typing additional chars. r=adw draft
authorMarco Bonardo <mbonardo@mozilla.com>
Fri, 08 Sep 2017 11:39:44 +0200
changeset 666904 ca3dd8305d99cba914d28377570c5e933009e9d3
parent 666274 ffe6cc09ccf38cca6f0e727837bbc6cb722d1e71
child 666905 1b0d5f88f911097c67572060ec6d77fdf4ab1ea4
push id80543
push usermak77@bonardo.net
push dateTue, 19 Sep 2017 11:38:28 +0000
reviewersadw
bugs1391293
milestone57.0a1
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");
 });