1 // Copyright 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "chrome/browser/autocomplete/search_provider.h"
6
7 #include <algorithm>
8 #include <cmath>
9
10 #include "base/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/google/google_util.h"
29 #include "chrome/browser/history/history_service.h"
30 #include "chrome/browser/history/history_service_factory.h"
31 #include "chrome/browser/history/in_memory_database.h"
32 #include "chrome/browser/metrics/variations/variations_http_header_provider.h"
33 #include "chrome/browser/omnibox/omnibox_field_trial.h"
34 #include "chrome/browser/profiles/profile.h"
35 #include "chrome/browser/search/search.h"
36 #include "chrome/browser/search_engines/template_url_prepopulate_data.h"
37 #include "chrome/browser/search_engines/template_url_service.h"
38 #include "chrome/browser/search_engines/template_url_service_factory.h"
39 #include "chrome/browser/sync/profile_sync_service.h"
40 #include "chrome/browser/sync/profile_sync_service_factory.h"
41 #include "chrome/browser/ui/browser.h"
42 #include "chrome/browser/ui/browser_finder.h"
43 #include "chrome/browser/ui/browser_instant_controller.h"
44 #include "chrome/browser/ui/search/instant_controller.h"
45 #include "chrome/common/net/url_fixer_upper.h"
46 #include "chrome/common/pref_names.h"
47 #include "chrome/common/url_constants.h"
48 #include "content/public/browser/user_metrics.h"
49 #include "grit/generated_resources.h"
50 #include "net/base/escape.h"
51 #include "net/base/load_flags.h"
52 #include "net/base/net_util.h"
53 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
54 #include "net/http/http_request_headers.h"
55 #include "net/http/http_response_headers.h"
56 #include "net/url_request/url_fetcher.h"
57 #include "net/url_request/url_request_status.h"
58 #include "ui/base/l10n/l10n_util.h"
59 #include "url/url_util.h"
60
61
62 // Helpers --------------------------------------------------------------------
63
64 namespace {
65
66 // We keep track in a histogram how many suggest requests we send, how
67 // many suggest requests we invalidate (e.g., due to a user typing
68 // another character), and how many replies we receive.
69 // *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! ***
70 // (excluding the end-of-list enum value)
71 // We do not want values of existing enums to change or else it screws
72 // up the statistics.
73 enum SuggestRequestsHistogramValue {
74 REQUEST_SENT = 1,
75 REQUEST_INVALIDATED,
76 REPLY_RECEIVED,
77 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE
78 };
79
80 // The verbatim score for an input which is not an URL.
81 const int kNonURLVerbatimRelevance = 1300;
82
83 // Increments the appropriate value in the histogram by one.
LogOmniboxSuggestRequest(SuggestRequestsHistogramValue request_value)84 void LogOmniboxSuggestRequest(
85 SuggestRequestsHistogramValue request_value) {
86 UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value,
87 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE);
88 }
89
HasMultipleWords(const base::string16 & text)90 bool HasMultipleWords(const base::string16& text) {
91 base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD);
92 bool found_word = false;
93 if (i.Init()) {
94 while (i.Advance()) {
95 if (i.IsWord()) {
96 if (found_word)
97 return true;
98 found_word = true;
99 }
100 }
101 }
102 return false;
103 }
104
105 // Builds the match contents and classification for the contents, and updates
106 // the given |AutocompleteMatch|.
SetAndClassifyMatchContents(const base::string16 & query_string,const base::string16 & input_text,const base::string16 & match_contents,AutocompleteMatch * match)107 void SetAndClassifyMatchContents(const base::string16& query_string,
108 const base::string16& input_text,
109 const base::string16& match_contents,
110 AutocompleteMatch* match) {
111 match->contents = match_contents.empty() ? query_string : match_contents;
112
113 // We do intra-string highlighting for suggestions - the suggested segment
114 // will be highlighted, e.g. for input_text = "you" the suggestion may be
115 // "youtube", so we'll bold the "tube" section: you*tube*.
116 if (input_text != match_contents) {
117 size_t input_position = match->contents.find(input_text);
118 if (input_position == base::string16::npos) {
119 // The input text is not a substring of the query string, e.g. input
120 // text is "slasdot" and the query string is "slashdot", so we bold the
121 // whole thing.
122 match->contents_class.push_back(ACMatchClassification(
123 0, ACMatchClassification::MATCH));
124 } else {
125 // TODO(beng): ACMatchClassification::MATCH now seems to just mean
126 // "bold" this. Consider modifying the terminology.
127 // We don't iterate over the string here annotating all matches because
128 // it looks odd to have every occurrence of a substring that may be as
129 // short as a single character highlighted in a query suggestion result,
130 // e.g. for input text "s" and query string "southwest airlines", it
131 // looks odd if both the first and last s are highlighted.
132 if (input_position != 0) {
133 match->contents_class.push_back(ACMatchClassification(
134 0, ACMatchClassification::MATCH));
135 }
136 match->contents_class.push_back(
137 ACMatchClassification(input_position, ACMatchClassification::NONE));
138 size_t next_fragment_position = input_position + input_text.length();
139 if (next_fragment_position < query_string.length()) {
140 match->contents_class.push_back(ACMatchClassification(
141 next_fragment_position, ACMatchClassification::MATCH));
142 }
143 }
144 } else {
145 // Otherwise, |match| is a verbatim (what-you-typed) match, either for the
146 // default provider or a keyword search provider.
147 match->contents_class.push_back(ACMatchClassification(
148 0, ACMatchClassification::NONE));
149 }
150 }
151
GetAutocompleteMatchType(const std::string & type)152 AutocompleteMatchType::Type GetAutocompleteMatchType(const std::string& type) {
153 if (type == "ENTITY")
154 return AutocompleteMatchType::SEARCH_SUGGEST_ENTITY;
155 if (type == "INFINITE")
156 return AutocompleteMatchType::SEARCH_SUGGEST_INFINITE;
157 if (type == "PERSONALIZED")
158 return AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED;
159 if (type == "PROFILE")
160 return AutocompleteMatchType::SEARCH_SUGGEST_PROFILE;
161 return AutocompleteMatchType::SEARCH_SUGGEST;
162 }
163
164 } // namespace
165
166
167 // SuggestionDeletionHandler -------------------------------------------------
168
169 // This class handles making requests to the server in order to delete
170 // personalized suggestions.
171 class SuggestionDeletionHandler : public net::URLFetcherDelegate {
172 public:
173 typedef base::Callback<void(bool, SuggestionDeletionHandler*)>
174 DeletionCompletedCallback;
175
176 SuggestionDeletionHandler(
177 const std::string& deletion_url,
178 Profile* profile,
179 const DeletionCompletedCallback& callback);
180
181 virtual ~SuggestionDeletionHandler();
182
183 private:
184 // net::URLFetcherDelegate:
185 virtual void OnURLFetchComplete(const net::URLFetcher* source) OVERRIDE;
186
187 scoped_ptr<net::URLFetcher> deletion_fetcher_;
188 DeletionCompletedCallback callback_;
189
190 DISALLOW_COPY_AND_ASSIGN(SuggestionDeletionHandler);
191 };
192
193
SuggestionDeletionHandler(const std::string & deletion_url,Profile * profile,const DeletionCompletedCallback & callback)194 SuggestionDeletionHandler::SuggestionDeletionHandler(
195 const std::string& deletion_url,
196 Profile* profile,
197 const DeletionCompletedCallback& callback) : callback_(callback) {
198 GURL url(deletion_url);
199 DCHECK(url.is_valid());
200
201 deletion_fetcher_.reset(net::URLFetcher::Create(
202 SearchProvider::kDeletionURLFetcherID,
203 url,
204 net::URLFetcher::GET,
205 this));
206 deletion_fetcher_->SetRequestContext(profile->GetRequestContext());
207 deletion_fetcher_->Start();
208 };
209
~SuggestionDeletionHandler()210 SuggestionDeletionHandler::~SuggestionDeletionHandler() {
211 };
212
OnURLFetchComplete(const net::URLFetcher * source)213 void SuggestionDeletionHandler::OnURLFetchComplete(
214 const net::URLFetcher* source) {
215 DCHECK(source == deletion_fetcher_.get());
216 callback_.Run(
217 source->GetStatus().is_success() && (source->GetResponseCode() == 200),
218 this);
219 };
220
221
222 // SearchProvider::Providers --------------------------------------------------
223
Providers(TemplateURLService * template_url_service)224 SearchProvider::Providers::Providers(TemplateURLService* template_url_service)
225 : template_url_service_(template_url_service) {
226 }
227
GetDefaultProviderURL() const228 const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const {
229 return default_provider_.empty() ? NULL :
230 template_url_service_->GetTemplateURLForKeyword(default_provider_);
231 }
232
GetKeywordProviderURL() const233 const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
234 return keyword_provider_.empty() ? NULL :
235 template_url_service_->GetTemplateURLForKeyword(keyword_provider_);
236 }
237
238
239 // SearchProvider::Result -----------------------------------------------------
240
Result(bool from_keyword_provider,int relevance,bool relevance_from_server)241 SearchProvider::Result::Result(bool from_keyword_provider,
242 int relevance,
243 bool relevance_from_server)
244 : from_keyword_provider_(from_keyword_provider),
245 relevance_(relevance),
246 relevance_from_server_(relevance_from_server) {
247 }
248
~Result()249 SearchProvider::Result::~Result() {
250 }
251
252
253 // SearchProvider::SuggestResult ----------------------------------------------
254
SuggestResult(const base::string16 & suggestion,AutocompleteMatchType::Type type,const base::string16 & match_contents,const base::string16 & annotation,const std::string & suggest_query_params,const std::string & deletion_url,bool from_keyword_provider,int relevance,bool relevance_from_server,bool should_prefetch)255 SearchProvider::SuggestResult::SuggestResult(
256 const base::string16& suggestion,
257 AutocompleteMatchType::Type type,
258 const base::string16& match_contents,
259 const base::string16& annotation,
260 const std::string& suggest_query_params,
261 const std::string& deletion_url,
262 bool from_keyword_provider,
263 int relevance,
264 bool relevance_from_server,
265 bool should_prefetch)
266 : Result(from_keyword_provider, relevance, relevance_from_server),
267 suggestion_(suggestion),
268 type_(type),
269 match_contents_(match_contents),
270 annotation_(annotation),
271 suggest_query_params_(suggest_query_params),
272 deletion_url_(deletion_url),
273 should_prefetch_(should_prefetch) {
274 }
275
~SuggestResult()276 SearchProvider::SuggestResult::~SuggestResult() {
277 }
278
IsInlineable(const base::string16 & input) const279 bool SearchProvider::SuggestResult::IsInlineable(
280 const base::string16& input) const {
281 return StartsWith(suggestion_, input, false);
282 }
283
CalculateRelevance(const AutocompleteInput & input,bool keyword_provider_requested) const284 int SearchProvider::SuggestResult::CalculateRelevance(
285 const AutocompleteInput& input,
286 bool keyword_provider_requested) const {
287 if (!from_keyword_provider_ && keyword_provider_requested)
288 return 100;
289 return ((input.type() == AutocompleteInput::URL) ? 300 : 600);
290 }
291
292
293 // SearchProvider::NavigationResult -------------------------------------------
294
NavigationResult(const AutocompleteProvider & provider,const GURL & url,const base::string16 & description,bool from_keyword_provider,int relevance,bool relevance_from_server)295 SearchProvider::NavigationResult::NavigationResult(
296 const AutocompleteProvider& provider,
297 const GURL& url,
298 const base::string16& description,
299 bool from_keyword_provider,
300 int relevance,
301 bool relevance_from_server)
302 : Result(from_keyword_provider, relevance, relevance_from_server),
303 url_(url),
304 formatted_url_(AutocompleteInput::FormattedStringWithEquivalentMeaning(
305 url, provider.StringForURLDisplay(url, true, false))),
306 description_(description) {
307 DCHECK(url_.is_valid());
308 }
309
~NavigationResult()310 SearchProvider::NavigationResult::~NavigationResult() {
311 }
312
IsInlineable(const base::string16 & input) const313 bool SearchProvider::NavigationResult::IsInlineable(
314 const base::string16& input) const {
315 return
316 URLPrefix::BestURLPrefix(base::UTF8ToUTF16(url_.spec()), input) != NULL;
317 }
318
CalculateRelevance(const AutocompleteInput & input,bool keyword_provider_requested) const319 int SearchProvider::NavigationResult::CalculateRelevance(
320 const AutocompleteInput& input,
321 bool keyword_provider_requested) const {
322 return (from_keyword_provider_ || !keyword_provider_requested) ? 800 : 150;
323 }
324
325
326 // SearchProvider::CompareScoredResults ---------------------------------------
327
328 class SearchProvider::CompareScoredResults {
329 public:
operator ()(const Result & a,const Result & b)330 bool operator()(const Result& a, const Result& b) {
331 // Sort in descending relevance order.
332 return a.relevance() > b.relevance();
333 }
334 };
335
336
337 // SearchProvider::Results ----------------------------------------------------
338
Results()339 SearchProvider::Results::Results() : verbatim_relevance(-1) {
340 }
341
~Results()342 SearchProvider::Results::~Results() {
343 }
344
Clear()345 void SearchProvider::Results::Clear() {
346 suggest_results.clear();
347 navigation_results.clear();
348 verbatim_relevance = -1;
349 metadata.clear();
350 }
351
HasServerProvidedScores() const352 bool SearchProvider::Results::HasServerProvidedScores() const {
353 if (verbatim_relevance >= 0)
354 return true;
355
356 // Right now either all results of one type will be server-scored or they will
357 // all be locally scored, but in case we change this later, we'll just check
358 // them all.
359 for (SuggestResults::const_iterator i(suggest_results.begin());
360 i != suggest_results.end(); ++i) {
361 if (i->relevance_from_server())
362 return true;
363 }
364 for (NavigationResults::const_iterator i(navigation_results.begin());
365 i != navigation_results.end(); ++i) {
366 if (i->relevance_from_server())
367 return true;
368 }
369
370 return false;
371 }
372
373
374 // SearchProvider -------------------------------------------------------------
375
376 // static
377 const int SearchProvider::kDefaultProviderURLFetcherID = 1;
378 const int SearchProvider::kKeywordProviderURLFetcherID = 2;
379 const int SearchProvider::kDeletionURLFetcherID = 3;
380 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
381 const char SearchProvider::kRelevanceFromServerKey[] = "relevance_from_server";
382 const char SearchProvider::kShouldPrefetchKey[] = "should_prefetch";
383 const char SearchProvider::kSuggestMetadataKey[] = "suggest_metadata";
384 const char SearchProvider::kDeletionUrlKey[] = "deletion_url";
385 const char SearchProvider::kTrue[] = "true";
386 const char SearchProvider::kFalse[] = "false";
387
SearchProvider(AutocompleteProviderListener * listener,Profile * profile)388 SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
389 Profile* profile)
390 : AutocompleteProvider(listener, profile,
391 AutocompleteProvider::TYPE_SEARCH),
392 providers_(TemplateURLServiceFactory::GetForProfile(profile)),
393 suggest_results_pending_(0),
394 field_trial_triggered_(false),
395 field_trial_triggered_in_session_(false) {
396 }
397
398 // static
CreateSearchSuggestion(AutocompleteProvider * autocomplete_provider,const AutocompleteInput & input,const base::string16 & input_text,int relevance,AutocompleteMatch::Type type,bool is_keyword,const base::string16 & match_contents,const base::string16 & annotation,const TemplateURL * template_url,const base::string16 & query_string,const std::string & suggest_query_params,int accepted_suggestion,int omnibox_start_margin,bool append_extra_query_params)399 AutocompleteMatch SearchProvider::CreateSearchSuggestion(
400 AutocompleteProvider* autocomplete_provider,
401 const AutocompleteInput& input,
402 const base::string16& input_text,
403 int relevance,
404 AutocompleteMatch::Type type,
405 bool is_keyword,
406 const base::string16& match_contents,
407 const base::string16& annotation,
408 const TemplateURL* template_url,
409 const base::string16& query_string,
410 const std::string& suggest_query_params,
411 int accepted_suggestion,
412 int omnibox_start_margin,
413 bool append_extra_query_params) {
414 AutocompleteMatch match(autocomplete_provider, relevance, false, type);
415
416 if (!template_url)
417 return match;
418 match.keyword = template_url->keyword();
419
420 SetAndClassifyMatchContents(query_string, input_text, match_contents, &match);
421
422 if (!annotation.empty())
423 match.description = annotation;
424
425 match.allowed_to_be_default_match = (input_text == match_contents);
426
427 // When the user forced a query, we need to make sure all the fill_into_edit
428 // values preserve that property. Otherwise, if the user starts editing a
429 // suggestion, non-Search results will suddenly appear.
430 if (input.type() == AutocompleteInput::FORCED_QUERY)
431 match.fill_into_edit.assign(ASCIIToUTF16("?"));
432 if (is_keyword)
433 match.fill_into_edit.append(match.keyword + char16(' '));
434 if (!input.prevent_inline_autocomplete() &&
435 StartsWith(query_string, input_text, false)) {
436 match.inline_autocompletion = query_string.substr(input_text.length());
437 match.allowed_to_be_default_match = true;
438 }
439 match.fill_into_edit.append(query_string);
440
441 const TemplateURLRef& search_url = template_url->url_ref();
442 DCHECK(search_url.SupportsReplacement());
443 match.search_terms_args.reset(
444 new TemplateURLRef::SearchTermsArgs(query_string));
445 match.search_terms_args->original_query = input_text;
446 match.search_terms_args->accepted_suggestion = accepted_suggestion;
447 match.search_terms_args->omnibox_start_margin = omnibox_start_margin;
448 match.search_terms_args->suggest_query_params = suggest_query_params;
449 match.search_terms_args->append_extra_query_params =
450 append_extra_query_params;
451 // This is the destination URL sans assisted query stats. This must be set
452 // so the AutocompleteController can properly de-dupe; the controller will
453 // eventually overwrite it before it reaches the user.
454 match.destination_url =
455 GURL(search_url.ReplaceSearchTerms(*match.search_terms_args.get()));
456
457 // Search results don't look like URLs.
458 match.transition = is_keyword ?
459 content::PAGE_TRANSITION_KEYWORD : content::PAGE_TRANSITION_GENERATED;
460
461 return match;
462 }
463
464 // static
ShouldPrefetch(const AutocompleteMatch & match)465 bool SearchProvider::ShouldPrefetch(const AutocompleteMatch& match) {
466 return match.GetAdditionalInfo(kShouldPrefetchKey) == kTrue;
467 }
468
469 // static
GetSuggestMetadata(const AutocompleteMatch & match)470 std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) {
471 return match.GetAdditionalInfo(kSuggestMetadataKey);
472 }
473
AddProviderInfo(ProvidersInfo * provider_info) const474 void SearchProvider::AddProviderInfo(ProvidersInfo* provider_info) const {
475 provider_info->push_back(metrics::OmniboxEventProto_ProviderInfo());
476 metrics::OmniboxEventProto_ProviderInfo& new_entry = provider_info->back();
477 new_entry.set_provider(AsOmniboxEventProviderType());
478 new_entry.set_provider_done(done_);
479 std::vector<uint32> field_trial_hashes;
480 OmniboxFieldTrial::GetActiveSuggestFieldTrialHashes(&field_trial_hashes);
481 for (size_t i = 0; i < field_trial_hashes.size(); ++i) {
482 if (field_trial_triggered_)
483 new_entry.mutable_field_trial_triggered()->Add(field_trial_hashes[i]);
484 if (field_trial_triggered_in_session_) {
485 new_entry.mutable_field_trial_triggered_in_session()->Add(
486 field_trial_hashes[i]);
487 }
488 }
489 }
490
DeleteMatch(const AutocompleteMatch & match)491 void SearchProvider::DeleteMatch(const AutocompleteMatch& match) {
492 DCHECK(match.deletable);
493
494 deletion_handlers_.push_back(new SuggestionDeletionHandler(
495 match.GetAdditionalInfo(SearchProvider::kDeletionUrlKey),
496 profile_,
497 base::Bind(&SearchProvider::OnDeletionComplete, base::Unretained(this))));
498
499 HistoryService* const history_service =
500 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
501 TemplateURL* template_url = match.GetTemplateURL(profile_, false);
502 // This may be NULL if the template corresponding to the keyword has been
503 // deleted or there is no keyword set.
504 if (template_url != NULL) {
505 history_service->DeleteMatchingURLsForKeyword(template_url->id(),
506 match.contents);
507 }
508
509 // Immediately update the list of matches to show the match was deleted,
510 // regardless of whether the server request actually succeeds.
511 DeleteMatchFromMatches(match);
512 }
513
ResetSession()514 void SearchProvider::ResetSession() {
515 field_trial_triggered_in_session_ = false;
516 }
517
~SearchProvider()518 SearchProvider::~SearchProvider() {
519 }
520
521 // static
RemoveStaleResults(const base::string16 & input,int verbatim_relevance,SuggestResults * suggest_results,NavigationResults * navigation_results)522 void SearchProvider::RemoveStaleResults(const base::string16& input,
523 int verbatim_relevance,
524 SuggestResults* suggest_results,
525 NavigationResults* navigation_results) {
526 DCHECK_GE(verbatim_relevance, 0);
527 // Keep pointers to the head of (the highest scoring elements of)
528 // |suggest_results| and |navigation_results|. Iterate down the lists
529 // removing non-inlineable results in order of decreasing relevance
530 // scores. Stop when the highest scoring element among those remaining
531 // is inlineable or the element is less than |verbatim_relevance|.
532 // This allows non-inlineable lower-scoring results to remain
533 // because (i) they are guaranteed to not be inlined and (ii)
534 // letting them remain reduces visual jank. For instance, as the
535 // user types the mis-spelled query "fpobar" (for foobar), the
536 // suggestion "foobar" will be suggested on every keystroke. If the
537 // SearchProvider always removes all non-inlineable results, the user will
538 // see visual jitter/jank as the result disappears and re-appears moments
539 // later as the suggest server returns results.
540 SuggestResults::iterator sug_it = suggest_results->begin();
541 NavigationResults::iterator nav_it = navigation_results->begin();
542 while ((sug_it != suggest_results->end()) ||
543 (nav_it != navigation_results->end())) {
544 const int sug_rel =
545 (sug_it != suggest_results->end()) ? sug_it->relevance() : -1;
546 const int nav_rel =
547 (nav_it != navigation_results->end()) ? nav_it->relevance() : -1;
548 if (std::max(sug_rel, nav_rel) < verbatim_relevance)
549 break;
550 if (sug_rel > nav_rel) {
551 // The current top result is a search suggestion.
552 if (sug_it->IsInlineable(input))
553 break;
554 sug_it = suggest_results->erase(sug_it);
555 } else if (sug_rel == nav_rel) {
556 // Have both results and they're tied.
557 const bool sug_inlineable = sug_it->IsInlineable(input);
558 const bool nav_inlineable = nav_it->IsInlineable(input);
559 if (!sug_inlineable)
560 sug_it = suggest_results->erase(sug_it);
561 if (!nav_inlineable)
562 nav_it = navigation_results->erase(nav_it);
563 if (sug_inlineable || nav_inlineable)
564 break;
565 } else {
566 // The current top result is a navigational suggestion.
567 if (nav_it->IsInlineable(input))
568 break;
569 nav_it = navigation_results->erase(nav_it);
570 }
571 }
572 }
573
574 // static
CalculateRelevanceForKeywordVerbatim(AutocompleteInput::Type type,bool prefer_keyword)575 int SearchProvider::CalculateRelevanceForKeywordVerbatim(
576 AutocompleteInput::Type type,
577 bool prefer_keyword) {
578 // This function is responsible for scoring verbatim query matches
579 // for non-extension keywords. KeywordProvider::CalculateRelevance()
580 // scores verbatim query matches for extension keywords, as well as
581 // for keyword matches (i.e., suggestions of a keyword itself, not a
582 // suggestion of a query on a keyword search engine). These two
583 // functions are currently in sync, but there's no reason we
584 // couldn't decide in the future to score verbatim matches
585 // differently for extension and non-extension keywords. If you
586 // make such a change, however, you should update this comment to
587 // describe it, so it's clear why the functions diverge.
588 if (prefer_keyword)
589 return 1500;
590 return (type == AutocompleteInput::QUERY) ? 1450 : 1100;
591 }
592
Start(const AutocompleteInput & input,bool minimal_changes)593 void SearchProvider::Start(const AutocompleteInput& input,
594 bool minimal_changes) {
595 // Do our best to load the model as early as possible. This will reduce
596 // odds of having the model not ready when really needed (a non-empty input).
597 TemplateURLService* model = providers_.template_url_service();
598 DCHECK(model);
599 model->Load();
600
601 matches_.clear();
602 field_trial_triggered_ = false;
603
604 // Can't return search/suggest results for bogus input or without a profile.
605 if (!profile_ || (input.type() == AutocompleteInput::INVALID)) {
606 Stop(false);
607 return;
608 }
609
610 keyword_input_ = input;
611 const TemplateURL* keyword_provider =
612 KeywordProvider::GetSubstitutingTemplateURLForInput(model,
613 &keyword_input_);
614 if (keyword_provider == NULL)
615 keyword_input_.Clear();
616 else if (keyword_input_.text().empty())
617 keyword_provider = NULL;
618
619 const TemplateURL* default_provider = model->GetDefaultSearchProvider();
620 if (default_provider && !default_provider->SupportsReplacement())
621 default_provider = NULL;
622
623 if (keyword_provider == default_provider)
624 default_provider = NULL; // No use in querying the same provider twice.
625
626 if (!default_provider && !keyword_provider) {
627 // No valid providers.
628 Stop(false);
629 return;
630 }
631
632 // If we're still running an old query but have since changed the query text
633 // or the providers, abort the query.
634 base::string16 default_provider_keyword(default_provider ?
635 default_provider->keyword() : base::string16());
636 base::string16 keyword_provider_keyword(keyword_provider ?
637 keyword_provider->keyword() : base::string16());
638 if (!minimal_changes ||
639 !providers_.equal(default_provider_keyword, keyword_provider_keyword)) {
640 // Cancel any in-flight suggest requests.
641 if (!done_)
642 Stop(false);
643 }
644
645 providers_.set(default_provider_keyword, keyword_provider_keyword);
646
647 if (input.text().empty()) {
648 // User typed "?" alone. Give them a placeholder result indicating what
649 // this syntax does.
650 if (default_provider) {
651 AutocompleteMatch match;
652 match.provider = this;
653 match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
654 match.contents_class.push_back(
655 ACMatchClassification(0, ACMatchClassification::NONE));
656 match.keyword = providers_.default_provider();
657 match.allowed_to_be_default_match = true;
658 matches_.push_back(match);
659 }
660 Stop(false);
661 return;
662 }
663
664 input_ = input;
665
666 DoHistoryQuery(minimal_changes);
667 StartOrStopSuggestQuery(minimal_changes);
668 UpdateMatches();
669 }
670
Stop(bool clear_cached_results)671 void SearchProvider::Stop(bool clear_cached_results) {
672 StopSuggest();
673 done_ = true;
674
675 if (clear_cached_results)
676 ClearAllResults();
677 }
678
OnURLFetchComplete(const net::URLFetcher * source)679 void SearchProvider::OnURLFetchComplete(const net::URLFetcher* source) {
680 DCHECK(!done_);
681 suggest_results_pending_--;
682 LogOmniboxSuggestRequest(REPLY_RECEIVED);
683 DCHECK_GE(suggest_results_pending_, 0); // Should never go negative.
684
685 const bool is_keyword = (source == keyword_fetcher_.get());
686 // Ensure the request succeeded and that the provider used is still available.
687 // A verbatim match cannot be generated without this provider, causing errors.
688 const bool request_succeeded =
689 source->GetStatus().is_success() && (source->GetResponseCode() == 200) &&
690 (is_keyword ?
691 providers_.GetKeywordProviderURL() :
692 providers_.GetDefaultProviderURL());
693
694 // Record response time for suggest requests sent to Google. We care
695 // only about the common case: the Google default provider used in
696 // non-keyword mode.
697 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
698 if (!is_keyword && default_url &&
699 (TemplateURLPrepopulateData::GetEngineType(*default_url) ==
700 SEARCH_ENGINE_GOOGLE)) {
701 const base::TimeDelta elapsed_time =
702 base::TimeTicks::Now() - time_suggest_request_sent_;
703 if (request_succeeded) {
704 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
705 elapsed_time);
706 } else {
707 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
708 elapsed_time);
709 }
710 }
711
712 bool results_updated = false;
713 if (request_succeeded) {
714 const net::HttpResponseHeaders* const response_headers =
715 source->GetResponseHeaders();
716 std::string json_data;
717 source->GetResponseAsString(&json_data);
718
719 // JSON is supposed to be UTF-8, but some suggest service providers send
720 // JSON files in non-UTF-8 encodings. The actual encoding is usually
721 // specified in the Content-Type header field.
722 if (response_headers) {
723 std::string charset;
724 if (response_headers->GetCharset(&charset)) {
725 base::string16 data_16;
726 // TODO(jungshik): Switch to CodePageToUTF8 after it's added.
727 if (base::CodepageToUTF16(json_data, charset.c_str(),
728 base::OnStringConversionError::FAIL,
729 &data_16))
730 json_data = UTF16ToUTF8(data_16);
731 }
732 }
733
734 scoped_ptr<Value> data(DeserializeJsonData(json_data));
735 results_updated = data.get() && ParseSuggestResults(data.get(), is_keyword);
736 }
737
738 UpdateMatches();
739 if (done_ || results_updated)
740 listener_->OnProviderUpdate(results_updated);
741 }
742
OnDeletionComplete(bool success,SuggestionDeletionHandler * handler)743 void SearchProvider::OnDeletionComplete(bool success,
744 SuggestionDeletionHandler* handler) {
745 RecordDeletionResult(success);
746 SuggestionDeletionHandlers::iterator it = std::find(
747 deletion_handlers_.begin(), deletion_handlers_.end(), handler);
748 DCHECK(it != deletion_handlers_.end());
749 deletion_handlers_.erase(it);
750 }
751
752
RecordDeletionResult(bool success)753 void SearchProvider::RecordDeletionResult(bool success) {
754 if (success) {
755 content::RecordAction(
756 content::UserMetricsAction("Omnibox.ServerSuggestDelete.Success"));
757 } else {
758 content::RecordAction(
759 content::UserMetricsAction("Omnibox.ServerSuggestDelete.Failure"));
760 }
761 }
762
DeleteMatchFromMatches(const AutocompleteMatch & match)763 void SearchProvider::DeleteMatchFromMatches(const AutocompleteMatch& match) {
764 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i) {
765 // Find the desired match to delete by checking the type and contents.
766 // We can't check the destination URL, because the autocomplete controller
767 // may have reformulated that. Not that while checking for matching
768 // contents works for personalized suggestions, if more match types gain
769 // deletion support, this algorithm may need to be re-examined.
770 if (i->contents == match.contents && i->type == match.type) {
771 matches_.erase(i);
772 break;
773 }
774 }
775 listener_->OnProviderUpdate(true);
776 }
777
Run()778 void SearchProvider::Run() {
779 // Start a new request with the current input.
780 suggest_results_pending_ = 0;
781 time_suggest_request_sent_ = base::TimeTicks::Now();
782
783 default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
784 providers_.GetDefaultProviderURL(), input_));
785 keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID,
786 providers_.GetKeywordProviderURL(), keyword_input_));
787
788 // Both the above can fail if the providers have been modified or deleted
789 // since the query began.
790 if (suggest_results_pending_ == 0) {
791 UpdateDone();
792 // We only need to update the listener if we're actually done.
793 if (done_)
794 listener_->OnProviderUpdate(false);
795 }
796 }
797
DoHistoryQuery(bool minimal_changes)798 void SearchProvider::DoHistoryQuery(bool minimal_changes) {
799 // The history query results are synchronous, so if minimal_changes is true,
800 // we still have the last results and don't need to do anything.
801 if (minimal_changes)
802 return;
803
804 base::TimeTicks do_history_query_start_time(base::TimeTicks::Now());
805
806 keyword_history_results_.clear();
807 default_history_results_.clear();
808
809 if (OmniboxFieldTrial::SearchHistoryDisable(
810 input_.current_page_classification()))
811 return;
812
813 base::TimeTicks start_time(base::TimeTicks::Now());
814 HistoryService* const history_service =
815 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
816 base::TimeTicks now(base::TimeTicks::Now());
817 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.GetHistoryServiceTime",
818 now - start_time);
819 start_time = now;
820 history::URLDatabase* url_db = history_service ?
821 history_service->InMemoryDatabase() : NULL;
822 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.InMemoryDatabaseTime",
823 base::TimeTicks::Now() - start_time);
824 if (!url_db)
825 return;
826
827 // Request history for both the keyword and default provider. We grab many
828 // more matches than we'll ultimately clamp to so that if there are several
829 // recent multi-word matches who scores are lowered (see
830 // AddHistoryResultsToMap()), they won't crowd out older, higher-scoring
831 // matches. Note that this doesn't fix the problem entirely, but merely
832 // limits it to cases with a very large number of such multi-word matches; for
833 // now, this seems OK compared with the complexity of a real fix, which would
834 // require multiple searches and tracking of "single- vs. multi-word" in the
835 // database.
836 int num_matches = kMaxMatches * 5;
837 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
838 if (default_url) {
839 start_time = base::TimeTicks::Now();
840 url_db->GetMostRecentKeywordSearchTerms(default_url->id(), input_.text(),
841 num_matches, &default_history_results_);
842 UMA_HISTOGRAM_TIMES(
843 "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime",
844 base::TimeTicks::Now() - start_time);
845 }
846 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
847 if (keyword_url) {
848 url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(),
849 keyword_input_.text(), num_matches, &keyword_history_results_);
850 }
851 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.DoHistoryQueryTime",
852 base::TimeTicks::Now() - do_history_query_start_time);
853 }
854
StartOrStopSuggestQuery(bool minimal_changes)855 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
856 if (!IsQuerySuitableForSuggest()) {
857 StopSuggest();
858 ClearAllResults();
859 return;
860 }
861
862 // For the minimal_changes case, if we finished the previous query and still
863 // have its results, or are allowed to keep running it, just do that, rather
864 // than starting a new query.
865 if (minimal_changes &&
866 (!default_results_.suggest_results.empty() ||
867 !default_results_.navigation_results.empty() ||
868 !keyword_results_.suggest_results.empty() ||
869 !keyword_results_.navigation_results.empty() ||
870 (!done_ &&
871 input_.matches_requested() == AutocompleteInput::ALL_MATCHES)))
872 return;
873
874 // We can't keep running any previous query, so halt it.
875 StopSuggest();
876
877 // Remove existing results that cannot inline autocomplete the new input.
878 RemoveAllStaleResults();
879
880 // We can't start a new query if we're only allowed synchronous results.
881 if (input_.matches_requested() != AutocompleteInput::ALL_MATCHES)
882 return;
883
884 // To avoid flooding the suggest server, don't send a query until at
885 // least 100 ms since the last query.
886 base::TimeTicks next_suggest_time(time_suggest_request_sent_ +
887 base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs));
888 base::TimeTicks now(base::TimeTicks::Now());
889 if (now >= next_suggest_time) {
890 Run();
891 return;
892 }
893 timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run);
894 }
895
IsQuerySuitableForSuggest() const896 bool SearchProvider::IsQuerySuitableForSuggest() const {
897 // Don't run Suggest in incognito mode, if the engine doesn't support it, or
898 // if the user has disabled it.
899 const TemplateURL* default_url = providers_.GetDefaultProviderURL();
900 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
901 if (profile_->IsOffTheRecord() ||
902 ((!default_url || default_url->suggestions_url().empty()) &&
903 (!keyword_url || keyword_url->suggestions_url().empty())) ||
904 !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled))
905 return false;
906
907 // If the input type might be a URL, we take extra care so that private data
908 // isn't sent to the server.
909
910 // FORCED_QUERY means the user is explicitly asking us to search for this, so
911 // we assume it isn't a URL and/or there isn't private data.
912 if (input_.type() == AutocompleteInput::FORCED_QUERY)
913 return true;
914
915 // Next we check the scheme. If this is UNKNOWN/URL with a scheme that isn't
916 // http/https/ftp, we shouldn't send it. Sending things like file: and data:
917 // is both a waste of time and a disclosure of potentially private, local
918 // data. Other "schemes" may actually be usernames, and we don't want to send
919 // passwords. If the scheme is OK, we still need to check other cases below.
920 // If this is QUERY, then the presence of these schemes means the user
921 // explicitly typed one, and thus this is probably a URL that's being entered
922 // and happens to currently be invalid -- in which case we again want to run
923 // our checks below. Other QUERY cases are less likely to be URLs and thus we
924 // assume we're OK.
925 if (!LowerCaseEqualsASCII(input_.scheme(), content::kHttpScheme) &&
926 !LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
927 !LowerCaseEqualsASCII(input_.scheme(), content::kFtpScheme))
928 return (input_.type() == AutocompleteInput::QUERY);
929
930 // Don't send URLs with usernames, queries or refs. Some of these are
931 // private, and the Suggest server is unlikely to have any useful results
932 // for any of them. Also don't send URLs with ports, as we may initially
933 // think that a username + password is a host + port (and we don't want to
934 // send usernames/passwords), and even if the port really is a port, the
935 // server is once again unlikely to have and useful results.
936 // Note that we only block based on refs if the input is URL-typed, as search
937 // queries can legitimately have #s in them which the URL parser
938 // overaggressively categorizes as a url with a ref.
939 const url_parse::Parsed& parts = input_.parts();
940 if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
941 parts.query.is_nonempty() ||
942 (parts.ref.is_nonempty() && (input_.type() == AutocompleteInput::URL)))
943 return false;
944
945 // Don't send anything for https except the hostname. Hostnames are OK
946 // because they are visible when the TCP connection is established, but the
947 // specific path may reveal private information.
948 if (LowerCaseEqualsASCII(input_.scheme(), content::kHttpsScheme) &&
949 parts.path.is_nonempty())
950 return false;
951
952 return true;
953 }
954
StopSuggest()955 void SearchProvider::StopSuggest() {
956 // Increment the appropriate field in the histogram by the number of
957 // pending requests that were invalidated.
958 for (int i = 0; i < suggest_results_pending_; i++)
959 LogOmniboxSuggestRequest(REQUEST_INVALIDATED);
960 suggest_results_pending_ = 0;
961 timer_.Stop();
962 // Stop any in-progress URL fetches.
963 keyword_fetcher_.reset();
964 default_fetcher_.reset();
965 }
966
ClearAllResults()967 void SearchProvider::ClearAllResults() {
968 keyword_results_.Clear();
969 default_results_.Clear();
970 }
971
RemoveAllStaleResults()972 void SearchProvider::RemoveAllStaleResults() {
973 // We only need to remove stale results (which ensures the top-scoring
974 // match is inlineable) if the user is not in reorder mode. In reorder
975 // mode, the autocomplete system will reorder results to make sure the
976 // top result is inlineable.
977 const bool omnibox_will_reorder_for_legal_default_match =
978 OmniboxFieldTrial::ReorderForLegalDefaultMatch(
979 input_.current_page_classification());
980 // In theory it would be better to run an algorithm like that in
981 // RemoveStaleResults(...) below that uses all four results lists
982 // and both verbatim scores at once. However, that will be much
983 // more complicated for little obvious gain. For code simplicity
984 // and ease in reasoning about the invariants involved, this code
985 // removes stales results from the keyword provider and default
986 // provider independently.
987 if (!omnibox_will_reorder_for_legal_default_match) {
988 RemoveStaleResults(input_.text(), GetVerbatimRelevance(NULL),
989 &default_results_.suggest_results,
990 &default_results_.navigation_results);
991 if (!keyword_input_.text().empty()) {
992 RemoveStaleResults(keyword_input_.text(),
993 GetKeywordVerbatimRelevance(NULL),
994 &keyword_results_.suggest_results,
995 &keyword_results_.navigation_results);
996 }
997 }
998 if (keyword_input_.text().empty()) {
999 // User is either in keyword mode with a blank input or out of
1000 // keyword mode entirely.
1001 keyword_results_.Clear();
1002 }
1003 }
1004
ApplyCalculatedRelevance()1005 void SearchProvider::ApplyCalculatedRelevance() {
1006 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
1007 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
1008 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
1009 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
1010 default_results_.verbatim_relevance = -1;
1011 keyword_results_.verbatim_relevance = -1;
1012 }
1013
ApplyCalculatedSuggestRelevance(SuggestResults * list)1014 void SearchProvider::ApplyCalculatedSuggestRelevance(SuggestResults* list) {
1015 for (size_t i = 0; i < list->size(); ++i) {
1016 SuggestResult& result = (*list)[i];
1017 result.set_relevance(
1018 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
1019 (list->size() - i - 1));
1020 result.set_relevance_from_server(false);
1021 }
1022 }
1023
ApplyCalculatedNavigationRelevance(NavigationResults * list)1024 void SearchProvider::ApplyCalculatedNavigationRelevance(
1025 NavigationResults* list) {
1026 for (size_t i = 0; i < list->size(); ++i) {
1027 NavigationResult& result = (*list)[i];
1028 result.set_relevance(
1029 result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
1030 (list->size() - i - 1));
1031 result.set_relevance_from_server(false);
1032 }
1033 }
1034
CreateSuggestFetcher(int id,const TemplateURL * template_url,const AutocompleteInput & input)1035 net::URLFetcher* SearchProvider::CreateSuggestFetcher(
1036 int id,
1037 const TemplateURL* template_url,
1038 const AutocompleteInput& input) {
1039 if (!template_url || template_url->suggestions_url().empty())
1040 return NULL;
1041
1042 // Bail if the suggestion URL is invalid with the given replacements.
1043 TemplateURLRef::SearchTermsArgs search_term_args(input.text());
1044 search_term_args.cursor_position = input.cursor_position();
1045 search_term_args.page_classification = input.current_page_classification();
1046 GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
1047 search_term_args));
1048 if (!suggest_url.is_valid())
1049 return NULL;
1050 // Send the current page URL if user setting and URL requirements are met and
1051 // the user is in the field trial.
1052 if (CanSendURL(current_page_url_, suggest_url, template_url,
1053 input.current_page_classification(), profile_) &&
1054 OmniboxFieldTrial::InZeroSuggestAfterTypingFieldTrial()) {
1055 search_term_args.current_page_url = current_page_url_.spec();
1056 // Create the suggest URL again with the current page URL.
1057 suggest_url = GURL(template_url->suggestions_url_ref().ReplaceSearchTerms(
1058 search_term_args));
1059 }
1060
1061 suggest_results_pending_++;
1062 LogOmniboxSuggestRequest(REQUEST_SENT);
1063
1064 net::URLFetcher* fetcher =
1065 net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this);
1066 fetcher->SetRequestContext(profile_->GetRequestContext());
1067 fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES);
1068 // Add Chrome experiment state to the request headers.
1069 net::HttpRequestHeaders headers;
1070 chrome_variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders(
1071 fetcher->GetOriginalURL(), profile_->IsOffTheRecord(), false, &headers);
1072 fetcher->SetExtraRequestHeaders(headers.ToString());
1073 fetcher->Start();
1074 return fetcher;
1075 }
1076
DeserializeJsonData(std::string json_data)1077 scoped_ptr<Value> SearchProvider::DeserializeJsonData(std::string json_data) {
1078 // The JSON response should be an array.
1079 for (size_t response_start_index = json_data.find("["), i = 0;
1080 response_start_index != std::string::npos && i < 5;
1081 response_start_index = json_data.find("[", 1), i++) {
1082 // Remove any XSSI guards to allow for JSON parsing.
1083 if (response_start_index > 0)
1084 json_data.erase(0, response_start_index);
1085
1086 JSONStringValueSerializer deserializer(json_data);
1087 deserializer.set_allow_trailing_comma(true);
1088 int error_code = 0;
1089 scoped_ptr<Value> data(deserializer.Deserialize(&error_code, NULL));
1090 if (error_code == 0)
1091 return data.Pass();
1092 }
1093 return scoped_ptr<Value>();
1094 }
1095
ParseSuggestResults(Value * root_val,bool is_keyword)1096 bool SearchProvider::ParseSuggestResults(Value* root_val, bool is_keyword) {
1097 base::string16 query;
1098 ListValue* root_list = NULL;
1099 ListValue* results_list = NULL;
1100 const base::string16& input_text =
1101 is_keyword ? keyword_input_.text() : input_.text();
1102 if (!root_val->GetAsList(&root_list) || !root_list->GetString(0, &query) ||
1103 (query != input_text) || !root_list->GetList(1, &results_list))
1104 return false;
1105
1106 // 3rd element: Description list.
1107 ListValue* descriptions = NULL;
1108 root_list->GetList(2, &descriptions);
1109
1110 // 4th element: Disregard the query URL list for now.
1111
1112 // Reset suggested relevance information from the default provider.
1113 Results* results = is_keyword ? &keyword_results_ : &default_results_;
1114 results->verbatim_relevance = -1;
1115
1116 // 5th element: Optional key-value pairs from the Suggest server.
1117 ListValue* types = NULL;
1118 ListValue* relevances = NULL;
1119 ListValue* suggestion_details = NULL;
1120 DictionaryValue* extras = NULL;
1121 int prefetch_index = -1;
1122 if (root_list->GetDictionary(4, &extras)) {
1123 extras->GetList("google:suggesttype", &types);
1124
1125 // Discard this list if its size does not match that of the suggestions.
1126 if (extras->GetList("google:suggestrelevance", &relevances) &&
1127 (relevances->GetSize() != results_list->GetSize()))
1128 relevances = NULL;
1129 extras->GetInteger("google:verbatimrelevance",
1130 &results->verbatim_relevance);
1131
1132 // Check if the active suggest field trial (if any) has triggered either
1133 // for the default provider or keyword provider.
1134 bool triggered = false;
1135 extras->GetBoolean("google:fieldtrialtriggered", &triggered);
1136 field_trial_triggered_ |= triggered;
1137 field_trial_triggered_in_session_ |= triggered;
1138
1139 DictionaryValue* client_data = NULL;
1140 if (extras->GetDictionary("google:clientdata", &client_data) && client_data)
1141 client_data->GetInteger("phi", &prefetch_index);
1142
1143 if (extras->GetList("google:suggestdetail", &suggestion_details) &&
1144 suggestion_details->GetSize() != results_list->GetSize())
1145 suggestion_details = NULL;
1146
1147 // Store the metadata that came with the response in case we need to pass it
1148 // along with the prefetch query to Instant.
1149 JSONStringValueSerializer json_serializer(&results->metadata);
1150 json_serializer.Serialize(*extras);
1151 }
1152
1153 // Clear the previous results now that new results are available.
1154 results->suggest_results.clear();
1155 results->navigation_results.clear();
1156
1157 base::string16 suggestion;
1158 std::string type;
1159 int relevance = -1;
1160 // Prohibit navsuggest in FORCED_QUERY mode. Users wants queries, not URLs.
1161 const bool allow_navsuggest =
1162 (is_keyword ? keyword_input_.type() : input_.type()) !=
1163 AutocompleteInput::FORCED_QUERY;
1164 for (size_t index = 0; results_list->GetString(index, &suggestion); ++index) {
1165 // Google search may return empty suggestions for weird input characters,
1166 // they make no sense at all and can cause problems in our code.
1167 if (suggestion.empty())
1168 continue;
1169
1170 // Apply valid suggested relevance scores; discard invalid lists.
1171 if (relevances != NULL && !relevances->GetInteger(index, &relevance))
1172 relevances = NULL;
1173 if (types && types->GetString(index, &type) && (type == "NAVIGATION")) {
1174 // Do not blindly trust the URL coming from the server to be valid.
1175 GURL url(URLFixerUpper::FixupURL(UTF16ToUTF8(suggestion), std::string()));
1176 if (url.is_valid() && allow_navsuggest) {
1177 base::string16 title;
1178 if (descriptions != NULL)
1179 descriptions->GetString(index, &title);
1180 results->navigation_results.push_back(NavigationResult(
1181 *this, url, title, is_keyword, relevance, true));
1182 }
1183 } else {
1184 AutocompleteMatchType::Type match_type = GetAutocompleteMatchType(type);
1185 bool should_prefetch = static_cast<int>(index) == prefetch_index;
1186 DictionaryValue* suggestion_detail = NULL;
1187 base::string16 match_contents = suggestion;
1188 base::string16 annotation;
1189 std::string suggest_query_params;
1190 std::string deletion_url;
1191
1192 if (suggestion_details) {
1193 suggestion_details->GetDictionary(index, &suggestion_detail);
1194 if (suggestion_detail) {
1195 suggestion_detail->GetString("du", &deletion_url);
1196 suggestion_detail->GetString("title", &match_contents) ||
1197 suggestion_detail->GetString("t", &match_contents);
1198 suggestion_detail->GetString("annotation", &annotation) ||
1199 suggestion_detail->GetString("a", &annotation);
1200 suggestion_detail->GetString("query_params", &suggest_query_params) ||
1201 suggestion_detail->GetString("q", &suggest_query_params);
1202 }
1203 }
1204
1205 // TODO(kochi): Improve calculator suggestion presentation.
1206 results->suggest_results.push_back(SuggestResult(
1207 suggestion, match_type, match_contents, annotation,
1208 suggest_query_params, deletion_url, is_keyword, relevance, true,
1209 should_prefetch));
1210 }
1211 }
1212
1213 // Ignore suggested scores for non-keyword matches in keyword mode; if the
1214 // server is allowed to score these, it could interfere with the user's
1215 // ability to get good keyword results.
1216 const bool abandon_suggested_scores =
1217 !is_keyword && !providers_.keyword_provider().empty();
1218 // Apply calculated relevance scores to suggestions if a valid list was
1219 // not provided or we're abandoning suggested scores entirely.
1220 if ((relevances == NULL) || abandon_suggested_scores) {
1221 ApplyCalculatedSuggestRelevance(&results->suggest_results);
1222 ApplyCalculatedNavigationRelevance(&results->navigation_results);
1223 // If abandoning scores entirely, also abandon the verbatim score.
1224 if (abandon_suggested_scores)
1225 results->verbatim_relevance = -1;
1226 }
1227
1228 // Keep the result lists sorted.
1229 const CompareScoredResults comparator = CompareScoredResults();
1230 std::stable_sort(results->suggest_results.begin(),
1231 results->suggest_results.end(),
1232 comparator);
1233 std::stable_sort(results->navigation_results.begin(),
1234 results->navigation_results.end(),
1235 comparator);
1236 return true;
1237 }
1238
ConvertResultsToAutocompleteMatches()1239 void SearchProvider::ConvertResultsToAutocompleteMatches() {
1240 // Convert all the results to matches and add them to a map, so we can keep
1241 // the most relevant match for each result.
1242 base::TimeTicks start_time(base::TimeTicks::Now());
1243 MatchMap map;
1244 const base::Time no_time;
1245 int did_not_accept_keyword_suggestion =
1246 keyword_results_.suggest_results.empty() ?
1247 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
1248 TemplateURLRef::NO_SUGGESTION_CHOSEN;
1249
1250 bool relevance_from_server;
1251 int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
1252 int did_not_accept_default_suggestion =
1253 default_results_.suggest_results.empty() ?
1254 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
1255 TemplateURLRef::NO_SUGGESTION_CHOSEN;
1256 if (verbatim_relevance > 0) {
1257 SuggestResult verbatim(
1258 input_.text(), AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
1259 input_.text(), base::string16(), std::string(), std::string(),
1260 false, verbatim_relevance, relevance_from_server, false);
1261 AddMatchToMap(verbatim, input_.text(), std::string(),
1262 did_not_accept_default_suggestion, &map);
1263 }
1264 if (!keyword_input_.text().empty()) {
1265 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1266 // We only create the verbatim search query match for a keyword
1267 // if it's not an extension keyword. Extension keywords are handled
1268 // in KeywordProvider::Start(). (Extensions are complicated...)
1269 // Note: in this provider, SEARCH_OTHER_ENGINE must correspond
1270 // to the keyword verbatim search query. Do not create other matches
1271 // of type SEARCH_OTHER_ENGINE.
1272 if (keyword_url &&
1273 (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
1274 bool keyword_relevance_from_server;
1275 const int keyword_verbatim_relevance =
1276 GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
1277 if (keyword_verbatim_relevance > 0) {
1278 SuggestResult verbatim(
1279 keyword_input_.text(), AutocompleteMatchType::SEARCH_OTHER_ENGINE,
1280 keyword_input_.text(), base::string16(), std::string(),
1281 std::string(), true, keyword_verbatim_relevance,
1282 keyword_relevance_from_server, false);
1283 AddMatchToMap(verbatim, keyword_input_.text(), std::string(),
1284 did_not_accept_keyword_suggestion, &map);
1285 }
1286 }
1287 }
1288 AddHistoryResultsToMap(keyword_history_results_, true,
1289 did_not_accept_keyword_suggestion, &map);
1290 AddHistoryResultsToMap(default_history_results_, false,
1291 did_not_accept_default_suggestion, &map);
1292
1293 AddSuggestResultsToMap(keyword_results_.suggest_results,
1294 keyword_results_.metadata, &map);
1295 AddSuggestResultsToMap(default_results_.suggest_results,
1296 default_results_.metadata, &map);
1297
1298 ACMatches matches;
1299 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
1300 matches.push_back(i->second);
1301
1302 AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
1303 AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
1304
1305 // Now add the most relevant matches to |matches_|. We take up to kMaxMatches
1306 // suggest/navsuggest matches, regardless of origin. If Instant Extended is
1307 // enabled and we have server-provided (and thus hopefully more accurate)
1308 // scores for some suggestions, we allow more of those, until we reach
1309 // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
1310 // whole popup).
1311 //
1312 // We will always return any verbatim matches, no matter how we obtained their
1313 // scores, unless we have already accepted AutocompleteResult::kMaxMatches
1314 // higher-scoring matches under the conditions above.
1315 UMA_HISTOGRAM_CUSTOM_COUNTS(
1316 "Omnibox.SearchProvider.NumMatchesToSort", matches.size(), 1, 50, 20);
1317 std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
1318 matches_.clear();
1319
1320 size_t num_suggestions = 0;
1321 for (ACMatches::const_iterator i(matches.begin());
1322 (i != matches.end()) &&
1323 (matches_.size() < AutocompleteResult::kMaxMatches);
1324 ++i) {
1325 // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
1326 // verbatim result, so this condition basically means "if this match is a
1327 // suggestion of some sort".
1328 if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
1329 (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
1330 // If we've already hit the limit on non-server-scored suggestions, and
1331 // this isn't a server-scored suggestion we can add, skip it.
1332 if ((num_suggestions >= kMaxMatches) &&
1333 (!chrome::IsInstantExtendedAPIEnabled() ||
1334 (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
1335 continue;
1336 }
1337
1338 ++num_suggestions;
1339 }
1340
1341 matches_.push_back(*i);
1342 }
1343 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime",
1344 base::TimeTicks::Now() - start_time);
1345 }
1346
FindTopMatch(bool autocomplete_result_will_reorder_for_default_match) const1347 ACMatches::const_iterator SearchProvider::FindTopMatch(
1348 bool autocomplete_result_will_reorder_for_default_match) const {
1349 if (!autocomplete_result_will_reorder_for_default_match)
1350 return matches_.begin();
1351 ACMatches::const_iterator it = matches_.begin();
1352 while ((it != matches_.end()) && !it->allowed_to_be_default_match)
1353 ++it;
1354 return it;
1355 }
1356
IsTopMatchNavigationInKeywordMode(bool autocomplete_result_will_reorder_for_default_match) const1357 bool SearchProvider::IsTopMatchNavigationInKeywordMode(
1358 bool autocomplete_result_will_reorder_for_default_match) const {
1359 ACMatches::const_iterator first_match =
1360 FindTopMatch(autocomplete_result_will_reorder_for_default_match);
1361 return !providers_.keyword_provider().empty() &&
1362 (first_match != matches_.end()) &&
1363 (first_match->type == AutocompleteMatchType::NAVSUGGEST);
1364 }
1365
HasKeywordDefaultMatchInKeywordMode() const1366 bool SearchProvider::HasKeywordDefaultMatchInKeywordMode() const {
1367 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1368 // If the user is not in keyword mode, return true to say that this
1369 // constraint is not violated.
1370 if (keyword_url == NULL)
1371 return true;
1372 for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
1373 ++it) {
1374 if ((it->keyword == keyword_url->keyword()) &&
1375 it->allowed_to_be_default_match)
1376 return true;
1377 }
1378 return false;
1379 }
1380
IsTopMatchScoreTooLow(bool autocomplete_result_will_reorder_for_default_match) const1381 bool SearchProvider::IsTopMatchScoreTooLow(
1382 bool autocomplete_result_will_reorder_for_default_match) const {
1383 // In reorder mode, there's no such thing as a score that's too low.
1384 if (autocomplete_result_will_reorder_for_default_match)
1385 return false;
1386
1387 // Here we use CalculateRelevanceForVerbatimIgnoringKeywordModeState()
1388 // rather than CalculateRelevanceForVerbatim() because the latter returns
1389 // a very low score (250) if keyword mode is active. This is because
1390 // when keyword mode is active the user probably wants the keyword matches,
1391 // not matches from the default provider. Hence, we use the version of
1392 // the function that ignores whether keyword mode is active. This allows
1393 // SearchProvider to maintain its contract with the AutocompleteController
1394 // that it will always provide an inlineable match with a reasonable
1395 // score.
1396 return matches_.front().relevance <
1397 CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1398 }
1399
IsTopMatchSearchWithURLInput(bool autocomplete_result_will_reorder_for_default_match) const1400 bool SearchProvider::IsTopMatchSearchWithURLInput(
1401 bool autocomplete_result_will_reorder_for_default_match) const {
1402 ACMatches::const_iterator first_match =
1403 FindTopMatch(autocomplete_result_will_reorder_for_default_match);
1404 return (input_.type() == AutocompleteInput::URL) &&
1405 (first_match != matches_.end()) &&
1406 (first_match->relevance > CalculateRelevanceForVerbatim()) &&
1407 (first_match->type != AutocompleteMatchType::NAVSUGGEST);
1408 }
1409
HasValidDefaultMatch(bool autocomplete_result_will_reorder_for_default_match) const1410 bool SearchProvider::HasValidDefaultMatch(
1411 bool autocomplete_result_will_reorder_for_default_match) const {
1412 // One of the SearchProvider matches may need to be the overall default. If
1413 // AutocompleteResult is allowed to reorder matches, this means we simply
1414 // need at least one match in the list to be |allowed_to_be_default_match|.
1415 // If no reordering is possible, however, then our first match needs to have
1416 // this flag.
1417 for (ACMatches::const_iterator it = matches_.begin(); it != matches_.end();
1418 ++it) {
1419 if (it->allowed_to_be_default_match)
1420 return true;
1421 if (!autocomplete_result_will_reorder_for_default_match)
1422 return false;
1423 }
1424 return false;
1425 }
1426
UpdateMatches()1427 void SearchProvider::UpdateMatches() {
1428 base::TimeTicks update_matches_start_time(base::TimeTicks::Now());
1429 ConvertResultsToAutocompleteMatches();
1430
1431 // Check constraints that may be violated by suggested relevances.
1432 if (!matches_.empty() &&
1433 (default_results_.HasServerProvidedScores() ||
1434 keyword_results_.HasServerProvidedScores())) {
1435 // These blocks attempt to repair undesirable behavior by suggested
1436 // relevances with minimal impact, preserving other suggested relevances.
1437
1438 // True if the omnibox will reorder matches as necessary to make the first
1439 // one something that is allowed to be the default match.
1440 const bool omnibox_will_reorder_for_legal_default_match =
1441 OmniboxFieldTrial::ReorderForLegalDefaultMatch(
1442 input_.current_page_classification());
1443 if (IsTopMatchNavigationInKeywordMode(
1444 omnibox_will_reorder_for_legal_default_match)) {
1445 // Correct the suggested relevance scores if the top match is a
1446 // navigation in keyword mode, since inlining a navigation match
1447 // would break the user out of keyword mode. This will only be
1448 // triggered in regular (non-reorder) mode; in reorder mode,
1449 // navigation matches are marked as not allowed to be the default
1450 // match and hence IsTopMatchNavigation() will always return false.
1451 DCHECK(!omnibox_will_reorder_for_legal_default_match);
1452 DemoteKeywordNavigationMatchesPastTopQuery();
1453 ConvertResultsToAutocompleteMatches();
1454 DCHECK(!IsTopMatchNavigationInKeywordMode(
1455 omnibox_will_reorder_for_legal_default_match));
1456 }
1457 if (!HasKeywordDefaultMatchInKeywordMode()) {
1458 // In keyword mode, disregard the keyword verbatim suggested relevance
1459 // if necessary so there at least one keyword match that's allowed to
1460 // be the default match.
1461 keyword_results_.verbatim_relevance = -1;
1462 ConvertResultsToAutocompleteMatches();
1463 }
1464 if (IsTopMatchScoreTooLow(omnibox_will_reorder_for_legal_default_match)) {
1465 // Disregard the suggested verbatim relevance if the top score is below
1466 // the usual verbatim value. For example, a BarProvider may rely on
1467 // SearchProvider's verbatim or inlineable matches for input "foo" (all
1468 // allowed to be default match) to always outrank its own lowly-ranked
1469 // "bar" matches that shouldn't be the default match.
1470 default_results_.verbatim_relevance = -1;
1471 keyword_results_.verbatim_relevance = -1;
1472 ConvertResultsToAutocompleteMatches();
1473 }
1474 if (IsTopMatchSearchWithURLInput(
1475 omnibox_will_reorder_for_legal_default_match)) {
1476 // Disregard the suggested search and verbatim relevances if the input
1477 // type is URL and the top match is a highly-ranked search suggestion.
1478 // For example, prevent a search for "foo.com" from outranking another
1479 // provider's navigation for "foo.com" or "foo.com/url_from_history".
1480 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
1481 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
1482 default_results_.verbatim_relevance = -1;
1483 keyword_results_.verbatim_relevance = -1;
1484 ConvertResultsToAutocompleteMatches();
1485 }
1486 if (!HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match)) {
1487 // If the omnibox is not going to reorder results to put a legal default
1488 // match at the top, then this provider needs to guarantee that its top
1489 // scoring result is a legal default match (i.e., it's either a verbatim
1490 // match or inlinable). For example, input "foo" should not invoke a
1491 // search for "bar", which would happen if the "bar" search match
1492 // outranked all other matches. On the other hand, if the omnibox will
1493 // reorder matches as necessary to put a legal default match at the top,
1494 // all we need to guarantee is that SearchProvider returns a legal
1495 // default match. (The omnibox always needs at least one legal default
1496 // match, and it relies on SearchProvider to always return one.)
1497 ApplyCalculatedRelevance();
1498 ConvertResultsToAutocompleteMatches();
1499 }
1500 DCHECK(!IsTopMatchNavigationInKeywordMode(
1501 omnibox_will_reorder_for_legal_default_match));
1502 DCHECK(HasKeywordDefaultMatchInKeywordMode());
1503 DCHECK(!IsTopMatchScoreTooLow(
1504 omnibox_will_reorder_for_legal_default_match));
1505 DCHECK(!IsTopMatchSearchWithURLInput(
1506 omnibox_will_reorder_for_legal_default_match));
1507 DCHECK(HasValidDefaultMatch(omnibox_will_reorder_for_legal_default_match));
1508 }
1509
1510 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
1511 if ((keyword_url != NULL) && HasKeywordDefaultMatchInKeywordMode()) {
1512 // If there is a keyword match that is allowed to be the default match,
1513 // then prohibit default provider matches from being the default match lest
1514 // such matches cause the user to break out of keyword mode.
1515 for (ACMatches::iterator it = matches_.begin(); it != matches_.end();
1516 ++it) {
1517 if (it->keyword != keyword_url->keyword())
1518 it->allowed_to_be_default_match = false;
1519 }
1520 }
1521
1522 base::TimeTicks update_starred_start_time(base::TimeTicks::Now());
1523 UpdateStarredStateOfMatches();
1524 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateStarredTime",
1525 base::TimeTicks::Now() - update_starred_start_time);
1526 UpdateDone();
1527 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.UpdateMatchesTime",
1528 base::TimeTicks::Now() - update_matches_start_time);
1529 }
1530
AddNavigationResultsToMatches(const NavigationResults & navigation_results,ACMatches * matches)1531 void SearchProvider::AddNavigationResultsToMatches(
1532 const NavigationResults& navigation_results,
1533 ACMatches* matches) {
1534 for (NavigationResults::const_iterator it = navigation_results.begin();
1535 it != navigation_results.end(); ++it) {
1536 matches->push_back(NavigationToMatch(*it));
1537 // In the absence of suggested relevance scores, use only the single
1538 // highest-scoring result. (The results are already sorted by relevance.)
1539 if (!it->relevance_from_server())
1540 return;
1541 }
1542 }
1543
AddHistoryResultsToMap(const HistoryResults & results,bool is_keyword,int did_not_accept_suggestion,MatchMap * map)1544 void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
1545 bool is_keyword,
1546 int did_not_accept_suggestion,
1547 MatchMap* map) {
1548 if (results.empty())
1549 return;
1550
1551 base::TimeTicks start_time(base::TimeTicks::Now());
1552 bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() ||
1553 (input_.type() == AutocompleteInput::URL);
1554 const base::string16& input_text =
1555 is_keyword ? keyword_input_.text() : input_.text();
1556 bool input_multiple_words = HasMultipleWords(input_text);
1557
1558 SuggestResults scored_results;
1559 if (!prevent_inline_autocomplete && input_multiple_words) {
1560 // ScoreHistoryResults() allows autocompletion of multi-word, 1-visit
1561 // queries if the input also has multiple words. But if we were already
1562 // autocompleting a multi-word, multi-visit query, and the current input is
1563 // still a prefix of it, then changing the autocompletion suddenly feels
1564 // wrong. To detect this case, first score as if only one word has been
1565 // typed, then check for a best result that is an autocompleted, multi-word
1566 // query. If we find one, then just keep that score set.
1567 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1568 false, input_text, is_keyword);
1569 if ((scored_results.front().relevance() <
1570 AutocompleteResult::kLowestDefaultScore) ||
1571 !HasMultipleWords(scored_results.front().suggestion()))
1572 scored_results.clear(); // Didn't detect the case above, score normally.
1573 }
1574 if (scored_results.empty())
1575 scored_results = ScoreHistoryResults(results, prevent_inline_autocomplete,
1576 input_multiple_words, input_text,
1577 is_keyword);
1578 for (SuggestResults::const_iterator i(scored_results.begin());
1579 i != scored_results.end(); ++i) {
1580 AddMatchToMap(*i, input_text, std::string(),
1581 did_not_accept_suggestion, map);
1582 }
1583 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime",
1584 base::TimeTicks::Now() - start_time);
1585 }
1586
ScoreHistoryResults(const HistoryResults & results,bool base_prevent_inline_autocomplete,bool input_multiple_words,const base::string16 & input_text,bool is_keyword)1587 SearchProvider::SuggestResults SearchProvider::ScoreHistoryResults(
1588 const HistoryResults& results,
1589 bool base_prevent_inline_autocomplete,
1590 bool input_multiple_words,
1591 const base::string16& input_text,
1592 bool is_keyword) {
1593 AutocompleteClassifier* classifier =
1594 AutocompleteClassifierFactory::GetForProfile(profile_);
1595 SuggestResults scored_results;
1596 const bool prevent_search_history_inlining =
1597 OmniboxFieldTrial::SearchHistoryPreventInlining(
1598 input_.current_page_classification());
1599 for (HistoryResults::const_iterator i(results.begin()); i != results.end();
1600 ++i) {
1601 // Don't autocomplete multi-word queries that have only been seen once
1602 // unless the user has typed more than one word.
1603 bool prevent_inline_autocomplete = base_prevent_inline_autocomplete ||
1604 (!input_multiple_words && (i->visits < 2) && HasMultipleWords(i->term));
1605
1606 // Don't autocomplete search terms that would normally be treated as URLs
1607 // when typed. For example, if the user searched for "google.com" and types
1608 // "goog", don't autocomplete to the search term "google.com". Otherwise,
1609 // the input will look like a URL but act like a search, which is confusing.
1610 // NOTE: We don't check this in the following cases:
1611 // * When inline autocomplete is disabled, we won't be inline
1612 // autocompleting this term, so we don't need to worry about confusion as
1613 // much. This also prevents calling Classify() again from inside the
1614 // classifier (which will corrupt state and likely crash), since the
1615 // classifier always disables inline autocomplete.
1616 // * When the user has typed the whole term, the "what you typed" history
1617 // match will outrank us for URL-like inputs anyway, so we need not do
1618 // anything special.
1619 if (!prevent_inline_autocomplete && classifier && (i->term != input_text)) {
1620 AutocompleteMatch match;
1621 classifier->Classify(i->term, false, false, &match, NULL);
1622 prevent_inline_autocomplete =
1623 !AutocompleteMatch::IsSearchType(match.type);
1624 }
1625
1626 int relevance = CalculateRelevanceForHistory(
1627 i->time, is_keyword, !prevent_inline_autocomplete,
1628 prevent_search_history_inlining);
1629 scored_results.push_back(SuggestResult(
1630 i->term, AutocompleteMatchType::SEARCH_HISTORY, i->term,
1631 base::string16(), std::string(), std::string(), is_keyword, relevance,
1632 false, false));
1633 }
1634
1635 // History returns results sorted for us. However, we may have docked some
1636 // results' scores, so things are no longer in order. Do a stable sort to get
1637 // things back in order without otherwise disturbing results with equal
1638 // scores, then force the scores to be unique, so that the order in which
1639 // they're shown is deterministic.
1640 std::stable_sort(scored_results.begin(), scored_results.end(),
1641 CompareScoredResults());
1642 int last_relevance = 0;
1643 for (SuggestResults::iterator i(scored_results.begin());
1644 i != scored_results.end(); ++i) {
1645 if ((i != scored_results.begin()) && (i->relevance() >= last_relevance))
1646 i->set_relevance(last_relevance - 1);
1647 last_relevance = i->relevance();
1648 }
1649
1650 return scored_results;
1651 }
1652
AddSuggestResultsToMap(const SuggestResults & results,const std::string & metadata,MatchMap * map)1653 void SearchProvider::AddSuggestResultsToMap(const SuggestResults& results,
1654 const std::string& metadata,
1655 MatchMap* map) {
1656 for (size_t i = 0; i < results.size(); ++i) {
1657 const bool is_keyword = results[i].from_keyword_provider();
1658 const base::string16& input = is_keyword ? keyword_input_.text()
1659 : input_.text();
1660 AddMatchToMap(results[i], input, metadata, i, map);
1661 }
1662 }
1663
GetVerbatimRelevance(bool * relevance_from_server) const1664 int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
1665 // Use the suggested verbatim relevance score if it is non-negative (valid),
1666 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1667 // and if it won't suppress verbatim, leaving no default provider matches.
1668 // Otherwise, if the default provider returned no matches and was still able
1669 // to suppress verbatim, the user would have no search/nav matches and may be
1670 // left unable to search using their default provider from the omnibox.
1671 // Check for results on each verbatim calculation, as results from older
1672 // queries (on previous input) may be trimmed for failing to inline new input.
1673 bool use_server_relevance =
1674 (default_results_.verbatim_relevance >= 0) &&
1675 !input_.prevent_inline_autocomplete() &&
1676 ((default_results_.verbatim_relevance > 0) ||
1677 !default_results_.suggest_results.empty() ||
1678 !default_results_.navigation_results.empty());
1679 if (relevance_from_server)
1680 *relevance_from_server = use_server_relevance;
1681 return use_server_relevance ?
1682 default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
1683 }
1684
CalculateRelevanceForVerbatim() const1685 int SearchProvider::CalculateRelevanceForVerbatim() const {
1686 if (!providers_.keyword_provider().empty())
1687 return 250;
1688 return CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1689 }
1690
1691 int SearchProvider::
CalculateRelevanceForVerbatimIgnoringKeywordModeState() const1692 CalculateRelevanceForVerbatimIgnoringKeywordModeState() const {
1693 switch (input_.type()) {
1694 case AutocompleteInput::UNKNOWN:
1695 case AutocompleteInput::QUERY:
1696 case AutocompleteInput::FORCED_QUERY:
1697 return kNonURLVerbatimRelevance;
1698
1699 case AutocompleteInput::URL:
1700 return 850;
1701
1702 default:
1703 NOTREACHED();
1704 return 0;
1705 }
1706 }
1707
GetKeywordVerbatimRelevance(bool * relevance_from_server) const1708 int SearchProvider::GetKeywordVerbatimRelevance(
1709 bool* relevance_from_server) const {
1710 // Use the suggested verbatim relevance score if it is non-negative (valid),
1711 // if inline autocomplete isn't prevented (always show verbatim on backspace),
1712 // and if it won't suppress verbatim, leaving no keyword provider matches.
1713 // Otherwise, if the keyword provider returned no matches and was still able
1714 // to suppress verbatim, the user would have no search/nav matches and may be
1715 // left unable to search using their keyword provider from the omnibox.
1716 // Check for results on each verbatim calculation, as results from older
1717 // queries (on previous input) may be trimmed for failing to inline new input.
1718 bool use_server_relevance =
1719 (keyword_results_.verbatim_relevance >= 0) &&
1720 !input_.prevent_inline_autocomplete() &&
1721 ((keyword_results_.verbatim_relevance > 0) ||
1722 !keyword_results_.suggest_results.empty() ||
1723 !keyword_results_.navigation_results.empty());
1724 if (relevance_from_server)
1725 *relevance_from_server = use_server_relevance;
1726 return use_server_relevance ?
1727 keyword_results_.verbatim_relevance :
1728 CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
1729 keyword_input_.prefer_keyword());
1730 }
1731
CalculateRelevanceForHistory(const base::Time & time,bool is_keyword,bool use_aggressive_method,bool prevent_search_history_inlining) const1732 int SearchProvider::CalculateRelevanceForHistory(
1733 const base::Time& time,
1734 bool is_keyword,
1735 bool use_aggressive_method,
1736 bool prevent_search_history_inlining) const {
1737 // The relevance of past searches falls off over time. There are two distinct
1738 // equations used. If the first equation is used (searches to the primary
1739 // provider that we want to score aggressively), the score is in the range
1740 // 1300-1599 (unless |prevent_search_history_inlining|, in which case
1741 // it's in the range 1200-1299). If the second equation is used the
1742 // relevance of a search 15 minutes ago is discounted 50 points, while the
1743 // relevance of a search two weeks ago is discounted 450 points.
1744 double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0);
1745 bool is_primary_provider = is_keyword || !providers_.has_keyword_provider();
1746 if (is_primary_provider && use_aggressive_method) {
1747 // Searches with the past two days get a different curve.
1748 const double autocomplete_time = 2 * 24 * 60 * 60;
1749 if (elapsed_time < autocomplete_time) {
1750 int max_score = is_keyword ? 1599 : 1399;
1751 if (prevent_search_history_inlining)
1752 max_score = 1299;
1753 return max_score - static_cast<int>(99 *
1754 std::pow(elapsed_time / autocomplete_time, 2.5));
1755 }
1756 elapsed_time -= autocomplete_time;
1757 }
1758
1759 const int score_discount =
1760 static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
1761
1762 // Don't let scores go below 0. Negative relevance scores are meaningful in
1763 // a different way.
1764 int base_score;
1765 if (is_primary_provider)
1766 base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050;
1767 else
1768 base_score = 200;
1769 return std::max(0, base_score - score_discount);
1770 }
1771
AddMatchToMap(const SuggestResult & result,const base::string16 & input_text,const std::string & metadata,int accepted_suggestion,MatchMap * map)1772 void SearchProvider::AddMatchToMap(const SuggestResult& result,
1773 const base::string16& input_text,
1774 const std::string& metadata,
1775 int accepted_suggestion,
1776 MatchMap* map) {
1777 // On non-mobile, ask the instant controller for the appropriate start margin.
1778 // On mobile the start margin is unused, so leave the value as default there.
1779 int omnibox_start_margin = chrome::kDisableStartMargin;
1780 #if !defined(OS_ANDROID) && !defined(IOS)
1781 if (chrome::IsInstantExtendedAPIEnabled()) {
1782 Browser* browser =
1783 chrome::FindBrowserWithProfile(profile_, chrome::GetActiveDesktop());
1784 if (browser && browser->instant_controller() &&
1785 browser->instant_controller()->instant()) {
1786 omnibox_start_margin =
1787 browser->instant_controller()->instant()->omnibox_bounds().x();
1788 }
1789 }
1790 #endif // !defined(OS_ANDROID) && !defined(IOS)
1791
1792 const TemplateURL* template_url = result.from_keyword_provider() ?
1793 providers_.GetKeywordProviderURL() : providers_.GetDefaultProviderURL();
1794 AutocompleteMatch match = CreateSearchSuggestion(
1795 this, input_, input_text, result.relevance(), result.type(),
1796 result.from_keyword_provider(), result.match_contents(),
1797 result.annotation(), template_url, result.suggestion(),
1798 result.suggest_query_params(), accepted_suggestion, omnibox_start_margin,
1799 !result.from_keyword_provider() || providers_.default_provider().empty());
1800 if (!match.destination_url.is_valid())
1801 return;
1802 match.search_terms_args->bookmark_bar_pinned =
1803 profile_->GetPrefs()->GetBoolean(prefs::kShowBookmarkBar);
1804 match.RecordAdditionalInfo(kRelevanceFromServerKey,
1805 result.relevance_from_server() ? kTrue : kFalse);
1806 match.RecordAdditionalInfo(kShouldPrefetchKey,
1807 result.should_prefetch() ? kTrue : kFalse);
1808
1809 if (!result.deletion_url().empty()) {
1810 GURL url(match.destination_url.GetOrigin().Resolve(result.deletion_url()));
1811 if (url.is_valid()) {
1812 match.RecordAdditionalInfo(kDeletionUrlKey, url.spec());
1813 match.deletable = true;
1814 }
1815 }
1816
1817 // Metadata is needed only for prefetching queries.
1818 if (result.should_prefetch())
1819 match.RecordAdditionalInfo(kSuggestMetadataKey, metadata);
1820
1821 // Try to add |match| to |map|. If a match for |query_string| is already in
1822 // |map|, replace it if |match| is more relevant.
1823 // NOTE: Keep this ToLower() call in sync with url_database.cc.
1824 MatchKey match_key(
1825 std::make_pair(base::i18n::ToLower(result.suggestion()),
1826 match.search_terms_args->suggest_query_params));
1827 const std::pair<MatchMap::iterator, bool> i(
1828 map->insert(std::make_pair(match_key, match)));
1829
1830 bool should_prefetch = result.should_prefetch();
1831 if (!i.second) {
1832 // NOTE: We purposefully do a direct relevance comparison here instead of
1833 // using AutocompleteMatch::MoreRelevant(), so that we'll prefer "items
1834 // added first" rather than "items alphabetically first" when the scores are
1835 // equal. The only case this matters is when a user has results with the
1836 // same score that differ only by capitalization; because the history system
1837 // returns results sorted by recency, this means we'll pick the most
1838 // recent such result even if the precision of our relevance score is too
1839 // low to distinguish the two.
1840 if (match.relevance > i.first->second.relevance) {
1841 i.first->second = match;
1842 } else if (match.keyword == i.first->second.keyword) {
1843 // Old and new matches are from the same search provider. It is okay to
1844 // record one match's prefetch data onto a different match (for the same
1845 // query string) for the following reasons:
1846 // 1. Because the suggest server only sends down a query string from which
1847 // we construct a URL, rather than sending a full URL, and because we
1848 // construct URLs from query strings in the same way every time, the URLs
1849 // for the two matches will be the same. Therefore, we won't end up
1850 // prefetching something the server didn't intend.
1851 // 2. Presumably the server sets the prefetch bit on a match it things is
1852 // sufficiently relevant that the user is likely to choose it. Surely
1853 // setting the prefetch bit on a match of even higher relevance won't
1854 // violate this assumption.
1855 should_prefetch |= ShouldPrefetch(i.first->second);
1856 i.first->second.RecordAdditionalInfo(kShouldPrefetchKey,
1857 should_prefetch ? kTrue : kFalse);
1858 if (should_prefetch)
1859 i.first->second.RecordAdditionalInfo(kSuggestMetadataKey, metadata);
1860 }
1861 }
1862 }
1863
NavigationToMatch(const NavigationResult & navigation)1864 AutocompleteMatch SearchProvider::NavigationToMatch(
1865 const NavigationResult& navigation) {
1866 const base::string16& input = navigation.from_keyword_provider() ?
1867 keyword_input_.text() : input_.text();
1868 AutocompleteMatch match(this, navigation.relevance(), false,
1869 AutocompleteMatchType::NAVSUGGEST);
1870 match.destination_url = navigation.url();
1871
1872 // First look for the user's input inside the fill_into_edit as it would be
1873 // without trimming the scheme, so we can find matches at the beginning of the
1874 // scheme.
1875 const base::string16& untrimmed_fill_into_edit = navigation.formatted_url();
1876 const URLPrefix* prefix =
1877 URLPrefix::BestURLPrefix(untrimmed_fill_into_edit, input);
1878 size_t match_start = (prefix == NULL) ?
1879 untrimmed_fill_into_edit.find(input) : prefix->prefix.length();
1880 size_t inline_autocomplete_offset = (prefix == NULL) ?
1881 base::string16::npos : (match_start + input.length());
1882 bool trim_http = !AutocompleteInput::HasHTTPScheme(input) &&
1883 (!prefix || (match_start != 0));
1884
1885 const std::string languages(
1886 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages));
1887 const net::FormatUrlTypes format_types =
1888 net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP);
1889 match.fill_into_edit +=
1890 AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url(),
1891 net::FormatUrl(navigation.url(), languages, format_types,
1892 net::UnescapeRule::SPACES, NULL, NULL,
1893 &inline_autocomplete_offset));
1894 // Preserve the forced query '?' prefix in |match.fill_into_edit|.
1895 // Otherwise, user edits to a suggestion would show non-Search results.
1896 if (input_.type() == AutocompleteInput::FORCED_QUERY) {
1897 match.fill_into_edit.insert(0, ASCIIToUTF16("?"));
1898 if (inline_autocomplete_offset != base::string16::npos)
1899 ++inline_autocomplete_offset;
1900 }
1901 if (inline_autocomplete_offset != base::string16::npos) {
1902 DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1903 match.inline_autocompletion =
1904 match.fill_into_edit.substr(inline_autocomplete_offset);
1905 }
1906 // An inlineable navsuggestion can only be the default match when there
1907 // is no keyword provider active, lest it appear first and break the user
1908 // out of keyword mode. It can also only be default when we're not
1909 // preventing inline autocompletion (unless the inline autocompletion
1910 // would be empty).
1911 match.allowed_to_be_default_match = navigation.IsInlineable(input) &&
1912 (providers_.GetKeywordProviderURL() == NULL) &&
1913 (!input_.prevent_inline_autocomplete() ||
1914 match.inline_autocompletion.empty());
1915
1916 match.contents = net::FormatUrl(navigation.url(), languages,
1917 format_types, net::UnescapeRule::SPACES, NULL, NULL, &match_start);
1918 // If the first match in the untrimmed string was inside a scheme that we
1919 // trimmed, look for a subsequent match.
1920 if (match_start == base::string16::npos)
1921 match_start = match.contents.find(input);
1922 // Safe if |match_start| is npos; also safe if the input is longer than the
1923 // remaining contents after |match_start|.
1924 AutocompleteMatch::ClassifyLocationInString(match_start, input.length(),
1925 match.contents.length(), ACMatchClassification::URL,
1926 &match.contents_class);
1927
1928 match.description = navigation.description();
1929 AutocompleteMatch::ClassifyMatchInString(input, match.description,
1930 ACMatchClassification::NONE, &match.description_class);
1931
1932 match.RecordAdditionalInfo(
1933 kRelevanceFromServerKey,
1934 navigation.relevance_from_server() ? kTrue : kFalse);
1935 match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse);
1936
1937 return match;
1938 }
1939
DemoteKeywordNavigationMatchesPastTopQuery()1940 void SearchProvider::DemoteKeywordNavigationMatchesPastTopQuery() {
1941 // First, determine the maximum score of any keyword query match (verbatim or
1942 // query suggestion).
1943 bool relevance_from_server;
1944 int max_query_relevance = GetKeywordVerbatimRelevance(&relevance_from_server);
1945 if (!keyword_results_.suggest_results.empty()) {
1946 const SuggestResult& top_keyword = keyword_results_.suggest_results.front();
1947 const int suggest_relevance = top_keyword.relevance();
1948 if (suggest_relevance > max_query_relevance) {
1949 max_query_relevance = suggest_relevance;
1950 relevance_from_server = top_keyword.relevance_from_server();
1951 } else if (suggest_relevance == max_query_relevance) {
1952 relevance_from_server |= top_keyword.relevance_from_server();
1953 }
1954 }
1955 // If no query is supposed to appear, then navigational matches cannot
1956 // be demoted past it. Get rid of suggested relevance scores for
1957 // navsuggestions and introduce the verbatim results again. The keyword
1958 // verbatim match will outscore the navsuggest matches.
1959 if (max_query_relevance == 0) {
1960 ApplyCalculatedNavigationRelevance(&keyword_results_.navigation_results);
1961 ApplyCalculatedNavigationRelevance(&default_results_.navigation_results);
1962 keyword_results_.verbatim_relevance = -1;
1963 default_results_.verbatim_relevance = -1;
1964 return;
1965 }
1966 // Now we know we can enforce the minimum score constraint even after
1967 // the navigation matches are demoted. Proceed to demote the navigation
1968 // matches to enforce the query-must-come-first constraint.
1969 // Cap the relevance score of all results.
1970 for (NavigationResults::iterator it =
1971 keyword_results_.navigation_results.begin();
1972 it != keyword_results_.navigation_results.end(); ++it) {
1973 if (it->relevance() < max_query_relevance)
1974 return;
1975 max_query_relevance = std::max(max_query_relevance - 1, 0);
1976 it->set_relevance(max_query_relevance);
1977 it->set_relevance_from_server(relevance_from_server);
1978 }
1979 }
1980
UpdateDone()1981 void SearchProvider::UpdateDone() {
1982 // We're done when the timer isn't running, there are no suggest queries
1983 // pending, and we're not waiting on Instant.
1984 done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0);
1985 }
1986
CanSendURL(const GURL & current_page_url,const GURL & suggest_url,const TemplateURL * template_url,AutocompleteInput::PageClassification page_classification,Profile * profile)1987 bool SearchProvider::CanSendURL(
1988 const GURL& current_page_url,
1989 const GURL& suggest_url,
1990 const TemplateURL* template_url,
1991 AutocompleteInput::PageClassification page_classification,
1992 Profile* profile) {
1993 if (!current_page_url.is_valid())
1994 return false;
1995
1996 // TODO(hfung): Show Most Visited on NTP with appropriate verbatim
1997 // description when the user actively focuses on the omnibox as discussed in
1998 // crbug/305366 if Most Visited (or something similar) will launch.
1999 if ((page_classification ==
2000 AutocompleteInput::INSTANT_NTP_WITH_FAKEBOX_AS_STARTING_FOCUS) ||
2001 (page_classification ==
2002 AutocompleteInput::INSTANT_NTP_WITH_OMNIBOX_AS_STARTING_FOCUS))
2003 return false;
2004
2005 // Only allow HTTP URLs or HTTPS URLs for the same domain as the search
2006 // provider.
2007 if ((current_page_url.scheme() != content::kHttpScheme) &&
2008 ((current_page_url.scheme() != content::kHttpsScheme) ||
2009 !net::registry_controlled_domains::SameDomainOrHost(
2010 current_page_url, suggest_url,
2011 net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES)))
2012 return false;
2013
2014 // Make sure we are sending the suggest request through HTTPS to prevent
2015 // exposing the current page URL to networks before the search provider.
2016 if (!suggest_url.SchemeIs(content::kHttpsScheme))
2017 return false;
2018
2019 // Don't run if there's no profile or in incognito mode.
2020 if (profile == NULL || profile->IsOffTheRecord())
2021 return false;
2022
2023 // Don't run if we can't get preferences or search suggest is not enabled.
2024 PrefService* prefs = profile->GetPrefs();
2025 if (!prefs->GetBoolean(prefs::kSearchSuggestEnabled))
2026 return false;
2027
2028 // Only make the request if we know that the provider supports zero suggest
2029 // (currently only the prepopulated Google provider).
2030 if (template_url == NULL || !template_url->SupportsReplacement() ||
2031 TemplateURLPrepopulateData::GetEngineType(*template_url) !=
2032 SEARCH_ENGINE_GOOGLE)
2033 return false;
2034
2035 // Check field trials and settings allow sending the URL on suggest requests.
2036 ProfileSyncService* service =
2037 ProfileSyncServiceFactory::GetInstance()->GetForProfile(profile);
2038 browser_sync::SyncPrefs sync_prefs(prefs);
2039 if (!OmniboxFieldTrial::InZeroSuggestFieldTrial() ||
2040 service == NULL ||
2041 !service->IsSyncEnabledAndLoggedIn() ||
2042 !sync_prefs.GetPreferredDataTypes(syncer::UserTypes()).Has(
2043 syncer::PROXY_TABS) ||
2044 service->GetEncryptedDataTypes().Has(syncer::SESSIONS))
2045 return false;
2046
2047 return true;
2048 }
2049