• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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