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/string16.h"
19 #include "base/strings/string_util.h"
20 #include "base/strings/utf_string_conversions.h"
21 #include "chrome/browser/autocomplete/autocomplete_classifier.h"
22 #include "chrome/browser/autocomplete/autocomplete_classifier_factory.h"
23 #include "chrome/browser/autocomplete/autocomplete_match.h"
24 #include "chrome/browser/autocomplete/autocomplete_provider_listener.h"
25 #include "chrome/browser/autocomplete/autocomplete_result.h"
26 #include "chrome/browser/autocomplete/keyword_provider.h"
27 #include "chrome/browser/autocomplete/url_prefix.h"
28 #include "chrome/browser/history/history_service.h"
29 #include "chrome/browser/history/history_service_factory.h"
30 #include "chrome/browser/history/in_memory_database.h"
31 #include "chrome/browser/metrics/variations/variations_http_header_provider.h"
32 #include "chrome/browser/omnibox/omnibox_field_trial.h"
33 #include "chrome/browser/profiles/profile.h"
34 #include "chrome/browser/search/search.h"
35 #include "chrome/browser/search_engines/template_url_prepopulate_data.h"
36 #include "chrome/browser/search_engines/template_url_service.h"
37 #include "chrome/browser/search_engines/template_url_service_factory.h"
38 #include "chrome/browser/ui/browser.h"
39 #include "chrome/browser/ui/browser_finder.h"
40 #include "chrome/browser/ui/browser_instant_controller.h"
41 #include "chrome/browser/ui/search/instant_controller.h"
42 #include "chrome/common/net/url_fixer_upper.h"
43 #include "chrome/common/pref_names.h"
44 #include "chrome/common/url_constants.h"
45 #include "grit/generated_resources.h"
46 #include "net/base/escape.h"
47 #include "net/base/load_flags.h"
48 #include "net/base/net_util.h"
49 #include "net/http/http_request_headers.h"
50 #include "net/http/http_response_headers.h"
51 #include "net/url_request/url_fetcher.h"
52 #include "net/url_request/url_request_status.h"
53 #include "ui/base/l10n/l10n_util.h"
54 #include "url/url_util.h"
57 // Helpers --------------------------------------------------------------------
61 // We keep track in a histogram how many suggest requests we send, how
62 // many suggest requests we invalidate (e.g., due to a user typing
63 // another character), and how many replies we receive.
64 // *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! ***
65 // (excluding the end-of-list enum value)
66 // We do not want values of existing enums to change or else it screws
68 enum SuggestRequestsHistogramValue {
72 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE
75 // The verbatim score for an input which is not an URL.
76 const int kNonURLVerbatimRelevance = 1300;
78 // Increments the appropriate value in the histogram by one.
79 void LogOmniboxSuggestRequest(
80 SuggestRequestsHistogramValue request_value) {
81 UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value,
82 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE);
85 bool HasMultipleWords(const string16& text) {
86 base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD);
87 bool found_word = false;
100 // Builds the match contents and classification for the contents, and updates
101 // the given |AutocompleteMatch|.
102 void SetAndClassifyMatchContents(const string16& query_string,
103 const string16& input_text,
104 const string16& match_contents,
105 const string16& annotation,
106 AutocompleteMatch* match) {
107 size_t match_contents_start = 0;
108 size_t annotation_start = match_contents.size();
109 // Append annotation if present.
110 if (annotation.empty()) {
111 match->contents = match_contents;
113 std::vector<size_t> positions;
114 match->contents = l10n_util::GetStringFUTF16(
115 IDS_ANNOTATED_SUGGESTION, match_contents, annotation, &positions);
116 match_contents_start = positions[0];
117 annotation_start = positions[1];
119 size_t match_contents_end = match_contents_start + match_contents.size();
121 if (!annotation.empty() && (annotation_start < match_contents_start))
122 match->contents_class.push_back(ACMatchClassification(
123 annotation_start, ACMatchClassification::DIM));
125 // We do intra-string highlighting for suggestions - the suggested segment
126 // will be highlighted, e.g. for input_text = "you" the suggestion may be
127 // "youtube", so we'll bold the "tube" section: you*tube*.
128 if (input_text != match_contents) {
129 size_t input_position = match->contents.substr(
130 match_contents_start, match_contents.length()).find(input_text);
131 if (input_position == string16::npos) {
132 // The input text is not a substring of the query string, e.g. input
133 // text is "slasdot" and the query string is "slashdot", so we bold the
135 match->contents_class.push_back(ACMatchClassification(
136 match_contents_start, ACMatchClassification::MATCH));
138 input_position += match_contents_start;
140 // TODO(beng): ACMatchClassification::MATCH now seems to just mean
141 // "bold" this. Consider modifying the terminology.
142 // We don't iterate over the string here annotating all matches because
143 // it looks odd to have every occurrence of a substring that may be as
144 // short as a single character highlighted in a query suggestion result,
145 // e.g. for input text "s" and query string "southwest airlines", it
146 // looks odd if both the first and last s are highlighted.
147 if (input_position != match_contents_start) {
148 match->contents_class.push_back(ACMatchClassification(
149 match_contents_start, ACMatchClassification::MATCH));
151 match->contents_class.push_back(
152 ACMatchClassification(input_position, ACMatchClassification::NONE));
153 size_t next_fragment_position = input_position + input_text.length();
154 if (next_fragment_position < query_string.length()) {
155 match->contents_class.push_back(ACMatchClassification(
156 next_fragment_position, ACMatchClassification::MATCH));
160 // Otherwise, |match| is a verbatim (what-you-typed) match, either for the
161 // default provider or a keyword search provider.
162 match->contents_class.push_back(ACMatchClassification(
163 match_contents_start, ACMatchClassification::NONE));
166 if (!annotation.empty() && (annotation_start >= match_contents_start))
167 match->contents_class.push_back(ACMatchClassification(
168 match_contents_end, ACMatchClassification::DIM));
174 // SearchProvider::Providers --------------------------------------------------
176 SearchProvider::Providers::Providers(TemplateURLService* template_url_service)
177 : template_url_service_(template_url_service) {
180 const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const {
181 return default_provider_.empty() ? NULL :
182 template_url_service_->GetTemplateURLForKeyword(default_provider_);
185 const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
186 return keyword_provider_.empty() ? NULL :
187 template_url_service_->GetTemplateURLForKeyword(keyword_provider_);
191 // SearchProvider::Result -----------------------------------------------------
193 SearchProvider::Result::Result(bool from_keyword_provider,
195 bool relevance_from_server)
196 : from_keyword_provider_(from_keyword_provider),
197 relevance_(relevance),
198 relevance_from_server_(relevance_from_server) {
201 SearchProvider::Result::~Result() {
205 // SearchProvider::SuggestResult ----------------------------------------------
207 SearchProvider::SuggestResult::SuggestResult(
208 const string16& suggestion,
209 const string16& match_contents,
210 const string16& annotation,
211 const std::string& suggest_query_params,
212 bool from_keyword_provider,
214 bool relevance_from_server,
215 bool should_prefetch)
216 : Result(from_keyword_provider, relevance, relevance_from_server),
217 suggestion_(suggestion),
218 match_contents_(match_contents),
219 annotation_(annotation),
220 suggest_query_params_(suggest_query_params),
221 should_prefetch_(should_prefetch) {
224 SearchProvider::SuggestResult::~SuggestResult() {
227 bool SearchProvider::SuggestResult::IsInlineable(const string16& input) const {
228 return StartsWith(suggestion_, input, false);
231 int SearchProvider::SuggestResult::CalculateRelevance(
232 const AutocompleteInput& input,
233 bool keyword_provider_requested) const {
234 if (!from_keyword_provider_ && keyword_provider_requested)
236 return ((input.type() == AutocompleteInput::URL) ? 300 : 600);
240 // SearchProvider::NavigationResult -------------------------------------------
242 SearchProvider::NavigationResult::NavigationResult(
243 const AutocompleteProvider& provider,
245 const string16& description,
246 bool from_keyword_provider,
248 bool relevance_from_server)
249 : Result(from_keyword_provider, relevance, relevance_from_server),
251 formatted_url_(AutocompleteInput::FormattedStringWithEquivalentMeaning(
252 url, provider.StringForURLDisplay(url, true, false))),
253 description_(description) {
254 DCHECK(url_.is_valid());
257 SearchProvider::NavigationResult::~NavigationResult() {
260 bool SearchProvider::NavigationResult::IsInlineable(
261 const string16& input) const {
262 return URLPrefix::BestURLPrefix(formatted_url_, input) != NULL;
265 int SearchProvider::NavigationResult::CalculateRelevance(
266 const AutocompleteInput& input,
267 bool keyword_provider_requested) const {
268 return (from_keyword_provider_ || !keyword_provider_requested) ? 800 : 150;
272 // SearchProvider::CompareScoredResults ---------------------------------------
274 class SearchProvider::CompareScoredResults {
276 bool operator()(const Result& a, const Result& b) {
277 // Sort in descending relevance order.
278 return a.relevance() > b.relevance();
283 // SearchProvider::Results ----------------------------------------------------
285 SearchProvider::Results::Results() : verbatim_relevance(-1) {
288 SearchProvider::Results::~Results() {
291 void SearchProvider::Results::Clear() {
292 suggest_results.clear();
293 navigation_results.clear();
294 verbatim_relevance = -1;
298 bool SearchProvider::Results::HasServerProvidedScores() const {
299 if (verbatim_relevance >= 0)
302 // Right now either all results of one type will be server-scored or they will
303 // all be locally scored, but in case we change this later, we'll just check
305 for (SuggestResults::const_iterator i(suggest_results.begin());
306 i != suggest_results.end(); ++i) {
307 if (i->relevance_from_server())
310 for (NavigationResults::const_iterator i(navigation_results.begin());
311 i != navigation_results.end(); ++i) {
312 if (i->relevance_from_server())
320 // SearchProvider -------------------------------------------------------------
323 const int SearchProvider::kDefaultProviderURLFetcherID = 1;
324 const int SearchProvider::kKeywordProviderURLFetcherID = 2;
325 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
326 const char SearchProvider::kRelevanceFromServerKey[] = "relevance_from_server";
327 const char SearchProvider::kShouldPrefetchKey[] = "should_prefetch";
328 const char SearchProvider::kSuggestMetadataKey[] = "suggest_metadata";
329 const char SearchProvider::kTrue[] = "true";
330 const char SearchProvider::kFalse[] = "false";
332 SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
334 : AutocompleteProvider(listener, profile,
335 AutocompleteProvider::TYPE_SEARCH),
336 providers_(TemplateURLServiceFactory::GetForProfile(profile)),
337 suggest_results_pending_(0),
338 field_trial_triggered_(false),
339 field_trial_triggered_in_session_(false) {
343 AutocompleteMatch SearchProvider::CreateSearchSuggestion(
344 AutocompleteProvider* autocomplete_provider,
345 const AutocompleteInput& input,
346 const string16& input_text,
348 AutocompleteMatch::Type type,
350 const string16& match_contents,
351 const string16& annotation,
352 const TemplateURL* template_url,
353 const string16& query_string,
354 const std::string& suggest_query_params,
355 int accepted_suggestion,
356 int omnibox_start_margin,
357 bool append_extra_query_params) {
358 AutocompleteMatch match(autocomplete_provider, relevance, false, type);
362 match.keyword = template_url->keyword();
364 SetAndClassifyMatchContents(
365 query_string, input_text, match_contents, annotation, &match);
367 match.allowed_to_be_default_match = (input_text == match_contents);
369 // When the user forced a query, we need to make sure all the fill_into_edit
370 // values preserve that property. Otherwise, if the user starts editing a
371 // suggestion, non-Search results will suddenly appear.
372 if (input.type() == AutocompleteInput::FORCED_QUERY)
373 match.fill_into_edit.assign(ASCIIToUTF16("?"));
375 match.fill_into_edit.append(match.keyword + char16(' '));
376 if (!input.prevent_inline_autocomplete() &&
377 StartsWith(query_string, input_text, false)) {
378 match.inline_autocompletion = query_string.substr(input_text.length());
379 match.allowed_to_be_default_match = true;
381 match.fill_into_edit.append(query_string);
383 const TemplateURLRef& search_url = template_url->url_ref();
384 DCHECK(search_url.SupportsReplacement());
385 match.search_terms_args.reset(
386 new TemplateURLRef::SearchTermsArgs(query_string));
387 match.search_terms_args->original_query = input_text;
388 match.search_terms_args->accepted_suggestion = accepted_suggestion;
389 match.search_terms_args->omnibox_start_margin = omnibox_start_margin;
390 match.search_terms_args->suggest_query_params = suggest_query_params;
391 match.search_terms_args->append_extra_query_params =
392 append_extra_query_params;
393 // This is the destination URL sans assisted query stats. This must be set
394 // so the AutocompleteController can properly de-dupe; the controller will
395 // eventually overwrite it before it reaches the user.
396 match.destination_url =
397 GURL(search_url.ReplaceSearchTerms(*match.search_terms_args.get()));
399 // Search results don't look like URLs.
400 match.transition = is_keyword ?
401 content::PAGE_TRANSITION_KEYWORD : content::PAGE_TRANSITION_GENERATED;
407 bool SearchProvider::ShouldPrefetch(const AutocompleteMatch& match) {
408 return match.GetAdditionalInfo(kShouldPrefetchKey) == kTrue;
412 std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) {
413 return match.GetAdditionalInfo(kSuggestMetadataKey);
416 void SearchProvider::AddProviderInfo(ProvidersInfo* provider_info) const {
417 provider_info->push_back(metrics::OmniboxEventProto_ProviderInfo());
418 metrics::OmniboxEventProto_ProviderInfo& new_entry = provider_info->back();
419 new_entry.set_provider(AsOmniboxEventProviderType());
420 new_entry.set_provider_done(done_);
421 std::vector<uint32> field_trial_hashes;
422 OmniboxFieldTrial::GetActiveSuggestFieldTrialHashes(&field_trial_hashes);
423 for (size_t i = 0; i < field_trial_hashes.size(); ++i) {
424 if (field_trial_triggered_)
425 new_entry.mutable_field_trial_triggered()->Add(field_trial_hashes[i]);
426 if (field_trial_triggered_in_session_) {
427 new_entry.mutable_field_trial_triggered_in_session()->Add(
428 field_trial_hashes[i]);
433 void SearchProvider::ResetSession() {
434 field_trial_triggered_in_session_ = false;
437 SearchProvider::~SearchProvider() {
441 void SearchProvider::RemoveStaleResults(const string16& input,
442 int verbatim_relevance,
443 SuggestResults* suggest_results,
444 NavigationResults* navigation_results) {
445 DCHECK_GE(verbatim_relevance, 0);
446 // Keep pointers to the head of (the highest scoring elements of)
447 // |suggest_results| and |navigation_results|. Iterate down the lists
448 // removing non-inlineable results in order of decreasing relevance
449 // scores. Stop when the highest scoring element among those remaining
450 // is inlineable or the element is less than |verbatim_relevance|.
451 // This allows non-inlineable lower-scoring results to remain
452 // because (i) they are guaranteed to not be inlined and (ii)
453 // letting them remain reduces visual jank. For instance, as the
454 // user types the mis-spelled query "fpobar" (for foobar), the
455 // suggestion "foobar" will be suggested on every keystroke. If the
456 // SearchProvider always removes all non-inlineable results, the user will
457 // see visual jitter/jank as the result disappears and re-appears moments
458 // later as the suggest server returns results.
459 SuggestResults::iterator sug_it = suggest_results->begin();
460 NavigationResults::iterator nav_it = navigation_results->begin();
461 while ((sug_it != suggest_results->end()) ||
462 (nav_it != navigation_results->end())) {
464 (sug_it != suggest_results->end()) ? sug_it->relevance() : -1;
466 (nav_it != navigation_results->end()) ? nav_it->relevance() : -1;
467 if (std::max(sug_rel, nav_rel) < verbatim_relevance)
469 if (sug_rel > nav_rel) {
470 // The current top result is a search suggestion.
471 if (sug_it->IsInlineable(input))
473 sug_it = suggest_results->erase(sug_it);
474 } else if (sug_rel == nav_rel) {
475 // Have both results and they're tied.
476 const bool sug_inlineable = sug_it->IsInlineable(input);
477 const bool nav_inlineable = nav_it->IsInlineable(input);
479 sug_it = suggest_results->erase(sug_it);
481 nav_it = navigation_results->erase(nav_it);
482 if (sug_inlineable || nav_inlineable)
485 // The current top result is a navigational suggestion.
486 if (nav_it->IsInlineable(input))
488 nav_it = navigation_results->erase(nav_it);
494 int SearchProvider::CalculateRelevanceForKeywordVerbatim(
495 AutocompleteInput::Type type,
496 bool prefer_keyword) {
497 // This function is responsible for scoring verbatim query matches
498 // for non-extension keywords. KeywordProvider::CalculateRelevance()
499 // scores verbatim query matches for extension keywords, as well as
500 // for keyword matches (i.e., suggestions of a keyword itself, not a
501 // suggestion of a query on a keyword search engine). These two
502 // functions are currently in sync, but there's no reason we
503 // couldn't decide in the future to score verbatim matches
504 // differently for extension and non-extension keywords. If you
505 // make such a change, however, you should update this comment to
506 // describe it, so it's clear why the functions diverge.
509 return (type == AutocompleteInput::QUERY) ? 1450 : 1100;
512 void SearchProvider::Start(const AutocompleteInput& input,
513 bool minimal_changes) {
514 // Do our best to load the model as early as possible. This will reduce
515 // odds of having the model not ready when really needed (a non-empty input).
516 TemplateURLService* model = providers_.template_url_service();
521 field_trial_triggered_ = false;
523 // Can't return search/suggest results for bogus input or without a profile.
524 if (!profile_ || (input.type() == AutocompleteInput::INVALID)) {
529 keyword_input_ = input;
530 const TemplateURL* keyword_provider =
531 KeywordProvider::GetSubstitutingTemplateURLForInput(model,
533 if (keyword_provider == NULL)
534 keyword_input_.Clear();
535 else if (keyword_input_.text().empty())
536 keyword_provider = NULL;
538 const TemplateURL* default_provider = model->GetDefaultSearchProvider();
539 if (default_provider && !default_provider->SupportsReplacement())
540 default_provider = NULL;
542 if (keyword_provider == default_provider)
543 default_provider = NULL; // No use in querying the same provider twice.
545 if (!default_provider && !keyword_provider) {
546 // No valid providers.
551 // If we're still running an old query but have since changed the query text
552 // or the providers, abort the query.
553 string16 default_provider_keyword(default_provider ?
554 default_provider->keyword() : string16());
555 string16 keyword_provider_keyword(keyword_provider ?
556 keyword_provider->keyword() : string16());
557 if (!minimal_changes ||
558 !providers_.equal(default_provider_keyword, keyword_provider_keyword)) {
559 // Cancel any in-flight suggest requests.
564 providers_.set(default_provider_keyword, keyword_provider_keyword);
566 if (input.text().empty()) {
567 // User typed "?" alone. Give them a placeholder result indicating what
569 if (default_provider) {
570 AutocompleteMatch match;
571 match.provider = this;
572 match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
573 match.contents_class.push_back(
574 ACMatchClassification(0, ACMatchClassification::NONE));
575 match.keyword = providers_.default_provider();
576 match.allowed_to_be_default_match = true;
577 matches_.push_back(match);
585 DoHistoryQuery(minimal_changes);
586 StartOrStopSuggestQuery(minimal_changes);
590 void SearchProvider::Stop(bool clear_cached_results) {
594 if (clear_cached_results)
598 void SearchProvider::OnURLFetchComplete(const net::URLFetcher* source) {
600 suggest_results_pending_--;
601 LogOmniboxSuggestRequest(REPLY_RECEIVED);
602 DCHECK_GE(suggest_results_pending_, 0); // Should never go negative.
604 const bool is_keyword = (source == keyword_fetcher_.get());
605 // Ensure the request succeeded and that the provider used is still available.
606 // A verbatim match cannot be generated without this provider, causing errors.
607 const bool request_succeeded =
608 source->GetStatus().is_success() && (source->GetResponseCode() == 200) &&
610 providers_.GetKeywordProviderURL() :
611 providers_.GetDefaultProviderURL());
613 // Record response time for suggest requests sent to Google. We care
614 // only about the common case: the Google default provider used in
616 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
617 if (!is_keyword && default_url &&
618 (TemplateURLPrepopulateData::GetEngineType(*default_url) ==
619 SEARCH_ENGINE_GOOGLE)) {
620 const base::TimeDelta elapsed_time =
621 base::TimeTicks::Now() - time_suggest_request_sent_;
622 if (request_succeeded) {
623 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
626 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
631 bool results_updated = false;
632 if (request_succeeded) {
633 const net::HttpResponseHeaders* const response_headers =
634 source->GetResponseHeaders();
635 std::string json_data;
636 source->GetResponseAsString(&json_data);
637 // JSON is supposed to be UTF-8, but some suggest service providers send
638 // JSON files in non-UTF-8 encodings. The actual encoding is usually
639 // specified in the Content-Type header field.
640 if (response_headers) {
642 if (response_headers->GetCharset(&charset)) {
644 // TODO(jungshik): Switch to CodePageToUTF8 after it's added.
645 if (base::CodepageToUTF16(json_data, charset.c_str(),
646 base::OnStringConversionError::FAIL,
648 json_data = UTF16ToUTF8(data_16);
652 // The JSON response should be an array.
653 for (size_t response_start_index = json_data.find("["), i = 0;
654 response_start_index != std::string::npos && i < 5;
655 response_start_index = json_data.find("[", 1), i++) {
656 // Remove any XSSI guards to allow for JSON parsing.
657 if (response_start_index > 0)
658 json_data.erase(0, response_start_index);
660 JSONStringValueSerializer deserializer(json_data);
661 deserializer.set_allow_trailing_comma(true);
663 scoped_ptr<Value> data(deserializer.Deserialize(&error_code, NULL));
664 if (error_code == 0) {
665 results_updated = data.get() &&
666 ParseSuggestResults(data.get(), is_keyword);
673 if (done_ || results_updated)
674 listener_->OnProviderUpdate(results_updated);
677 void SearchProvider::Run() {
678 // Start a new request with the current input.
679 suggest_results_pending_ = 0;
680 time_suggest_request_sent_ = base::TimeTicks::Now();
682 default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
683 providers_.GetDefaultProviderURL(), input_));
684 keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID,
685 providers_.GetKeywordProviderURL(), keyword_input_));
687 // Both the above can fail if the providers have been modified or deleted
688 // since the query began.
689 if (suggest_results_pending_ == 0) {
691 // We only need to update the listener if we're actually done.
693 listener_->OnProviderUpdate(false);
697 void SearchProvider::DoHistoryQuery(bool minimal_changes) {
698 // The history query results are synchronous, so if minimal_changes is true,
699 // we still have the last results and don't need to do anything.
703 base::TimeTicks do_history_query_start_time(base::TimeTicks::Now());
705 keyword_history_results_.clear();
706 default_history_results_.clear();
708 if (OmniboxFieldTrial::SearchHistoryDisable(
709 input_.current_page_classification()))
712 base::TimeTicks start_time(base::TimeTicks::Now());
713 HistoryService* const history_service =
714 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
715 base::TimeTicks now(base::TimeTicks::Now());
716 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.GetHistoryServiceTime",
719 history::URLDatabase* url_db = history_service ?
720 history_service->InMemoryDatabase() : NULL;
721 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.InMemoryDatabaseTime",
722 base::TimeTicks::Now() - start_time);
726 // Request history for both the keyword and default provider. We grab many
727 // more matches than we'll ultimately clamp to so that if there are several
728 // recent multi-word matches who scores are lowered (see
729 // AddHistoryResultsToMap()), they won't crowd out older, higher-scoring
730 // matches. Note that this doesn't fix the problem entirely, but merely
731 // limits it to cases with a very large number of such multi-word matches; for
732 // now, this seems OK compared with the complexity of a real fix, which would
733 // require multiple searches and tracking of "single- vs. multi-word" in the
735 int num_matches = kMaxMatches * 5;
736 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
738 start_time = base::TimeTicks::Now();
739 url_db->GetMostRecentKeywordSearchTerms(default_url->id(), input_.text(),
740 num_matches, &default_history_results_);
742 "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime",
743 base::TimeTicks::Now() - start_time);
745 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
747 url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(),
748 keyword_input_.text(), num_matches, &keyword_history_results_);
750 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.DoHistoryQueryTime",
751 base::TimeTicks::Now() - do_history_query_start_time);
754 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
755 if (!IsQuerySuitableForSuggest()) {
761 // For the minimal_changes case, if we finished the previous query and still
762 // have its results, or are allowed to keep running it, just do that, rather
763 // than starting a new query.
764 if (minimal_changes &&
765 (!default_results_.suggest_results.empty() ||
766 !default_results_.navigation_results.empty() ||
767 !keyword_results_.suggest_results.empty() ||
768 !keyword_results_.navigation_results.empty() ||
770 input_.matches_requested() == AutocompleteInput::ALL_MATCHES)))
773 // We can't keep running any previous query, so halt it.
776 // Remove existing results that cannot inline autocomplete the new input.
777 RemoveAllStaleResults();
779 // We can't start a new query if we're only allowed synchronous results.
780 if (input_.matches_requested() != AutocompleteInput::ALL_MATCHES)
783 // To avoid flooding the suggest server, don't send a query until at
784 // least 100 ms since the last query.
785 base::TimeTicks next_suggest_time(time_suggest_request_sent_ +
786 base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs));
787 base::TimeTicks now(base::TimeTicks::Now());
788 if (now >= next_suggest_time) {
792 timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run);
795 bool SearchProvider::IsQuerySuitableForSuggest() const {
796 // Don't run Suggest in incognito mode, if the engine doesn't support it, or
797 // if the user has disabled it.
798 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
799 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
800 if (profile_->IsOffTheRecord() ||
801 ((!default_url || default_url->suggestions_url().empty()) &&
802 (!keyword_url || keyword_url->suggestions_url().empty())) ||
803 !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled))
806 // If the input type might be a URL, we take extra care so that private data
807 // isn't sent to the server.
809 // FORCED_QUERY means the user is explicitly asking us to search for this, so
810 // we assume it isn't a URL and/or there isn't private data.
811 if (input_.type() == AutocompleteInput::FORCED_QUERY)
814 // Next we check the scheme. If this is UNKNOWN/URL with a scheme that isn't
815 // http/https/ftp, we shouldn't send it. Sending things like file: and data:
816 // is both a waste of time and a disclosure of potentially private, local
817 // data. Other "schemes" may actually be usernames, and we don't want to send
818 // passwords. If the scheme is OK, we still need to check other cases below.
819 // If this is QUERY, then the presence of these schemes means the user
820 // explicitly typed one, and thus this is probably a URL that's being entered
821 // and happens to currently be invalid -- in which case we again want to run
822 // our checks below. Other QUERY cases are less likely to be URLs and thus we
824 if (!LowerCaseEqualsASCII(input_.scheme(), content::kHttpScheme) &&
825 !LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
826 !LowerCaseEqualsASCII(input_.scheme(), chrome::kFtpScheme))
827 return (input_.type() == AutocompleteInput::QUERY);
829 // Don't send URLs with usernames, queries or refs. Some of these are
830 // private, and the Suggest server is unlikely to have any useful results
831 // for any of them. Also don't send URLs with ports, as we may initially
832 // think that a username + password is a host + port (and we don't want to
833 // send usernames/passwords), and even if the port really is a port, the
834 // server is once again unlikely to have and useful results.
835 // Note that we only block based on refs if the input is URL-typed, as search
836 // queries can legitimately have #s in them which the URL parser
837 // overaggressively categorizes as a url with a ref.
838 const url_parse::Parsed& parts = input_.parts();
839 if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
840 parts.query.is_nonempty() ||
841 (parts.ref.is_nonempty() && (input_.type() == AutocompleteInput::URL)))
844 // Don't send anything for https except the hostname. Hostnames are OK
845 // because they are visible when the TCP connection is established, but the
846 // specific path may reveal private information.
847 if (LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
848 parts.path.is_nonempty())
854 void SearchProvider::StopSuggest() {
855 // Increment the appropriate field in the histogram by the number of
856 // pending requests that were invalidated.
857 for (int i = 0; i < suggest_results_pending_; i++)
858 LogOmniboxSuggestRequest(REQUEST_INVALIDATED);
859 suggest_results_pending_ = 0;
861 // Stop any in-progress URL fetches.
862 keyword_fetcher_.reset();
863 default_fetcher_.reset();
866 void SearchProvider::ClearAllResults() {
867 keyword_results_.Clear();
868 default_results_.Clear();
871 void SearchProvider::RemoveAllStaleResults() {
872 // In theory it would be better to run an algorithm like that in
873 // RemoveStaleResults(...) below that uses all four results lists
874 // and both verbatim scores at once. However, that will be much
875 // more complicated for little obvious gain. For code simplicity
876 // and ease in reasoning about the invariants involved, this code
877 // removes stales results from the keyword provider and default
878 // provider independently.
879 RemoveStaleResults(input_.text(), GetVerbatimRelevance(NULL),
880 &default_results_.suggest_results,
881 &default_results_.navigation_results);
882 if (!keyword_input_.text().empty()) {
883 RemoveStaleResults(keyword_input_.text(), GetKeywordVerbatimRelevance(NULL),
884 &keyword_results_.suggest_results,
885 &keyword_results_.navigation_results);
887 // User is either in keyword mode with a blank input or out of
888 // keyword mode entirely.
889 keyword_results_.Clear();
893 void SearchProvider::ApplyCalculatedRelevance() {
894 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
895 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
896 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
897 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
898 default_results_.verbatim_relevance = -1;
899 keyword_results_.verbatim_relevance = -1;
902 void SearchProvider::ApplyCalculatedSuggestRelevance(SuggestResults* list) {
903 for (size_t i = 0; i < list->size(); ++i) {
904 SuggestResult& result = (*list)[i];
905 result.set_relevance(
906 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
907 (list->size() - i - 1));
908 result.set_relevance_from_server(false);
912 void SearchProvider::ApplyCalculatedNavigationRelevance(
913 NavigationResults* list) {
914 for (size_t i = 0; i < list->size(); ++i) {
915 NavigationResult& result = (*list)[i];
916 result.set_relevance(
917 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
918 (list->size() - i - 1));
919 result.set_relevance_from_server(false);
923 net::URLFetcher* SearchProvider::CreateSuggestFetcher(
925 const TemplateURL* template_url,
926 const AutocompleteInput& input) {
927 if (!template_url || template_url->suggestions_url().empty())
930 // Bail if the suggestion URL is invalid with the given replacements.
931 TemplateURLRef::SearchTermsArgs search_term_args(input.text());
932 search_term_args.cursor_position = input.cursor_position();
933 search_term_args.page_classification = input.current_page_classification();
934 GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
936 if (!suggest_url.is_valid())
939 suggest_results_pending_++;
940 LogOmniboxSuggestRequest(REQUEST_SENT);
942 net::URLFetcher* fetcher =
943 net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this);
944 fetcher->SetRequestContext(profile_->GetRequestContext());
945 fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES);
946 // Add Chrome experiment state to the request headers.
947 net::HttpRequestHeaders headers;
948 chrome_variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders(
949 fetcher->GetOriginalURL(), profile_->IsOffTheRecord(), false, &headers);
950 fetcher->SetExtraRequestHeaders(headers.ToString());
955 bool SearchProvider::ParseSuggestResults(Value* root_val, bool is_keyword) {
957 ListValue* root_list = NULL;
958 ListValue* results_list = NULL;
959 const string16& input_text =
960 is_keyword ? keyword_input_.text() : input_.text();
961 if (!root_val->GetAsList(&root_list) || !root_list->GetString(0, &query) ||
962 (query != input_text) || !root_list->GetList(1, &results_list))
965 // 3rd element: Description list.
966 ListValue* descriptions = NULL;
967 root_list->GetList(2, &descriptions);
969 // 4th element: Disregard the query URL list for now.
971 // Reset suggested relevance information from the default provider.
972 Results* results = is_keyword ? &keyword_results_ : &default_results_;
973 results->verbatim_relevance = -1;
975 // 5th element: Optional key-value pairs from the Suggest server.
976 ListValue* types = NULL;
977 ListValue* relevances = NULL;
978 ListValue* suggestion_details = NULL;
979 DictionaryValue* extras = NULL;
980 int prefetch_index = -1;
981 if (root_list->GetDictionary(4, &extras)) {
982 extras->GetList("google:suggesttype", &types);
984 // Discard this list if its size does not match that of the suggestions.
985 if (extras->GetList("google:suggestrelevance", &relevances) &&
986 (relevances->GetSize() != results_list->GetSize()))
988 extras->GetInteger("google:verbatimrelevance",
989 &results->verbatim_relevance);
991 // Check if the active suggest field trial (if any) has triggered either
992 // for the default provider or keyword provider.
993 bool triggered = false;
994 extras->GetBoolean("google:fieldtrialtriggered", &triggered);
995 field_trial_triggered_ |= triggered;
996 field_trial_triggered_in_session_ |= triggered;
998 DictionaryValue* client_data = NULL;
999 if (extras->GetDictionary("google:clientdata", &client_data) && client_data)
1000 client_data->GetInteger("phi", &prefetch_index);
1002 if (extras->GetList("google:suggestdetail", &suggestion_details) &&
1003 suggestion_details->GetSize() != results_list->GetSize())
1004 suggestion_details = NULL;
1006 // Store the metadata that came with the response in case we need to pass it
1007 // along with the prefetch query to Instant.
1008 JSONStringValueSerializer json_serializer(&results->metadata);
1009 json_serializer.Serialize(*extras);
1012 // Clear the previous results now that new results are available.
1013 results->suggest_results.clear();
1014 results->navigation_results.clear();
1016 string16 suggestion;
1019 for (size_t index = 0; results_list->GetString(index, &suggestion); ++index) {
1020 // Google search may return empty suggestions for weird input characters,
1021 // they make no sense at all and can cause problems in our code.
1022 if (suggestion.empty())
1025 // Apply valid suggested relevance scores; discard invalid lists.
1026 if (relevances != NULL && !relevances->GetInteger(index, &relevance))
1028 if (types && types->GetString(index, &type) && (type == "NAVIGATION")) {
1029 // Do not blindly trust the URL coming from the server to be valid.
1030 GURL url(URLFixerUpper::FixupURL(UTF16ToUTF8(suggestion), std::string()));
1031 if (url.is_valid()) {
1033 if (descriptions != NULL)
1034 descriptions->GetString(index, &title);
1035 results->navigation_results.push_back(NavigationResult(
1036 *this, url, title, is_keyword, relevance, true));
1039 bool should_prefetch = static_cast<int>(index) == prefetch_index;
1040 DictionaryValue* suggestion_detail = NULL;
1041 string16 match_contents = suggestion;
1042 string16 disambiguating_query;
1043 string16 annotation;
1044 std::string suggest_query_params;
1045 if (suggestion_details && (type == "ENTITY") &&
1046 suggestion_details->GetDictionary(index, &suggestion_detail) &&
1047 suggestion_detail) {
1048 suggestion_detail->GetString("a", &annotation);
1049 if (suggestion_detail->GetString("dq", &disambiguating_query) &&
1050 !disambiguating_query.empty())
1051 suggestion = disambiguating_query;
1052 suggestion_detail->GetString("q", &suggest_query_params);
1054 // TODO(kochi): Improve calculator suggestion presentation.
1055 results->suggest_results.push_back(SuggestResult(
1056 suggestion, match_contents, annotation, suggest_query_params,
1057 is_keyword, relevance, true, should_prefetch));
1061 // Apply calculated relevance scores if a valid list was not provided.
1062 if (relevances == NULL) {
1063 ApplyCalculatedSuggestRelevance(&results->suggest_results);
1064 ApplyCalculatedNavigationRelevance(&results->navigation_results);
1066 // Keep the result lists sorted.
1067 const CompareScoredResults comparator = CompareScoredResults();
1068 std::stable_sort(results->suggest_results.begin(),
1069 results->suggest_results.end(),
1071 std::stable_sort(results->navigation_results.begin(),
1072 results->navigation_results.end(),
1077 void SearchProvider::ConvertResultsToAutocompleteMatches() {
1078 // Convert all the results to matches and add them to a map, so we can keep
1079 // the most relevant match for each result.
1080 base::TimeTicks start_time(base::TimeTicks::Now());
1082 const base::Time no_time;
1083 int did_not_accept_keyword_suggestion =
1084 keyword_results_.suggest_results.empty() ?
1085 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
1086 TemplateURLRef::NO_SUGGESTION_CHOSEN;
1088 bool relevance_from_server;
1089 int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
1090 int did_not_accept_default_suggestion =
1091 default_results_.suggest_results.empty() ?
1092 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
1093 TemplateURLRef::NO_SUGGESTION_CHOSEN;
1094 if (verbatim_relevance > 0) {
1095 AddMatchToMap(input_.text(),
1097 relevance_from_server,
1100 AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
1105 did_not_accept_default_suggestion,
1109 if (!keyword_input_.text().empty()) {
1110 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1111 // We only create the verbatim search query match for a keyword
1112 // if it's not an extension keyword. Extension keywords are handled
1113 // in KeywordProvider::Start(). (Extensions are complicated...)
1114 // Note: in this provider, SEARCH_OTHER_ENGINE must correspond
1115 // to the keyword verbatim search query. Do not create other matches
1116 // of type SEARCH_OTHER_ENGINE.
1118 (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
1119 bool keyword_relevance_from_server;
1120 const int keyword_verbatim_relevance =
1121 GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
1122 if (keyword_verbatim_relevance > 0) {
1123 AddMatchToMap(keyword_input_.text(),
1124 keyword_verbatim_relevance,
1125 keyword_relevance_from_server,
1128 AutocompleteMatchType::SEARCH_OTHER_ENGINE,
1130 keyword_input_.text(),
1132 keyword_input_.text(),
1133 did_not_accept_keyword_suggestion,
1139 AddHistoryResultsToMap(keyword_history_results_, true,
1140 did_not_accept_keyword_suggestion, &map);
1141 AddHistoryResultsToMap(default_history_results_, false,
1142 did_not_accept_default_suggestion, &map);
1144 AddSuggestResultsToMap(keyword_results_.suggest_results,
1145 keyword_results_.metadata, &map);
1146 AddSuggestResultsToMap(default_results_.suggest_results,
1147 default_results_.metadata, &map);
1150 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
1151 matches.push_back(i->second);
1153 AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
1154 AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
1156 // Now add the most relevant matches to |matches_|. We take up to kMaxMatches
1157 // suggest/navsuggest matches, regardless of origin. If Instant Extended is
1158 // enabled and we have server-provided (and thus hopefully more accurate)
1159 // scores for some suggestions, we allow more of those, until we reach
1160 // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
1163 // We will always return any verbatim matches, no matter how we obtained their
1164 // scores, unless we have already accepted AutocompleteResult::kMaxMatches
1165 // higher-scoring matches under the conditions above.
1166 UMA_HISTOGRAM_CUSTOM_COUNTS(
1167 "Omnibox.SearchProvider.NumMatchesToSort", matches.size(), 1, 50, 20);
1168 std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
1171 size_t num_suggestions = 0;
1172 for (ACMatches::const_iterator i(matches.begin());
1173 (i != matches.end()) &&
1174 (matches_.size() < AutocompleteResult::kMaxMatches);
1176 // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
1177 // verbatim result, so this condition basically means "if this match is a
1178 // suggestion of some sort".
1179 if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
1180 (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
1181 // If we've already hit the limit on non-server-scored suggestions, and
1182 // this isn't a server-scored suggestion we can add, skip it.
1183 if ((num_suggestions >= kMaxMatches) &&
1184 (!chrome::IsInstantExtendedAPIEnabled() ||
1185 (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
1192 matches_.push_back(*i);
1194 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime",
1195 base::TimeTicks::Now() - start_time);
1198 bool SearchProvider::IsTopMatchNavigationInKeywordMode() const {
1199 return (!providers_.keyword_provider().empty() &&
1200 (matches_.front().type == AutocompleteMatchType::NAVSUGGEST));
1203 bool SearchProvider::IsTopMatchScoreTooLow() const {
1204 // Here we use CalculateRelevanceForVerbatimIgnoringKeywordModeState()
1205 // rather than CalculateRelevanceForVerbatim() because the latter returns
1206 // a very low score (250) if keyword mode is active. This is because
1207 // when keyword mode is active the user probably wants the keyword matches,
1208 // not matches from the default provider. Hence, we use the version of
1209 // the function that ignores whether keyword mode is active. This allows
1210 // SearchProvider to maintain its contract with the AutocompleteController
1211 // that it will always provide an inlineable match with a reasonable
1213 return matches_.front().relevance <
1214 CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1217 bool SearchProvider::IsTopMatchSearchWithURLInput() const {
1218 return input_.type() == AutocompleteInput::URL &&
1219 matches_.front().relevance > CalculateRelevanceForVerbatim() &&
1220 matches_.front().type != AutocompleteMatchType::NAVSUGGEST;
1223 bool SearchProvider::HasValidDefaultMatch(
1224 bool autocomplete_result_will_reorder_for_default_match) const {
1225 // One of the SearchProvider matches may need to be the overall default. If
1226 // AutocompleteResult is allowed to reorder matches, this means we simply
1227 // need at least one match in the list to be |allowed_to_be_default_match|.
1228 // If no reordering is possible, however, then our first match needs to have
1230 for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
1232 if (it->allowed_to_be_default_match)
1234 if (!autocomplete_result_will_reorder_for_default_match)
1240 void SearchProvider::UpdateMatches() {
1241 base::TimeTicks update_matches_start_time(base::TimeTicks::Now());
1242 ConvertResultsToAutocompleteMatches();
1244 // Check constraints that may be violated by suggested relevances.
1245 if (!matches_.empty() &&
1246 (default_results_.HasServerProvidedScores() ||
1247 keyword_results_.HasServerProvidedScores())) {
1248 // These blocks attempt to repair undesirable behavior by suggested
1249 // relevances with minimal impact, preserving other suggested relevances.
1250 if (IsTopMatchNavigationInKeywordMode()) {
1251 // Correct the suggested relevance scores if the top match is a
1252 // navigation in keyword mode, since inlining a navigation match
1253 // would break the user out of keyword mode. By the way, if the top
1254 // match is a non-keyword match (query or navsuggestion) in keyword
1255 // mode, the user would also break out of keyword mode. However,
1256 // that situation is impossible given the current scoring paradigm
1257 // and the fact that only one search engine (Google) provides suggested
1258 // relevance scores at this time.
1259 DemoteKeywordNavigationMatchesPastTopQuery();
1260 ConvertResultsToAutocompleteMatches();
1261 DCHECK(!IsTopMatchNavigationInKeywordMode());
1263 // True if the omnibox will reorder matches as necessary to make the top
1264 // one something that is allowed to be the default match.
1265 const bool omnibox_will_reorder_for_legal_default_match =
1266 OmniboxFieldTrial::ReorderForLegalDefaultMatch(
1267 input_.current_page_classification());
1268 if (!omnibox_will_reorder_for_legal_default_match &&
1269 IsTopMatchScoreTooLow()) {
1270 // Disregard the suggested verbatim relevance if the top score is below
1271 // the usual verbatim value. For example, a BarProvider may rely on
1272 // SearchProvider's verbatim or inlineable matches for input "foo" (all
1273 // allowed to be default match) to always outrank its own lowly-ranked
1274 // "bar" matches that shouldn't be the default match. This only needs
1275 // to be enforced when the omnibox will not reorder results to make a
1276 // legal default match first.
1277 default_results_.verbatim_relevance = -1;
1278 keyword_results_.verbatim_relevance = -1;
1279 ConvertResultsToAutocompleteMatches();
1281 if (IsTopMatchSearchWithURLInput()) {
1282 // Disregard the suggested search and verbatim relevances if the input
1283 // type is URL and the top match is a highly-ranked search suggestion.
1284 // For example, prevent a search for "foo.com" from outranking another
1285 // provider's navigation for "foo.com" or "foo.com/url_from_history".
1286 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
1287 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
1288 default_results_.verbatim_relevance = -1;
1289 keyword_results_.verbatim_relevance = -1;
1290 ConvertResultsToAutocompleteMatches();
1292 if (!HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match)) {
1293 // If the omnibox is not going to reorder results to put a legal default
1294 // match at the top, then this provider needs to guarantee that its top
1295 // scoring result is a legal default match (i.e., it's either a verbatim
1296 // match or inlinable). For example, input "foo" should not invoke a
1297 // search for "bar", which would happen if the "bar" search match
1298 // outranked all other matches. On the other hand, if the omnibox will
1299 // reorder matches as necessary to put a legal default match at the top,
1300 // all we need to guarantee is that SearchProvider returns a legal
1301 // default match. (The omnibox always needs at least one legal default
1302 // match, and it relies on SearchProvider to always return one.)
1303 ApplyCalculatedRelevance();
1304 ConvertResultsToAutocompleteMatches();
1306 DCHECK(!IsTopMatchNavigationInKeywordMode());
1307 DCHECK(omnibox_will_reorder_for_legal_default_match ||
1308 !IsTopMatchScoreTooLow());
1309 DCHECK(!IsTopMatchSearchWithURLInput());
1310 DCHECK(HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match));
1313 base::TimeTicks update_starred_start_time(base::TimeTicks::Now());
1314 UpdateStarredStateOfMatches();
1315 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateStarredTime",
1316 base::TimeTicks::Now() - update_starred_start_time);
1318 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateMatchesTime",
1319 base::TimeTicks::Now() - update_matches_start_time);
1322 void SearchProvider::AddNavigationResultsToMatches(
1323 const NavigationResults& navigation_results,
1324 ACMatches* matches) {
1325 for (NavigationResults::const_iterator it = navigation_results.begin();
1326 it != navigation_results.end(); ++it) {
1327 matches->push_back(NavigationToMatch(*it));
1328 // In the absence of suggested relevance scores, use only the single
1329 // highest-scoring result. (The results are already sorted by relevance.)
1330 if (!it->relevance_from_server())
1335 void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
1337 int did_not_accept_suggestion,
1339 if (results.empty())
1342 base::TimeTicks start_time(base::TimeTicks::Now());
1343 bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() ||
1344 (input_.type() == AutocompleteInput::URL);
1345 const string16& input_text =
1346 is_keyword ? keyword_input_.text() : input_.text();
1347 bool input_multiple_words = HasMultipleWords(input_text);
1349 SuggestResults scored_results;
1350 if (!prevent_inline_autocomplete && input_multiple_words) {
1351 // ScoreHistoryResults() allows autocompletion of multi-word, 1-visit
1352 // queries if the input also has multiple words. But if we were already
1353 // autocompleting a multi-word, multi-visit query, and the current input is
1354 // still a prefix of it, then changing the autocompletion suddenly feels
1355 // wrong. To detect this case, first score as if only one word has been
1356 // typed, then check for a best result that is an autocompleted, multi-word
1357 // query. If we find one, then just keep that score set.
1358 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1359 false, input_text, is_keyword);
1360 if ((scored_results.front().relevance() <
1361 AutocompleteResult::kLowestDefaultScore) ||
1362 !HasMultipleWords(scored_results.front().suggestion()))
1363 scored_results.clear(); // Didn't detect the case above, score normally.
1365 if (scored_results.empty())
1366 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1367 input_multiple_words, input_text,
1369 for (SuggestResults::const_iterator i(scored_results.begin());
1370 i != scored_results.end(); ++i) {
1371 AddMatchToMap(input_text,
1376 AutocompleteMatchType::SEARCH_HISTORY,
1381 did_not_accept_suggestion,
1385 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime",
1386 base::TimeTicks::Now() - start_time);
1389 SearchProvider::SuggestResults SearchProvider::ScoreHistoryResults(
1390 const HistoryResults& results,
1391 bool base_prevent_inline_autocomplete,
1392 bool input_multiple_words,
1393 const string16& input_text,
1395 AutocompleteClassifier* classifier =
1396 AutocompleteClassifierFactory::GetForProfile(profile_);
1397 SuggestResults scored_results;
1398 const bool prevent_search_history_inlining =
1399 OmniboxFieldTrial::SearchHistoryPreventInlining(
1400 input_.current_page_classification());
1401 for (HistoryResults::const_iterator i(results.begin()); i != results.end();
1403 // Don't autocomplete multi-word queries that have only been seen once
1404 // unless the user has typed more than one word.
1405 bool prevent_inline_autocomplete = base_prevent_inline_autocomplete ||
1406 (!input_multiple_words && (i->visits < 2) && HasMultipleWords(i->term));
1408 // Don't autocomplete search terms that would normally be treated as URLs
1409 // when typed. For example, if the user searched for "google.com" and types
1410 // "goog", don't autocomplete to the search term "google.com". Otherwise,
1411 // the input will look like a URL but act like a search, which is confusing.
1412 // NOTE: We don't check this in the following cases:
1413 // * When inline autocomplete is disabled, we won't be inline
1414 // autocompleting this term, so we don't need to worry about confusion as
1415 // much. This also prevents calling Classify() again from inside the
1416 // classifier (which will corrupt state and likely crash), since the
1417 // classifier always disables inline autocomplete.
1418 // * When the user has typed the whole term, the "what you typed" history
1419 // match will outrank us for URL-like inputs anyway, so we need not do
1420 // anything special.
1421 if (!prevent_inline_autocomplete && classifier && (i->term != input_text)) {
1422 AutocompleteMatch match;
1423 classifier->Classify(i->term, false, false, &match, NULL);
1424 prevent_inline_autocomplete =
1425 !AutocompleteMatch::IsSearchType(match.type);
1428 int relevance = CalculateRelevanceForHistory(
1429 i->time, is_keyword, !prevent_inline_autocomplete,
1430 prevent_search_history_inlining);
1431 scored_results.push_back(
1432 SuggestResult(i->term, string16(), string16(), std::string(),
1433 is_keyword, relevance, false, false));
1436 // History returns results sorted for us. However, we may have docked some
1437 // results' scores, so things are no longer in order. Do a stable sort to get
1438 // things back in order without otherwise disturbing results with equal
1439 // scores, then force the scores to be unique, so that the order in which
1440 // they're shown is deterministic.
1441 std::stable_sort(scored_results.begin(), scored_results.end(),
1442 CompareScoredResults());
1443 int last_relevance = 0;
1444 for (SuggestResults::iterator i(scored_results.begin());
1445 i != scored_results.end(); ++i) {
1446 if ((i != scored_results.begin()) && (i->relevance() >= last_relevance))
1447 i->set_relevance(last_relevance - 1);
1448 last_relevance = i->relevance();
1451 return scored_results;
1454 void SearchProvider::AddSuggestResultsToMap(const SuggestResults& results,
1455 const std::string& metadata,
1457 for (size_t i = 0; i < results.size(); ++i) {
1458 const bool is_keyword = results[i].from_keyword_provider();
1459 const string16& input = is_keyword ? keyword_input_.text() : input_.text();
1460 AddMatchToMap(input,
1461 results[i].relevance(),
1462 results[i].relevance_from_server(),
1463 results[i].should_prefetch(),
1465 AutocompleteMatchType::SEARCH_SUGGEST,
1467 results[i].match_contents(),
1468 results[i].annotation(),
1469 results[i].suggestion(),
1471 results[i].suggest_query_params(),
1476 int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
1477 // Use the suggested verbatim relevance score if it is non-negative (valid),
1478 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1479 // and if it won't suppress verbatim, leaving no default provider matches.
1480 // Otherwise, if the default provider returned no matches and was still able
1481 // to suppress verbatim, the user would have no search/nav matches and may be
1482 // left unable to search using their default provider from the omnibox.
1483 // Check for results on each verbatim calculation, as results from older
1484 // queries (on previous input) may be trimmed for failing to inline new input.
1485 bool use_server_relevance =
1486 (default_results_.verbatim_relevance >= 0) &&
1487 !input_.prevent_inline_autocomplete() &&
1488 ((default_results_.verbatim_relevance > 0) ||
1489 !default_results_.suggest_results.empty() ||
1490 !default_results_.navigation_results.empty());
1491 if (relevance_from_server)
1492 *relevance_from_server = use_server_relevance;
1493 return use_server_relevance ?
1494 default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
1497 int SearchProvider::CalculateRelevanceForVerbatim() const {
1498 if (!providers_.keyword_provider().empty())
1500 return CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1503 int SearchProvider::
1504 CalculateRelevanceForVerbatimIgnoringKeywordModeState() const {
1505 switch (input_.type()) {
1506 case AutocompleteInput::UNKNOWN:
1507 case AutocompleteInput::QUERY:
1508 case AutocompleteInput::FORCED_QUERY:
1509 return kNonURLVerbatimRelevance;
1511 case AutocompleteInput::URL:
1520 int SearchProvider::GetKeywordVerbatimRelevance(
1521 bool* relevance_from_server) const {
1522 // Use the suggested verbatim relevance score if it is non-negative (valid),
1523 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1524 // and if it won't suppress verbatim, leaving no keyword provider matches.
1525 // Otherwise, if the keyword provider returned no matches and was still able
1526 // to suppress verbatim, the user would have no search/nav matches and may be
1527 // left unable to search using their keyword provider from the omnibox.
1528 // Check for results on each verbatim calculation, as results from older
1529 // queries (on previous input) may be trimmed for failing to inline new input.
1530 bool use_server_relevance =
1531 (keyword_results_.verbatim_relevance >= 0) &&
1532 !input_.prevent_inline_autocomplete() &&
1533 ((keyword_results_.verbatim_relevance > 0) ||
1534 !keyword_results_.suggest_results.empty() ||
1535 !keyword_results_.navigation_results.empty());
1536 if (relevance_from_server)
1537 *relevance_from_server = use_server_relevance;
1538 return use_server_relevance ?
1539 keyword_results_.verbatim_relevance :
1540 CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
1541 keyword_input_.prefer_keyword());
1544 int SearchProvider::CalculateRelevanceForHistory(
1545 const base::Time& time,
1547 bool use_aggressive_method,
1548 bool prevent_search_history_inlining) const {
1549 // The relevance of past searches falls off over time. There are two distinct
1550 // equations used. If the first equation is used (searches to the primary
1551 // provider that we want to score aggressively), the score is in the range
1552 // 1300-1599 (unless |prevent_search_history_inlining|, in which case
1553 // it's in the range 1200-1299). If the second equation is used the
1554 // relevance of a search 15 minutes ago is discounted 50 points, while the
1555 // relevance of a search two weeks ago is discounted 450 points.
1556 double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0);
1557 bool is_primary_provider = is_keyword || !providers_.has_keyword_provider();
1558 if (is_primary_provider && use_aggressive_method) {
1559 // Searches with the past two days get a different curve.
1560 const double autocomplete_time = 2 * 24 * 60 * 60;
1561 if (elapsed_time < autocomplete_time) {
1562 int max_score = is_keyword ? 1599 : 1399;
1563 if (prevent_search_history_inlining)
1565 return max_score - static_cast<int>(99 *
1566 std::pow(elapsed_time / autocomplete_time, 2.5));
1568 elapsed_time -= autocomplete_time;
1571 const int score_discount =
1572 static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
1574 // Don't let scores go below 0. Negative relevance scores are meaningful in
1577 if (is_primary_provider)
1578 base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050;
1581 return std::max(0, base_score - score_discount);
1584 void SearchProvider::AddMatchToMap(const string16& input_text,
1586 bool relevance_from_server,
1587 bool should_prefetch,
1588 const std::string& metadata,
1589 AutocompleteMatch::Type type,
1591 const string16& match_contents,
1592 const string16& annotation,
1593 const string16& query_string,
1594 int accepted_suggestion,
1595 const std::string& suggest_query_params,
1597 // On non-mobile, ask the instant controller for the appropriate start margin.
1598 // On mobile the start margin is unused, so leave the value as default there.
1599 int omnibox_start_margin = chrome::kDisableStartMargin;
1600 #if !defined(OS_ANDROID) && !defined(IOS)
1601 if (chrome::IsInstantExtendedAPIEnabled()) {
1603 chrome::FindBrowserWithProfile(profile_, chrome::GetActiveDesktop());
1604 if (browser && browser->instant_controller() &&
1605 browser->instant_controller()->instant()) {
1606 omnibox_start_margin =
1607 browser->instant_controller()->instant()->omnibox_bounds().x();
1610 #endif // !defined(OS_ANDROID) && !defined(IOS)
1612 const TemplateURL* template_url = is_keyword ?
1613 providers_.GetKeywordProviderURL() : providers_.GetDefaultProviderURL();
1614 AutocompleteMatch match = CreateSearchSuggestion(
1615 this, input_, input_text, relevance, type, is_keyword, match_contents,
1616 annotation, template_url, query_string, suggest_query_params,
1617 accepted_suggestion, omnibox_start_margin,
1618 !is_keyword || providers_.default_provider().empty());
1619 if (!match.destination_url.is_valid())
1621 match.search_terms_args->bookmark_bar_pinned =
1622 profile_->GetPrefs()->GetBoolean(prefs::kShowBookmarkBar);
1623 match.RecordAdditionalInfo(kRelevanceFromServerKey,
1624 relevance_from_server ? kTrue : kFalse);
1625 match.RecordAdditionalInfo(kShouldPrefetchKey,
1626 should_prefetch ? kTrue : kFalse);
1628 // Metadata is needed only for prefetching queries.
1629 if (should_prefetch)
1630 match.RecordAdditionalInfo(kSuggestMetadataKey, metadata);
1632 // Try to add |match| to |map|. If a match for |query_string| is already in
1633 // |map|, replace it if |match| is more relevant.
1634 // NOTE: Keep this ToLower() call in sync with url_database.cc.
1636 std::make_pair(base::i18n::ToLower(query_string),
1637 match.search_terms_args->suggest_query_params));
1638 const std::pair<MatchMap::iterator, bool> i(
1639 map->insert(std::make_pair(match_key, match)));
1642 // NOTE: We purposefully do a direct relevance comparison here instead of
1643 // using AutocompleteMatch::MoreRelevant(), so that we'll prefer "items
1644 // added first" rather than "items alphabetically first" when the scores are
1645 // equal. The only case this matters is when a user has results with the
1646 // same score that differ only by capitalization; because the history system
1647 // returns results sorted by recency, this means we'll pick the most
1648 // recent such result even if the precision of our relevance score is too
1649 // low to distinguish the two.
1650 if (match.relevance > i.first->second.relevance) {
1651 i.first->second = match;
1652 } else if (match.keyword == i.first->second.keyword) {
1653 // Old and new matches are from the same search provider. It is okay to
1654 // record one match's prefetch data onto a different match (for the same
1655 // query string) for the following reasons:
1656 // 1. Because the suggest server only sends down a query string from which
1657 // we construct a URL, rather than sending a full URL, and because we
1658 // construct URLs from query strings in the same way every time, the URLs
1659 // for the two matches will be the same. Therefore, we won't end up
1660 // prefetching something the server didn't intend.
1661 // 2. Presumably the server sets the prefetch bit on a match it things is
1662 // sufficiently relevant that the user is likely to choose it. Surely
1663 // setting the prefetch bit on a match of even higher relevance won't
1664 // violate this assumption.
1665 should_prefetch |= ShouldPrefetch(i.first->second);
1666 i.first->second.RecordAdditionalInfo(kShouldPrefetchKey,
1667 should_prefetch ? kTrue : kFalse);
1668 if (should_prefetch)
1669 i.first->second.RecordAdditionalInfo(kSuggestMetadataKey, metadata);
1674 AutocompleteMatch SearchProvider::NavigationToMatch(
1675 const NavigationResult& navigation) {
1676 const string16& input = navigation.from_keyword_provider() ?
1677 keyword_input_.text() : input_.text();
1678 AutocompleteMatch match(this, navigation.relevance(), false,
1679 AutocompleteMatchType::NAVSUGGEST);
1680 match.destination_url = navigation.url();
1682 // First look for the user's input inside the fill_into_edit as it would be
1683 // without trimming the scheme, so we can find matches at the beginning of the
1685 const string16& untrimmed_fill_into_edit = navigation.formatted_url();
1686 const URLPrefix* prefix =
1687 URLPrefix::BestURLPrefix(untrimmed_fill_into_edit, input);
1688 size_t match_start = (prefix == NULL) ?
1689 untrimmed_fill_into_edit.find(input) : prefix->prefix.length();
1690 size_t inline_autocomplete_offset = (prefix == NULL) ?
1691 string16::npos : (match_start + input.length());
1692 bool trim_http = !AutocompleteInput::HasHTTPScheme(input) &&
1693 (!prefix || (match_start != 0));
1695 // Preserve the forced query '?' prefix in |match.fill_into_edit|.
1696 // Otherwise, user edits to a suggestion would show non-Search results.
1697 if (input_.type() == AutocompleteInput::FORCED_QUERY) {
1698 match.fill_into_edit = ASCIIToUTF16("?");
1699 if (inline_autocomplete_offset != string16::npos)
1700 ++inline_autocomplete_offset;
1703 const std::string languages(
1704 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
1705 const net::FormatUrlTypes format_types =
1706 net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP);
1707 match.fill_into_edit +=
1708 AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url(),
1709 net::FormatUrl(navigation.url(), languages, format_types,
1710 net::UnescapeRule::SPACES, NULL, NULL,
1711 &inline_autocomplete_offset));
1712 if (!input_.prevent_inline_autocomplete() &&
1713 (inline_autocomplete_offset != string16::npos)) {
1714 DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1715 match.allowed_to_be_default_match = true;
1716 match.inline_autocompletion =
1717 match.fill_into_edit.substr(inline_autocomplete_offset);
1720 match.contents = net::FormatUrl(navigation.url(), languages,
1721 format_types, net::UnescapeRule::SPACES, NULL, NULL, &match_start);
1722 // If the first match in the untrimmed string was inside a scheme that we
1723 // trimmed, look for a subsequent match.
1724 if (match_start == string16::npos)
1725 match_start = match.contents.find(input);
1726 // Safe if |match_start| is npos; also safe if the input is longer than the
1727 // remaining contents after |match_start|.
1728 AutocompleteMatch::ClassifyLocationInString(match_start, input.length(),
1729 match.contents.length(), ACMatchClassification::URL,
1730 &match.contents_class);
1732 match.description = navigation.description();
1733 AutocompleteMatch::ClassifyMatchInString(input, match.description,
1734 ACMatchClassification::NONE, &match.description_class);
1736 match.RecordAdditionalInfo(
1737 kRelevanceFromServerKey,
1738 navigation.relevance_from_server() ? kTrue : kFalse);
1739 match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse);
1744 void SearchProvider::DemoteKeywordNavigationMatchesPastTopQuery() {
1745 // First, determine the maximum score of any keyword query match (verbatim or
1746 // query suggestion).
1747 bool relevance_from_server;
1748 int max_query_relevance = GetKeywordVerbatimRelevance(&relevance_from_server);
1749 if (!keyword_results_.suggest_results.empty()) {
1750 const SuggestResult& top_keyword = keyword_results_.suggest_results.front();
1751 const int suggest_relevance = top_keyword.relevance();
1752 if (suggest_relevance > max_query_relevance) {
1753 max_query_relevance = suggest_relevance;
1754 relevance_from_server = top_keyword.relevance_from_server();
1755 } else if (suggest_relevance == max_query_relevance) {
1756 relevance_from_server |= top_keyword.relevance_from_server();
1759 // If no query is supposed to appear, then navigational matches cannot
1760 // be demoted past it. Get rid of suggested relevance scores for
1761 // navsuggestions and introduce the verbatim results again. The keyword
1762 // verbatim match will outscore the navsuggest matches.
1763 if (max_query_relevance == 0) {
1764 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
1765 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
1766 keyword_results_.verbatim_relevance = -1;
1767 default_results_.verbatim_relevance = -1;
1770 // Now we know we can enforce the minimum score constraint even after
1771 // the navigation matches are demoted. Proceed to demote the navigation
1772 // matches to enforce the query-must-come-first constraint.
1773 // Cap the relevance score of all results.
1774 for (NavigationResults::iterator it =
1775 keyword_results_.navigation_results.begin();
1776 it != keyword_results_.navigation_results.end(); ++it) {
1777 if (it->relevance() < max_query_relevance)
1779 max_query_relevance = std::max(max_query_relevance - 1, 0);
1780 it->set_relevance(max_query_relevance);
1781 it->set_relevance_from_server(relevance_from_server);
1785 void SearchProvider::UpdateDone() {
1786 // We're done when the timer isn't running, there are no suggest queries
1787 // pending, and we're not waiting on Instant.
1788 done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0);