chrome/browser/autocomplete/search_provider.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/autocomplete/search_provider.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9
  10 #include "base/base64.h"
  11 #include "base/callback.h"
  12 #include "base/command_line.h"
  13 #include "base/i18n/break_iterator.h"
  14 #include "base/i18n/case_conversion.h"
  15 #include "base/json/json_string_value_serializer.h"
  16 #include "base/message_loop/message_loop.h"
  17 #include "base/metrics/histogram.h"
  18 #include "base/prefs/pref_service.h"
  19 #include "base/rand_util.h"
  20 #include "base/strings/string_util.h"
  21 #include "base/strings/utf_string_conversions.h"
  22 #include "chrome/browser/autocomplete/autocomplete_classifier.h"
  23 #include "chrome/browser/autocomplete/autocomplete_classifier_factory.h"
  24 #include "chrome/browser/autocomplete/autocomplete_provider_listener.h"
  25 #include "chrome/browser/autocomplete/autocomplete_result.h"
  26 #include "chrome/browser/autocomplete/keyword_provider.h"
  27 #include "chrome/browser/autocomplete/url_prefix.h"
  28 #include "chrome/browser/google/google_util.h"
  29 #include "chrome/browser/history/history_service.h"
  30 #include "chrome/browser/history/history_service_factory.h"
  31 #include "chrome/browser/history/in_memory_database.h"
  32 #include "chrome/browser/metrics/variations/variations_http_header_provider.h"
  33 #include "chrome/browser/omnibox/omnibox_field_trial.h"
  34 #include "chrome/browser/profiles/profile.h"
  35 #include "chrome/browser/search/search.h"
  36 #include "chrome/browser/search_engines/template_url_prepopulate_data.h"
  37 #include "chrome/browser/search_engines/template_url_service.h"
  38 #include "chrome/browser/search_engines/template_url_service_factory.h"
  39 #include "chrome/browser/ui/search/instant_controller.h"
  40 #include "chrome/common/chrome_switches.h"
  41 #include "chrome/common/pref_names.h"
  42 #include "chrome/common/url_constants.h"
  43 #include "content/public/browser/user_metrics.h"
  44 #include "grit/generated_resources.h"
  45 #include "net/base/escape.h"
  46 #include "net/base/load_flags.h"
  47 #include "net/base/net_util.h"
  48 #include "net/http/http_request_headers.h"
  49 #include "net/url_request/url_fetcher.h"
  50 #include "net/url_request/url_request_status.h"
  51 #include "ui/base/l10n/l10n_util.h"
  52 #include "url/url_util.h"
  53
  54 // Helpers --------------------------------------------------------------------
  55
  56 namespace {
  57
  58 // We keep track in a histogram how many suggest requests we send, how
  59 // many suggest requests we invalidate (e.g., due to a user typing
  60 // another character), and how many replies we receive.
  61 // *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! ***
  62 //     (excluding the end-of-list enum value)
  63 // We do not want values of existing enums to change or else it screws
  64 // up the statistics.
  65 enum SuggestRequestsHistogramValue {
  66   REQUEST_SENT = 1,
  67   REQUEST_INVALIDATED,
  68   REPLY_RECEIVED,
  69   MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE
  70 };
  71
  72 // The verbatim score for an input which is not an URL.
  73 const int kNonURLVerbatimRelevance = 1300;
  74
  75 // Increments the appropriate value in the histogram by one.
  76 void LogOmniboxSuggestRequest(
  77     SuggestRequestsHistogramValue request_value) {
  78   UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value,
  79                             MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE);
  80 }
  81
  82 bool HasMultipleWords(const base::string16& text) {
  83   base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD);
  84   bool found_word = false;
  85   if (i.Init()) {
  86     while (i.Advance()) {
  87       if (i.IsWord()) {
  88         if (found_word)
  89           return true;
  90         found_word = true;
  91       }
  92     }
  93   }
  94   return false;
  95 }
  96
  97 }  // namespace
  98
  99 // SearchProvider::Providers --------------------------------------------------
 100
 101 SearchProvider::Providers::Providers(TemplateURLService* template_url_service)
 102     : template_url_service_(template_url_service) {}
 103
 104 const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const {
 105   return default_provider_.empty() ? NULL :
 106       template_url_service_->GetTemplateURLForKeyword(default_provider_);
 107 }
 108
 109 const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
 110   return keyword_provider_.empty() ? NULL :
 111       template_url_service_->GetTemplateURLForKeyword(keyword_provider_);
 112 }
 113
 114
 115 // SearchProvider::CompareScoredResults ---------------------------------------
 116
 117 class SearchProvider::CompareScoredResults {
 118  public:
 119   bool operator()(const Result& a, const Result& b) {
 120     // Sort in descending relevance order.
 121     return a.relevance() > b.relevance();
 122   }
 123 };
 124
 125
 126 // SearchProvider -------------------------------------------------------------
 127
 128 // static
 129 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
 130
 131 SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
 132                                Profile* profile)
 133     : BaseSearchProvider(listener, profile, AutocompleteProvider::TYPE_SEARCH),
 134       providers_(TemplateURLServiceFactory::GetForProfile(profile)) {
 135 }
 136
 137 // static
 138 std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) {
 139   return match.GetAdditionalInfo(kSuggestMetadataKey);
 140 }
 141
 142 void SearchProvider::ResetSession() {
 143   field_trial_triggered_in_session_ = false;
 144 }
 145
 146 SearchProvider::~SearchProvider() {
 147 }
 148
 149 void SearchProvider::UpdateMatchContentsClass(const base::string16& input_text,
 150                                               Results* results) {
 151   for (SuggestResults::iterator sug_it = results->suggest_results.begin();
 152        sug_it != results->suggest_results.end(); ++sug_it) {
 153     sug_it->ClassifyMatchContents(false, input_text);
 154   }
 155   const std::string languages(
 156       profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
 157   for (NavigationResults::iterator nav_it = results->navigation_results.begin();
 158        nav_it != results->navigation_results.end(); ++nav_it) {
 159     nav_it->CalculateAndClassifyMatchContents(false, input_text, languages);
 160   }
 161 }
 162
 163 // static
 164 int SearchProvider::CalculateRelevanceForKeywordVerbatim(
 165     AutocompleteInput::Type type,
 166     bool prefer_keyword) {
 167   // This function is responsible for scoring verbatim query matches
 168   // for non-extension keywords.  KeywordProvider::CalculateRelevance()
 169   // scores verbatim query matches for extension keywords, as well as
 170   // for keyword matches (i.e., suggestions of a keyword itself, not a
 171   // suggestion of a query on a keyword search engine).  These two
 172   // functions are currently in sync, but there's no reason we
 173   // couldn't decide in the future to score verbatim matches
 174   // differently for extension and non-extension keywords.  If you
 175   // make such a change, however, you should update this comment to
 176   // describe it, so it's clear why the functions diverge.
 177   if (prefer_keyword)
 178     return 1500;
 179   return (type == AutocompleteInput::QUERY) ? 1450 : 1100;
 180 }
 181
 182 void SearchProvider::Start(const AutocompleteInput& input,
 183                            bool minimal_changes) {
 184   // Do our best to load the model as early as possible.  This will reduce
 185   // odds of having the model not ready when really needed (a non-empty input).
 186   TemplateURLService* model = providers_.template_url_service();
 187   DCHECK(model);
 188   model->Load();
 189
 190   matches_.clear();
 191   field_trial_triggered_ = false;
 192
 193   // Can't return search/suggest results for bogus input or without a profile.
 194   if (!profile_ || (input.type() == AutocompleteInput::INVALID)) {
 195     Stop(true);
 196     return;
 197   }
 198
 199   keyword_input_ = input;
 200   const TemplateURL* keyword_provider =
 201       KeywordProvider::GetSubstitutingTemplateURLForInput(model,
 202                                                           &keyword_input_);
 203   if (keyword_provider == NULL)
 204     keyword_input_.Clear();
 205   else if (keyword_input_.text().empty())
 206     keyword_provider = NULL;
 207
 208   const TemplateURL* default_provider = model->GetDefaultSearchProvider();
 209   if (default_provider && !default_provider->SupportsReplacement())
 210     default_provider = NULL;
 211
 212   if (keyword_provider == default_provider)
 213     default_provider = NULL;  // No use in querying the same provider twice.
 214
 215   if (!default_provider && !keyword_provider) {
 216     // No valid providers.
 217     Stop(true);
 218     return;
 219   }
 220
 221   // If we're still running an old query but have since changed the query text
 222   // or the providers, abort the query.
 223   base::string16 default_provider_keyword(default_provider ?
 224       default_provider->keyword() : base::string16());
 225   base::string16 keyword_provider_keyword(keyword_provider ?
 226       keyword_provider->keyword() : base::string16());
 227   if (!minimal_changes ||
 228       !providers_.equal(default_provider_keyword, keyword_provider_keyword)) {
 229     // Cancel any in-flight suggest requests.
 230     if (!done_)
 231       Stop(false);
 232   }
 233
 234   providers_.set(default_provider_keyword, keyword_provider_keyword);
 235
 236   if (input.text().empty()) {
 237     // User typed "?" alone.  Give them a placeholder result indicating what
 238     // this syntax does.
 239     if (default_provider) {
 240       AutocompleteMatch match;
 241       match.provider = this;
 242       match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
 243       match.contents_class.push_back(
 244           ACMatchClassification(0, ACMatchClassification::NONE));
 245       match.keyword = providers_.default_provider();
 246       match.allowed_to_be_default_match = true;
 247       matches_.push_back(match);
 248     }
 249     Stop(true);
 250     return;
 251   }
 252
 253   input_ = input;
 254
 255   DoHistoryQuery(minimal_changes);
 256   StartOrStopSuggestQuery(minimal_changes);
 257   UpdateMatches();
 258 }
 259
 260 void SearchProvider::SortResults(bool is_keyword,
 261                                  const base::ListValue* relevances,
 262                                  Results* results) {
 263   // Ignore suggested scores for non-keyword matches in keyword mode; if the
 264   // server is allowed to score these, it could interfere with the user's
 265   // ability to get good keyword results.
 266   const bool abandon_suggested_scores =
 267       !is_keyword && !providers_.keyword_provider().empty();
 268   // Apply calculated relevance scores to suggestions if a valid list was
 269   // not provided or we're abandoning suggested scores entirely.
 270   if ((relevances == NULL) || abandon_suggested_scores) {
 271     ApplyCalculatedSuggestRelevance(&results->suggest_results);
 272     ApplyCalculatedNavigationRelevance(&results->navigation_results);
 273     // If abandoning scores entirely, also abandon the verbatim score.
 274     if (abandon_suggested_scores)
 275       results->verbatim_relevance = -1;
 276   }
 277
 278   // Keep the result lists sorted.
 279   const CompareScoredResults comparator = CompareScoredResults();
 280   std::stable_sort(results->suggest_results.begin(),
 281                    results->suggest_results.end(),
 282                    comparator);
 283   std::stable_sort(results->navigation_results.begin(),
 284                    results->navigation_results.end(),
 285                    comparator);
 286 }
 287
 288 const TemplateURL* SearchProvider::GetTemplateURL(bool is_keyword) const {
 289   return is_keyword ? providers_.GetKeywordProviderURL()
 290                     : providers_.GetDefaultProviderURL();
 291 }
 292
 293 const AutocompleteInput SearchProvider::GetInput(bool is_keyword) const {
 294   return is_keyword ? keyword_input_ : input_;
 295 }
 296
 297 BaseSearchProvider::Results* SearchProvider::GetResultsToFill(bool is_keyword) {
 298   return is_keyword ? &keyword_results_ : &default_results_;
 299 }
 300
 301 bool SearchProvider::ShouldAppendExtraParams(
 302     const SuggestResult& result) const {
 303   return !result.from_keyword_provider() ||
 304       providers_.default_provider().empty();
 305 }
 306
 307 void SearchProvider::StopSuggest() {
 308   // Increment the appropriate field in the histogram by the number of
 309   // pending requests that were invalidated.
 310   for (int i = 0; i < suggest_results_pending_; ++i)
 311     LogOmniboxSuggestRequest(REQUEST_INVALIDATED);
 312   suggest_results_pending_ = 0;
 313   timer_.Stop();
 314   // Stop any in-progress URL fetches.
 315   keyword_fetcher_.reset();
 316   default_fetcher_.reset();
 317 }
 318
 319 void SearchProvider::ClearAllResults() {
 320   keyword_results_.Clear();
 321   default_results_.Clear();
 322 }
 323
 324 int SearchProvider::GetDefaultResultRelevance() const {
 325   return -1;
 326 }
 327
 328 void SearchProvider::RecordDeletionResult(bool success) {
 329   if (success) {
 330     content::RecordAction(
 331         base::UserMetricsAction("Omnibox.ServerSuggestDelete.Success"));
 332   } else {
 333     content::RecordAction(
 334         base::UserMetricsAction("Omnibox.ServerSuggestDelete.Failure"));
 335   }
 336 }
 337
 338 void SearchProvider::LogFetchComplete(bool success, bool is_keyword) {
 339   LogOmniboxSuggestRequest(REPLY_RECEIVED);
 340   // Record response time for suggest requests sent to Google.  We care
 341   // only about the common case: the Google default provider used in
 342   // non-keyword mode.
 343   const TemplateURL* default_url = providers_.GetDefaultProviderURL();
 344   if (!is_keyword && default_url &&
 345       (TemplateURLPrepopulateData::GetEngineType(*default_url) ==
 346        SEARCH_ENGINE_GOOGLE)) {
 347     const base::TimeDelta elapsed_time =
 348         base::TimeTicks::Now() - time_suggest_request_sent_;
 349     if (success) {
 350       UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
 351                           elapsed_time);
 352     } else {
 353       UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
 354                           elapsed_time);
 355     }
 356   }
 357 }
 358
 359 bool SearchProvider::IsKeywordFetcher(const net::URLFetcher* fetcher) const {
 360   return fetcher == keyword_fetcher_.get();
 361 }
 362
 363 void SearchProvider::UpdateMatches() {
 364   ConvertResultsToAutocompleteMatches();
 365
 366   // Check constraints that may be violated by suggested relevances.
 367   if (!matches_.empty() &&
 368       (default_results_.HasServerProvidedScores() ||
 369        keyword_results_.HasServerProvidedScores())) {
 370     // These blocks attempt to repair undesirable behavior by suggested
 371     // relevances with minimal impact, preserving other suggested relevances.
 372
 373     if (!HasKeywordDefaultMatchInKeywordMode()) {
 374       // In keyword mode, disregard the keyword verbatim suggested relevance
 375       // if necessary so there at least one keyword match that's allowed to
 376       // be the default match.
 377       keyword_results_.verbatim_relevance = -1;
 378       ConvertResultsToAutocompleteMatches();
 379     }
 380     if (IsTopMatchSearchWithURLInput()) {
 381       // Disregard the suggested search and verbatim relevances if the input
 382       // type is URL and the top match is a highly-ranked search suggestion.
 383       // For example, prevent a search for "foo.com" from outranking another
 384       // provider's navigation for "foo.com" or "foo.com/url_from_history".
 385       ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
 386       ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
 387       default_results_.verbatim_relevance = -1;
 388       keyword_results_.verbatim_relevance = -1;
 389       ConvertResultsToAutocompleteMatches();
 390     }
 391     if (FindTopMatch() == matches_.end()) {
 392       // Guarantee that SearchProvider returns a legal default match.  (The
 393       // omnibox always needs at least one legal default match, and it relies
 394       // on SearchProvider to always return one.)
 395       ApplyCalculatedRelevance();
 396       ConvertResultsToAutocompleteMatches();
 397     }
 398     DCHECK(HasKeywordDefaultMatchInKeywordMode());
 399     DCHECK(!IsTopMatchSearchWithURLInput());
 400     DCHECK(FindTopMatch() != matches_.end());
 401   }
 402   UMA_HISTOGRAM_CUSTOM_COUNTS(
 403       "Omnibox.SearchProviderMatches", matches_.size(), 1, 6, 7);
 404
 405   const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
 406   if ((keyword_url != NULL) && HasKeywordDefaultMatchInKeywordMode()) {
 407     // If there is a keyword match that is allowed to be the default match,
 408     // then prohibit default provider matches from being the default match lest
 409     // such matches cause the user to break out of keyword mode.
 410     for (ACMatches::iterator it = matches_.begin(); it != matches_.end();
 411          ++it) {
 412       if (it->keyword != keyword_url->keyword())
 413         it->allowed_to_be_default_match = false;
 414     }
 415   }
 416
 417   base::TimeTicks update_starred_start_time(base::TimeTicks::Now());
 418   UpdateStarredStateOfMatches();
 419   UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateStarredTime",
 420                       base::TimeTicks::Now() - update_starred_start_time);
 421   UpdateDone();
 422 }
 423
 424 void SearchProvider::Run() {
 425   // Start a new request with the current input.
 426   suggest_results_pending_ = 0;
 427   time_suggest_request_sent_ = base::TimeTicks::Now();
 428
 429   default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
 430       providers_.GetDefaultProviderURL(), input_));
 431   keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID,
 432       providers_.GetKeywordProviderURL(), keyword_input_));
 433
 434   // Both the above can fail if the providers have been modified or deleted
 435   // since the query began.
 436   if (suggest_results_pending_ == 0) {
 437     UpdateDone();
 438     // We only need to update the listener if we're actually done.
 439     if (done_)
 440       listener_->OnProviderUpdate(false);
 441   }
 442 }
 443
 444 void SearchProvider::DoHistoryQuery(bool minimal_changes) {
 445   // The history query results are synchronous, so if minimal_changes is true,
 446   // we still have the last results and don't need to do anything.
 447   if (minimal_changes)
 448     return;
 449
 450   keyword_history_results_.clear();
 451   default_history_results_.clear();
 452
 453   if (OmniboxFieldTrial::SearchHistoryDisable(
 454       input_.current_page_classification()))
 455     return;
 456
 457   HistoryService* const history_service =
 458       HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
 459   history::URLDatabase* url_db = history_service ?
 460       history_service->InMemoryDatabase() : NULL;
 461   if (!url_db)
 462     return;
 463
 464   // Request history for both the keyword and default provider.  We grab many
 465   // more matches than we'll ultimately clamp to so that if there are several
 466   // recent multi-word matches who scores are lowered (see
 467   // AddHistoryResultsToMap()), they won't crowd out older, higher-scoring
 468   // matches.  Note that this doesn't fix the problem entirely, but merely
 469   // limits it to cases with a very large number of such multi-word matches; for
 470   // now, this seems OK compared with the complexity of a real fix, which would
 471   // require multiple searches and tracking of "single- vs. multi-word" in the
 472   // database.
 473   int num_matches = kMaxMatches * 5;
 474   const TemplateURL* default_url = providers_.GetDefaultProviderURL();
 475   if (default_url) {
 476     const base::TimeTicks start_time = base::TimeTicks::Now();
 477     url_db->GetMostRecentKeywordSearchTerms(default_url->id(), input_.text(),
 478         num_matches, &default_history_results_);
 479     UMA_HISTOGRAM_TIMES(
 480         "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime",
 481         base::TimeTicks::Now() - start_time);
 482   }
 483   const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
 484   if (keyword_url) {
 485     url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(),
 486         keyword_input_.text(), num_matches, &keyword_history_results_);
 487   }
 488 }
 489
 490 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
 491   if (!IsQuerySuitableForSuggest()) {
 492     StopSuggest();
 493     ClearAllResults();
 494     return;
 495   }
 496
 497   // For the minimal_changes case, if we finished the previous query and still
 498   // have its results, or are allowed to keep running it, just do that, rather
 499   // than starting a new query.
 500   if (minimal_changes &&
 501       (!default_results_.suggest_results.empty() ||
 502        !default_results_.navigation_results.empty() ||
 503        !keyword_results_.suggest_results.empty() ||
 504        !keyword_results_.navigation_results.empty() ||
 505        (!done_ && input_.want_asynchronous_matches())))
 506     return;
 507
 508   // We can't keep running any previous query, so halt it.
 509   StopSuggest();
 510
 511   // Remove existing results that cannot inline autocomplete the new input.
 512   RemoveAllStaleResults();
 513
 514   // Update the content classifications of remaining results so they look good
 515   // against the current input.
 516   UpdateMatchContentsClass(input_.text(), &default_results_);
 517   if (!keyword_input_.text().empty())
 518     UpdateMatchContentsClass(keyword_input_.text(), &keyword_results_);
 519
 520   // We can't start a new query if we're only allowed synchronous results.
 521   if (!input_.want_asynchronous_matches())
 522     return;
 523
 524   // To avoid flooding the suggest server, don't send a query until at
 525   // least 100 ms since the last query.
 526   base::TimeTicks next_suggest_time(time_suggest_request_sent_ +
 527       base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs));
 528   base::TimeTicks now(base::TimeTicks::Now());
 529   if (now >= next_suggest_time) {
 530     Run();
 531     return;
 532   }
 533   timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run);
 534 }
 535
 536 bool SearchProvider::IsQuerySuitableForSuggest() const {
 537   // Don't run Suggest in incognito mode, if the engine doesn't support it, or
 538   // if the user has disabled it.
 539   const TemplateURL* default_url = providers_.GetDefaultProviderURL();
 540   const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
 541   if (profile_->IsOffTheRecord() ||
 542       ((!default_url || default_url->suggestions_url().empty()) &&
 543        (!keyword_url || keyword_url->suggestions_url().empty())) ||
 544       !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled))
 545     return false;
 546
 547   // If the input type might be a URL, we take extra care so that private data
 548   // isn't sent to the server.
 549
 550   // FORCED_QUERY means the user is explicitly asking us to search for this, so
 551   // we assume it isn't a URL and/or there isn't private data.
 552   if (input_.type() == AutocompleteInput::FORCED_QUERY)
 553     return true;
 554
 555   // Next we check the scheme.  If this is UNKNOWN/URL with a scheme that isn't
 556   // http/https/ftp, we shouldn't send it.  Sending things like file: and data:
 557   // is both a waste of time and a disclosure of potentially private, local
 558   // data.  Other "schemes" may actually be usernames, and we don't want to send
 559   // passwords.  If the scheme is OK, we still need to check other cases below.
 560   // If this is QUERY, then the presence of these schemes means the user
 561   // explicitly typed one, and thus this is probably a URL that's being entered
 562   // and happens to currently be invalid -- in which case we again want to run
 563   // our checks below.  Other QUERY cases are less likely to be URLs and thus we
 564   // assume we're OK.
 565   if (!LowerCaseEqualsASCII(input_.scheme(), url::kHttpScheme) &&
 566       !LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) &&
 567       !LowerCaseEqualsASCII(input_.scheme(), content::kFtpScheme))
 568     return (input_.type() == AutocompleteInput::QUERY);
 569
 570   // Don't send URLs with usernames, queries or refs.  Some of these are
 571   // private, and the Suggest server is unlikely to have any useful results
 572   // for any of them.  Also don't send URLs with ports, as we may initially
 573   // think that a username + password is a host + port (and we don't want to
 574   // send usernames/passwords), and even if the port really is a port, the
 575   // server is once again unlikely to have and useful results.
 576   // Note that we only block based on refs if the input is URL-typed, as search
 577   // queries can legitimately have #s in them which the URL parser
 578   // overaggressively categorizes as a url with a ref.
 579   const url::Parsed& parts = input_.parts();
 580   if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
 581       parts.query.is_nonempty() ||
 582       (parts.ref.is_nonempty() && (input_.type() == AutocompleteInput::URL)))
 583     return false;
 584
 585   // Don't send anything for https except the hostname.  Hostnames are OK
 586   // because they are visible when the TCP connection is established, but the
 587   // specific path may reveal private information.
 588   if (LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) &&
 589       parts.path.is_nonempty())
 590     return false;
 591
 592   return true;
 593 }
 594
 595 void SearchProvider::RemoveAllStaleResults() {
 596   if (keyword_input_.text().empty()) {
 597     // User is either in keyword mode with a blank input or out of
 598     // keyword mode entirely.
 599     keyword_results_.Clear();
 600   }
 601 }
 602
 603 void SearchProvider::ApplyCalculatedRelevance() {
 604   ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
 605   ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
 606   ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
 607   ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
 608   default_results_.verbatim_relevance = -1;
 609   keyword_results_.verbatim_relevance = -1;
 610 }
 611
 612 void SearchProvider::ApplyCalculatedSuggestRelevance(SuggestResults* list) {
 613   for (size_t i = 0; i < list->size(); ++i) {
 614     SuggestResult& result = (*list)[i];
 615     result.set_relevance(
 616         result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
 617         (list->size() - i - 1));
 618     result.set_relevance_from_server(false);
 619   }
 620 }
 621
 622 void SearchProvider::ApplyCalculatedNavigationRelevance(
 623     NavigationResults* list) {
 624   for (size_t i = 0; i < list->size(); ++i) {
 625     NavigationResult& result = (*list)[i];
 626     result.set_relevance(
 627         result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
 628         (list->size() - i - 1));
 629     result.set_relevance_from_server(false);
 630   }
 631 }
 632
 633 net::URLFetcher* SearchProvider::CreateSuggestFetcher(
 634     int id,
 635     const TemplateURL* template_url,
 636     const AutocompleteInput& input) {
 637   if (!template_url || template_url->suggestions_url().empty())
 638     return NULL;
 639
 640   // Bail if the suggestion URL is invalid with the given replacements.
 641   TemplateURLRef::SearchTermsArgs search_term_args(input.text());
 642   search_term_args.cursor_position = input.cursor_position();
 643   search_term_args.page_classification = input.current_page_classification();
 644   if (CommandLine::ForCurrentProcess()->HasSwitch(
 645           switches::kEnableAnswersInSuggest))
 646     search_term_args.session_token = GetSessionToken();
 647   GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
 648       search_term_args));
 649   if (!suggest_url.is_valid())
 650     return NULL;
 651   // Send the current page URL if user setting and URL requirements are met and
 652   // the user is in the field trial.
 653   if (CanSendURL(current_page_url_, suggest_url, template_url,
 654                  input.current_page_classification(), profile_) &&
 655       OmniboxFieldTrial::InZeroSuggestAfterTypingFieldTrial()) {
 656     search_term_args.current_page_url = current_page_url_.spec();
 657     // Create the suggest URL again with the current page URL.
 658     suggest_url = GURL(template_url->suggestions_url_ref().ReplaceSearchTerms(
 659         search_term_args));
 660   }
 661
 662   suggest_results_pending_++;
 663   LogOmniboxSuggestRequest(REQUEST_SENT);
 664
 665   net::URLFetcher* fetcher =
 666       net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this);
 667   fetcher->SetRequestContext(profile_->GetRequestContext());
 668   fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES);
 669   // Add Chrome experiment state to the request headers.
 670   net::HttpRequestHeaders headers;
 671   chrome_variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders(
 672       fetcher->GetOriginalURL(), profile_->IsOffTheRecord(), false, &headers);
 673   fetcher->SetExtraRequestHeaders(headers.ToString());
 674   fetcher->Start();
 675   return fetcher;
 676 }
 677
 678 void SearchProvider::ConvertResultsToAutocompleteMatches() {
 679   // Convert all the results to matches and add them to a map, so we can keep
 680   // the most relevant match for each result.
 681   base::TimeTicks start_time(base::TimeTicks::Now());
 682   MatchMap map;
 683   const base::Time no_time;
 684   int did_not_accept_keyword_suggestion =
 685       keyword_results_.suggest_results.empty() ?
 686       TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
 687       TemplateURLRef::NO_SUGGESTION_CHOSEN;
 688
 689   bool relevance_from_server;
 690   int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
 691   int did_not_accept_default_suggestion =
 692       default_results_.suggest_results.empty() ?
 693       TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
 694       TemplateURLRef::NO_SUGGESTION_CHOSEN;
 695   if (verbatim_relevance > 0) {
 696     const base::string16& trimmed_verbatim =
 697         base::CollapseWhitespace(input_.text(), false);
 698     SuggestResult verbatim(
 699         trimmed_verbatim, AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
 700         trimmed_verbatim, base::string16(), base::string16(), base::string16(),
 701         base::string16(), std::string(), std::string(), false,
 702         verbatim_relevance, relevance_from_server, false,
 703         trimmed_verbatim);
 704     AddMatchToMap(verbatim, std::string(), did_not_accept_default_suggestion,
 705                   false, &map);
 706   }
 707   if (!keyword_input_.text().empty()) {
 708     const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
 709     // We only create the verbatim search query match for a keyword
 710     // if it's not an extension keyword.  Extension keywords are handled
 711     // in KeywordProvider::Start().  (Extensions are complicated...)
 712     // Note: in this provider, SEARCH_OTHER_ENGINE must correspond
 713     // to the keyword verbatim search query.  Do not create other matches
 714     // of type SEARCH_OTHER_ENGINE.
 715     if (keyword_url &&
 716         (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
 717       bool keyword_relevance_from_server;
 718       const int keyword_verbatim_relevance =
 719           GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
 720       if (keyword_verbatim_relevance > 0) {
 721         const base::string16& trimmed_verbatim =
 722             base::CollapseWhitespace(keyword_input_.text(), false);
 723         SuggestResult verbatim(
 724             trimmed_verbatim, AutocompleteMatchType::SEARCH_OTHER_ENGINE,
 725             trimmed_verbatim, base::string16(), base::string16(),
 726             base::string16(), base::string16(), std::string(), std::string(),
 727             true, keyword_verbatim_relevance, keyword_relevance_from_server,
 728             false, trimmed_verbatim);
 729         AddMatchToMap(verbatim, std::string(),
 730                       did_not_accept_keyword_suggestion, false, &map);
 731       }
 732     }
 733   }
 734   AddHistoryResultsToMap(keyword_history_results_, true,
 735                          did_not_accept_keyword_suggestion, &map);
 736   AddHistoryResultsToMap(default_history_results_, false,
 737                          did_not_accept_default_suggestion, &map);
 738
 739   AddSuggestResultsToMap(keyword_results_.suggest_results,
 740                          keyword_results_.metadata, &map);
 741   AddSuggestResultsToMap(default_results_.suggest_results,
 742                          default_results_.metadata, &map);
 743
 744   ACMatches matches;
 745   for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
 746     matches.push_back(i->second);
 747
 748   AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
 749   AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
 750
 751   // Now add the most relevant matches to |matches_|.  We take up to kMaxMatches
 752   // suggest/navsuggest matches, regardless of origin.  If Instant Extended is
 753   // enabled and we have server-provided (and thus hopefully more accurate)
 754   // scores for some suggestions, we allow more of those, until we reach
 755   // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
 756   // whole popup).
 757   //
 758   // We will always return any verbatim matches, no matter how we obtained their
 759   // scores, unless we have already accepted AutocompleteResult::kMaxMatches
 760   // higher-scoring matches under the conditions above.
 761   std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
 762   matches_.clear();
 763
 764   size_t num_suggestions = 0;
 765   for (ACMatches::const_iterator i(matches.begin());
 766        (i != matches.end()) &&
 767            (matches_.size() < AutocompleteResult::kMaxMatches);
 768        ++i) {
 769     // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
 770     // verbatim result, so this condition basically means "if this match is a
 771     // suggestion of some sort".
 772     if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
 773         (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
 774       // If we've already hit the limit on non-server-scored suggestions, and
 775       // this isn't a server-scored suggestion we can add, skip it.
 776       if ((num_suggestions >= kMaxMatches) &&
 777           (!chrome::IsInstantExtendedAPIEnabled() ||
 778            (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
 779         continue;
 780       }
 781
 782       ++num_suggestions;
 783     }
 784
 785     matches_.push_back(*i);
 786   }
 787   UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime",
 788                       base::TimeTicks::Now() - start_time);
 789 }
 790
 791 ACMatches::const_iterator SearchProvider::FindTopMatch() const {
 792   ACMatches::const_iterator it = matches_.begin();
 793   while ((it != matches_.end()) && !it->allowed_to_be_default_match)
 794     ++it;
 795   return it;
 796 }
 797
 798 bool SearchProvider::HasKeywordDefaultMatchInKeywordMode() const {
 799   const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
 800   // If the user is not in keyword mode, return true to say that this
 801   // constraint is not violated.
 802   if (keyword_url == NULL)
 803     return true;
 804   for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
 805        ++it) {
 806     if ((it->keyword == keyword_url->keyword()) &&
 807         it->allowed_to_be_default_match)
 808       return true;
 809   }
 810   return false;
 811 }
 812
 813 bool SearchProvider::IsTopMatchSearchWithURLInput() const {
 814   ACMatches::const_iterator first_match = FindTopMatch();
 815   return (input_.type() == AutocompleteInput::URL) &&
 816       (first_match != matches_.end()) &&
 817       (first_match->relevance > CalculateRelevanceForVerbatim()) &&
 818       (first_match->type != AutocompleteMatchType::NAVSUGGEST) &&
 819       (first_match->type != AutocompleteMatchType::NAVSUGGEST_PERSONALIZED);
 820 }
 821
 822 void SearchProvider::AddNavigationResultsToMatches(
 823     const NavigationResults& navigation_results,
 824     ACMatches* matches) {
 825   for (NavigationResults::const_iterator it = navigation_results.begin();
 826         it != navigation_results.end(); ++it) {
 827     matches->push_back(NavigationToMatch(*it));
 828     // In the absence of suggested relevance scores, use only the single
 829     // highest-scoring result.  (The results are already sorted by relevance.)
 830     if (!it->relevance_from_server())
 831       return;
 832   }
 833 }
 834
 835 void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
 836                                             bool is_keyword,
 837                                             int did_not_accept_suggestion,
 838                                             MatchMap* map) {
 839   if (results.empty())
 840     return;
 841
 842   base::TimeTicks start_time(base::TimeTicks::Now());
 843   bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() ||
 844       (input_.type() == AutocompleteInput::URL);
 845   const base::string16& input_text =
 846       is_keyword ? keyword_input_.text() : input_.text();
 847   bool input_multiple_words = HasMultipleWords(input_text);
 848
 849   SuggestResults scored_results;
 850   if (!prevent_inline_autocomplete && input_multiple_words) {
 851     // ScoreHistoryResults() allows autocompletion of multi-word, 1-visit
 852     // queries if the input also has multiple words.  But if we were already
 853     // scoring a multi-word, multi-visit query aggressively, and the current
 854     // input is still a prefix of it, then changing the suggestion suddenly
 855     // feels wrong.  To detect this case, first score as if only one word has
 856     // been typed, then check if the best result came from aggressive search
 857     // history scoring.  If it did, then just keep that score set.  This
 858     // 1200 the lowest possible score in CalculateRelevanceForHistory()'s
 859     // aggressive-scoring curve.
 860     scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
 861                                          false, input_text, is_keyword);
 862     if ((scored_results.front().relevance() < 1200) ||
 863         !HasMultipleWords(scored_results.front().suggestion()))
 864       scored_results.clear();  // Didn't detect the case above, score normally.
 865   }
 866   if (scored_results.empty())
 867     scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
 868                                          input_multiple_words, input_text,
 869                                          is_keyword);
 870   for (SuggestResults::const_iterator i(scored_results.begin());
 871        i != scored_results.end(); ++i) {
 872     AddMatchToMap(*i, std::string(), did_not_accept_suggestion, true, map);
 873   }
 874   UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime",
 875                       base::TimeTicks::Now() - start_time);
 876 }
 877
 878 SearchProvider::SuggestResults SearchProvider::ScoreHistoryResults(
 879     const HistoryResults& results,
 880     bool base_prevent_inline_autocomplete,
 881     bool input_multiple_words,
 882     const base::string16& input_text,
 883     bool is_keyword) {
 884   AutocompleteClassifier* classifier =
 885       AutocompleteClassifierFactory::GetForProfile(profile_);
 886   SuggestResults scored_results;
 887   const bool prevent_search_history_inlining =
 888       OmniboxFieldTrial::SearchHistoryPreventInlining(
 889           input_.current_page_classification());
 890   const base::string16& trimmed_input =
 891       base::CollapseWhitespace(input_text, false);
 892   for (HistoryResults::const_iterator i(results.begin()); i != results.end();
 893        ++i) {
 894     const base::string16& trimmed_suggestion =
 895         base::CollapseWhitespace(i->term, false);
 896
 897     // Don't autocomplete multi-word queries that have only been seen once
 898     // unless the user has typed more than one word.
 899     bool prevent_inline_autocomplete = base_prevent_inline_autocomplete ||
 900         (!input_multiple_words && (i->visits < 2) &&
 901          HasMultipleWords(trimmed_suggestion));
 902
 903     // Don't autocomplete search terms that would normally be treated as URLs
 904     // when typed. For example, if the user searched for "google.com" and types
 905     // "goog", don't autocomplete to the search term "google.com". Otherwise,
 906     // the input will look like a URL but act like a search, which is confusing.
 907     // NOTE: We don't check this in the following cases:
 908     //  * When inline autocomplete is disabled, we won't be inline
 909     //    autocompleting this term, so we don't need to worry about confusion as
 910     //    much.  This also prevents calling Classify() again from inside the
 911     //    classifier (which will corrupt state and likely crash), since the
 912     //    classifier always disables inline autocomplete.
 913     //  * When the user has typed the whole term, the "what you typed" history
 914     //    match will outrank us for URL-like inputs anyway, so we need not do
 915     //    anything special.
 916     if (!prevent_inline_autocomplete && classifier &&
 917         (trimmed_suggestion != trimmed_input)) {
 918       AutocompleteMatch match;
 919       classifier->Classify(trimmed_suggestion, false, false,
 920                            input_.current_page_classification(), &match, NULL);
 921       prevent_inline_autocomplete =
 922           !AutocompleteMatch::IsSearchType(match.type);
 923     }
 924
 925     int relevance = CalculateRelevanceForHistory(
 926         i->time, is_keyword, !prevent_inline_autocomplete,
 927         prevent_search_history_inlining);
 928     scored_results.push_back(SuggestResult(
 929         trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY,
 930         trimmed_suggestion, base::string16(), base::string16(),
 931         base::string16(), base::string16(), std::string(), std::string(),
 932         is_keyword, relevance, false, false, trimmed_input));
 933   }
 934
 935   // History returns results sorted for us.  However, we may have docked some
 936   // results' scores, so things are no longer in order.  Do a stable sort to get
 937   // things back in order without otherwise disturbing results with equal
 938   // scores, then force the scores to be unique, so that the order in which
 939   // they're shown is deterministic.
 940   std::stable_sort(scored_results.begin(), scored_results.end(),
 941                    CompareScoredResults());
 942   int last_relevance = 0;
 943   for (SuggestResults::iterator i(scored_results.begin());
 944        i != scored_results.end(); ++i) {
 945     if ((i != scored_results.begin()) && (i->relevance() >= last_relevance))
 946       i->set_relevance(last_relevance - 1);
 947     last_relevance = i->relevance();
 948   }
 949
 950   return scored_results;
 951 }
 952
 953 void SearchProvider::AddSuggestResultsToMap(const SuggestResults& results,
 954                                             const std::string& metadata,
 955                                             MatchMap* map) {
 956   for (size_t i = 0; i < results.size(); ++i)
 957     AddMatchToMap(results[i], metadata, i, false, map);
 958 }
 959
 960 int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
 961   // Use the suggested verbatim relevance score if it is non-negative (valid),
 962   // if inline autocomplete isn't prevented (always show verbatim on backspace),
 963   // and if it won't suppress verbatim, leaving no default provider matches.
 964   // Otherwise, if the default provider returned no matches and was still able
 965   // to suppress verbatim, the user would have no search/nav matches and may be
 966   // left unable to search using their default provider from the omnibox.
 967   // Check for results on each verbatim calculation, as results from older
 968   // queries (on previous input) may be trimmed for failing to inline new input.
 969   bool use_server_relevance =
 970       (default_results_.verbatim_relevance >= 0) &&
 971       !input_.prevent_inline_autocomplete() &&
 972       ((default_results_.verbatim_relevance > 0) ||
 973        !default_results_.suggest_results.empty() ||
 974        !default_results_.navigation_results.empty());
 975   if (relevance_from_server)
 976     *relevance_from_server = use_server_relevance;
 977   return use_server_relevance ?
 978       default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
 979 }
 980
 981 int SearchProvider::CalculateRelevanceForVerbatim() const {
 982   if (!providers_.keyword_provider().empty())
 983     return 250;
 984   return CalculateRelevanceForVerbatimIgnoringKeywordModeState();
 985 }
 986
 987 int SearchProvider::
 988     CalculateRelevanceForVerbatimIgnoringKeywordModeState() const {
 989   switch (input_.type()) {
 990     case AutocompleteInput::UNKNOWN:
 991     case AutocompleteInput::QUERY:
 992     case AutocompleteInput::FORCED_QUERY:
 993       return kNonURLVerbatimRelevance;
 994
 995     case AutocompleteInput::URL:
 996       return 850;
 997
 998     default:
 999       NOTREACHED();
1000       return 0;
1001   }
1002 }
1003
1004 int SearchProvider::GetKeywordVerbatimRelevance(
1005     bool* relevance_from_server) const {
1006   // Use the suggested verbatim relevance score if it is non-negative (valid),
1007   // if inline autocomplete isn't prevented (always show verbatim on backspace),
1008   // and if it won't suppress verbatim, leaving no keyword provider matches.
1009   // Otherwise, if the keyword provider returned no matches and was still able
1010   // to suppress verbatim, the user would have no search/nav matches and may be
1011   // left unable to search using their keyword provider from the omnibox.
1012   // Check for results on each verbatim calculation, as results from older
1013   // queries (on previous input) may be trimmed for failing to inline new input.
1014   bool use_server_relevance =
1015       (keyword_results_.verbatim_relevance >= 0) &&
1016       !input_.prevent_inline_autocomplete() &&
1017       ((keyword_results_.verbatim_relevance > 0) ||
1018        !keyword_results_.suggest_results.empty() ||
1019        !keyword_results_.navigation_results.empty());
1020   if (relevance_from_server)
1021     *relevance_from_server = use_server_relevance;
1022   return use_server_relevance ?
1023       keyword_results_.verbatim_relevance :
1024       CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
1025                                            keyword_input_.prefer_keyword());
1026 }
1027
1028 int SearchProvider::CalculateRelevanceForHistory(
1029     const base::Time& time,
1030     bool is_keyword,
1031     bool use_aggressive_method,
1032     bool prevent_search_history_inlining) const {
1033   // The relevance of past searches falls off over time. There are two distinct
1034   // equations used. If the first equation is used (searches to the primary
1035   // provider that we want to score aggressively), the score is in the range
1036   // 1300-1599 (unless |prevent_search_history_inlining|, in which case
1037   // it's in the range 1200-1299). If the second equation is used the
1038   // relevance of a search 15 minutes ago is discounted 50 points, while the
1039   // relevance of a search two weeks ago is discounted 450 points.
1040   double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0);
1041   bool is_primary_provider = is_keyword || !providers_.has_keyword_provider();
1042   if (is_primary_provider && use_aggressive_method) {
1043     // Searches with the past two days get a different curve.
1044     const double autocomplete_time = 2 * 24 * 60 * 60;
1045     if (elapsed_time < autocomplete_time) {
1046       int max_score = is_keyword ? 1599 : 1399;
1047       if (prevent_search_history_inlining)
1048         max_score = 1299;
1049       return max_score - static_cast<int>(99 *
1050           std::pow(elapsed_time / autocomplete_time, 2.5));
1051     }
1052     elapsed_time -= autocomplete_time;
1053   }
1054
1055   const int score_discount =
1056       static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
1057
1058   // Don't let scores go below 0.  Negative relevance scores are meaningful in
1059   // a different way.
1060   int base_score;
1061   if (is_primary_provider)
1062     base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050;
1063   else
1064     base_score = 200;
1065   return std::max(0, base_score - score_discount);
1066 }
1067
1068 AutocompleteMatch SearchProvider::NavigationToMatch(
1069     const NavigationResult& navigation) {
1070   base::string16 input;
1071   const bool trimmed_whitespace = base::TrimWhitespace(
1072       navigation.from_keyword_provider() ?
1073           keyword_input_.text() : input_.text(),
1074       base::TRIM_TRAILING, &input) != base::TRIM_NONE;
1075   AutocompleteMatch match(this, navigation.relevance(), false,
1076                           navigation.type());
1077   match.destination_url = navigation.url();
1078   BaseSearchProvider::SetDeletionURL(navigation.deletion_url(), &match);
1079   // First look for the user's input inside the formatted url as it would be
1080   // without trimming the scheme, so we can find matches at the beginning of the
1081   // scheme.
1082   const URLPrefix* prefix =
1083       URLPrefix::BestURLPrefix(navigation.formatted_url(), input);
1084   size_t match_start = (prefix == NULL) ?
1085       navigation.formatted_url().find(input) : prefix->prefix.length();
1086   bool trim_http = !AutocompleteInput::HasHTTPScheme(input) &&
1087       (!prefix || (match_start != 0));
1088   const net::FormatUrlTypes format_types =
1089       net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP);
1090
1091   const std::string languages(
1092       profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
1093   size_t inline_autocomplete_offset = (prefix == NULL) ?
1094       base::string16::npos : (match_start + input.length());
1095   match.fill_into_edit +=
1096       AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url(),
1097           net::FormatUrl(navigation.url(), languages, format_types,
1098                          net::UnescapeRule::SPACES, NULL, NULL,
1099                          &inline_autocomplete_offset));
1100   // Preserve the forced query '?' prefix in |match.fill_into_edit|.
1101   // Otherwise, user edits to a suggestion would show non-Search results.
1102   if (input_.type() == AutocompleteInput::FORCED_QUERY) {
1103     match.fill_into_edit.insert(0, base::ASCIIToUTF16("?"));
1104     if (inline_autocomplete_offset != base::string16::npos)
1105       ++inline_autocomplete_offset;
1106   }
1107   if (inline_autocomplete_offset != base::string16::npos) {
1108     DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1109     match.inline_autocompletion =
1110         match.fill_into_edit.substr(inline_autocomplete_offset);
1111   }
1112   // An inlineable navsuggestion can only be the default match when there
1113   // is no keyword provider active, lest it appear first and break the user
1114   // out of keyword mode.  It can also only be default if either the inline
1115   // autocompletion is empty or we're not preventing inline autocompletion.
1116   // Finally, if we have an inlineable navsuggestion with an inline completion
1117   // that we're not preventing, make sure we didn't trim any whitespace.
1118   // We don't want to claim http://foo.com/bar is inlineable against the
1119   // input "foo.com/b ".
1120   match.allowed_to_be_default_match = navigation.IsInlineable(input) &&
1121       (providers_.GetKeywordProviderURL() == NULL) &&
1122       (match.inline_autocompletion.empty() ||
1123       (!input_.prevent_inline_autocomplete() && !trimmed_whitespace));
1124
1125   match.contents = navigation.match_contents();
1126   match.contents_class = navigation.match_contents_class();
1127   match.description = navigation.description();
1128   AutocompleteMatch::ClassifyMatchInString(input, match.description,
1129       ACMatchClassification::NONE, &match.description_class);
1130
1131   match.RecordAdditionalInfo(
1132       kRelevanceFromServerKey,
1133       navigation.relevance_from_server() ? kTrue : kFalse);
1134   match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse);
1135
1136   return match;
1137 }
1138
1139 void SearchProvider::UpdateDone() {
1140   // We're done when the timer isn't running, there are no suggest queries
1141   // pending, and we're not waiting on Instant.
1142   done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0);
1143 }
1144
1145 std::string SearchProvider::GetSessionToken() {
1146   base::TimeTicks current_time(base::TimeTicks::Now());
1147   // Renew token if it expired.
1148   if (current_time > token_expiration_time_) {
1149     const size_t kTokenBytes = 12;
1150     std::string raw_data;
1151     base::RandBytes(WriteInto(&raw_data, kTokenBytes + 1), kTokenBytes);
1152     base::Base64Encode(raw_data, &current_token_);
1153
1154     // Make the base64 encoded value URL and filename safe(see RFC 3548).
1155     std::replace(current_token_.begin(), current_token_.end(), '+', '-');
1156     std::replace(current_token_.begin(), current_token_.end(), '/', '_');
1157   }
1158
1159   // Extend expiration time another 60 seconds.
1160   token_expiration_time_ = current_time + base::TimeDelta::FromSeconds(60);
1161
1162   return current_token_;
1163 }