Increase number of matches SearchProvider can return to the full popup size,

assuming:

(1) Instant Extended is enabled (so we can get metrics comparing before/after)
(2) The extra matches come from server-scored suggestions.  We allow the highest
ranking 3 non-verbatim matches to come from any source, but after that we only
allow server-scored matches (and verbatim matches) until we hit the result set
limit.

This requires extending the Result class in the search provider to track the
origin of each match's score, as well as recording this information in the
AutocompleteMatch's |additional_info| field.

Note that https://codereview.chromium.org/17391005/ will simplify this somewhat
since we'll be able to stop worrying about FinalizeInstantQuery() etc.

BUG=252506
TEST=With instant extended on, type a query that generates lots of suggestions and see you get a full dropdown worth.
R=mpearson@chromium.org, msw@chromium.org

Review URL: https://codereview.chromium.org/17382015

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@208567 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 311 insertions, 93 deletions

diff --git a/chrome/browser/autocomplete/autocomplete_match.cc b/chrome/browser/autocomplete/autocomplete_match.cc
index 22a049c..5c45f4b 100644
--- a/chrome/browser/autocomplete/autocomplete_match.cc
+++ b/chrome/browser/autocomplete/autocomplete_match.cc
@@ -436,6 +436,12 @@ void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
                        UTF16ToUTF8(base::TimeFormatShortDateAndTime(value)));
 }
 
