Omnibox: Prevent Asynchronous Suggestions from Changing Default Match

chrome/browser/autocomplete/search_provider.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/autocomplete/search_provider.h"
 
 #include <algorithm>
 #include <cmath>
 
 #include "base/base64.h"
@@ skipping 152 matching lines @@
   // functions are currently in sync, but there's no reason we
   // couldn't decide in the future to score verbatim matches
   // differently for extension and non-extension keywords.  If you
   // make such a change, however, you should update this comment to
   // describe it, so it's clear why the functions diverge.
   if (prefer_keyword)
     return 1500;
   return (type == metrics::OmniboxInputType::QUERY) ? 1450 : 1100;
 }
 
+// static
+void SearchProvider::UpdateOldResults(
+    bool minimal_changes,
+    SearchSuggestionParser::Results* results) {
+  // When called without |minimal_changes|, it likely means the user has
+  // pressed a key.  Revise the cached results appropriately.
+  if (!minimal_changes) {
+    for (SearchSuggestionParser::SuggestResults::iterator sug_it =
+             results->suggest_results.begin();
+         sug_it != results->suggest_results.end(); ++sug_it) {
+      sug_it->set_received_after_last_keystroke(false);
+    }
+    for (SearchSuggestionParser::NavigationResults::iterator nav_it =
+             results->navigation_results.begin();
+         nav_it != results->navigation_results.end(); ++nav_it) {
+      nav_it->set_received_after_last_keystroke(false);
+    }
+  }
+}
+
+// static
+ACMatches::iterator SearchProvider::FindTopMatch(ACMatches* matches) {
+  ACMatches::iterator it = matches->begin();
+  while ((it != matches->end()) && !it->allowed_to_be_default_match)
+    ++it;
+  return it;
+}
+
 void SearchProvider::Start(const AutocompleteInput& input,
                            bool minimal_changes) {
   // Do our best to load the model as early as possible.  This will reduce
   // odds of having the model not ready when really needed (a non-empty input).
   TemplateURLService* model = providers_.template_url_service();
   DCHECK(model);
   model->Load();
 
   matches_.clear();
   field_trial_triggered_ = false;
@@ skipping 202 matching lines @@
       UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
                           elapsed_time);
     } else {
       UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
                           elapsed_time);
     }
   }
 }
 
 void SearchProvider::UpdateMatches() {
+  PersistTopSuggestions(&default_results_);
+  PersistTopSuggestions(&keyword_results_);
   ConvertResultsToAutocompleteMatches();
 
   // Check constraints that may be violated by suggested relevances.
   if (!matches_.empty() &&
       (default_results_.HasServerProvidedScores() ||
        keyword_results_.HasServerProvidedScores())) {
     // These blocks attempt to repair undesirable behavior by suggested
     // relevances with minimal impact, preserving other suggested relevances.
 
     if ((providers_.GetKeywordProviderURL() != NULL) &&
         (FindTopMatch() == matches_.end())) {
       // In keyword mode, disregard the keyword verbatim suggested relevance
-      // if necessary, so at least one match is allowed to be default.
-      keyword_results_.verbatim_relevance = -1;
+      // if necessary, so at least one match is allowed to be default.  (This
+      // is only necessary if we were told to suppress keyword verbatim and
+      // hence have no default keyword match.)  Give keyword verbatim the
+      // lowest non-zero score to best reflect what the server desired.
+      DCHECK_EQ(0, keyword_results_.verbatim_relevance);
+      keyword_results_.verbatim_relevance = 1;
       ConvertResultsToAutocompleteMatches();
     }
     if (IsTopMatchSearchWithURLInput()) {
       // Disregard the suggested search and verbatim relevances if the input
       // type is URL and the top match is a highly-ranked search suggestion.
       // For example, prevent a search for "foo.com" from outranking another
       // provider's navigation for "foo.com" or "foo.com/url_from_history".
       ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
       ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
       default_results_.verbatim_relevance = -1;
       keyword_results_.verbatim_relevance = -1;
       ConvertResultsToAutocompleteMatches();
     }
     if (FindTopMatch() == matches_.end()) {
       // Guarantee that SearchProvider returns a legal default match.  (The
       // omnibox always needs at least one legal default match, and it relies
-      // on SearchProvider to always return one.)
-      ApplyCalculatedRelevance();
+      // on SearchProvider to always return one.)  Give the verbatim suggestion
+      // the lowest non-zero scores to best reflect what the server desired.
+      DCHECK_EQ(0, default_results_.verbatim_relevance);
+      default_results_.verbatim_relevance = 1;
+      // We do not have to alter keyword_results_.verbatim_relevance here.
+      // If the user is in keyword mode, we already reverted (earlier in this
+      // function) the instructions to suppress keyword verbatim.
       ConvertResultsToAutocompleteMatches();
     }
     DCHECK(!IsTopMatchSearchWithURLInput());
     DCHECK(FindTopMatch() != matches_.end());
   }
   UMA_HISTOGRAM_CUSTOM_COUNTS(
       "Omnibox.SearchProviderMatches", matches_.size(), 1, 6, 7);
+
+  // Record the top suggestion (if any) for future use.
+  top_query_suggestion_match_contents_ = base::string16();
+  top_navigation_suggestion_ = GURL();
+  ACMatches::const_iterator first_match = FindTopMatch();
+  if ((first_match != matches_.end()) &&
+      !first_match->inline_autocompletion.empty()) {
+    // Identify if this match came from a query suggestion or a navsuggestion.
+    // In either case, extracts the identifying feature of the suggestion
+    // (query string or navigation url).
+    if (AutocompleteMatch::IsSearchType(first_match->type))
+      top_query_suggestion_match_contents_ = first_match->contents;
+    else
+      top_navigation_suggestion_ = first_match->destination_url;
+  }
+
   UpdateDone();
 }
 
 void SearchProvider::Run() {
   // Start a new request with the current input.
   suggest_results_pending_ = 0;
   time_suggest_request_sent_ = base::TimeTicks::Now();
 
   default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
       providers_.GetDefaultProviderURL(), input_));
