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