+std::string AutocompleteMatch::GetAdditionalInfo(
+    const std::string& property) const {
+  AdditionalInfo::const_iterator i(additional_info.find(property));
+  return (i == additional_info.end()) ? std::string() : i->second;
+}
+
 #ifndef NDEBUG
 void AutocompleteMatch::Validate() const {
   ValidateClassifications(contents, contents_class);
diff --git a/chrome/browser/autocomplete/autocomplete_match.h b/chrome/browser/autocomplete/autocomplete_match.h
index 146586e..b7d514e 100644
--- a/chrome/browser/autocomplete/autocomplete_match.h
+++ b/chrome/browser/autocomplete/autocomplete_match.h
@@ -214,6 +214,10 @@ struct AutocompleteMatch {
   void RecordAdditionalInfo(const std::string& property,
                             const base::Time& value);
 
+  // Returns the value recorded for |property| in the |additional_info|
+  // dictionary.  Returns the empty string if no such value exists.
+  std::string GetAdditionalInfo(const std::string& property) const;
+
   // The provider of this match, used to remember which provider the user had
   // selected when the input changes. This may be NULL, in which case there is
   // no provider (or memory of the user's selection).
diff --git a/chrome/browser/autocomplete/search_provider.cc b/chrome/browser/autocomplete/search_provider.cc
index 45f7803..6c19708 100644
--- a/chrome/browser/autocomplete/search_provider.cc
+++ b/chrome/browser/autocomplete/search_provider.cc
@@ -118,9 +118,11 @@ const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
 // SearchProvider::Result -----------------------------------------------------
 
 SearchProvider::Result::Result(bool from_keyword_provider,
-                               int relevance)
+                               int relevance,
+                               bool relevance_from_server)
     : from_keyword_provider_(from_keyword_provider),
-      relevance_(relevance) {
+      relevance_(relevance),
+      relevance_from_server_(relevance_from_server) {
 }
 
 SearchProvider::Result::~Result() {
@@ -131,8 +133,9 @@ SearchProvider::Result::~Result() {
 
 SearchProvider::SuggestResult::SuggestResult(const string16& suggestion,
                                              bool from_keyword_provider,
-                                             int relevance)
-    : Result(from_keyword_provider, relevance),
+                                             int relevance,
+                                             bool relevance_from_server)
+    : Result(from_keyword_provider, relevance, relevance_from_server),
       suggestion_(suggestion) {
 }
 
@@ -159,8 +162,9 @@ SearchProvider::NavigationResult::NavigationResult(
     const GURL& url,
     const string16& description,
     bool from_keyword_provider,
-    int relevance)
-    : Result(from_keyword_provider, relevance),
+    int relevance,
+    bool relevance_from_server)
+    : Result(from_keyword_provider, relevance, relevance_from_server),
       url_(url),
       formatted_url_(AutocompleteInput::FormattedStringWithEquivalentMeaning(
           url, provider.StringForURLDisplay(url, true, false))),
@@ -196,9 +200,7 @@ class SearchProvider::CompareScoredResults {
 
 // SearchProvider::Results ----------------------------------------------------
 
-SearchProvider::Results::Results()
-    : has_suggested_relevance(false),
-      verbatim_relevance(-1) {
+SearchProvider::Results::Results() : verbatim_relevance(-1) {
 }
 
 SearchProvider::Results::~Results() {
@@ -207,7 +209,6 @@ SearchProvider::Results::~Results() {
 void SearchProvider::Results::Clear() {
   suggest_results.clear();
   navigation_results.clear();
-  has_suggested_relevance = false;
   verbatim_relevance = -1;
 }
 
@@ -215,14 +216,33 @@ bool SearchProvider::Results::HasServerProvidedScores() const {
   if (verbatim_relevance >= 0)
     return true;
 
-  return has_suggested_relevance;
+  // Right now either all results of one type will be server-scored or they will
+  // all be locally scored, but in case we change this later, we'll just check
+  // them all.
+  for (SuggestResults::const_iterator i(suggest_results.begin());
+       i != suggest_results.end(); ++i) {
+    if (i->relevance_from_server())
+      return true;
+  }
+  for (NavigationResults::const_iterator i(navigation_results.begin());
+       i != navigation_results.end(); ++i) {
+    if (i->relevance_from_server())
+      return true;
+  }
+
+  return false;
 }
+
+
 // SearchProvider -------------------------------------------------------------
 
 // static
 const int SearchProvider::kDefaultProviderURLFetcherID = 1;
 const int SearchProvider::kKeywordProviderURLFetcherID = 2;
 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
+const char SearchProvider::kRelevanceFromServerKey[] = "relevance_from_server";
+const char SearchProvider::kTrue[] = "true";
+const char SearchProvider::kFalse[] = "false";
 
 SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
                                Profile* profile)
@@ -394,27 +414,29 @@ void SearchProvider::FinalizeInstantQuery(const string16& input_text,
   if (suggestion.type == INSTANT_SUGGESTION_SEARCH) {
     // Instant has a query suggestion. Rank it higher than SEARCH_WHAT_YOU_TYPED
     // so that it gets autocompleted.
-    const int verbatim_relevance = GetVerbatimRelevance();
+    bool relevance_from_server;
+    const int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
     int did_not_accept_default_suggestion =
         default_results_.suggest_results.empty() ?
         TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
         TemplateURLRef::NO_SUGGESTION_CHOSEN;
     MatchMap match_map;
     AddMatchToMap(text, adjusted_input_text, verbatim_relevance + 1,
-                  AutocompleteMatchType::SEARCH_SUGGEST,
+                  relevance_from_server, AutocompleteMatchType::SEARCH_SUGGEST,
                   did_not_accept_default_suggestion, false, &match_map);
     if (!match_map.empty()) {
       matches_.push_back(match_map.begin()->second);
       results_updated = true;
     }
   } else {
-    // Instant has a URL suggestion. Rank it higher than URL_WHAT_YOU_TYPED so
-    // it gets autocompleted; use kNonURLVerbatimRelevance rather than
-    // verbatim_relevance so that the score does not change if the user keeps
-    // typing and the input changes from type UNKNOWN to URL.
+    // Instant has a URL suggestion. Rank it higher than other providers would
+    // rank URL_WHAT_YOU_TYPED so it gets autocompleted; use
+    // kNonURLVerbatimRelevance rather than |verbatim_relevance| so that the
+    // score does not change if the user keeps typing and the input changes from
+    // type UNKNOWN to URL.
     matches_.push_back(NavigationToMatch(NavigationResult(
         *this, GURL(UTF16ToUTF8(suggestion.text)), string16(), false,
-        kNonURLVerbatimRelevance + 1)));
+        kNonURLVerbatimRelevance + 1, false)));
     results_updated = true;
   }
 
@@ -869,11 +891,11 @@ void SearchProvider::RemoveAllStaleResults() {
   // and ease in reasoning about the invariants involved, this code
   // removes stales results from the keyword provider and default
   // provider independently.
-  RemoveStaleResults(input_.text(), GetVerbatimRelevance(),
+  RemoveStaleResults(input_.text(), GetVerbatimRelevance(NULL),
                      &default_results_.suggest_results,
                      &default_results_.navigation_results);
   if (!keyword_input_.text().empty()) {
-    RemoveStaleResults(keyword_input_.text(), GetKeywordVerbatimRelevance(),
+    RemoveStaleResults(keyword_input_.text(), GetKeywordVerbatimRelevance(NULL),
                        &keyword_results_.suggest_results,
                        &keyword_results_.navigation_results);
   } else {
@@ -889,7 +911,7 @@ void SearchProvider::AdjustDefaultProviderSuggestion(
   if (default_provider_suggestion_.type == INSTANT_SUGGESTION_URL) {
     // Description and relevance do not matter in the check for staleness.
     NavigationResult result(*this, GURL(default_provider_suggestion_.text),
-                            string16(), false, 100);
+                            string16(), false, 100, false);
     // If navigation suggestion is stale, clear |default_provider_suggestion_|.
     if (!result.IsInlineable(current_input))
       default_provider_suggestion_ = InstantSuggestion();
@@ -921,8 +943,6 @@ void SearchProvider::ApplyCalculatedRelevance() {
   ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
   ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
   ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
-  default_results_.has_suggested_relevance = false;
-  keyword_results_.has_suggested_relevance = false;
   default_results_.verbatim_relevance = -1;
   keyword_results_.verbatim_relevance = -1;
 }
@@ -933,6 +953,7 @@ void SearchProvider::ApplyCalculatedSuggestRelevance(SuggestResults* list) {
     result.set_relevance(
         result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
         (list->size() - i - 1));
+    result.set_relevance_from_server(false);
   }
 }
 
@@ -943,6 +964,7 @@ void SearchProvider::ApplyCalculatedNavigationRelevance(
     result.set_relevance(
         result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
         (list->size() - i - 1));
+    result.set_relevance_from_server(false);
   }
 }
 
@@ -995,7 +1017,6 @@ bool SearchProvider::ParseSuggestResults(Value* root_val, bool is_keyword) {
 
   // Reset suggested relevance information from the default provider.
   Results* results = is_keyword ? &keyword_results_ : &default_results_;
-  results->has_suggested_relevance = false;
   results->verbatim_relevance = -1;
 
   // 5th element: Optional key-value pairs from the Suggest server.
@@ -1042,13 +1063,13 @@ bool SearchProvider::ParseSuggestResults(Value* root_val, bool is_keyword) {
       if (url.is_valid()) {
         if (descriptions != NULL)
           descriptions->GetString(index, &title);
-        results->navigation_results.push_back(
-            NavigationResult(*this, url, title, is_keyword, relevance));
+        results->navigation_results.push_back(NavigationResult(
+            *this, url, title, is_keyword, relevance, true));
       }
     } else {
       // TODO(kochi): Improve calculator result presentation.
       results->suggest_results.push_back(
-          SuggestResult(result, is_keyword, relevance));
+          SuggestResult(result, is_keyword, relevance, true));
     }
   }
 
@@ -1056,8 +1077,6 @@ bool SearchProvider::ParseSuggestResults(Value* root_val, bool is_keyword) {
   if (relevances == NULL) {
     ApplyCalculatedSuggestRelevance(&results->suggest_results);
     ApplyCalculatedNavigationRelevance(&results->navigation_results);
-  } else {
-    results->has_suggested_relevance = true;
   }
   // Keep the result lists sorted.
   const CompareScoredResults comparator = CompareScoredResults();
@@ -1080,13 +1099,15 @@ void SearchProvider::ConvertResultsToAutocompleteMatches() {
       TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
       TemplateURLRef::NO_SUGGESTION_CHOSEN;
 
-  int verbatim_relevance = GetVerbatimRelevance();
+  bool relevance_from_server;
+  int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
   int did_not_accept_default_suggestion =
       default_results_.suggest_results.empty() ?
       TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
       TemplateURLRef::NO_SUGGESTION_CHOSEN;
   if (verbatim_relevance > 0) {
     AddMatchToMap(input_.text(), input_.text(), verbatim_relevance,
+                  relevance_from_server,
                   AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
                   did_not_accept_default_suggestion, false, &map);
   }
@@ -1099,21 +1120,22 @@ void SearchProvider::ConvertResultsToAutocompleteMatches() {
     // to the keyword verbatim search query.  Do not create other matches
     // of type SEARCH_OTHER_ENGINE.
     if (keyword_url && !keyword_url->IsExtensionKeyword()) {
-      const int keyword_verbatim_relevance = GetKeywordVerbatimRelevance();
+      bool keyword_relevance_from_server;
+      const int keyword_verbatim_relevance =
+          GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
       if (keyword_verbatim_relevance > 0) {
         AddMatchToMap(keyword_input_.text(), keyword_input_.text(),
-                      keyword_verbatim_relevance,
+                      keyword_verbatim_relevance, keyword_relevance_from_server,
                       AutocompleteMatchType::SEARCH_OTHER_ENGINE,
                       did_not_accept_keyword_suggestion, true, &map);
       }
     }
   }
-  const size_t verbatim_matches_size = map.size();
   if (!default_provider_suggestion_.text.empty() &&
       default_provider_suggestion_.type == INSTANT_SUGGESTION_SEARCH &&
       !input_.prevent_inline_autocomplete())
     AddMatchToMap(input_.text() + default_provider_suggestion_.text,
-                  input_.text(), verbatim_relevance + 1,
+                  input_.text(), verbatim_relevance + 1, relevance_from_server,
                   AutocompleteMatchType::SEARCH_SUGGEST,
                   did_not_accept_default_suggestion, false, &map);
 
@@ -1125,31 +1147,58 @@ void SearchProvider::ConvertResultsToAutocompleteMatches() {
   AddSuggestResultsToMap(keyword_results_.suggest_results, &map);
   AddSuggestResultsToMap(default_results_.suggest_results, &map);
 
-  // Now add the most relevant matches from the map to |matches_|.
-  matches_.clear();
+  ACMatches matches;
   for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
-    matches_.push_back(i->second);
+    matches.push_back(i->second);
 
   if (!default_provider_suggestion_.text.empty() &&
       default_provider_suggestion_.type == INSTANT_SUGGESTION_URL &&
       !input_.prevent_inline_autocomplete()) {
     // See comment in FinalizeInstantQuery() for why we don't use
     // |verbatim_relevance| here.
-    matches_.push_back(NavigationToMatch(NavigationResult(
+    matches.push_back(NavigationToMatch(NavigationResult(
         *this, GURL(UTF16ToUTF8(default_provider_suggestion_.text)), string16(),
-        false, kNonURLVerbatimRelevance + 1)));
+        false, kNonURLVerbatimRelevance + 1, false)));
   }
-  AddNavigationResultsToMatches(keyword_results_.navigation_results);
-  AddNavigationResultsToMatches(default_results_.navigation_results);
+  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
+  // 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();
+
+  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) &&
+        (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
+      // If we've already hit the limit on non-server-scored suggestions, and
+      // this isn't a server-scored suggestion we can add, skip it.
+      if ((num_suggestions >= kMaxMatches) &&
+          (!chrome::IsInstantExtendedAPIEnabled() ||
+           (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
+        continue;
+      }
 
-  // Allow additional match(es) for verbatim results if present.
-  const size_t max_total_matches = kMaxMatches + verbatim_matches_size;
-  std::partial_sort(matches_.begin(),
-      matches_.begin() + std::min(max_total_matches, matches_.size()),
-      matches_.end(), &AutocompleteMatch::MoreRelevant);
+      ++num_suggestions;
+    }
 
-  if (matches_.size() > max_total_matches)
-    matches_.resize(max_total_matches);
+    matches_.push_back(*i);
+  }
 }
 
 bool SearchProvider::IsTopMatchNavigationInKeywordMode() const {
@@ -1186,7 +1235,6 @@ bool SearchProvider::IsTopMatchNotInlinable() const {
   // not create any other match of type SEARCH_OTHER_ENGINE.
   return
       matches_.front().type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED &&
-      matches_.front().type != AutocompleteMatchType::URL_WHAT_YOU_TYPED &&
       matches_.front().type != AutocompleteMatchType::SEARCH_OTHER_ENGINE &&
       matches_.front().inline_autocomplete_offset == string16::npos &&
       matches_.front().fill_into_edit != input_.text();
@@ -1235,11 +1283,10 @@ void SearchProvider::UpdateMatches() {
       ConvertResultsToAutocompleteMatches();
     }
     if (IsTopMatchNotInlinable()) {
-      // Disregard suggested relevances if the top match is not a verbatim
-      // match, inlinable, or URL_WHAT_YOU_TYPED (which may be top match
-      // regardless of inlining).  For example, input "foo" should not
-      // invoke a search for "bar", which would happen if the "bar" search
-      // match outranked all other matches.
+      // Disregard suggested relevances if the top match is not a verbatim match
+      // or inlinable.  For example, input "foo" should not invoke a search for
+      // "bar", which would happen if the "bar" search match outranked all other
+      // matches.
       ApplyCalculatedRelevance();
       ConvertResultsToAutocompleteMatches();
     }
@@ -1254,15 +1301,14 @@ void SearchProvider::UpdateMatches() {
 }
 
 void SearchProvider::AddNavigationResultsToMatches(
-    const NavigationResults& navigation_results) {
+    const NavigationResults& navigation_results,
+    ACMatches* matches) {
   for (NavigationResults::const_iterator it = navigation_results.begin();
         it != navigation_results.end(); ++it) {
-    matches_.push_back(NavigationToMatch(*it));
+    matches->push_back(NavigationToMatch(*it));
     // In the absence of suggested relevance scores, use only the single
     // highest-scoring result.  (The results are already sorted by relevance.)
-    if (!(it->from_keyword_provider() ?
-        keyword_results_.has_suggested_relevance :
-        default_results_.has_suggested_relevance))
+    if (!it->relevance_from_server())
       return;
   }
 }
@@ -1302,7 +1348,7 @@ void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
                                          is_keyword);
   for (SuggestResults::const_iterator i(scored_results.begin());
        i != scored_results.end(); ++i) {
-    AddMatchToMap(i->suggestion(), input_text, i->relevance(),
+    AddMatchToMap(i->suggestion(), input_text, i->relevance(), false,
                   AutocompleteMatchType::SEARCH_HISTORY,
                   did_not_accept_suggestion,
                   is_keyword, map);
@@ -1347,7 +1393,8 @@ SearchProvider::SuggestResults SearchProvider::ScoreHistoryResults(
 
     int relevance = CalculateRelevanceForHistory(i->time, is_keyword,
                                                  prevent_inline_autocomplete);
-    scored_results.push_back(SuggestResult(i->term, is_keyword, relevance));
+    scored_results.push_back(
+        SuggestResult(i->term, is_keyword, relevance, false));
   }
 
   // History returns results sorted for us.  However, we may have docked some
@@ -1374,11 +1421,12 @@ void SearchProvider::AddSuggestResultsToMap(const SuggestResults& results,
     const bool is_keyword = results[i].from_keyword_provider();
     const string16& input = is_keyword ? keyword_input_.text() : input_.text();
     AddMatchToMap(results[i].suggestion(), input, results[i].relevance(),
+                  results[i].relevance_from_server(),
                   AutocompleteMatchType::SEARCH_SUGGEST, i, is_keyword, map);
   }
 }
 
-int SearchProvider::GetVerbatimRelevance() const {
+int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
   // Use the suggested verbatim relevance score if it is non-negative (valid),
   // if inline autocomplete isn't prevented (always show verbatim on backspace),
   // and if it won't suppress verbatim, leaving no default provider matches.
@@ -1393,6 +1441,8 @@ int SearchProvider::GetVerbatimRelevance() const {
       ((default_results_.verbatim_relevance > 0) ||
        !default_results_.suggest_results.empty() ||
        !default_results_.navigation_results.empty());
+  if (relevance_from_server)
+    *relevance_from_server = use_server_relevance;
   return use_server_relevance ?
       default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
 }
@@ -1420,7 +1470,8 @@ int SearchProvider::
   }
 }
 
-int SearchProvider::GetKeywordVerbatimRelevance() const {
+int SearchProvider::GetKeywordVerbatimRelevance(
+    bool* relevance_from_server) const {
   // Use the suggested verbatim relevance score if it is non-negative (valid),
   // if inline autocomplete isn't prevented (always show verbatim on backspace),
   // and if it won't suppress verbatim, leaving no keyword provider matches.
@@ -1435,6 +1486,8 @@ int SearchProvider::GetKeywordVerbatimRelevance() const {
       ((keyword_results_.verbatim_relevance > 0) ||
        !keyword_results_.suggest_results.empty() ||
        !keyword_results_.navigation_results.empty());
+  if (relevance_from_server)
+    *relevance_from_server = use_server_relevance;
   return use_server_relevance ?
       keyword_results_.verbatim_relevance :
       CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
@@ -1479,6 +1532,7 @@ int SearchProvider::CalculateRelevanceForHistory(
 void SearchProvider::AddMatchToMap(const string16& query_string,
                                    const string16& input_text,
                                    int relevance,
+                                   bool relevance_from_server,
                                    AutocompleteMatch::Type type,
                                    int accepted_suggestion,
                                    bool is_keyword,
@@ -1487,7 +1541,7 @@ void SearchProvider::AddMatchToMap(const string16& query_string,
   // -- they should always use grey text if they are to autocomplete at all. So
   // we clamp non-verbatim results to just below the verbatim score to ensure
   // that none of them are inline autocompleted.
-  // TODO(pkasting): This shouldn't depend on instant extended.  If we think
+  // TODO(pkasting): This shouldn't depend on Instant Extended.  If we think
   // this change is a win, let's change the suggest server to not send
   // high-ranking suggest scores, and change CalculateRelevanceForHistory() to
   // use lower curves.  This code is also buggy as-is because it can demote many
@@ -1505,6 +1559,8 @@ void SearchProvider::AddMatchToMap(const string16& query_string,
       is_keyword, keyword, omnibox_start_margin_);
   if (!match.destination_url.is_valid())
     return;
+  match.RecordAdditionalInfo(kRelevanceFromServerKey,
+                             relevance_from_server ? kTrue : kFalse);
 
   // Try to add |match| to |map|.  If a match for |query_string| is already in
   // |map|, replace it if |match| is more relevant.
@@ -1580,17 +1636,28 @@ AutocompleteMatch SearchProvider::NavigationToMatch(
   match.description = navigation.description();
   AutocompleteMatch::ClassifyMatchInString(input, match.description,
       ACMatchClassification::NONE, &match.description_class);
+
+  match.RecordAdditionalInfo(
+      kRelevanceFromServerKey,
+      navigation.relevance_from_server() ? kTrue : kFalse);
+
   return match;
 }
 
 void SearchProvider::DemoteKeywordNavigationMatchesPastTopQuery() {
   // First, determine the maximum score of any keyword query match (verbatim or
   // query suggestion).
-  int max_query_relevance = GetKeywordVerbatimRelevance();
+  bool relevance_from_server;
+  int max_query_relevance = GetKeywordVerbatimRelevance(&relevance_from_server);
   if (!keyword_results_.suggest_results.empty()) {
-    max_query_relevance =
-        std::max(keyword_results_.suggest_results.front().relevance(),
-                 max_query_relevance);
+    const SuggestResult& top_keyword = keyword_results_.suggest_results.front();
+    const int suggest_relevance = top_keyword.relevance();
+    if (suggest_relevance > max_query_relevance) {
+      max_query_relevance = suggest_relevance;
+      relevance_from_server = top_keyword.relevance_from_server();
+    } else if (suggest_relevance == max_query_relevance) {
+      relevance_from_server |= top_keyword.relevance_from_server();
+    }
   }
   // If no query is supposed to appear, then navigational matches cannot
   // be demoted past it.  Get rid of suggested relevance scores for
@@ -1614,6 +1681,7 @@ void SearchProvider::DemoteKeywordNavigationMatchesPastTopQuery() {
       return;
     max_query_relevance = std::max(max_query_relevance - 1, 0);
     it->set_relevance(max_query_relevance);
+    it->set_relevance_from_server(relevance_from_server);
   }
 }
 
diff --git a/chrome/browser/autocomplete/search_provider.h b/chrome/browser/autocomplete/search_provider.h
index e4400fd..2bf17f5 100644
--- a/chrome/browser/autocomplete/search_provider.h
+++ b/chrome/browser/autocomplete/search_provider.h
@@ -184,7 +184,9 @@ class SearchProvider : public AutocompleteProvider,
   //           highly fragmented SearchProvider logic for each Result type.
   class Result {
    public:
-    Result(bool from_keyword_provider, int relevance);
+    Result(bool from_keyword_provider,
+           int relevance,
+           bool relevance_from_server);
     virtual ~Result();
 
     bool from_keyword_provider() const { return from_keyword_provider_; }
@@ -192,6 +194,11 @@ class SearchProvider : public AutocompleteProvider,
     int relevance() const { return relevance_; }
     void set_relevance(int relevance) { relevance_ = relevance; }
 
+    bool relevance_from_server() const { return relevance_from_server_; }
+    void set_relevance_from_server(bool relevance_from_server) {
+      relevance_from_server_ = relevance_from_server;
+    }
+
     // Returns if this result is inlineable against the current input |input|.
     // Non-inlineable results are stale.
     virtual bool IsInlineable(const string16& input) const = 0;
@@ -209,13 +216,22 @@ class SearchProvider : public AutocompleteProvider,
 
     // The relevance score.
     int relevance_;
+
+   private:
+    // Whether this result's relevance score was fully or partly calculated
+    // based on server information, and thus is assumed to be more accurate.
+    // This is ultimately used in
+    // SearchProvider::ConvertResultsToAutocompleteMatches(), see comments
+    // there.
+    bool relevance_from_server_;
   };
 
   class SuggestResult : public Result {
    public:
     SuggestResult(const string16& suggestion,
                   bool from_keyword_provider,
-                  int relevance);
+                  int relevance,
+                  bool relevance_from_server);
     virtual ~SuggestResult();
 
     const string16& suggestion() const { return suggestion_; }
@@ -239,7 +255,8 @@ class SearchProvider : public AutocompleteProvider,
                      const GURL& url,
                      const string16& description,
                      bool from_keyword_provider,
-                     int relevance);
+                     int relevance,
+                     bool relevance_from_server);
     virtual ~NavigationResult();
 
     const GURL& url() const { return url_; }
@@ -281,8 +298,7 @@ class SearchProvider : public AutocompleteProvider,
     ~Results();
 
     // Clears |suggest_results| and |navigation_results| and resets
-    // |has_suggested_relevance| and |verbatim_relevance| to default
-    // values (false and -1 (implies unset), respectively).
+    // |verbatim_relevance| to -1 (implies unset).
     void Clear();
 
     // Returns whether any of the results (including verbatim) have
@@ -295,9 +311,6 @@ class SearchProvider : public AutocompleteProvider,
     // Navigational suggestions sorted by relevance score.
     NavigationResults navigation_results;
 
-    // Flag indicating server supplied relevance score.
-    bool has_suggested_relevance;
-
     // The server supplied verbatim relevance scores. Negative values
     // indicate that there is no suggested score; a value of 0
     // suppresses the verbatim result.
@@ -394,9 +407,10 @@ class SearchProvider : public AutocompleteProvider,
   void UpdateMatches();
 
   // Converts an appropriate number of navigation results in
-  // |navigation_results| to matches and adds them to |matches_|.
+  // |navigation_results| to matches and adds them to |matches|.
   void AddNavigationResultsToMatches(
-      const NavigationResults& navigation_results);
+      const NavigationResults& navigation_results,
+      ACMatches* matches);
 
   // Adds a match for each result in |results| to |map|. |is_keyword| indicates
   // whether the results correspond to the keyword provider or default provider.
@@ -416,8 +430,10 @@ class SearchProvider : public AutocompleteProvider,
   void AddSuggestResultsToMap(const SuggestResults& results, MatchMap* map);
 
   // Gets the relevance score for the verbatim result.  This value may be
-  // provided by the suggest server or calculated locally.
-  int GetVerbatimRelevance() const;
+  // provided by the suggest server or calculated locally; if
+  // |relevance_from_server| is non-NULL, it will be set to indicate which of
+  // those is true.
+  int GetVerbatimRelevance(bool* relevance_from_server) const;
 
   // Calculates the relevance score for the verbatim result from the
   // default search engine.  This version takes into account context:
@@ -432,10 +448,11 @@ class SearchProvider : public AutocompleteProvider,
   int CalculateRelevanceForVerbatimIgnoringKeywordModeState() const;
 
   // Gets the relevance score for the keyword verbatim result.
+  // |relevance_from_server| is handled as in GetVerbatimRelevance().
   // TODO(mpearson): Refactor so this duplication isn't necesary or
   // restructure so one static function takes all the parameters it needs
   // (rather than looking at internal state).
-  int GetKeywordVerbatimRelevance() const;
+  int GetKeywordVerbatimRelevance(bool* relevance_from_server) const;
 
   // |time| is the time at which this query was last seen.  |is_keyword|
   // indicates whether the results correspond to the keyword provider or default
@@ -451,6 +468,7 @@ class SearchProvider : public AutocompleteProvider,
   void AddMatchToMap(const string16& query_string,
                      const string16& input_text,
                      int relevance,
+                     bool relevance_from_server,
                      AutocompleteMatch::Type type,
                      int accepted_suggestion,
                      bool is_keyword,
@@ -476,6 +494,13 @@ class SearchProvider : public AutocompleteProvider,
   // previous one.  Non-const because some unittests modify this value.
   static int kMinimumTimeBetweenSuggestQueriesMs;
 
+  // We annotate our AutocompleteMatches with whether their relevance scores
+  // were server-provided using this key in the |additional_info| field.
+  static const char kRelevanceFromServerKey[];
+  // These are the values we record with the above key.
+  static const char kTrue[];
+  static const char kFalse[];
+
   // Maintains the TemplateURLs used.
   Providers providers_;
 
diff --git a/chrome/browser/autocomplete/search_provider_unittest.cc b/chrome/browser/autocomplete/search_provider_unittest.cc
index 6d244b8..36453c2 100644
--- a/chrome/browser/autocomplete/search_provider_unittest.cc
+++ b/chrome/browser/autocomplete/search_provider_unittest.cc
@@ -1204,6 +1204,7 @@ TEST_F(SearchProviderTest, DefaultFetcherSuggestRelevance) {
     const std::string description = "for input with json=" + cases[i].json;
     const ACMatches& matches = provider_->matches();
     // The top match must inline and score as highly as calculated verbatim.
+    ASSERT_FALSE(matches.empty());
     EXPECT_NE(string16::npos, matches[0].inline_autocomplete_offset) <<
         description;
     EXPECT_GE(matches[0].relevance, 1300) << description;
@@ -1567,20 +1568,20 @@ TEST_F(SearchProviderTest, KeywordFetcherSuggestRelevance) {
         { "k a", false },
         { kNotApplicable, false } } },
     // Check when there is neither verbatim nor a query suggestion that,
-    // because we can demote navsuggestions below a query suggestion,
+    // because we can't demote navsuggestions below a query suggestion,
     // we abandon suggested relevance scores entirely.  One consequence is
     // that this means we restore the keyword verbatim match.  Note
     // that in this case of abandoning suggested relevance scores, we still
-    // keep the navsuggestions in the same order, and continue to allow multiple
-    // navsuggestions to appear.
+    // keep the navsuggestions in the same order, but we revert to only allowing
+    // one navigation to appear because the scores are completely local.
     { "[\"a\",[\"http://a1.com\", \"http://a2.com\"],[],[],"
        "{\"google:suggesttype\":[\"NAVIGATION\", \"NAVIGATION\"],"
         "\"google:verbatimrelevance\":0,"
         "\"google:suggestrelevance\":[9998, 9999]}]",
       { { "a", true },
         { "a2.com", false },
-        { "a1.com", false },
         { "k a", false },
+        { kNotApplicable, false },
         { kNotApplicable, false } } },
     { "[\"a\",[\"http://a1.com\", \"http://a2.com\"],[],[],"
        "{\"google:suggesttype\":[\"NAVIGATION\", \"NAVIGATION\"],"
@@ -1588,8 +1589,8 @@ TEST_F(SearchProviderTest, KeywordFetcherSuggestRelevance) {
         "\"google:suggestrelevance\":[9999, 9998]}]",
       { { "a", true },
         { "a1.com", false },
-        { "a2.com", false },
         { "k a", false },
+        { kNotApplicable, false },
         { kNotApplicable, false } } },
     // More checks that everything works when it's not necessary to demote.
     { "[\"a\",[\"http://a1.com\", \"http://a2.com\", \"a3\"],[],[],"
@@ -1636,6 +1637,7 @@ TEST_F(SearchProviderTest, KeywordFetcherSuggestRelevance) {
     const std::string description = "for input with json=" + cases[i].json;
     const ACMatches& matches = provider_->matches();
     // The top match must inline and score as highly as calculated verbatim.
+    ASSERT_FALSE(matches.empty());
     EXPECT_NE(string16::npos, matches[0].inline_autocomplete_offset) <<
         description;
     EXPECT_GE(matches[0].relevance, 1300) << description;
@@ -1655,6 +1657,116 @@ TEST_F(SearchProviderTest, KeywordFetcherSuggestRelevance) {
   }
 }
 
+TEST_F(SearchProviderTest, LocalAndRemoteRelevances) {
+  // Enable Instant Extended in order to allow an increased number of
+  // suggestions.  Unfortunately this requires us to call FinalizeInstantQuery()
+  // every time, and also means we'll clamp non-verbatim results to score below
+  // the verbatim result (see http://crbug.com/251493 ).
+  chrome::EnableInstantExtendedAPIForTesting();
+
+  // We hardcode the string "term1" below, so ensure that the search term that
+  // got added to history already is that string.
+  ASSERT_EQ(ASCIIToUTF16("term1"), term1_);
+  string16 term = term1_.substr(0, term1_.length() - 1);
+
+  AddSearchToHistory(default_t_url_, term + ASCIIToUTF16("2"), 2);
+  profile_.BlockUntilHistoryProcessesPendingRequests();
+
+  struct {
+    const string16 input;
+    const std::string json;
+    const std::string matches[6];
+  } cases[] = {
+    // The verbatim result is always first because of the clamping mentioned
+    // above.  The history results are in alphabetical order because they score
+    // the same and thus are pulled out of the MatchMap in the order of their
+    // map keys.
+    { term,
+      "[\"term\",[\"a1\", \"a2\", \"a3\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"QUERY\"],"
+        "\"google:suggestrelevance\":[1, 2, 3]}]",
+      { "term", "term1", "term2", "a3", "a2", "a1" } },
+    // Because we already have three suggestions by the time we see the history
+    // results, they don't get returned.
+    { term,
+      "[\"term\",[\"a1\", \"a2\", \"a3\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"QUERY\"],"
+        "\"google:verbatimrelevance\":1350,"
+        "\"google:suggestrelevance\":[1340, 1330, 1320]}]",
+      { "term", "a1", "a2", "a3", kNotApplicable, kNotApplicable } },
+    // If we only have two suggestions, we have room for a history result.
+    { term,
+      "[\"term\",[\"a1\", \"a2\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\"],"
+        "\"google:verbatimrelevance\":1350,"
+        "\"google:suggestrelevance\":[1330, 1310]}]",
+      { "term", "a1", "a2", "term1", kNotApplicable, kNotApplicable } },
+    // If we have more than three suggestions, they should all be returned as
+    // long as we have enough total space for them.
+    { term,
+      "[\"term\",[\"a1\", \"a2\", \"a3\", \"a4\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"QUERY\", \"QUERY\"],"
+        "\"google:verbatimrelevance\":1350,"
+        "\"google:suggestrelevance\":[1340, 1330, 1320, 1310]}]",
+      { "term", "a1", "a2", "a3", "a4", kNotApplicable } },
+    { term,
+      "[\"term\",[\"a1\", \"a2\", \"a3\", \"a4\", \"a5\", \"a6\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"QUERY\", \"QUERY\","
+                                "\"QUERY\", \"QUERY\"],"
+        "\"google:verbatimrelevance\":1350,"
+        "\"google:suggestrelevance\":[1340, 1330, 1320, 1310, 1300, 1290]}]",
+      { "term", "a1", "a2", "a3", "a4", "a5" } },
+    { term,
+      "[\"term\",[\"a1\", \"a2\", \"a3\", \"a4\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"QUERY\", \"QUERY\"],"
+        "\"google:verbatimrelevance\":1350,"
+        "\"google:suggestrelevance\":[1330, 1310, 1290, 1270]}]",
+      { "term", "a1", "a2", "term1", "a3", "a4" } },
+    // When the input looks like a URL, we disallow having a query as the
+    // highest-ranking result.  If the query was provided by a suggestion, we
+    // reset the suggest scores to enforce this (see
+    // SearchProvider::UpdateMatches()).  Even if we reset the suggest scores,
+    // however, we should still allow navsuggestions to be treated as
+    // server-provided.
+    { ASCIIToUTF16("a.com"),
+      "[\"a.com\",[\"a1\", \"a2\", \"a.com/1\", \"a.com/2\"],[],[],"
+       "{\"google:suggesttype\":[\"QUERY\", \"QUERY\", \"NAVIGATION\","
+                                "\"NAVIGATION\"],"
+        // A verbatim query for URL-like input scores 850, so the navigation
+        // scores here should bracket it.
+        "\"google:suggestrelevance\":[9999, 9998, 900, 800]}]",
+      { "a.com/1", "a.com", "a.com/2", "a1", kNotApplicable, kNotApplicable } },
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(cases); i++) {
+    QueryForInput(cases[i].input, false, false);
+    provider_->FinalizeInstantQuery(string16(), InstantSuggestion());
+    net::TestURLFetcher* fetcher = WaitUntilURLFetcherIsReady(
+        SearchProvider::kDefaultProviderURLFetcherID);
+    ASSERT_TRUE(fetcher);
+    fetcher->set_response_code(200);
+    fetcher->SetResponseString(cases[i].json);
+    fetcher->delegate()->OnURLFetchComplete(fetcher);
+    RunTillProviderDone();
+
+    const std::string description = "for input with json=" + cases[i].json;
+    const ACMatches& matches = provider_->matches();
+
+    // Ensure no extra matches are present.
+    ASSERT_LE(matches.size(), 6U);
+
+    size_t j = 0;
+    // Ensure that the returned matches equal the expectations.
+    for (; j < matches.size(); ++j)
+      EXPECT_EQ(ASCIIToUTF16(cases[i].matches[j]),
+                matches[j].contents) << description;
+    // Ensure that no expected matches are missing.
+    for (; j < ARRAYSIZE_UNSAFE(cases[i].matches); ++j)
+      EXPECT_EQ(kNotApplicable, cases[i].matches[j]) <<
+          "Case # " << i << " " << description;
+  }
+}
+
 // Verifies suggest relevance behavior for URL input.
 TEST_F(SearchProviderTest, DefaultProviderSuggestRelevanceScoringUrlInput) {
   struct {
@@ -1929,7 +2041,8 @@ TEST_F(SearchProviderTest, NavigationInline) {
     QueryForInput(ASCIIToUTF16(cases[i].input), false, false);
     AutocompleteMatch match(
         provider_->NavigationToMatch(SearchProvider::NavigationResult(
-            *provider_.get(), GURL(cases[i].url), string16(), false, 0)));
+            *provider_.get(), GURL(cases[i].url), string16(), false, 0,
+            false)));
     EXPECT_EQ(cases[i].inline_offset, match.inline_autocomplete_offset);
     EXPECT_EQ(ASCIIToUTF16(cases[i].fill_into_edit), match.fill_into_edit);
   }
@@ -1940,7 +2053,7 @@ TEST_F(SearchProviderTest, NavigationInlineSchemeSubstring) {
   const string16 input(ASCIIToUTF16("ht"));
   const string16 url(ASCIIToUTF16("http://a.com"));
   const SearchProvider::NavigationResult result(
-      *provider_.get(), GURL(url), string16(), false, 0);
+      *provider_.get(), GURL(url), string16(), false, 0, false);
 
   // Check the offset and strings when inline autocompletion is allowed.
   QueryForInput(input, false, false);
@@ -1962,7 +2075,8 @@ TEST_F(SearchProviderTest, NavigationInlineDomainClassify) {
   QueryForInput(ASCIIToUTF16("w"), false, false);
   AutocompleteMatch match(
       provider_->NavigationToMatch(SearchProvider::NavigationResult(
-          *provider_.get(), GURL("http://www.wow.com"), string16(), false, 0)));
+          *provider_.get(), GURL("http://www.wow.com"), string16(), false, 0,
+          false)));
   EXPECT_EQ(5U, match.inline_autocomplete_offset);
   EXPECT_EQ(ASCIIToUTF16("www.wow.com"), match.fill_into_edit);
   EXPECT_EQ(ASCIIToUTF16("www.wow.com"), match.contents);
@@ -2124,11 +2238,12 @@ TEST_F(SearchProviderTest, RemoveStaleResultsTest) {
         provider_->default_results_.navigation_results.push_back(
             SearchProvider::NavigationResult(
                 *provider_.get(), GURL(suggestion), string16(), false,
-                cases[i].results[j].relevance));
+                cases[i].results[j].relevance, false));
       } else {
         provider_->default_results_.suggest_results.push_back(
             SearchProvider::SuggestResult(ASCIIToUTF16(suggestion), false,
-                                          cases[i].results[j].relevance));
+                                          cases[i].results[j].relevance,
+                                          false));
       }
     }
 
diff --git a/chrome/browser/autocomplete/zero_suggest_provider.cc b/chrome/browser/autocomplete/zero_suggest_provider.cc
index a1927ec..09296a1 100644
--- a/chrome/browser/autocomplete/zero_suggest_provider.cc
+++ b/chrome/browser/autocomplete/zero_suggest_provider.cc
@@ -285,11 +285,11 @@ void ZeroSuggestProvider::FillResults(
         if (descriptions != NULL)
           descriptions->GetString(index, &title);
         navigation_results->push_back(SearchProvider::NavigationResult(
-            *this, url, title, false, relevance));
+            *this, url, title, false, relevance, relevances != NULL));
       }
     } else {
       suggest_results->push_back(SearchProvider::SuggestResult(
-          result, false, relevance));
+          result, false, relevance, relevances != NULL));
     }
   }
 }