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/i18n/icu_string_conversions.h"
14 #include "base/json/json_string_value_serializer.h"
15 #include "base/message_loop/message_loop.h"
16 #include "base/metrics/histogram.h"
17 #include "base/prefs/pref_service.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/net/url_fixer_upper.h"
38 #include "chrome/common/pref_names.h"
39 #include "chrome/common/url_constants.h"
40 #include "content/public/browser/user_metrics.h"
41 #include "grit/generated_resources.h"
42 #include "net/base/escape.h"
43 #include "net/base/load_flags.h"
44 #include "net/base/net_util.h"
45 #include "net/http/http_request_headers.h"
46 #include "net/http/http_response_headers.h"
47 #include "net/url_request/url_fetcher.h"
48 #include "net/url_request/url_request_status.h"
49 #include "ui/base/l10n/l10n_util.h"
50 #include "url/url_util.h"
53 // Helpers --------------------------------------------------------------------
57 // We keep track in a histogram how many suggest requests we send, how
58 // many suggest requests we invalidate (e.g., due to a user typing
59 // another character), and how many replies we receive.
60 // *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! ***
61 // (excluding the end-of-list enum value)
62 // We do not want values of existing enums to change or else it screws
64 enum SuggestRequestsHistogramValue {
68 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE
71 // The verbatim score for an input which is not an URL.
72 const int kNonURLVerbatimRelevance = 1300;
74 // Increments the appropriate value in the histogram by one.
75 void LogOmniboxSuggestRequest(
76 SuggestRequestsHistogramValue request_value) {
77 UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value,
78 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE);
81 bool HasMultipleWords(const base::string16& text) {
82 base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD);
83 bool found_word = false;
96 AutocompleteMatchType::Type GetAutocompleteMatchType(const std::string& type) {
98 return AutocompleteMatchType::SEARCH_SUGGEST_ENTITY;
99 if (type == "INFINITE")
100 return AutocompleteMatchType::SEARCH_SUGGEST_INFINITE;
101 if (type == "PERSONALIZED_QUERY")
102 return AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED;
103 if (type == "PROFILE")
104 return AutocompleteMatchType::SEARCH_SUGGEST_PROFILE;
105 return AutocompleteMatchType::SEARCH_SUGGEST;
111 // SuggestionDeletionHandler -------------------------------------------------
113 // This class handles making requests to the server in order to delete
114 // personalized suggestions.
115 class SuggestionDeletionHandler : public net::URLFetcherDelegate {
117 typedef base::Callback<void(bool, SuggestionDeletionHandler*)>
118 DeletionCompletedCallback;
120 SuggestionDeletionHandler(
121 const std::string& deletion_url,
123 const DeletionCompletedCallback& callback);
125 virtual ~SuggestionDeletionHandler();
128 // net::URLFetcherDelegate:
129 virtual void OnURLFetchComplete(const net::URLFetcher* source) OVERRIDE;
131 scoped_ptr<net::URLFetcher> deletion_fetcher_;
132 DeletionCompletedCallback callback_;
134 DISALLOW_COPY_AND_ASSIGN(SuggestionDeletionHandler);
138 SuggestionDeletionHandler::SuggestionDeletionHandler(
139 const std::string& deletion_url,
141 const DeletionCompletedCallback& callback) : callback_(callback) {
142 GURL url(deletion_url);
143 DCHECK(url.is_valid());
145 deletion_fetcher_.reset(net::URLFetcher::Create(
146 SearchProvider::kDeletionURLFetcherID,
148 net::URLFetcher::GET,
150 deletion_fetcher_->SetRequestContext(profile->GetRequestContext());
151 deletion_fetcher_->Start();
154 SuggestionDeletionHandler::~SuggestionDeletionHandler() {
157 void SuggestionDeletionHandler::OnURLFetchComplete(
158 const net::URLFetcher* source) {
159 DCHECK(source == deletion_fetcher_.get());
161 source->GetStatus().is_success() && (source->GetResponseCode() == 200),
166 // SearchProvider::Providers --------------------------------------------------
168 SearchProvider::Providers::Providers(TemplateURLService* template_url_service)
169 : template_url_service_(template_url_service) {}
171 const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const {
172 return default_provider_.empty() ? NULL :
173 template_url_service_->GetTemplateURLForKeyword(default_provider_);
176 const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
177 return keyword_provider_.empty() ? NULL :
178 template_url_service_->GetTemplateURLForKeyword(keyword_provider_);
182 // SearchProvider::CompareScoredResults ---------------------------------------
184 class SearchProvider::CompareScoredResults {
186 bool operator()(const Result& a, const Result& b) {
187 // Sort in descending relevance order.
188 return a.relevance() > b.relevance();
193 // SearchProvider -------------------------------------------------------------
196 const int SearchProvider::kDefaultProviderURLFetcherID = 1;
197 const int SearchProvider::kKeywordProviderURLFetcherID = 2;
198 const int SearchProvider::kDeletionURLFetcherID = 3;
199 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
201 SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
203 : BaseSearchProvider(listener, profile, AutocompleteProvider::TYPE_SEARCH),
204 providers_(TemplateURLServiceFactory::GetForProfile(profile)),
205 suggest_results_pending_(0) {
209 std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) {
210 return match.GetAdditionalInfo(kSuggestMetadataKey);
213 void SearchProvider::DeleteMatch(const AutocompleteMatch& match) {
214 DCHECK(match.deletable);
216 deletion_handlers_.push_back(new SuggestionDeletionHandler(
217 match.GetAdditionalInfo(SearchProvider::kDeletionUrlKey),
219 base::Bind(&SearchProvider::OnDeletionComplete, base::Unretained(this))));
221 HistoryService* const history_service =
222 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
223 TemplateURL* template_url = match.GetTemplateURL(profile_, false);
224 // This may be NULL if the template corresponding to the keyword has been
225 // deleted or there is no keyword set.
226 if (template_url != NULL) {
227 history_service->DeleteMatchingURLsForKeyword(template_url->id(),
231 // Immediately update the list of matches to show the match was deleted,
232 // regardless of whether the server request actually succeeds.
233 DeleteMatchFromMatches(match);
236 void SearchProvider::ResetSession() {
237 field_trial_triggered_in_session_ = false;
240 SearchProvider::~SearchProvider() {
244 void SearchProvider::RemoveStaleResults(const base::string16& input,
245 int verbatim_relevance,
246 SuggestResults* suggest_results,
247 NavigationResults* navigation_results) {
248 DCHECK_GE(verbatim_relevance, 0);
249 // Keep pointers to the head of (the highest scoring elements of)
250 // |suggest_results| and |navigation_results|. Iterate down the lists
251 // removing non-inlineable results in order of decreasing relevance
252 // scores. Stop when the highest scoring element among those remaining
253 // is inlineable or the element is less than |verbatim_relevance|.
254 // This allows non-inlineable lower-scoring results to remain
255 // because (i) they are guaranteed to not be inlined and (ii)
256 // letting them remain reduces visual jank. For instance, as the
257 // user types the mis-spelled query "fpobar" (for foobar), the
258 // suggestion "foobar" will be suggested on every keystroke. If the
259 // SearchProvider always removes all non-inlineable results, the user will
260 // see visual jitter/jank as the result disappears and re-appears moments
261 // later as the suggest server returns results.
262 SuggestResults::iterator sug_it = suggest_results->begin();
263 NavigationResults::iterator nav_it = navigation_results->begin();
264 while ((sug_it != suggest_results->end()) ||
265 (nav_it != navigation_results->end())) {
267 (sug_it != suggest_results->end()) ? sug_it->relevance() : -1;
269 (nav_it != navigation_results->end()) ? nav_it->relevance() : -1;
270 if (std::max(sug_rel, nav_rel) < verbatim_relevance)
272 if (sug_rel > nav_rel) {
273 // The current top result is a search suggestion.
274 if (sug_it->IsInlineable(input))
276 sug_it = suggest_results->erase(sug_it);
277 } else if (sug_rel == nav_rel) {
278 // Have both results and they're tied.
279 const bool sug_inlineable = sug_it->IsInlineable(input);
280 const bool nav_inlineable = nav_it->IsInlineable(input);
282 sug_it = suggest_results->erase(sug_it);
284 nav_it = navigation_results->erase(nav_it);
285 if (sug_inlineable || nav_inlineable)
288 // The current top result is a navigational suggestion.
289 if (nav_it->IsInlineable(input))
291 nav_it = navigation_results->erase(nav_it);
296 void SearchProvider::UpdateMatchContentsClass(const base::string16& input_text,
298 for (SuggestResults::iterator sug_it = results->suggest_results.begin();
299 sug_it != results->suggest_results.end(); ++sug_it) {
300 sug_it->ClassifyMatchContents(false, input_text);
302 const std::string languages(
303 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
304 for (NavigationResults::iterator nav_it = results->navigation_results.begin();
305 nav_it != results->navigation_results.end(); ++nav_it) {
306 nav_it->CalculateAndClassifyMatchContents(false, input_text, languages);
311 int SearchProvider::CalculateRelevanceForKeywordVerbatim(
312 AutocompleteInput::Type type,
313 bool prefer_keyword) {
314 // This function is responsible for scoring verbatim query matches
315 // for non-extension keywords. KeywordProvider::CalculateRelevance()
316 // scores verbatim query matches for extension keywords, as well as
317 // for keyword matches (i.e., suggestions of a keyword itself, not a
318 // suggestion of a query on a keyword search engine). These two
319 // functions are currently in sync, but there's no reason we
320 // couldn't decide in the future to score verbatim matches
321 // differently for extension and non-extension keywords. If you
322 // make such a change, however, you should update this comment to
323 // describe it, so it's clear why the functions diverge.
326 return (type == AutocompleteInput::QUERY) ? 1450 : 1100;
329 void SearchProvider::Start(const AutocompleteInput& input,
330 bool minimal_changes) {
331 // Do our best to load the model as early as possible. This will reduce
332 // odds of having the model not ready when really needed (a non-empty input).
333 TemplateURLService* model = providers_.template_url_service();
338 field_trial_triggered_ = false;
340 // Can't return search/suggest results for bogus input or without a profile.
341 if (!profile_ || (input.type() == AutocompleteInput::INVALID)) {
346 keyword_input_ = input;
347 const TemplateURL* keyword_provider =
348 KeywordProvider::GetSubstitutingTemplateURLForInput(model,
350 if (keyword_provider == NULL)
351 keyword_input_.Clear();
352 else if (keyword_input_.text().empty())
353 keyword_provider = NULL;
355 const TemplateURL* default_provider = model->GetDefaultSearchProvider();
356 if (default_provider && !default_provider->SupportsReplacement())
357 default_provider = NULL;
359 if (keyword_provider == default_provider)
360 default_provider = NULL; // No use in querying the same provider twice.
362 if (!default_provider && !keyword_provider) {
363 // No valid providers.
368 // If we're still running an old query but have since changed the query text
369 // or the providers, abort the query.
370 base::string16 default_provider_keyword(default_provider ?
371 default_provider->keyword() : base::string16());
372 base::string16 keyword_provider_keyword(keyword_provider ?
373 keyword_provider->keyword() : base::string16());
374 if (!minimal_changes ||
375 !providers_.equal(default_provider_keyword, keyword_provider_keyword)) {
376 // Cancel any in-flight suggest requests.
381 providers_.set(default_provider_keyword, keyword_provider_keyword);
383 if (input.text().empty()) {
384 // User typed "?" alone. Give them a placeholder result indicating what
386 if (default_provider) {
387 AutocompleteMatch match;
388 match.provider = this;
389 match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
390 match.contents_class.push_back(
391 ACMatchClassification(0, ACMatchClassification::NONE));
392 match.keyword = providers_.default_provider();
393 match.allowed_to_be_default_match = true;
394 matches_.push_back(match);
402 DoHistoryQuery(minimal_changes);
403 StartOrStopSuggestQuery(minimal_changes);
407 void SearchProvider::OnURLFetchComplete(const net::URLFetcher* source) {
409 suggest_results_pending_--;
410 LogOmniboxSuggestRequest(REPLY_RECEIVED);
411 DCHECK_GE(suggest_results_pending_, 0); // Should never go negative.
413 const bool is_keyword = (source == keyword_fetcher_.get());
414 // Ensure the request succeeded and that the provider used is still available.
415 // A verbatim match cannot be generated without this provider, causing errors.
416 const bool request_succeeded =
417 source->GetStatus().is_success() && (source->GetResponseCode() == 200) &&
419 providers_.GetKeywordProviderURL() :
420 providers_.GetDefaultProviderURL());
422 // Record response time for suggest requests sent to Google. We care
423 // only about the common case: the Google default provider used in
425 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
426 if (!is_keyword && default_url &&
427 (TemplateURLPrepopulateData::GetEngineType(*default_url) ==
428 SEARCH_ENGINE_GOOGLE)) {
429 const base::TimeDelta elapsed_time =
430 base::TimeTicks::Now() - time_suggest_request_sent_;
431 if (request_succeeded) {
432 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
435 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
440 bool results_updated = false;
441 if (request_succeeded) {
442 const net::HttpResponseHeaders* const response_headers =
443 source->GetResponseHeaders();
444 std::string json_data;
445 source->GetResponseAsString(&json_data);
447 // JSON is supposed to be UTF-8, but some suggest service providers send
448 // JSON files in non-UTF-8 encodings. The actual encoding is usually
449 // specified in the Content-Type header field.
450 if (response_headers) {
452 if (response_headers->GetCharset(&charset)) {
453 base::string16 data_16;
454 // TODO(jungshik): Switch to CodePageToUTF8 after it's added.
455 if (base::CodepageToUTF16(json_data, charset.c_str(),
456 base::OnStringConversionError::FAIL,
458 json_data = base::UTF16ToUTF8(data_16);
462 scoped_ptr<base::Value> data(DeserializeJsonData(json_data));
463 results_updated = data.get() && ParseSuggestResults(data.get(), is_keyword);
467 if (done_ || results_updated)
468 listener_->OnProviderUpdate(results_updated);
471 const TemplateURL* SearchProvider::GetTemplateURL(
472 const SuggestResult& result) const {
473 return result.from_keyword_provider() ? providers_.GetKeywordProviderURL()
474 : providers_.GetDefaultProviderURL();
477 const AutocompleteInput SearchProvider::GetInput(
478 const SuggestResult& result) const {
479 return result.from_keyword_provider() ? keyword_input_ : input_;
482 bool SearchProvider::ShouldAppendExtraParams(
483 const SuggestResult& result) const {
484 return !result.from_keyword_provider() ||
485 providers_.default_provider().empty();
488 void SearchProvider::StopSuggest() {
489 // Increment the appropriate field in the histogram by the number of
490 // pending requests that were invalidated.
491 for (int i = 0; i < suggest_results_pending_; ++i)
492 LogOmniboxSuggestRequest(REQUEST_INVALIDATED);
493 suggest_results_pending_ = 0;
495 // Stop any in-progress URL fetches.
496 keyword_fetcher_.reset();
497 default_fetcher_.reset();
500 void SearchProvider::ClearAllResults() {
501 keyword_results_.Clear();
502 default_results_.Clear();
505 void SearchProvider::OnDeletionComplete(bool success,
506 SuggestionDeletionHandler* handler) {
507 RecordDeletionResult(success);
508 SuggestionDeletionHandlers::iterator it = std::find(
509 deletion_handlers_.begin(), deletion_handlers_.end(), handler);
510 DCHECK(it != deletion_handlers_.end());
511 deletion_handlers_.erase(it);
515 void SearchProvider::RecordDeletionResult(bool success) {
517 content::RecordAction(
518 base::UserMetricsAction("Omnibox.ServerSuggestDelete.Success"));
520 content::RecordAction(
521 base::UserMetricsAction("Omnibox.ServerSuggestDelete.Failure"));
525 void SearchProvider::DeleteMatchFromMatches(const AutocompleteMatch& match) {
526 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i) {
527 // Find the desired match to delete by checking the type and contents.
528 // We can't check the destination URL, because the autocomplete controller
529 // may have reformulated that. Not that while checking for matching
530 // contents works for personalized suggestions, if more match types gain
531 // deletion support, this algorithm may need to be re-examined.
532 if (i->contents == match.contents && i->type == match.type) {
537 listener_->OnProviderUpdate(true);
540 void SearchProvider::Run() {
541 // Start a new request with the current input.
542 suggest_results_pending_ = 0;
543 time_suggest_request_sent_ = base::TimeTicks::Now();
545 default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
546 providers_.GetDefaultProviderURL(), input_));
547 keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID,
548 providers_.GetKeywordProviderURL(), keyword_input_));
550 // Both the above can fail if the providers have been modified or deleted
551 // since the query began.
552 if (suggest_results_pending_ == 0) {
554 // We only need to update the listener if we're actually done.
556 listener_->OnProviderUpdate(false);
560 void SearchProvider::DoHistoryQuery(bool minimal_changes) {
561 // The history query results are synchronous, so if minimal_changes is true,
562 // we still have the last results and don't need to do anything.
566 base::TimeTicks do_history_query_start_time(base::TimeTicks::Now());
568 keyword_history_results_.clear();
569 default_history_results_.clear();
571 if (OmniboxFieldTrial::SearchHistoryDisable(
572 input_.current_page_classification()))
575 base::TimeTicks start_time(base::TimeTicks::Now());
576 HistoryService* const history_service =
577 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
578 base::TimeTicks now(base::TimeTicks::Now());
579 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.GetHistoryServiceTime",
582 history::URLDatabase* url_db = history_service ?
583 history_service->InMemoryDatabase() : NULL;
584 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.InMemoryDatabaseTime",
585 base::TimeTicks::Now() - start_time);
589 // Request history for both the keyword and default provider. We grab many
590 // more matches than we'll ultimately clamp to so that if there are several
591 // recent multi-word matches who scores are lowered (see
592 // AddHistoryResultsToMap()), they won't crowd out older, higher-scoring
593 // matches. Note that this doesn't fix the problem entirely, but merely
594 // limits it to cases with a very large number of such multi-word matches; for
595 // now, this seems OK compared with the complexity of a real fix, which would
596 // require multiple searches and tracking of "single- vs. multi-word" in the
598 int num_matches = kMaxMatches * 5;
599 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
601 start_time = base::TimeTicks::Now();
602 url_db->GetMostRecentKeywordSearchTerms(default_url->id(), input_.text(),
603 num_matches, &default_history_results_);
605 "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime",
606 base::TimeTicks::Now() - start_time);
608 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
610 url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(),
611 keyword_input_.text(), num_matches, &keyword_history_results_);
613 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.DoHistoryQueryTime",
614 base::TimeTicks::Now() - do_history_query_start_time);
617 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
618 if (!IsQuerySuitableForSuggest()) {
624 // For the minimal_changes case, if we finished the previous query and still
625 // have its results, or are allowed to keep running it, just do that, rather
626 // than starting a new query.
627 if (minimal_changes &&
628 (!default_results_.suggest_results.empty() ||
629 !default_results_.navigation_results.empty() ||
630 !keyword_results_.suggest_results.empty() ||
631 !keyword_results_.navigation_results.empty() ||
633 input_.matches_requested() == AutocompleteInput::ALL_MATCHES)))
636 // We can't keep running any previous query, so halt it.
639 // Remove existing results that cannot inline autocomplete the new input.
640 RemoveAllStaleResults();
642 // Update the content classifications of remaining results so they look good
643 // against the current input.
644 UpdateMatchContentsClass(input_.text(), &default_results_);
645 if (!keyword_input_.text().empty())
646 UpdateMatchContentsClass(keyword_input_.text(), &keyword_results_);
648 // We can't start a new query if we're only allowed synchronous results.
649 if (input_.matches_requested() != AutocompleteInput::ALL_MATCHES)
652 // To avoid flooding the suggest server, don't send a query until at
653 // least 100 ms since the last query.
654 base::TimeTicks next_suggest_time(time_suggest_request_sent_ +
655 base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs));
656 base::TimeTicks now(base::TimeTicks::Now());
657 if (now >= next_suggest_time) {
661 timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run);
664 bool SearchProvider::IsQuerySuitableForSuggest() const {
665 // Don't run Suggest in incognito mode, if the engine doesn't support it, or
666 // if the user has disabled it.
667 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
668 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
669 if (profile_->IsOffTheRecord() ||
670 ((!default_url || default_url->suggestions_url().empty()) &&
671 (!keyword_url || keyword_url->suggestions_url().empty())) ||
672 !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled))
675 // If the input type might be a URL, we take extra care so that private data
676 // isn't sent to the server.
678 // FORCED_QUERY means the user is explicitly asking us to search for this, so
679 // we assume it isn't a URL and/or there isn't private data.
680 if (input_.type() == AutocompleteInput::FORCED_QUERY)
683 // Next we check the scheme. If this is UNKNOWN/URL with a scheme that isn't
684 // http/https/ftp, we shouldn't send it. Sending things like file: and data:
685 // is both a waste of time and a disclosure of potentially private, local
686 // data. Other "schemes" may actually be usernames, and we don't want to send
687 // passwords. If the scheme is OK, we still need to check other cases below.
688 // If this is QUERY, then the presence of these schemes means the user
689 // explicitly typed one, and thus this is probably a URL that's being entered
690 // and happens to currently be invalid -- in which case we again want to run
691 // our checks below. Other QUERY cases are less likely to be URLs and thus we
693 if (!LowerCaseEqualsASCII(input_.scheme(), content::kHttpScheme) &&
694 !LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
695 !LowerCaseEqualsASCII(input_.scheme(), content::kFtpScheme))
696 return (input_.type() == AutocompleteInput::QUERY);
698 // Don't send URLs with usernames, queries or refs. Some of these are
699 // private, and the Suggest server is unlikely to have any useful results
700 // for any of them. Also don't send URLs with ports, as we may initially
701 // think that a username + password is a host + port (and we don't want to
702 // send usernames/passwords), and even if the port really is a port, the
703 // server is once again unlikely to have and useful results.
704 // Note that we only block based on refs if the input is URL-typed, as search
705 // queries can legitimately have #s in them which the URL parser
706 // overaggressively categorizes as a url with a ref.
707 const url_parse::Parsed& parts = input_.parts();
708 if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
709 parts.query.is_nonempty() ||
710 (parts.ref.is_nonempty() && (input_.type() == AutocompleteInput::URL)))
713 // Don't send anything for https except the hostname. Hostnames are OK
714 // because they are visible when the TCP connection is established, but the
715 // specific path may reveal private information.
716 if (LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
717 parts.path.is_nonempty())
723 void SearchProvider::RemoveAllStaleResults() {
724 // We only need to remove stale results (which ensures the top-scoring
725 // match is inlineable) if the user is not in reorder mode. In reorder
726 // mode, the autocomplete system will reorder results to make sure the
727 // top result is inlineable.
728 const bool omnibox_will_reorder_for_legal_default_match =
729 OmniboxFieldTrial::ReorderForLegalDefaultMatch(
730 input_.current_page_classification());
731 // In theory it would be better to run an algorithm like that in
732 // RemoveStaleResults(...) below that uses all four results lists
733 // and both verbatim scores at once. However, that will be much
734 // more complicated for little obvious gain. For code simplicity
735 // and ease in reasoning about the invariants involved, this code
736 // removes stales results from the keyword provider and default
737 // provider independently.
738 if (!omnibox_will_reorder_for_legal_default_match) {
739 RemoveStaleResults(input_.text(), GetVerbatimRelevance(NULL),
740 &default_results_.suggest_results,
741 &default_results_.navigation_results);
742 if (!keyword_input_.text().empty()) {
743 RemoveStaleResults(keyword_input_.text(),
744 GetKeywordVerbatimRelevance(NULL),
745 &keyword_results_.suggest_results,
746 &keyword_results_.navigation_results);
749 if (keyword_input_.text().empty()) {
750 // User is either in keyword mode with a blank input or out of
751 // keyword mode entirely.
752 keyword_results_.Clear();
756 void SearchProvider::ApplyCalculatedRelevance() {
757 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
758 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
759 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
760 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
761 default_results_.verbatim_relevance = -1;
762 keyword_results_.verbatim_relevance = -1;
765 void SearchProvider::ApplyCalculatedSuggestRelevance(SuggestResults* list) {
766 for (size_t i = 0; i < list->size(); ++i) {
767 SuggestResult& result = (*list)[i];
768 result.set_relevance(
769 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
770 (list->size() - i - 1));
771 result.set_relevance_from_server(false);
775 void SearchProvider::ApplyCalculatedNavigationRelevance(
776 NavigationResults* list) {
777 for (size_t i = 0; i < list->size(); ++i) {
778 NavigationResult& result = (*list)[i];
779 result.set_relevance(
780 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
781 (list->size() - i - 1));
782 result.set_relevance_from_server(false);
786 net::URLFetcher* SearchProvider::CreateSuggestFetcher(
788 const TemplateURL* template_url,
789 const AutocompleteInput& input) {
790 if (!template_url || template_url->suggestions_url().empty())
793 // Bail if the suggestion URL is invalid with the given replacements.
794 TemplateURLRef::SearchTermsArgs search_term_args(input.text());
795 search_term_args.cursor_position = input.cursor_position();
796 search_term_args.page_classification = input.current_page_classification();
797 GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
799 if (!suggest_url.is_valid())
801 // Send the current page URL if user setting and URL requirements are met and
802 // the user is in the field trial.
803 if (CanSendURL(current_page_url_, suggest_url, template_url,
804 input.current_page_classification(), profile_) &&
805 OmniboxFieldTrial::InZeroSuggestAfterTypingFieldTrial()) {
806 search_term_args.current_page_url = current_page_url_.spec();
807 // Create the suggest URL again with the current page URL.
808 suggest_url = GURL(template_url->suggestions_url_ref().ReplaceSearchTerms(
812 suggest_results_pending_++;
813 LogOmniboxSuggestRequest(REQUEST_SENT);
815 net::URLFetcher* fetcher =
816 net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this);
817 fetcher->SetRequestContext(profile_->GetRequestContext());
818 fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES);
819 // Add Chrome experiment state to the request headers.
820 net::HttpRequestHeaders headers;
821 chrome_variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders(
822 fetcher->GetOriginalURL(), profile_->IsOffTheRecord(), false, &headers);
823 fetcher->SetExtraRequestHeaders(headers.ToString());
828 bool SearchProvider::ParseSuggestResults(base::Value* root_val,
830 base::string16 query;
831 base::ListValue* root_list = NULL;
832 base::ListValue* results_list = NULL;
833 const base::string16& input_text =
834 is_keyword ? keyword_input_.text() : input_.text();
835 if (!root_val->GetAsList(&root_list) || !root_list->GetString(0, &query) ||
836 (query != input_text) || !root_list->GetList(1, &results_list))
839 // 3rd element: Description list.
840 base::ListValue* descriptions = NULL;
841 root_list->GetList(2, &descriptions);
843 // 4th element: Disregard the query URL list for now.
845 // Reset suggested relevance information from the default provider.
846 Results* results = is_keyword ? &keyword_results_ : &default_results_;
847 results->verbatim_relevance = -1;
849 // 5th element: Optional key-value pairs from the Suggest server.
850 base::ListValue* types = NULL;
851 base::ListValue* relevances = NULL;
852 base::ListValue* suggestion_details = NULL;
853 base::DictionaryValue* extras = NULL;
854 int prefetch_index = -1;
855 if (root_list->GetDictionary(4, &extras)) {
856 extras->GetList("google:suggesttype", &types);
858 // Discard this list if its size does not match that of the suggestions.
859 if (extras->GetList("google:suggestrelevance", &relevances) &&
860 (relevances->GetSize() != results_list->GetSize()))
862 extras->GetInteger("google:verbatimrelevance",
863 &results->verbatim_relevance);
865 // Check if the active suggest field trial (if any) has triggered either
866 // for the default provider or keyword provider.
867 bool triggered = false;
868 extras->GetBoolean("google:fieldtrialtriggered", &triggered);
869 field_trial_triggered_ |= triggered;
870 field_trial_triggered_in_session_ |= triggered;
872 base::DictionaryValue* client_data = NULL;
873 if (extras->GetDictionary("google:clientdata", &client_data) && client_data)
874 client_data->GetInteger("phi", &prefetch_index);
876 if (extras->GetList("google:suggestdetail", &suggestion_details) &&
877 suggestion_details->GetSize() != results_list->GetSize())
878 suggestion_details = NULL;
880 // Store the metadata that came with the response in case we need to pass it
881 // along with the prefetch query to Instant.
882 JSONStringValueSerializer json_serializer(&results->metadata);
883 json_serializer.Serialize(*extras);
886 // Clear the previous results now that new results are available.
887 results->suggest_results.clear();
888 results->navigation_results.clear();
890 base::string16 suggestion;
893 // Prohibit navsuggest in FORCED_QUERY mode. Users wants queries, not URLs.
894 const bool allow_navsuggest =
895 (is_keyword ? keyword_input_.type() : input_.type()) !=
896 AutocompleteInput::FORCED_QUERY;
897 const std::string languages(
898 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
899 for (size_t index = 0; results_list->GetString(index, &suggestion); ++index) {
900 // Google search may return empty suggestions for weird input characters,
901 // they make no sense at all and can cause problems in our code.
902 if (suggestion.empty())
905 // Apply valid suggested relevance scores; discard invalid lists.
906 if (relevances != NULL && !relevances->GetInteger(index, &relevance))
908 if (types && types->GetString(index, &type) && (type == "NAVIGATION")) {
909 // Do not blindly trust the URL coming from the server to be valid.
910 GURL url(URLFixerUpper::FixupURL(
911 base::UTF16ToUTF8(suggestion), std::string()));
912 if (url.is_valid() && allow_navsuggest) {
913 base::string16 title;
914 if (descriptions != NULL)
915 descriptions->GetString(index, &title);
916 results->navigation_results.push_back(NavigationResult(
917 *this, url, title, is_keyword, relevance, true, input_text,
921 AutocompleteMatchType::Type match_type = GetAutocompleteMatchType(type);
922 bool should_prefetch = static_cast<int>(index) == prefetch_index;
923 base::DictionaryValue* suggestion_detail = NULL;
924 base::string16 match_contents = suggestion;
925 base::string16 annotation;
926 std::string suggest_query_params;
927 std::string deletion_url;
929 if (suggestion_details) {
930 suggestion_details->GetDictionary(index, &suggestion_detail);
931 if (suggestion_detail) {
932 suggestion_detail->GetString("du", &deletion_url);
933 suggestion_detail->GetString("title", &match_contents) ||
934 suggestion_detail->GetString("t", &match_contents);
935 // Error correction for bad data from server.
936 if (match_contents.empty())
937 match_contents = suggestion;
938 suggestion_detail->GetString("annotation", &annotation) ||
939 suggestion_detail->GetString("a", &annotation);
940 suggestion_detail->GetString("query_params", &suggest_query_params) ||
941 suggestion_detail->GetString("q", &suggest_query_params);
945 // TODO(kochi): Improve calculator suggestion presentation.
946 results->suggest_results.push_back(SuggestResult(
947 suggestion, match_type, match_contents, annotation,
948 suggest_query_params, deletion_url, is_keyword, relevance, true,
949 should_prefetch, input_text));
953 // Ignore suggested scores for non-keyword matches in keyword mode; if the
954 // server is allowed to score these, it could interfere with the user's
955 // ability to get good keyword results.
956 const bool abandon_suggested_scores =
957 !is_keyword && !providers_.keyword_provider().empty();
958 // Apply calculated relevance scores to suggestions if a valid list was
959 // not provided or we're abandoning suggested scores entirely.
960 if ((relevances == NULL) || abandon_suggested_scores) {
961 ApplyCalculatedSuggestRelevance(&results->suggest_results);
962 ApplyCalculatedNavigationRelevance(&results->navigation_results);
963 // If abandoning scores entirely, also abandon the verbatim score.
964 if (abandon_suggested_scores)
965 results->verbatim_relevance = -1;
968 // Keep the result lists sorted.
969 const CompareScoredResults comparator = CompareScoredResults();
970 std::stable_sort(results->suggest_results.begin(),
971 results->suggest_results.end(),
973 std::stable_sort(results->navigation_results.begin(),
974 results->navigation_results.end(),
979 void SearchProvider::ConvertResultsToAutocompleteMatches() {
980 // Convert all the results to matches and add them to a map, so we can keep
981 // the most relevant match for each result.
982 base::TimeTicks start_time(base::TimeTicks::Now());
984 const base::Time no_time;
985 int did_not_accept_keyword_suggestion =
986 keyword_results_.suggest_results.empty() ?
987 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
988 TemplateURLRef::NO_SUGGESTION_CHOSEN;
990 bool relevance_from_server;
991 int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
992 int did_not_accept_default_suggestion =
993 default_results_.suggest_results.empty() ?
994 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
995 TemplateURLRef::NO_SUGGESTION_CHOSEN;
996 if (verbatim_relevance > 0) {
997 SuggestResult verbatim(
998 input_.text(), AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
999 input_.text(), base::string16(), std::string(), std::string(), false,
1000 verbatim_relevance, relevance_from_server, false, input_.text());
1002 verbatim, std::string(), did_not_accept_default_suggestion, &map);
1004 if (!keyword_input_.text().empty()) {
1005 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1006 // We only create the verbatim search query match for a keyword
1007 // if it's not an extension keyword. Extension keywords are handled
1008 // in KeywordProvider::Start(). (Extensions are complicated...)
1009 // Note: in this provider, SEARCH_OTHER_ENGINE must correspond
1010 // to the keyword verbatim search query. Do not create other matches
1011 // of type SEARCH_OTHER_ENGINE.
1013 (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
1014 bool keyword_relevance_from_server;
1015 const int keyword_verbatim_relevance =
1016 GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
1017 if (keyword_verbatim_relevance > 0) {
1018 SuggestResult verbatim(
1019 keyword_input_.text(), AutocompleteMatchType::SEARCH_OTHER_ENGINE,
1020 keyword_input_.text(), base::string16(), std::string(),
1021 std::string(), true, keyword_verbatim_relevance,
1022 keyword_relevance_from_server, false, keyword_input_.text());
1024 verbatim, std::string(), did_not_accept_keyword_suggestion, &map);
1028 AddHistoryResultsToMap(keyword_history_results_, true,
1029 did_not_accept_keyword_suggestion, &map);
1030 AddHistoryResultsToMap(default_history_results_, false,
1031 did_not_accept_default_suggestion, &map);
1033 AddSuggestResultsToMap(keyword_results_.suggest_results,
1034 keyword_results_.metadata, &map);
1035 AddSuggestResultsToMap(default_results_.suggest_results,
1036 default_results_.metadata, &map);
1039 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
1040 matches.push_back(i->second);
1042 AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
1043 AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
1045 // Now add the most relevant matches to |matches_|. We take up to kMaxMatches
1046 // suggest/navsuggest matches, regardless of origin. If Instant Extended is
1047 // enabled and we have server-provided (and thus hopefully more accurate)
1048 // scores for some suggestions, we allow more of those, until we reach
1049 // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
1052 // We will always return any verbatim matches, no matter how we obtained their
1053 // scores, unless we have already accepted AutocompleteResult::kMaxMatches
1054 // higher-scoring matches under the conditions above.
1055 UMA_HISTOGRAM_CUSTOM_COUNTS(
1056 "Omnibox.SearchProvider.NumMatchesToSort", matches.size(), 1, 50, 20);
1057 std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
1060 size_t num_suggestions = 0;
1061 for (ACMatches::const_iterator i(matches.begin());
1062 (i != matches.end()) &&
1063 (matches_.size() < AutocompleteResult::kMaxMatches);
1065 // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
1066 // verbatim result, so this condition basically means "if this match is a
1067 // suggestion of some sort".
1068 if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
1069 (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
1070 // If we've already hit the limit on non-server-scored suggestions, and
1071 // this isn't a server-scored suggestion we can add, skip it.
1072 if ((num_suggestions >= kMaxMatches) &&
1073 (!chrome::IsInstantExtendedAPIEnabled() ||
1074 (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
1081 matches_.push_back(*i);
1083 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime",
1084 base::TimeTicks::Now() - start_time);
1087 ACMatches::const_iterator SearchProvider::FindTopMatch(
1088 bool autocomplete_result_will_reorder_for_default_match) const {
1089 if (!autocomplete_result_will_reorder_for_default_match)
1090 return matches_.begin();
1091 ACMatches::const_iterator it = matches_.begin();
1092 while ((it != matches_.end()) && !it->allowed_to_be_default_match)
1097 bool SearchProvider::IsTopMatchNavigationInKeywordMode(
1098 bool autocomplete_result_will_reorder_for_default_match) const {
1099 ACMatches::const_iterator first_match =
1100 FindTopMatch(autocomplete_result_will_reorder_for_default_match);
1101 return !providers_.keyword_provider().empty() &&
1102 (first_match != matches_.end()) &&
1103 (first_match->type == AutocompleteMatchType::NAVSUGGEST);
1106 bool SearchProvider::HasKeywordDefaultMatchInKeywordMode() const {
1107 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1108 // If the user is not in keyword mode, return true to say that this
1109 // constraint is not violated.
1110 if (keyword_url == NULL)
1112 for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
1114 if ((it->keyword == keyword_url->keyword()) &&
1115 it->allowed_to_be_default_match)
1121 bool SearchProvider::IsTopMatchScoreTooLow(
1122 bool autocomplete_result_will_reorder_for_default_match) const {
1123 // In reorder mode, there's no such thing as a score that's too low.
1124 if (autocomplete_result_will_reorder_for_default_match)
1127 // Here we use CalculateRelevanceForVerbatimIgnoringKeywordModeState()
1128 // rather than CalculateRelevanceForVerbatim() because the latter returns
1129 // a very low score (250) if keyword mode is active. This is because
1130 // when keyword mode is active the user probably wants the keyword matches,
1131 // not matches from the default provider. Hence, we use the version of
1132 // the function that ignores whether keyword mode is active. This allows
1133 // SearchProvider to maintain its contract with the AutocompleteController
1134 // that it will always provide an inlineable match with a reasonable
1136 return matches_.front().relevance <
1137 CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1140 bool SearchProvider::IsTopMatchSearchWithURLInput(
1141 bool autocomplete_result_will_reorder_for_default_match) const {
1142 ACMatches::const_iterator first_match =
1143 FindTopMatch(autocomplete_result_will_reorder_for_default_match);
1144 return (input_.type() == AutocompleteInput::URL) &&
1145 (first_match != matches_.end()) &&
1146 (first_match->relevance > CalculateRelevanceForVerbatim()) &&
1147 (first_match->type != AutocompleteMatchType::NAVSUGGEST);
1150 bool SearchProvider::HasValidDefaultMatch(
1151 bool autocomplete_result_will_reorder_for_default_match) const {
1152 // One of the SearchProvider matches may need to be the overall default. If
1153 // AutocompleteResult is allowed to reorder matches, this means we simply
1154 // need at least one match in the list to be |allowed_to_be_default_match|.
1155 // If no reordering is possible, however, then our first match needs to have
1157 for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
1159 if (it->allowed_to_be_default_match)
1161 if (!autocomplete_result_will_reorder_for_default_match)
1167 void SearchProvider::UpdateMatches() {
1168 base::TimeTicks update_matches_start_time(base::TimeTicks::Now());
1169 ConvertResultsToAutocompleteMatches();
1171 // Check constraints that may be violated by suggested relevances.
1172 if (!matches_.empty() &&
1173 (default_results_.HasServerProvidedScores() ||
1174 keyword_results_.HasServerProvidedScores())) {
1175 // These blocks attempt to repair undesirable behavior by suggested
1176 // relevances with minimal impact, preserving other suggested relevances.
1178 // True if the omnibox will reorder matches as necessary to make the first
1179 // one something that is allowed to be the default match.
1180 const bool omnibox_will_reorder_for_legal_default_match =
1181 OmniboxFieldTrial::ReorderForLegalDefaultMatch(
1182 input_.current_page_classification());
1183 if (IsTopMatchNavigationInKeywordMode(
1184 omnibox_will_reorder_for_legal_default_match)) {
1185 // Correct the suggested relevance scores if the top match is a
1186 // navigation in keyword mode, since inlining a navigation match
1187 // would break the user out of keyword mode. This will only be
1188 // triggered in regular (non-reorder) mode; in reorder mode,
1189 // navigation matches are marked as not allowed to be the default
1190 // match and hence IsTopMatchNavigation() will always return false.
1191 DCHECK(!omnibox_will_reorder_for_legal_default_match);
1192 DemoteKeywordNavigationMatchesPastTopQuery();
1193 ConvertResultsToAutocompleteMatches();
1194 DCHECK(!IsTopMatchNavigationInKeywordMode(
1195 omnibox_will_reorder_for_legal_default_match));
1197 if (!HasKeywordDefaultMatchInKeywordMode()) {
1198 // In keyword mode, disregard the keyword verbatim suggested relevance
1199 // if necessary so there at least one keyword match that's allowed to
1200 // be the default match.
1201 keyword_results_.verbatim_relevance = -1;
1202 ConvertResultsToAutocompleteMatches();
1204 if (IsTopMatchScoreTooLow(omnibox_will_reorder_for_legal_default_match)) {
1205 // Disregard the suggested verbatim relevance if the top score is below
1206 // the usual verbatim value. For example, a BarProvider may rely on
1207 // SearchProvider's verbatim or inlineable matches for input "foo" (all
1208 // allowed to be default match) to always outrank its own lowly-ranked
1209 // "bar" matches that shouldn't be the default match.
1210 default_results_.verbatim_relevance = -1;
1211 keyword_results_.verbatim_relevance = -1;
1212 ConvertResultsToAutocompleteMatches();
1214 if (IsTopMatchSearchWithURLInput(
1215 omnibox_will_reorder_for_legal_default_match)) {
1216 // Disregard the suggested search and verbatim relevances if the input
1217 // type is URL and the top match is a highly-ranked search suggestion.
1218 // For example, prevent a search for "foo.com" from outranking another
1219 // provider's navigation for "foo.com" or "foo.com/url_from_history".
1220 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
1221 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
1222 default_results_.verbatim_relevance = -1;
1223 keyword_results_.verbatim_relevance = -1;
1224 ConvertResultsToAutocompleteMatches();
1226 if (!HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match)) {
1227 // If the omnibox is not going to reorder results to put a legal default
1228 // match at the top, then this provider needs to guarantee that its top
1229 // scoring result is a legal default match (i.e., it's either a verbatim
1230 // match or inlinable). For example, input "foo" should not invoke a
1231 // search for "bar", which would happen if the "bar" search match
1232 // outranked all other matches. On the other hand, if the omnibox will
1233 // reorder matches as necessary to put a legal default match at the top,
1234 // all we need to guarantee is that SearchProvider returns a legal
1235 // default match. (The omnibox always needs at least one legal default
1236 // match, and it relies on SearchProvider to always return one.)
1237 ApplyCalculatedRelevance();
1238 ConvertResultsToAutocompleteMatches();
1240 DCHECK(!IsTopMatchNavigationInKeywordMode(
1241 omnibox_will_reorder_for_legal_default_match));
1242 DCHECK(HasKeywordDefaultMatchInKeywordMode());
1243 DCHECK(!IsTopMatchScoreTooLow(
1244 omnibox_will_reorder_for_legal_default_match));
1245 DCHECK(!IsTopMatchSearchWithURLInput(
1246 omnibox_will_reorder_for_legal_default_match));
1247 DCHECK(HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match));
1249 UMA_HISTOGRAM_CUSTOM_COUNTS(
1250 "Omnibox.SearchProviderMatches", matches_.size(), 1, 6, 7);
1252 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1253 if ((keyword_url != NULL) && HasKeywordDefaultMatchInKeywordMode()) {
1254 // If there is a keyword match that is allowed to be the default match,
1255 // then prohibit default provider matches from being the default match lest
1256 // such matches cause the user to break out of keyword mode.
1257 for (ACMatches::iterator it = matches_.begin(); it != matches_.end();
1259 if (it->keyword != keyword_url->keyword())
1260 it->allowed_to_be_default_match = false;
1264 base::TimeTicks update_starred_start_time(base::TimeTicks::Now());
1265 UpdateStarredStateOfMatches();
1266 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateStarredTime",
1267 base::TimeTicks::Now() - update_starred_start_time);
1269 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateMatchesTime",
1270 base::TimeTicks::Now() - update_matches_start_time);
1273 void SearchProvider::AddNavigationResultsToMatches(
1274 const NavigationResults& navigation_results,
1275 ACMatches* matches) {
1276 for (NavigationResults::const_iterator it = navigation_results.begin();
1277 it != navigation_results.end(); ++it) {
1278 matches->push_back(NavigationToMatch(*it));
1279 // In the absence of suggested relevance scores, use only the single
1280 // highest-scoring result. (The results are already sorted by relevance.)
1281 if (!it->relevance_from_server())
1286 void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
1288 int did_not_accept_suggestion,
1290 if (results.empty())
1293 base::TimeTicks start_time(base::TimeTicks::Now());
1294 bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() ||
1295 (input_.type() == AutocompleteInput::URL);
1296 const base::string16& input_text =
1297 is_keyword ? keyword_input_.text() : input_.text();
1298 bool input_multiple_words = HasMultipleWords(input_text);
1300 SuggestResults scored_results;
1301 if (!prevent_inline_autocomplete && input_multiple_words) {
1302 // ScoreHistoryResults() allows autocompletion of multi-word, 1-visit
1303 // queries if the input also has multiple words. But if we were already
1304 // autocompleting a multi-word, multi-visit query, and the current input is
1305 // still a prefix of it, then changing the autocompletion suddenly feels
1306 // wrong. To detect this case, first score as if only one word has been
1307 // typed, then check for a best result that is an autocompleted, multi-word
1308 // query. If we find one, then just keep that score set.
1309 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1310 false, input_text, is_keyword);
1311 if ((scored_results.front().relevance() <
1312 AutocompleteResult::kLowestDefaultScore) ||
1313 !HasMultipleWords(scored_results.front().suggestion()))
1314 scored_results.clear(); // Didn't detect the case above, score normally.
1316 if (scored_results.empty())
1317 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1318 input_multiple_words, input_text,
1320 for (SuggestResults::const_iterator i(scored_results.begin());
1321 i != scored_results.end(); ++i) {
1322 AddMatchToMap(*i, std::string(), did_not_accept_suggestion, map);
1324 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime",
1325 base::TimeTicks::Now() - start_time);
1328 SearchProvider::SuggestResults SearchProvider::ScoreHistoryResults(
1329 const HistoryResults& results,
1330 bool base_prevent_inline_autocomplete,
1331 bool input_multiple_words,
1332 const base::string16& input_text,
1334 AutocompleteClassifier* classifier =
1335 AutocompleteClassifierFactory::GetForProfile(profile_);
1336 SuggestResults scored_results;
1337 const bool prevent_search_history_inlining =
1338 OmniboxFieldTrial::SearchHistoryPreventInlining(
1339 input_.current_page_classification());
1340 for (HistoryResults::const_iterator i(results.begin()); i != results.end();
1342 // Don't autocomplete multi-word queries that have only been seen once
1343 // unless the user has typed more than one word.
1344 bool prevent_inline_autocomplete = base_prevent_inline_autocomplete ||
1345 (!input_multiple_words && (i->visits < 2) && HasMultipleWords(i->term));
1347 // Don't autocomplete search terms that would normally be treated as URLs
1348 // when typed. For example, if the user searched for "google.com" and types
1349 // "goog", don't autocomplete to the search term "google.com". Otherwise,
1350 // the input will look like a URL but act like a search, which is confusing.
1351 // NOTE: We don't check this in the following cases:
1352 // * When inline autocomplete is disabled, we won't be inline
1353 // autocompleting this term, so we don't need to worry about confusion as
1354 // much. This also prevents calling Classify() again from inside the
1355 // classifier (which will corrupt state and likely crash), since the
1356 // classifier always disables inline autocomplete.
1357 // * When the user has typed the whole term, the "what you typed" history
1358 // match will outrank us for URL-like inputs anyway, so we need not do
1359 // anything special.
1360 if (!prevent_inline_autocomplete && classifier && (i->term != input_text)) {
1361 AutocompleteMatch match;
1362 classifier->Classify(i->term, false, false,
1363 input_.current_page_classification(), &match, NULL);
1364 prevent_inline_autocomplete =
1365 !AutocompleteMatch::IsSearchType(match.type);
1368 int relevance = CalculateRelevanceForHistory(
1369 i->time, is_keyword, !prevent_inline_autocomplete,
1370 prevent_search_history_inlining);
1371 scored_results.push_back(SuggestResult(
1372 i->term, AutocompleteMatchType::SEARCH_HISTORY, i->term,
1373 base::string16(), std::string(), std::string(), is_keyword, relevance,
1374 false, false, input_text));
1377 // History returns results sorted for us. However, we may have docked some
1378 // results' scores, so things are no longer in order. Do a stable sort to get
1379 // things back in order without otherwise disturbing results with equal
1380 // scores, then force the scores to be unique, so that the order in which
1381 // they're shown is deterministic.
1382 std::stable_sort(scored_results.begin(), scored_results.end(),
1383 CompareScoredResults());
1384 int last_relevance = 0;
1385 for (SuggestResults::iterator i(scored_results.begin());
1386 i != scored_results.end(); ++i) {
1387 if ((i != scored_results.begin()) && (i->relevance() >= last_relevance))
1388 i->set_relevance(last_relevance - 1);
1389 last_relevance = i->relevance();
1392 return scored_results;
1395 void SearchProvider::AddSuggestResultsToMap(const SuggestResults& results,
1396 const std::string& metadata,
1398 for (size_t i = 0; i < results.size(); ++i)
1399 AddMatchToMap(results[i], metadata, i, map);
1402 int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
1403 // Use the suggested verbatim relevance score if it is non-negative (valid),
1404 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1405 // and if it won't suppress verbatim, leaving no default provider matches.
1406 // Otherwise, if the default provider returned no matches and was still able
1407 // to suppress verbatim, the user would have no search/nav matches and may be
1408 // left unable to search using their default provider from the omnibox.
1409 // Check for results on each verbatim calculation, as results from older
1410 // queries (on previous input) may be trimmed for failing to inline new input.
1411 bool use_server_relevance =
1412 (default_results_.verbatim_relevance >= 0) &&
1413 !input_.prevent_inline_autocomplete() &&
1414 ((default_results_.verbatim_relevance > 0) ||
1415 !default_results_.suggest_results.empty() ||
1416 !default_results_.navigation_results.empty());
1417 if (relevance_from_server)
1418 *relevance_from_server = use_server_relevance;
1419 return use_server_relevance ?
1420 default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
1423 int SearchProvider::CalculateRelevanceForVerbatim() const {
1424 if (!providers_.keyword_provider().empty())
1426 return CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1429 int SearchProvider::
1430 CalculateRelevanceForVerbatimIgnoringKeywordModeState() const {
1431 switch (input_.type()) {
1432 case AutocompleteInput::UNKNOWN:
1433 case AutocompleteInput::QUERY:
1434 case AutocompleteInput::FORCED_QUERY:
1435 return kNonURLVerbatimRelevance;
1437 case AutocompleteInput::URL:
1446 int SearchProvider::GetKeywordVerbatimRelevance(
1447 bool* relevance_from_server) const {
1448 // Use the suggested verbatim relevance score if it is non-negative (valid),
1449 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1450 // and if it won't suppress verbatim, leaving no keyword provider matches.
1451 // Otherwise, if the keyword provider returned no matches and was still able
1452 // to suppress verbatim, the user would have no search/nav matches and may be
1453 // left unable to search using their keyword provider from the omnibox.
1454 // Check for results on each verbatim calculation, as results from older
1455 // queries (on previous input) may be trimmed for failing to inline new input.
1456 bool use_server_relevance =
1457 (keyword_results_.verbatim_relevance >= 0) &&
1458 !input_.prevent_inline_autocomplete() &&
1459 ((keyword_results_.verbatim_relevance > 0) ||
1460 !keyword_results_.suggest_results.empty() ||
1461 !keyword_results_.navigation_results.empty());
1462 if (relevance_from_server)
1463 *relevance_from_server = use_server_relevance;
1464 return use_server_relevance ?
1465 keyword_results_.verbatim_relevance :
1466 CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
1467 keyword_input_.prefer_keyword());
1470 int SearchProvider::CalculateRelevanceForHistory(
1471 const base::Time& time,
1473 bool use_aggressive_method,
1474 bool prevent_search_history_inlining) const {
1475 // The relevance of past searches falls off over time. There are two distinct
1476 // equations used. If the first equation is used (searches to the primary
1477 // provider that we want to score aggressively), the score is in the range
1478 // 1300-1599 (unless |prevent_search_history_inlining|, in which case
1479 // it's in the range 1200-1299). If the second equation is used the
1480 // relevance of a search 15 minutes ago is discounted 50 points, while the
1481 // relevance of a search two weeks ago is discounted 450 points.
1482 double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0);
1483 bool is_primary_provider = is_keyword || !providers_.has_keyword_provider();
1484 if (is_primary_provider && use_aggressive_method) {
1485 // Searches with the past two days get a different curve.
1486 const double autocomplete_time = 2 * 24 * 60 * 60;
1487 if (elapsed_time < autocomplete_time) {
1488 int max_score = is_keyword ? 1599 : 1399;
1489 if (prevent_search_history_inlining)
1491 return max_score - static_cast<int>(99 *
1492 std::pow(elapsed_time / autocomplete_time, 2.5));
1494 elapsed_time -= autocomplete_time;
1497 const int score_discount =
1498 static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
1500 // Don't let scores go below 0. Negative relevance scores are meaningful in
1503 if (is_primary_provider)
1504 base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050;
1507 return std::max(0, base_score - score_discount);
1510 AutocompleteMatch SearchProvider::NavigationToMatch(
1511 const NavigationResult& navigation) {
1512 const base::string16& input = navigation.from_keyword_provider() ?
1513 keyword_input_.text() : input_.text();
1514 AutocompleteMatch match(this, navigation.relevance(), false,
1515 AutocompleteMatchType::NAVSUGGEST);
1516 match.destination_url = navigation.url();
1518 // First look for the user's input inside the formatted url as it would be
1519 // without trimming the scheme, so we can find matches at the beginning of the
1521 const URLPrefix* prefix =
1522 URLPrefix::BestURLPrefix(navigation.formatted_url(), input);
1523 size_t match_start = (prefix == NULL) ?
1524 navigation.formatted_url().find(input) : prefix->prefix.length();
1525 bool trim_http = !AutocompleteInput::HasHTTPScheme(input) &&
1526 (!prefix || (match_start != 0));
1527 const net::FormatUrlTypes format_types =
1528 net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP);
1530 const std::string languages(
1531 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
1532 size_t inline_autocomplete_offset = (prefix == NULL) ?
1533 base::string16::npos : (match_start + input.length());
1534 match.fill_into_edit +=
1535 AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url(),
1536 net::FormatUrl(navigation.url(), languages, format_types,
1537 net::UnescapeRule::SPACES, NULL, NULL,
1538 &inline_autocomplete_offset));
1539 // Preserve the forced query '?' prefix in |match.fill_into_edit|.
1540 // Otherwise, user edits to a suggestion would show non-Search results.
1541 if (input_.type() == AutocompleteInput::FORCED_QUERY) {
1542 match.fill_into_edit.insert(0, base::ASCIIToUTF16("?"));
1543 if (inline_autocomplete_offset != base::string16::npos)
1544 ++inline_autocomplete_offset;
1546 if (inline_autocomplete_offset != base::string16::npos) {
1547 DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1548 match.inline_autocompletion =
1549 match.fill_into_edit.substr(inline_autocomplete_offset);
1551 // An inlineable navsuggestion can only be the default match when there
1552 // is no keyword provider active, lest it appear first and break the user
1553 // out of keyword mode. It can also only be default when we're not
1554 // preventing inline autocompletion (unless the inline autocompletion
1556 match.allowed_to_be_default_match = navigation.IsInlineable(input) &&
1557 (providers_.GetKeywordProviderURL() == NULL) &&
1558 (!input_.prevent_inline_autocomplete() ||
1559 match.inline_autocompletion.empty());
1561 match.contents = navigation.match_contents();
1562 match.contents_class = navigation.match_contents_class();
1563 match.description = navigation.description();
1564 AutocompleteMatch::ClassifyMatchInString(input, match.description,
1565 ACMatchClassification::NONE, &match.description_class);
1567 match.RecordAdditionalInfo(
1568 kRelevanceFromServerKey,
1569 navigation.relevance_from_server() ? kTrue : kFalse);
1570 match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse);
1575 void SearchProvider::DemoteKeywordNavigationMatchesPastTopQuery() {
1576 // First, determine the maximum score of any keyword query match (verbatim or
1577 // query suggestion).
1578 bool relevance_from_server;
1579 int max_query_relevance = GetKeywordVerbatimRelevance(&relevance_from_server);
1580 if (!keyword_results_.suggest_results.empty()) {
1581 const SuggestResult& top_keyword = keyword_results_.suggest_results.front();
1582 const int suggest_relevance = top_keyword.relevance();
1583 if (suggest_relevance > max_query_relevance) {
1584 max_query_relevance = suggest_relevance;
1585 relevance_from_server = top_keyword.relevance_from_server();
1586 } else if (suggest_relevance == max_query_relevance) {
1587 relevance_from_server |= top_keyword.relevance_from_server();
1590 // If no query is supposed to appear, then navigational matches cannot
1591 // be demoted past it. Get rid of suggested relevance scores for
1592 // navsuggestions and introduce the verbatim results again. The keyword
1593 // verbatim match will outscore the navsuggest matches.
1594 if (max_query_relevance == 0) {
1595 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
1596 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
1597 keyword_results_.verbatim_relevance = -1;
1598 default_results_.verbatim_relevance = -1;
1601 // Now we know we can enforce the minimum score constraint even after
1602 // the navigation matches are demoted. Proceed to demote the navigation
1603 // matches to enforce the query-must-come-first constraint.
1604 // Cap the relevance score of all results.
1605 for (NavigationResults::iterator it =
1606 keyword_results_.navigation_results.begin();
1607 it != keyword_results_.navigation_results.end(); ++it) {
1608 if (it->relevance() < max_query_relevance)
1610 max_query_relevance = std::max(max_query_relevance - 1, 0);
1611 it->set_relevance(max_query_relevance);
1612 it->set_relevance_from_server(relevance_from_server);
1616 void SearchProvider::UpdateDone() {
1617 // We're done when the timer isn't running, there are no suggest queries
1618 // pending, and we're not waiting on Instant.
1619 done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0);