@@ skipping 70 matching lines @@
       (!default_results_.suggest_results.empty() ||
        !default_results_.navigation_results.empty() ||
        !keyword_results_.suggest_results.empty() ||
        !keyword_results_.navigation_results.empty() ||
        (!done_ && input_.want_asynchronous_matches())))
     return;
 
   // We can't keep running any previous query, so halt it.
   StopSuggest();
 
-  // Remove existing results that cannot inline autocomplete the new input.
-  RemoveAllStaleResults();
+  UpdateAllOldResults(minimal_changes);
 
   // Update the content classifications of remaining results so they look good
   // against the current input.
   UpdateMatchContentsClass(input_.text(), &default_results_);
   if (!keyword_input_.text().empty())
     UpdateMatchContentsClass(keyword_input_.text(), &keyword_results_);
 
   // We can't start a new query if we're only allowed synchronous results.
   if (!input_.want_asynchronous_matches())
     return;
@@ skipping 63 matching lines @@
   // Don't send anything for https except the hostname.  Hostnames are OK
   // because they are visible when the TCP connection is established, but the
   // specific path may reveal private information.
   if (LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) &&
       parts.path.is_nonempty())
     return false;
 
   return true;
 }
 
-void SearchProvider::RemoveAllStaleResults() {
+void SearchProvider::UpdateAllOldResults(bool minimal_changes) {
   if (keyword_input_.text().empty()) {
     // User is either in keyword mode with a blank input or out of
     // keyword mode entirely.
     keyword_results_.Clear();
   }
+  UpdateOldResults(minimal_changes, &default_results_);
+  UpdateOldResults(minimal_changes, &keyword_results_);
 }
 
-void SearchProvider::ApplyCalculatedRelevance() {
-  ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
-  ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
-  ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
-  ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
-  default_results_.verbatim_relevance = -1;
-  keyword_results_.verbatim_relevance = -1;
+void SearchProvider::PersistTopSuggestions(
+    SearchSuggestionParser::Results* results) {
+  // Mark any results matching the current top results as having been received
+  // prior to the last keystroke.  That prevents asynchronous updates from
+  // clobbering top results, which may be used for inline autocompletion.
+  // Other results don't need similar changes, because they shouldn't be
+  // displayed asynchronously anyway.
+  if (!top_query_suggestion_match_contents_.empty()) {
+    for (SearchSuggestionParser::SuggestResults::iterator sug_it =
+             results->suggest_results.begin();
+         sug_it != results->suggest_results.end(); ++sug_it) {
+      if (sug_it->match_contents() == top_query_suggestion_match_contents_)
+        sug_it->set_received_after_last_keystroke(false);
+    }
+  }
+  if (top_navigation_suggestion_.is_valid()) {
+    for (SearchSuggestionParser::NavigationResults::iterator nav_it =
+             results->navigation_results.begin();
+         nav_it != results->navigation_results.end(); ++nav_it) {
+      if (nav_it->url() == top_navigation_suggestion_)
+        nav_it->set_received_after_last_keystroke(false);
+    }
+  }
 }
 
 void SearchProvider::ApplyCalculatedSuggestRelevance(
     SearchSuggestionParser::SuggestResults* list) {
   for (size_t i = 0; i < list->size(); ++i) {
     SearchSuggestionParser::SuggestResult& result = (*list)[i];
     result.set_relevance(
         result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
         (list->size() - i - 1));
     result.set_relevance_from_server(false);
@@ skipping 148 matching lines @@
                          default_results_.metadata, &map);
 
   ACMatches matches;
   for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
     matches.push_back(i->second);
 
   AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
   AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
 
   // Now add the most relevant matches to |matches_|.  We take up to kMaxMatches
-  // suggest/navsuggest matches, regardless of origin.  If Instant Extended is
-  // enabled and we have server-provided (and thus hopefully more accurate)
-  // scores for some suggestions, we allow more of those, until we reach
+  // suggest/navsuggest matches, regardless of origin.  We always include in
+  // that set a legal default match if possible.  If Instant Extended is enabled
+  // and we have server-provided (and thus hopefully more accurate) scores for
+  // some suggestions, we allow more of those, until we reach
   // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
   // whole popup).
   //
   // We will always return any verbatim matches, no matter how we obtained their
   // scores, unless we have already accepted AutocompleteResult::kMaxMatches
   // higher-scoring matches under the conditions above.
   std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
   matches_.clear();
+  // Guarantee that if there's a legal default match anywhere in the result
+  // set that it'll get returned.  The rotate() call does this by moving the
+  // default match to the front of the list.
+  ACMatches::iterator default_match = FindTopMatch(&matches);
+  if (default_match != matches.end())
+    std::rotate(matches.begin(), default_match, default_match + 1);
 
   size_t num_suggestions = 0;
   for (ACMatches::const_iterator i(matches.begin());
        (i != matches.end()) &&
            (matches_.size() < AutocompleteResult::kMaxMatches);
        ++i) {
     // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
     // verbatim result, so this condition basically means "if this match is a
     // suggestion of some sort".
     if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
@@ skipping 118 matching lines @@
         prevent_search_history_inlining);
     // Add the match to |scored_results| by putting the what-you-typed match
     // on the front and appending all other matches.  We want the what-you-
     // typed match to always be first.
     SearchSuggestionParser::SuggestResults::iterator insertion_position =
         scored_results.end();
     if (trimmed_suggestion == trimmed_input) {
       found_what_you_typed_match = true;
       insertion_position = scored_results.begin();
     }
-    scored_results.insert(
-        insertion_position,
-        SearchSuggestionParser::SuggestResult(
-            trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY,
-            trimmed_suggestion, base::string16(), base::string16(),
-            base::string16(), base::string16(), std::string(), std::string(),
-            is_keyword, relevance, false, false, trimmed_input));
+    SearchSuggestionParser::SuggestResult history_suggestion(
+        trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY,
+        trimmed_suggestion, base::string16(), base::string16(),
+        base::string16(), base::string16(), std::string(), std::string(),
+        is_keyword, relevance, false, false, trimmed_input);
+    // History results are synchronous; they are received upon the last
+    // keystroke.
+    history_suggestion.set_received_after_last_keystroke(false);
+    scored_results.insert(insertion_position, history_suggestion);
   }
 
   // History returns results sorted for us.  However, we may have docked some
   // results' scores, so things are no longer in order.  While keeping the
   // what-you-typed match at the front (if it exists), do a stable sort to get
   // things back in order without otherwise disturbing results with equal
   // scores, then force the scores to be unique, so that the order in which
   // they're shown is deterministic.
   std::stable_sort(scored_results.begin() +
                        (found_what_you_typed_match ? 1 : 0),
@@ skipping 214 matching lines @@
     if (inline_autocomplete_offset != base::string16::npos)
       ++inline_autocomplete_offset;
   }
   if (inline_autocomplete_offset != base::string16::npos) {
     DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
     match.inline_autocompletion =
         match.fill_into_edit.substr(inline_autocomplete_offset);
   }
   // An inlineable navsuggestion can only be the default match when there
   // is no keyword provider active, lest it appear first and break the user
-  // out of keyword mode.  It can also only be default if either the inline
+  // out of keyword mode.  We also must have received the navsuggestion before
+  // the last keystroke, to prevent asynchronous inline autocompletions changes.
+  // The navsuggestion can also only be default if either the inline
   // autocompletion is empty or we're not preventing inline autocompletion.
   // Finally, if we have an inlineable navsuggestion with an inline completion
   // that we're not preventing, make sure we didn't trim any whitespace.
   // We don't want to claim http://foo.com/bar is inlineable against the
   // input "foo.com/b ".
-  match.allowed_to_be_default_match = (prefix != NULL) &&
+  match.allowed_to_be_default_match =
+      (prefix != NULL) &&
       (providers_.GetKeywordProviderURL() == NULL) &&
+      !navigation.received_after_last_keystroke() &&
       (match.inline_autocompletion.empty() ||
       (!input_.prevent_inline_autocomplete() && !trimmed_whitespace));
   match.EnsureUWYTIsAllowedToBeDefault(
       input_.canonicalized_url(), providers_.template_url_service());
 
   match.contents = navigation.match_contents();
   match.contents_class = navigation.match_contents_class();
   match.description = navigation.description();
   AutocompleteMatch::ClassifyMatchInString(input, match.description,
       ACMatchClassification::NONE, &match.description_class);
@@ skipping 52 matching lines @@
   last_answer_seen_.query_type = match->answer_type;
 }
 
 void SearchProvider::DoAnswersQuery(const AutocompleteInput& input) {
   // If the query text starts with trimmed input, this is valid prefetch data.
   prefetch_data_ = StartsWith(last_answer_seen_.full_query_text,
                               base::CollapseWhitespace(input.text(), false),
                               false) ?
       last_answer_seen_ : AnswersQueryData();
 }