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 "components/omnibox/search_provider.h"
6
7#include <algorithm>
8#include <cmath>
9
10#include "base/base64.h"
11#include "base/callback.h"
12#include "base/i18n/break_iterator.h"
13#include "base/i18n/case_conversion.h"
14#include "base/json/json_string_value_serializer.h"
15#include "base/metrics/histogram.h"
16#include "base/metrics/user_metrics.h"
17#include "base/rand_util.h"
18#include "base/strings/string_util.h"
19#include "base/strings/utf_string_conversions.h"
20#include "components/history/core/browser/in_memory_database.h"
21#include "components/history/core/browser/keyword_search_term.h"
22#include "components/metrics/proto/omnibox_input_type.pb.h"
23#include "components/omnibox/autocomplete_provider_client.h"
24#include "components/omnibox/autocomplete_provider_listener.h"
25#include "components/omnibox/autocomplete_result.h"
26#include "components/omnibox/keyword_provider.h"
27#include "components/omnibox/omnibox_field_trial.h"
28#include "components/omnibox/url_prefix.h"
29#include "components/search/search.h"
30#include "components/search_engines/template_url_prepopulate_data.h"
31#include "components/search_engines/template_url_service.h"
32#include "components/variations/variations_http_header_provider.h"
33#include "grit/components_strings.h"
34#include "net/base/escape.h"
35#include "net/base/load_flags.h"
36#include "net/base/net_util.h"
37#include "net/http/http_request_headers.h"
38#include "net/url_request/url_fetcher.h"
39#include "net/url_request/url_request_status.h"
40#include "ui/base/l10n/l10n_util.h"
41#include "url/url_constants.h"
42#include "url/url_util.h"
43
44// Helpers --------------------------------------------------------------------
45
46namespace {
47
48// We keep track in a histogram how many suggest requests we send, how
49// many suggest requests we invalidate (e.g., due to a user typing
50// another character), and how many replies we receive.
51// *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! ***
52//     (excluding the end-of-list enum value)
53// We do not want values of existing enums to change or else it screws
54// up the statistics.
55enum SuggestRequestsHistogramValue {
56  REQUEST_SENT = 1,
57  REQUEST_INVALIDATED,
58  REPLY_RECEIVED,
59  MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE
60};
61
62// The verbatim score for an input which is not an URL.
63const int kNonURLVerbatimRelevance = 1300;
64
65// Increments the appropriate value in the histogram by one.
66void LogOmniboxSuggestRequest(
67    SuggestRequestsHistogramValue request_value) {
68  UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value,
69                            MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE);
70}
71
72bool HasMultipleWords(const base::string16& text) {
73  base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD);
74  bool found_word = false;
75  if (i.Init()) {
76    while (i.Advance()) {
77      if (i.IsWord()) {
78        if (found_word)
79          return true;
80        found_word = true;
81      }
82    }
83  }
84  return false;
85}
86
87}  // namespace
88
89// SearchProvider::Providers --------------------------------------------------
90
91SearchProvider::Providers::Providers(TemplateURLService* template_url_service)
92    : template_url_service_(template_url_service) {}
93
94const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const {
95  return default_provider_.empty() ? NULL :
96      template_url_service_->GetTemplateURLForKeyword(default_provider_);
97}
98
99const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const {
100  return keyword_provider_.empty() ? NULL :
101      template_url_service_->GetTemplateURLForKeyword(keyword_provider_);
102}
103
104
105// SearchProvider::CompareScoredResults ---------------------------------------
106
107class SearchProvider::CompareScoredResults {
108 public:
109  bool operator()(const SearchSuggestionParser::Result& a,
110                  const SearchSuggestionParser::Result& b) {
111    // Sort in descending relevance order.
112    return a.relevance() > b.relevance();
113  }
114};
115
116
117// SearchProvider -------------------------------------------------------------
118
119// static
120int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100;
121
122SearchProvider::SearchProvider(
123    AutocompleteProviderListener* listener,
124    TemplateURLService* template_url_service,
125    scoped_ptr<AutocompleteProviderClient> client)
126    : BaseSearchProvider(template_url_service, client.Pass(),
127                         AutocompleteProvider::TYPE_SEARCH),
128      listener_(listener),
129      suggest_results_pending_(0),
130      providers_(template_url_service),
131      answers_cache_(10) {
132}
133
134// static
135std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) {
136  return match.GetAdditionalInfo(kSuggestMetadataKey);
137}
138
139void SearchProvider::ResetSession() {
140  field_trial_triggered_in_session_ = false;
141}
142
143SearchProvider::~SearchProvider() {
144}
145
146// static
147int SearchProvider::CalculateRelevanceForKeywordVerbatim(
148    metrics::OmniboxInputType::Type type,
149    bool prefer_keyword) {
150  // This function is responsible for scoring verbatim query matches
151  // for non-extension keywords.  KeywordProvider::CalculateRelevance()
152  // scores verbatim query matches for extension keywords, as well as
153  // for keyword matches (i.e., suggestions of a keyword itself, not a
154  // suggestion of a query on a keyword search engine).  These two
155  // functions are currently in sync, but there's no reason we
156  // couldn't decide in the future to score verbatim matches
157  // differently for extension and non-extension keywords.  If you
158  // make such a change, however, you should update this comment to
159  // describe it, so it's clear why the functions diverge.
160  if (prefer_keyword)
161    return 1500;
162  return (type == metrics::OmniboxInputType::QUERY) ? 1450 : 1100;
163}
164
165// static
166void SearchProvider::UpdateOldResults(
167    bool minimal_changes,
168    SearchSuggestionParser::Results* results) {
169  // When called without |minimal_changes|, it likely means the user has
170  // pressed a key.  Revise the cached results appropriately.
171  if (!minimal_changes) {
172    for (SearchSuggestionParser::SuggestResults::iterator sug_it =
173             results->suggest_results.begin();
174         sug_it != results->suggest_results.end(); ++sug_it) {
175      sug_it->set_received_after_last_keystroke(false);
176    }
177    for (SearchSuggestionParser::NavigationResults::iterator nav_it =
178             results->navigation_results.begin();
179         nav_it != results->navigation_results.end(); ++nav_it) {
180      nav_it->set_received_after_last_keystroke(false);
181    }
182  }
183}
184
185// static
186ACMatches::iterator SearchProvider::FindTopMatch(ACMatches* matches) {
187  ACMatches::iterator it = matches->begin();
188  while ((it != matches->end()) && !it->allowed_to_be_default_match)
189    ++it;
190  return it;
191}
192
193void SearchProvider::Start(const AutocompleteInput& input,
194                           bool minimal_changes) {
195  // Do our best to load the model as early as possible.  This will reduce
196  // odds of having the model not ready when really needed (a non-empty input).
197  TemplateURLService* model = providers_.template_url_service();
198  DCHECK(model);
199  model->Load();
200
201  matches_.clear();
202  field_trial_triggered_ = false;
203
204  // Can't return search/suggest results for bogus input.
205  if (input.type() == metrics::OmniboxInputType::INVALID) {
206    Stop(true);
207    return;
208  }
209
210  keyword_input_ = input;
211  const TemplateURL* keyword_provider =
212      KeywordProvider::GetSubstitutingTemplateURLForInput(model,
213                                                          &keyword_input_);
214  if (keyword_provider == NULL)
215    keyword_input_.Clear();
216  else if (keyword_input_.text().empty())
217    keyword_provider = NULL;
218
219  const TemplateURL* default_provider = model->GetDefaultSearchProvider();
220  if (default_provider &&
221      !default_provider->SupportsReplacement(model->search_terms_data()))
222    default_provider = NULL;
223
224  if (keyword_provider == default_provider)
225    default_provider = NULL;  // No use in querying the same provider twice.
226
227  if (!default_provider && !keyword_provider) {
228    // No valid providers.
229    Stop(true);
230    return;
231  }
232
233  // If we're still running an old query but have since changed the query text
234  // or the providers, abort the query.
235  base::string16 default_provider_keyword(default_provider ?
236      default_provider->keyword() : base::string16());
237  base::string16 keyword_provider_keyword(keyword_provider ?
238      keyword_provider->keyword() : base::string16());
239  if (!minimal_changes ||
240      !providers_.equal(default_provider_keyword, keyword_provider_keyword)) {
241    // Cancel any in-flight suggest requests.
242    if (!done_)
243      Stop(false);
244  }
245
246  providers_.set(default_provider_keyword, keyword_provider_keyword);
247
248  if (input.text().empty()) {
249    // User typed "?" alone.  Give them a placeholder result indicating what
250    // this syntax does.
251    if (default_provider) {
252      AutocompleteMatch match;
253      match.provider = this;
254      match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
255      match.contents_class.push_back(
256          ACMatchClassification(0, ACMatchClassification::NONE));
257      match.keyword = providers_.default_provider();
258      match.allowed_to_be_default_match = true;
259      matches_.push_back(match);
260    }
261    Stop(true);
262    return;
263  }
264
265  input_ = input;
266
267  DoHistoryQuery(minimal_changes);
268  // Answers needs scored history results before any suggest query has been
269  // started, since the query for answer-bearing results needs additional
270  // prefetch information based on the highest-scored local history result.
271  if (OmniboxFieldTrial::EnableAnswersInSuggest()) {
272    ScoreHistoryResults(raw_default_history_results_,
273                        false,
274                        &transformed_default_history_results_);
275    ScoreHistoryResults(raw_keyword_history_results_,
276                        true,
277                        &transformed_keyword_history_results_);
278    prefetch_data_ = FindAnswersPrefetchData();
279
280    // Raw results are not needed any more.
281    raw_default_history_results_.clear();
282    raw_keyword_history_results_.clear();
283  } else {
284    transformed_default_history_results_.clear();
285    transformed_keyword_history_results_.clear();
286  }
287
288  StartOrStopSuggestQuery(minimal_changes);
289  UpdateMatches();
290}
291
292void SearchProvider::Stop(bool clear_cached_results) {
293  StopSuggest();
294  done_ = true;
295
296  if (clear_cached_results)
297    ClearAllResults();
298}
299
300const TemplateURL* SearchProvider::GetTemplateURL(bool is_keyword) const {
301  return is_keyword ? providers_.GetKeywordProviderURL()
302                    : providers_.GetDefaultProviderURL();
303}
304
305const AutocompleteInput SearchProvider::GetInput(bool is_keyword) const {
306  return is_keyword ? keyword_input_ : input_;
307}
308
309bool SearchProvider::ShouldAppendExtraParams(
310    const SearchSuggestionParser::SuggestResult& result) const {
311  return !result.from_keyword_provider() ||
312      providers_.default_provider().empty();
313}
314
315void SearchProvider::RecordDeletionResult(bool success) {
316  if (success) {
317    base::RecordAction(
318        base::UserMetricsAction("Omnibox.ServerSuggestDelete.Success"));
319  } else {
320    base::RecordAction(
321        base::UserMetricsAction("Omnibox.ServerSuggestDelete.Failure"));
322  }
323}
324
325void SearchProvider::OnURLFetchComplete(const net::URLFetcher* source) {
326  DCHECK(!done_);
327  --suggest_results_pending_;
328  DCHECK_GE(suggest_results_pending_, 0);  // Should never go negative.
329
330  const bool is_keyword = source == keyword_fetcher_.get();
331
332  // Ensure the request succeeded and that the provider used is still available.
333  // A verbatim match cannot be generated without this provider, causing errors.
334  const bool request_succeeded =
335      source->GetStatus().is_success() && (source->GetResponseCode() == 200) &&
336      GetTemplateURL(is_keyword);
337
338  LogFetchComplete(request_succeeded, is_keyword);
339
340  bool results_updated = false;
341  if (request_succeeded) {
342    scoped_ptr<base::Value> data(SearchSuggestionParser::DeserializeJsonData(
343        SearchSuggestionParser::ExtractJsonData(source)));
344    if (data) {
345      SearchSuggestionParser::Results* results =
346          is_keyword ? &keyword_results_ : &default_results_;
347      results_updated = ParseSuggestResults(*data, -1, is_keyword, results);
348      if (results_updated)
349        SortResults(is_keyword, results);
350    }
351  }
352  UpdateMatches();
353  if (done_ || results_updated)
354    listener_->OnProviderUpdate(results_updated);
355}
356
357void SearchProvider::StopSuggest() {
358  // Increment the appropriate field in the histogram by the number of
359  // pending requests that were invalidated.
360  for (int i = 0; i < suggest_results_pending_; ++i)
361    LogOmniboxSuggestRequest(REQUEST_INVALIDATED);
362  suggest_results_pending_ = 0;
363  timer_.Stop();
364  // Stop any in-progress URL fetches.
365  keyword_fetcher_.reset();
366  default_fetcher_.reset();
367}
368
369void SearchProvider::ClearAllResults() {
370  keyword_results_.Clear();
371  default_results_.Clear();
372}
373
374void SearchProvider::UpdateMatchContentsClass(
375    const base::string16& input_text,
376    SearchSuggestionParser::Results* results) {
377  for (SearchSuggestionParser::SuggestResults::iterator sug_it =
378           results->suggest_results.begin();
379       sug_it != results->suggest_results.end(); ++sug_it) {
380    sug_it->ClassifyMatchContents(false, input_text);
381  }
382  const std::string languages(client_->AcceptLanguages());
383  for (SearchSuggestionParser::NavigationResults::iterator nav_it =
384           results->navigation_results.begin();
385       nav_it != results->navigation_results.end(); ++nav_it) {
386    nav_it->CalculateAndClassifyMatchContents(false, input_text, languages);
387  }
388}
389
390void SearchProvider::SortResults(bool is_keyword,
391                                 SearchSuggestionParser::Results* results) {
392  // Ignore suggested scores for non-keyword matches in keyword mode; if the
393  // server is allowed to score these, it could interfere with the user's
394  // ability to get good keyword results.
395  const bool abandon_suggested_scores =
396      !is_keyword && !providers_.keyword_provider().empty();
397  // Apply calculated relevance scores to suggestions if valid relevances were
398  // not provided or we're abandoning suggested scores entirely.
399  if (!results->relevances_from_server || abandon_suggested_scores) {
400    ApplyCalculatedSuggestRelevance(&results->suggest_results);
401    ApplyCalculatedNavigationRelevance(&results->navigation_results);
402    // If abandoning scores entirely, also abandon the verbatim score.
403    if (abandon_suggested_scores)
404      results->verbatim_relevance = -1;
405  }
406
407  // Keep the result lists sorted.
408  const CompareScoredResults comparator = CompareScoredResults();
409  std::stable_sort(results->suggest_results.begin(),
410                   results->suggest_results.end(),
411                   comparator);
412  std::stable_sort(results->navigation_results.begin(),
413                   results->navigation_results.end(),
414                   comparator);
415}
416
417void SearchProvider::LogFetchComplete(bool success, bool is_keyword) {
418  LogOmniboxSuggestRequest(REPLY_RECEIVED);
419  // Record response time for suggest requests sent to Google.  We care
420  // only about the common case: the Google default provider used in
421  // non-keyword mode.
422  const TemplateURL* default_url = providers_.GetDefaultProviderURL();
423  if (!is_keyword && default_url &&
424      (TemplateURLPrepopulateData::GetEngineType(
425          *default_url,
426          providers_.template_url_service()->search_terms_data()) ==
427       SEARCH_ENGINE_GOOGLE)) {
428    const base::TimeDelta elapsed_time =
429        base::TimeTicks::Now() - time_suggest_request_sent_;
430    if (success) {
431      UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime",
432                          elapsed_time);
433    } else {
434      UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime",
435                          elapsed_time);
436    }
437  }
438}
439
440void SearchProvider::UpdateMatches() {
441  PersistTopSuggestions(&default_results_);
442  PersistTopSuggestions(&keyword_results_);
443  ConvertResultsToAutocompleteMatches();
444
445  // Check constraints that may be violated by suggested relevances.
446  if (!matches_.empty() &&
447      (default_results_.HasServerProvidedScores() ||
448       keyword_results_.HasServerProvidedScores())) {
449    // These blocks attempt to repair undesirable behavior by suggested
450    // relevances with minimal impact, preserving other suggested relevances.
451
452    const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
453    const bool is_extension_keyword = (keyword_url != NULL) &&
454        (keyword_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION);
455    if ((keyword_url != NULL) && !is_extension_keyword &&
456        (FindTopMatch() == matches_.end())) {
457      // In non-extension keyword mode, disregard the keyword verbatim suggested
458      // relevance if necessary, so at least one match is allowed to be default.
459      // (In extension keyword mode this is not necessary because the extension
460      // will return a default match.)  Give keyword verbatim the lowest
461      // non-zero score to best reflect what the server desired.
462      DCHECK_EQ(0, keyword_results_.verbatim_relevance);
463      keyword_results_.verbatim_relevance = 1;
464      ConvertResultsToAutocompleteMatches();
465    }
466    if (IsTopMatchSearchWithURLInput()) {
467      // Disregard the suggested search and verbatim relevances if the input
468      // type is URL and the top match is a highly-ranked search suggestion.
469      // For example, prevent a search for "foo.com" from outranking another
470      // provider's navigation for "foo.com" or "foo.com/url_from_history".
471      ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results);
472      ApplyCalculatedSuggestRelevance(&default_results_.suggest_results);
473      default_results_.verbatim_relevance = -1;
474      keyword_results_.verbatim_relevance = -1;
475      ConvertResultsToAutocompleteMatches();
476    }
477    if (!is_extension_keyword && (FindTopMatch() == matches_.end())) {
478      // Guarantee that SearchProvider returns a legal default match (except
479      // when in extension-based keyword mode).  The omnibox always needs at
480      // least one legal default match, and it relies on SearchProvider in
481      // combination with KeywordProvider (for extension-based keywords) to
482      // always return one.  Give the verbatim suggestion the lowest non-zero
483      // scores to best reflect what the server desired.
484      DCHECK_EQ(0, default_results_.verbatim_relevance);
485      default_results_.verbatim_relevance = 1;
486      // We do not have to alter keyword_results_.verbatim_relevance here.
487      // If the user is in keyword mode, we already reverted (earlier in this
488      // function) the instructions to suppress keyword verbatim.
489      ConvertResultsToAutocompleteMatches();
490    }
491    DCHECK(!IsTopMatchSearchWithURLInput());
492    DCHECK(is_extension_keyword || (FindTopMatch() != matches_.end()));
493  }
494  UMA_HISTOGRAM_CUSTOM_COUNTS(
495      "Omnibox.SearchProviderMatches", matches_.size(), 1, 6, 7);
496
497  // Record the top suggestion (if any) for future use.
498  top_query_suggestion_match_contents_ = base::string16();
499  top_navigation_suggestion_ = GURL();
500  ACMatches::const_iterator first_match = FindTopMatch();
501  if ((first_match != matches_.end()) &&
502      !first_match->inline_autocompletion.empty()) {
503    // Identify if this match came from a query suggestion or a navsuggestion.
504    // In either case, extracts the identifying feature of the suggestion
505    // (query string or navigation url).
506    if (AutocompleteMatch::IsSearchType(first_match->type))
507      top_query_suggestion_match_contents_ = first_match->contents;
508    else
509      top_navigation_suggestion_ = first_match->destination_url;
510  }
511
512  UpdateDone();
513}
514
515void SearchProvider::Run() {
516  // Start a new request with the current input.
517  suggest_results_pending_ = 0;
518  time_suggest_request_sent_ = base::TimeTicks::Now();
519
520  default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID,
521      providers_.GetDefaultProviderURL(), input_));
522  keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID,
523      providers_.GetKeywordProviderURL(), keyword_input_));
524
525  // Both the above can fail if the providers have been modified or deleted
526  // since the query began.
527  if (suggest_results_pending_ == 0) {
528    UpdateDone();
529    // We only need to update the listener if we're actually done.
530    if (done_)
531      listener_->OnProviderUpdate(false);
532  }
533}
534
535void SearchProvider::DoHistoryQuery(bool minimal_changes) {
536  // The history query results are synchronous, so if minimal_changes is true,
537  // we still have the last results and don't need to do anything.
538  if (minimal_changes)
539    return;
540
541  raw_keyword_history_results_.clear();
542  raw_default_history_results_.clear();
543
544  if (OmniboxFieldTrial::SearchHistoryDisable(
545      input_.current_page_classification()))
546    return;
547
548  history::URLDatabase* url_db = client_->InMemoryDatabase();
549  if (!url_db)
550    return;
551
552  // Request history for both the keyword and default provider.  We grab many
553  // more matches than we'll ultimately clamp to so that if there are several
554  // recent multi-word matches who scores are lowered (see
555  // ScoreHistoryResults()), they won't crowd out older, higher-scoring
556  // matches.  Note that this doesn't fix the problem entirely, but merely
557  // limits it to cases with a very large number of such multi-word matches; for
558  // now, this seems OK compared with the complexity of a real fix, which would
559  // require multiple searches and tracking of "single- vs. multi-word" in the
560  // database.
561  int num_matches = kMaxMatches * 5;
562  const TemplateURL* default_url = providers_.GetDefaultProviderURL();
563  if (default_url) {
564    const base::TimeTicks start_time = base::TimeTicks::Now();
565    url_db->GetMostRecentKeywordSearchTerms(default_url->id(),
566                                            input_.text(),
567                                            num_matches,
568                                            &raw_default_history_results_);
569    UMA_HISTOGRAM_TIMES(
570        "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime",
571        base::TimeTicks::Now() - start_time);
572  }
573  const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
574  if (keyword_url) {
575    url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(),
576                                            keyword_input_.text(),
577                                            num_matches,
578                                            &raw_keyword_history_results_);
579  }
580}
581
582void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
583  if (!IsQuerySuitableForSuggest()) {
584    StopSuggest();
585    ClearAllResults();
586    return;
587  }
588
589  // For the minimal_changes case, if we finished the previous query and still
590  // have its results, or are allowed to keep running it, just do that, rather
591  // than starting a new query.
592  if (minimal_changes &&
593      (!default_results_.suggest_results.empty() ||
594       !default_results_.navigation_results.empty() ||
595       !keyword_results_.suggest_results.empty() ||
596       !keyword_results_.navigation_results.empty() ||
597       (!done_ && input_.want_asynchronous_matches())))
598    return;
599
600  // We can't keep running any previous query, so halt it.
601  StopSuggest();
602
603  UpdateAllOldResults(minimal_changes);
604
605  // Update the content classifications of remaining results so they look good
606  // against the current input.
607  UpdateMatchContentsClass(input_.text(), &default_results_);
608  if (!keyword_input_.text().empty())
609    UpdateMatchContentsClass(keyword_input_.text(), &keyword_results_);
610
611  // We can't start a new query if we're only allowed synchronous results.
612  if (!input_.want_asynchronous_matches())
613    return;
614
615  // To avoid flooding the suggest server, don't send a query until at
616  // least 100 ms since the last query.
617  base::TimeTicks next_suggest_time(time_suggest_request_sent_ +
618      base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs));
619  base::TimeTicks now(base::TimeTicks::Now());
620  if (now >= next_suggest_time) {
621    Run();
622    return;
623  }
624  timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run);
625}
626
627bool SearchProvider::IsQuerySuitableForSuggest() const {
628  // Don't run Suggest in incognito mode, if the engine doesn't support it, or
629  // if the user has disabled it.
630  const TemplateURL* default_url = providers_.GetDefaultProviderURL();
631  const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
632  if (client_->IsOffTheRecord() ||
633      ((!default_url || default_url->suggestions_url().empty()) &&
634       (!keyword_url || keyword_url->suggestions_url().empty())) ||
635      !client_->SearchSuggestEnabled())
636    return false;
637
638  // If the input type might be a URL, we take extra care so that private data
639  // isn't sent to the server.
640
641  // FORCED_QUERY means the user is explicitly asking us to search for this, so
642  // we assume it isn't a URL and/or there isn't private data.
643  if (input_.type() == metrics::OmniboxInputType::FORCED_QUERY)
644    return true;
645
646  // Next we check the scheme.  If this is UNKNOWN/URL with a scheme that isn't
647  // http/https/ftp, we shouldn't send it.  Sending things like file: and data:
648  // is both a waste of time and a disclosure of potentially private, local
649  // data.  Other "schemes" may actually be usernames, and we don't want to send
650  // passwords.  If the scheme is OK, we still need to check other cases below.
651  // If this is QUERY, then the presence of these schemes means the user
652  // explicitly typed one, and thus this is probably a URL that's being entered
653  // and happens to currently be invalid -- in which case we again want to run
654  // our checks below.  Other QUERY cases are less likely to be URLs and thus we
655  // assume we're OK.
656  if (!LowerCaseEqualsASCII(input_.scheme(), url::kHttpScheme) &&
657      !LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) &&
658      !LowerCaseEqualsASCII(input_.scheme(), url::kFtpScheme))
659    return (input_.type() == metrics::OmniboxInputType::QUERY);
660
661  // Don't send URLs with usernames, queries or refs.  Some of these are
662  // private, and the Suggest server is unlikely to have any useful results
663  // for any of them.  Also don't send URLs with ports, as we may initially
664  // think that a username + password is a host + port (and we don't want to
665  // send usernames/passwords), and even if the port really is a port, the
666  // server is once again unlikely to have and useful results.
667  // Note that we only block based on refs if the input is URL-typed, as search
668  // queries can legitimately have #s in them which the URL parser
669  // overaggressively categorizes as a url with a ref.
670  const url::Parsed& parts = input_.parts();
671  if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
672      parts.query.is_nonempty() ||
673      (parts.ref.is_nonempty() &&
674       (input_.type() == metrics::OmniboxInputType::URL)))
675    return false;
676
677  // Don't send anything for https except the hostname.  Hostnames are OK
678  // because they are visible when the TCP connection is established, but the
679  // specific path may reveal private information.
680  if (LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) &&
681      parts.path.is_nonempty())
682    return false;
683
684  return true;
685}
686
687void SearchProvider::UpdateAllOldResults(bool minimal_changes) {
688  if (keyword_input_.text().empty()) {
689    // User is either in keyword mode with a blank input or out of
690    // keyword mode entirely.
691    keyword_results_.Clear();
692  }
693  UpdateOldResults(minimal_changes, &default_results_);
694  UpdateOldResults(minimal_changes, &keyword_results_);
695}
696
697void SearchProvider::PersistTopSuggestions(
698    SearchSuggestionParser::Results* results) {
699  // Mark any results matching the current top results as having been received
700  // prior to the last keystroke.  That prevents asynchronous updates from
701  // clobbering top results, which may be used for inline autocompletion.
702  // Other results don't need similar changes, because they shouldn't be
703  // displayed asynchronously anyway.
704  if (!top_query_suggestion_match_contents_.empty()) {
705    for (SearchSuggestionParser::SuggestResults::iterator sug_it =
706             results->suggest_results.begin();
707         sug_it != results->suggest_results.end(); ++sug_it) {
708      if (sug_it->match_contents() == top_query_suggestion_match_contents_)
709        sug_it->set_received_after_last_keystroke(false);
710    }
711  }
712  if (top_navigation_suggestion_.is_valid()) {
713    for (SearchSuggestionParser::NavigationResults::iterator nav_it =
714             results->navigation_results.begin();
715         nav_it != results->navigation_results.end(); ++nav_it) {
716      if (nav_it->url() == top_navigation_suggestion_)
717        nav_it->set_received_after_last_keystroke(false);
718    }
719  }
720}
721
722void SearchProvider::ApplyCalculatedSuggestRelevance(
723    SearchSuggestionParser::SuggestResults* list) {
724  for (size_t i = 0; i < list->size(); ++i) {
725    SearchSuggestionParser::SuggestResult& result = (*list)[i];
726    result.set_relevance(
727        result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
728        (list->size() - i - 1));
729    result.set_relevance_from_server(false);
730  }
731}
732
733void SearchProvider::ApplyCalculatedNavigationRelevance(
734    SearchSuggestionParser::NavigationResults* list) {
735  for (size_t i = 0; i < list->size(); ++i) {
736    SearchSuggestionParser::NavigationResult& result = (*list)[i];
737    result.set_relevance(
738        result.CalculateRelevance(input_, providers_.has_keyword_provider()) +
739        (list->size() - i - 1));
740    result.set_relevance_from_server(false);
741  }
742}
743
744net::URLFetcher* SearchProvider::CreateSuggestFetcher(
745    int id,
746    const TemplateURL* template_url,
747    const AutocompleteInput& input) {
748  if (!template_url || template_url->suggestions_url().empty())
749    return NULL;
750
751  // Bail if the suggestion URL is invalid with the given replacements.
752  TemplateURLRef::SearchTermsArgs search_term_args(input.text());
753  search_term_args.input_type = input.type();
754  search_term_args.cursor_position = input.cursor_position();
755  search_term_args.page_classification = input.current_page_classification();
756  if (OmniboxFieldTrial::EnableAnswersInSuggest()) {
757    search_term_args.session_token = GetSessionToken();
758    if (!prefetch_data_.full_query_text.empty()) {
759      search_term_args.prefetch_query =
760          base::UTF16ToUTF8(prefetch_data_.full_query_text);
761      search_term_args.prefetch_query_type =
762          base::UTF16ToUTF8(prefetch_data_.query_type);
763    }
764  }
765  GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
766      search_term_args,
767      providers_.template_url_service()->search_terms_data()));
768  if (!suggest_url.is_valid())
769    return NULL;
770  // Send the current page URL if user setting and URL requirements are met and
771  // the user is in the field trial.
772  if (CanSendURL(current_page_url_, suggest_url, template_url,
773                 input.current_page_classification(),
774                 template_url_service_->search_terms_data(), client_.get()) &&
775      OmniboxFieldTrial::InZeroSuggestAfterTypingFieldTrial()) {
776    search_term_args.current_page_url = current_page_url_.spec();
777    // Create the suggest URL again with the current page URL.
778    suggest_url = GURL(template_url->suggestions_url_ref().ReplaceSearchTerms(
779        search_term_args,
780        providers_.template_url_service()->search_terms_data()));
781  }
782
783  suggest_results_pending_++;
784  LogOmniboxSuggestRequest(REQUEST_SENT);
785
786  net::URLFetcher* fetcher =
787      net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this);
788  fetcher->SetRequestContext(client_->RequestContext());
789  fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES);
790  // Add Chrome experiment state to the request headers.
791  net::HttpRequestHeaders headers;
792  variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders(
793      fetcher->GetOriginalURL(), client_->IsOffTheRecord(), false, &headers);
794  fetcher->SetExtraRequestHeaders(headers.ToString());
795  fetcher->Start();
796  return fetcher;
797}
798
799void SearchProvider::ConvertResultsToAutocompleteMatches() {
800  // Convert all the results to matches and add them to a map, so we can keep
801  // the most relevant match for each result.
802  base::TimeTicks start_time(base::TimeTicks::Now());
803  MatchMap map;
804  const base::Time no_time;
805  int did_not_accept_keyword_suggestion =
806      keyword_results_.suggest_results.empty() ?
807      TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
808      TemplateURLRef::NO_SUGGESTION_CHOSEN;
809
810  bool relevance_from_server;
811  int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server);
812  int did_not_accept_default_suggestion =
813      default_results_.suggest_results.empty() ?
814      TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
815      TemplateURLRef::NO_SUGGESTION_CHOSEN;
816  const TemplateURL* keyword_url = providers_.GetKeywordProviderURL();
817  if (verbatim_relevance > 0) {
818    const base::string16& trimmed_verbatim =
819        base::CollapseWhitespace(input_.text(), false);
820
821    // Verbatim results don't get suggestions and hence, answers.
822    // Scan previous matches if the last answer-bearing suggestion matches
823    // verbatim, and if so, copy over answer contents.
824    base::string16 answer_contents;
825    base::string16 answer_type;
826    for (ACMatches::iterator it = matches_.begin(); it != matches_.end();
827         ++it) {
828      if (!it->answer_contents.empty() &&
829          it->fill_into_edit == trimmed_verbatim) {
830        answer_contents = it->answer_contents;
831        answer_type = it->answer_type;
832        break;
833      }
834    }
835
836    SearchSuggestionParser::SuggestResult verbatim(
837        trimmed_verbatim, AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED,
838        trimmed_verbatim, base::string16(), base::string16(), answer_contents,
839        answer_type, std::string(), std::string(), false, verbatim_relevance,
840        relevance_from_server, false, trimmed_verbatim);
841    AddMatchToMap(verbatim, std::string(), did_not_accept_default_suggestion,
842                  false, keyword_url != NULL, &map);
843  }
844  if (!keyword_input_.text().empty()) {
845    // We only create the verbatim search query match for a keyword
846    // if it's not an extension keyword.  Extension keywords are handled
847    // in KeywordProvider::Start().  (Extensions are complicated...)
848    // Note: in this provider, SEARCH_OTHER_ENGINE must correspond
849    // to the keyword verbatim search query.  Do not create other matches
850    // of type SEARCH_OTHER_ENGINE.
851    if (keyword_url &&
852        (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
853      bool keyword_relevance_from_server;
854      const int keyword_verbatim_relevance =
855          GetKeywordVerbatimRelevance(&keyword_relevance_from_server);
856      if (keyword_verbatim_relevance > 0) {
857        const base::string16& trimmed_verbatim =
858            base::CollapseWhitespace(keyword_input_.text(), false);
859        SearchSuggestionParser::SuggestResult verbatim(
860            trimmed_verbatim, AutocompleteMatchType::SEARCH_OTHER_ENGINE,
861            trimmed_verbatim, base::string16(), base::string16(),
862            base::string16(), base::string16(), std::string(), std::string(),
863            true, keyword_verbatim_relevance, keyword_relevance_from_server,
864            false, trimmed_verbatim);
865        AddMatchToMap(verbatim, std::string(),
866                      did_not_accept_keyword_suggestion, false, true, &map);
867      }
868    }
869  }
870  AddRawHistoryResultsToMap(true, did_not_accept_keyword_suggestion, &map);
871  AddRawHistoryResultsToMap(false, did_not_accept_default_suggestion, &map);
872
873  AddSuggestResultsToMap(keyword_results_.suggest_results,
874                         keyword_results_.metadata, &map);
875  AddSuggestResultsToMap(default_results_.suggest_results,
876                         default_results_.metadata, &map);
877
878  ACMatches matches;
879  for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
880    matches.push_back(i->second);
881
882  AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches);
883  AddNavigationResultsToMatches(default_results_.navigation_results, &matches);
884
885  // Now add the most relevant matches to |matches_|.  We take up to kMaxMatches
886  // suggest/navsuggest matches, regardless of origin.  We always include in
887  // that set a legal default match if possible.  If Instant Extended is enabled
888  // and we have server-provided (and thus hopefully more accurate) scores for
889  // some suggestions, we allow more of those, until we reach
890  // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the
891  // whole popup).
892  //
893  // We will always return any verbatim matches, no matter how we obtained their
894  // scores, unless we have already accepted AutocompleteResult::kMaxMatches
895  // higher-scoring matches under the conditions above.
896  std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
897
898  // Guarantee that if there's a legal default match anywhere in the result
899  // set that it'll get returned.  The rotate() call does this by moving the
900  // default match to the front of the list.
901  ACMatches::iterator default_match = FindTopMatch(&matches);
902  if (default_match != matches.end())
903    std::rotate(matches.begin(), default_match, default_match + 1);
904
905  // It's possible to get a copy of an answer from previous matches and get the
906  // same or a different answer to another server-provided suggestion.  In the
907  // future we may decide that we want to have answers attached to multiple
908  // suggestions, but the current assumption is that there should only ever be
909  // one suggestion with an answer.  To maintain this assumption, remove any
910  // answers after the first.
911  RemoveExtraAnswers(&matches);
912
913  matches_.clear();
914  size_t num_suggestions = 0;
915  for (ACMatches::const_iterator i(matches.begin());
916       (i != matches.end()) &&
917           (matches_.size() < AutocompleteResult::kMaxMatches);
918       ++i) {
919    // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword
920    // verbatim result, so this condition basically means "if this match is a
921    // suggestion of some sort".
922    if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) &&
923        (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) {
924      // If we've already hit the limit on non-server-scored suggestions, and
925      // this isn't a server-scored suggestion we can add, skip it.
926      if ((num_suggestions >= kMaxMatches) &&
927          (!chrome::IsInstantExtendedAPIEnabled() ||
928           (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) {
929        continue;
930      }
931
932      ++num_suggestions;
933    }
934
935    matches_.push_back(*i);
936  }
937  UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime",
938                      base::TimeTicks::Now() - start_time);
939}
940
941void SearchProvider::RemoveExtraAnswers(ACMatches* matches) {
942  bool answer_seen = false;
943  for (ACMatches::iterator it = matches->begin(); it != matches->end(); ++it) {
944    if (!it->answer_contents.empty()) {
945      if (!answer_seen) {
946        answer_seen = true;
947      } else {
948        it->answer_contents.clear();
949        it->answer_type.clear();
950      }
951    }
952  }
953}
954
955ACMatches::const_iterator SearchProvider::FindTopMatch() const {
956  ACMatches::const_iterator it = matches_.begin();
957  while ((it != matches_.end()) && !it->allowed_to_be_default_match)
958    ++it;
959  return it;
960}
961
962bool SearchProvider::IsTopMatchSearchWithURLInput() const {
963  ACMatches::const_iterator first_match = FindTopMatch();
964  return (input_.type() == metrics::OmniboxInputType::URL) &&
965      (first_match != matches_.end()) &&
966      (first_match->relevance > CalculateRelevanceForVerbatim()) &&
967      (first_match->type != AutocompleteMatchType::NAVSUGGEST) &&
968      (first_match->type != AutocompleteMatchType::NAVSUGGEST_PERSONALIZED);
969}
970
971void SearchProvider::AddNavigationResultsToMatches(
972    const SearchSuggestionParser::NavigationResults& navigation_results,
973    ACMatches* matches) {
974  for (SearchSuggestionParser::NavigationResults::const_iterator it =
975           navigation_results.begin(); it != navigation_results.end(); ++it) {
976    matches->push_back(NavigationToMatch(*it));
977    // In the absence of suggested relevance scores, use only the single
978    // highest-scoring result.  (The results are already sorted by relevance.)
979    if (!it->relevance_from_server())
980      return;
981  }
982}
983
984void SearchProvider::AddRawHistoryResultsToMap(bool is_keyword,
985                                               int did_not_accept_suggestion,
986                                               MatchMap* map) {
987  const HistoryResults& raw_results =
988      is_keyword ? raw_keyword_history_results_ : raw_default_history_results_;
989  if (!OmniboxFieldTrial::EnableAnswersInSuggest() && raw_results.empty())
990    return;
991
992  base::TimeTicks start_time(base::TimeTicks::Now());
993
994  // Until Answers becomes default, scoring of history results will still happen
995  // here for non-Answers Chrome, to prevent scoring performance regressions
996  // resulting from moving the scoring code before the suggest request is sent.
997  // For users with Answers enabled, the history results have already been
998  // scored earlier, right after calling DoHistoryQuery().
999  SearchSuggestionParser::SuggestResults local_transformed_results;
1000  const SearchSuggestionParser::SuggestResults* transformed_results = NULL;
1001  if (!OmniboxFieldTrial::EnableAnswersInSuggest()) {
1002    ScoreHistoryResults(raw_results, is_keyword, &local_transformed_results);
1003    transformed_results = &local_transformed_results;
1004  } else {
1005    transformed_results = is_keyword ? &transformed_keyword_history_results_
1006                                     : &transformed_default_history_results_;
1007  }
1008  DCHECK(transformed_results);
1009  AddTransformedHistoryResultsToMap(
1010      *transformed_results, did_not_accept_suggestion, map);
1011  UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime",
1012                      base::TimeTicks::Now() - start_time);
1013}
1014
1015void SearchProvider::AddTransformedHistoryResultsToMap(
1016    const SearchSuggestionParser::SuggestResults& transformed_results,
1017    int did_not_accept_suggestion,
1018    MatchMap* map) {
1019  for (SearchSuggestionParser::SuggestResults::const_iterator i(
1020           transformed_results.begin());
1021       i != transformed_results.end();
1022       ++i) {
1023    AddMatchToMap(*i, std::string(), did_not_accept_suggestion, true,
1024                  providers_.GetKeywordProviderURL() != NULL, map);
1025  }
1026}
1027
1028SearchSuggestionParser::SuggestResults
1029SearchProvider::ScoreHistoryResultsHelper(const HistoryResults& results,
1030                                          bool base_prevent_inline_autocomplete,
1031                                          bool input_multiple_words,
1032                                          const base::string16& input_text,
1033                                          bool is_keyword) {
1034  SearchSuggestionParser::SuggestResults scored_results;
1035  // True if the user has asked this exact query previously.
1036  bool found_what_you_typed_match = false;
1037  const bool prevent_search_history_inlining =
1038      OmniboxFieldTrial::SearchHistoryPreventInlining(
1039          input_.current_page_classification());
1040  const base::string16& trimmed_input =
1041      base::CollapseWhitespace(input_text, false);
1042  for (HistoryResults::const_iterator i(results.begin()); i != results.end();
1043       ++i) {
1044    const base::string16& trimmed_suggestion =
1045        base::CollapseWhitespace(i->term, false);
1046
1047    // Don't autocomplete multi-word queries that have only been seen once
1048    // unless the user has typed more than one word.
1049    bool prevent_inline_autocomplete = base_prevent_inline_autocomplete ||
1050        (!input_multiple_words && (i->visits < 2) &&
1051         HasMultipleWords(trimmed_suggestion));
1052
1053    int relevance = CalculateRelevanceForHistory(
1054        i->time, is_keyword, !prevent_inline_autocomplete,
1055        prevent_search_history_inlining);
1056    // Add the match to |scored_results| by putting the what-you-typed match
1057    // on the front and appending all other matches.  We want the what-you-
1058    // typed match to always be first.
1059    SearchSuggestionParser::SuggestResults::iterator insertion_position =
1060        scored_results.end();
1061    if (trimmed_suggestion == trimmed_input) {
1062      found_what_you_typed_match = true;
1063      insertion_position = scored_results.begin();
1064    }
1065    SearchSuggestionParser::SuggestResult history_suggestion(
1066        trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY,
1067        trimmed_suggestion, base::string16(), base::string16(),
1068        base::string16(), base::string16(), std::string(), std::string(),
1069        is_keyword, relevance, false, false, trimmed_input);
1070    // History results are synchronous; they are received on the last keystroke.
1071    history_suggestion.set_received_after_last_keystroke(false);
1072    scored_results.insert(insertion_position, history_suggestion);
1073  }
1074
1075  // History returns results sorted for us.  However, we may have docked some
1076  // results' scores, so things are no longer in order.  While keeping the
1077  // what-you-typed match at the front (if it exists), do a stable sort to get
1078  // things back in order without otherwise disturbing results with equal
1079  // scores, then force the scores to be unique, so that the order in which
1080  // they're shown is deterministic.
1081  std::stable_sort(scored_results.begin() +
1082                       (found_what_you_typed_match ? 1 : 0),
1083                   scored_results.end(),
1084                   CompareScoredResults());
1085
1086  // Don't autocomplete to search terms that would normally be treated as URLs
1087  // when typed. For example, if the user searched for "google.com" and types
1088  // "goog", don't autocomplete to the search term "google.com". Otherwise,
1089  // the input will look like a URL but act like a search, which is confusing.
1090  // The 1200 relevance score threshold in the test below is the lowest
1091  // possible score in CalculateRelevanceForHistory()'s aggressive-scoring
1092  // curve.  This is an appropriate threshold to use to decide if we're overly
1093  // aggressively inlining because, if we decide the answer is yes, the
1094  // way we resolve it it to not use the aggressive-scoring curve.
1095  // NOTE: We don't check for autocompleting to URLs in the following cases:
1096  //  * When inline autocomplete is disabled, we won't be inline autocompleting
1097  //    this term, so we don't need to worry about confusion as much.  This
1098  //    also prevents calling Classify() again from inside the classifier
1099  //    (which will corrupt state and likely crash), since the classifier
1100  //    always disables inline autocomplete.
1101  //  * When the user has typed the whole string before as a query, then it's
1102  //    likely the user has no expectation that term should be interpreted as
1103  //    as a URL, so we need not do anything special to preserve user
1104  //    expectation.
1105  int last_relevance = 0;
1106  if (!base_prevent_inline_autocomplete && !found_what_you_typed_match &&
1107      scored_results.front().relevance() >= 1200) {
1108    AutocompleteMatch match;
1109    client_->Classify(scored_results.front().suggestion(), false, false,
1110                      input_.current_page_classification(), &match, NULL);
1111    // Demote this match that would normally be interpreted as a URL to have
1112    // the highest score a previously-issued search query could have when
1113    // scoring with the non-aggressive method.  A consequence of demoting
1114    // by revising |last_relevance| is that this match and all following
1115    // matches get demoted; the relative order of matches is preserved.
1116    // One could imagine demoting only those matches that might cause
1117    // confusion (which, by the way, might change the relative order of
1118    // matches.  We have decided to go with the simple demote-all approach
1119    // because selective demotion requires multiple Classify() calls and
1120    // such calls can be expensive (as expensive as running the whole
1121    // autocomplete system).
1122    if (!AutocompleteMatch::IsSearchType(match.type)) {
1123      last_relevance = CalculateRelevanceForHistory(
1124          base::Time::Now(), is_keyword, false,
1125          prevent_search_history_inlining);
1126    }
1127  }
1128
1129  for (SearchSuggestionParser::SuggestResults::iterator i(
1130           scored_results.begin()); i != scored_results.end(); ++i) {
1131    if ((last_relevance != 0) && (i->relevance() >= last_relevance))
1132      i->set_relevance(last_relevance - 1);
1133    last_relevance = i->relevance();
1134  }
1135
1136  return scored_results;
1137}
1138
1139void SearchProvider::ScoreHistoryResults(
1140    const HistoryResults& results,
1141    bool is_keyword,
1142    SearchSuggestionParser::SuggestResults* scored_results) {
1143  DCHECK(scored_results);
1144  if (results.empty()) {
1145    scored_results->clear();
1146    return;
1147  }
1148
1149  bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() ||
1150      (input_.type() == metrics::OmniboxInputType::URL);
1151  const base::string16 input_text = GetInput(is_keyword).text();
1152  bool input_multiple_words = HasMultipleWords(input_text);
1153
1154  if (!prevent_inline_autocomplete && input_multiple_words) {
1155    // ScoreHistoryResultsHelper() allows autocompletion of multi-word, 1-visit
1156    // queries if the input also has multiple words.  But if we were already
1157    // scoring a multi-word, multi-visit query aggressively, and the current
1158    // input is still a prefix of it, then changing the suggestion suddenly
1159    // feels wrong.  To detect this case, first score as if only one word has
1160    // been typed, then check if the best result came from aggressive search
1161    // history scoring.  If it did, then just keep that score set.  This
1162    // 1200 the lowest possible score in CalculateRelevanceForHistory()'s
1163    // aggressive-scoring curve.
1164    *scored_results = ScoreHistoryResultsHelper(
1165        results, prevent_inline_autocomplete, false, input_text, is_keyword);
1166    if ((scored_results->front().relevance() < 1200) ||
1167        !HasMultipleWords(scored_results->front().suggestion()))
1168      scored_results->clear();  // Didn't detect the case above, score normally.
1169  }
1170  if (scored_results->empty()) {
1171    *scored_results = ScoreHistoryResultsHelper(results,
1172                                                prevent_inline_autocomplete,
1173                                                input_multiple_words,
1174                                                input_text,
1175                                                is_keyword);
1176  }
1177}
1178
1179void SearchProvider::AddSuggestResultsToMap(
1180    const SearchSuggestionParser::SuggestResults& results,
1181    const std::string& metadata,
1182    MatchMap* map) {
1183  for (size_t i = 0; i < results.size(); ++i) {
1184    AddMatchToMap(results[i], metadata, i, false,
1185                  providers_.GetKeywordProviderURL() != NULL, map);
1186  }
1187}
1188
1189int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const {
1190  // Use the suggested verbatim relevance score if it is non-negative (valid),
1191  // if inline autocomplete isn't prevented (always show verbatim on backspace),
1192  // and if it won't suppress verbatim, leaving no default provider matches.
1193  // Otherwise, if the default provider returned no matches and was still able
1194  // to suppress verbatim, the user would have no search/nav matches and may be
1195  // left unable to search using their default provider from the omnibox.
1196  // Check for results on each verbatim calculation, as results from older
1197  // queries (on previous input) may be trimmed for failing to inline new input.
1198  bool use_server_relevance =
1199      (default_results_.verbatim_relevance >= 0) &&
1200      !input_.prevent_inline_autocomplete() &&
1201      ((default_results_.verbatim_relevance > 0) ||
1202       !default_results_.suggest_results.empty() ||
1203       !default_results_.navigation_results.empty());
1204  if (relevance_from_server)
1205    *relevance_from_server = use_server_relevance;
1206  return use_server_relevance ?
1207      default_results_.verbatim_relevance : CalculateRelevanceForVerbatim();
1208}
1209
1210int SearchProvider::CalculateRelevanceForVerbatim() const {
1211  if (!providers_.keyword_provider().empty())
1212    return 250;
1213  return CalculateRelevanceForVerbatimIgnoringKeywordModeState();
1214}
1215
1216int SearchProvider::
1217    CalculateRelevanceForVerbatimIgnoringKeywordModeState() const {
1218  switch (input_.type()) {
1219    case metrics::OmniboxInputType::UNKNOWN:
1220    case metrics::OmniboxInputType::QUERY:
1221    case metrics::OmniboxInputType::FORCED_QUERY:
1222      return kNonURLVerbatimRelevance;
1223
1224    case metrics::OmniboxInputType::URL:
1225      return 850;
1226
1227    default:
1228      NOTREACHED();
1229      return 0;
1230  }
1231}
1232
1233int SearchProvider::GetKeywordVerbatimRelevance(
1234    bool* relevance_from_server) const {
1235  // Use the suggested verbatim relevance score if it is non-negative (valid),
1236  // if inline autocomplete isn't prevented (always show verbatim on backspace),
1237  // and if it won't suppress verbatim, leaving no keyword provider matches.
1238  // Otherwise, if the keyword provider returned no matches and was still able
1239  // to suppress verbatim, the user would have no search/nav matches and may be
1240  // left unable to search using their keyword provider from the omnibox.
1241  // Check for results on each verbatim calculation, as results from older
1242  // queries (on previous input) may be trimmed for failing to inline new input.
1243  bool use_server_relevance =
1244      (keyword_results_.verbatim_relevance >= 0) &&
1245      !input_.prevent_inline_autocomplete() &&
1246      ((keyword_results_.verbatim_relevance > 0) ||
1247       !keyword_results_.suggest_results.empty() ||
1248       !keyword_results_.navigation_results.empty());
1249  if (relevance_from_server)
1250    *relevance_from_server = use_server_relevance;
1251  return use_server_relevance ?
1252      keyword_results_.verbatim_relevance :
1253      CalculateRelevanceForKeywordVerbatim(keyword_input_.type(),
1254                                           keyword_input_.prefer_keyword());
1255}
1256
1257int SearchProvider::CalculateRelevanceForHistory(
1258    const base::Time& time,
1259    bool is_keyword,
1260    bool use_aggressive_method,
1261    bool prevent_search_history_inlining) const {
1262  // The relevance of past searches falls off over time. There are two distinct
1263  // equations used. If the first equation is used (searches to the primary
1264  // provider that we want to score aggressively), the score is in the range
1265  // 1300-1599 (unless |prevent_search_history_inlining|, in which case
1266  // it's in the range 1200-1299). If the second equation is used the
1267  // relevance of a search 15 minutes ago is discounted 50 points, while the
1268  // relevance of a search two weeks ago is discounted 450 points.
1269  double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0);
1270  bool is_primary_provider = is_keyword || !providers_.has_keyword_provider();
1271  if (is_primary_provider && use_aggressive_method) {
1272    // Searches with the past two days get a different curve.
1273    const double autocomplete_time = 2 * 24 * 60 * 60;
1274    if (elapsed_time < autocomplete_time) {
1275      int max_score = is_keyword ? 1599 : 1399;
1276      if (prevent_search_history_inlining)
1277        max_score = 1299;
1278      return max_score - static_cast<int>(99 *
1279          std::pow(elapsed_time / autocomplete_time, 2.5));
1280    }
1281    elapsed_time -= autocomplete_time;
1282  }
1283
1284  const int score_discount =
1285      static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
1286
1287  // Don't let scores go below 0.  Negative relevance scores are meaningful in
1288  // a different way.
1289  int base_score;
1290  if (is_primary_provider)
1291    base_score = (input_.type() == metrics::OmniboxInputType::URL) ? 750 : 1050;
1292  else
1293    base_score = 200;
1294  return std::max(0, base_score - score_discount);
1295}
1296
1297AutocompleteMatch SearchProvider::NavigationToMatch(
1298    const SearchSuggestionParser::NavigationResult& navigation) {
1299  base::string16 input;
1300  const bool trimmed_whitespace = base::TrimWhitespace(
1301      navigation.from_keyword_provider() ?
1302          keyword_input_.text() : input_.text(),
1303      base::TRIM_TRAILING, &input) != base::TRIM_NONE;
1304  AutocompleteMatch match(this, navigation.relevance(), false,
1305                          navigation.type());
1306  match.destination_url = navigation.url();
1307  BaseSearchProvider::SetDeletionURL(navigation.deletion_url(), &match);
1308  // First look for the user's input inside the formatted url as it would be
1309  // without trimming the scheme, so we can find matches at the beginning of the
1310  // scheme.
1311  const URLPrefix* prefix =
1312      URLPrefix::BestURLPrefix(navigation.formatted_url(), input);
1313  size_t match_start = (prefix == NULL) ?
1314      navigation.formatted_url().find(input) : prefix->prefix.length();
1315  bool trim_http = !AutocompleteInput::HasHTTPScheme(input) &&
1316      (!prefix || (match_start != 0));
1317  const net::FormatUrlTypes format_types =
1318      net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP);
1319
1320  const std::string languages(client_->AcceptLanguages());
1321  size_t inline_autocomplete_offset = (prefix == NULL) ?
1322      base::string16::npos : (match_start + input.length());
1323  match.fill_into_edit +=
1324      AutocompleteInput::FormattedStringWithEquivalentMeaning(
1325          navigation.url(),
1326          net::FormatUrl(navigation.url(), languages, format_types,
1327                         net::UnescapeRule::SPACES, NULL, NULL,
1328                         &inline_autocomplete_offset),
1329          client_->SchemeClassifier());
1330  // Preserve the forced query '?' prefix in |match.fill_into_edit|.
1331  // Otherwise, user edits to a suggestion would show non-Search results.
1332  if (input_.type() == metrics::OmniboxInputType::FORCED_QUERY) {
1333    match.fill_into_edit.insert(0, base::ASCIIToUTF16("?"));
1334    if (inline_autocomplete_offset != base::string16::npos)
1335      ++inline_autocomplete_offset;
1336  }
1337  if (inline_autocomplete_offset != base::string16::npos) {
1338    DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1339    match.inline_autocompletion =
1340        match.fill_into_edit.substr(inline_autocomplete_offset);
1341  }
1342  // An inlineable navsuggestion can only be the default match when there
1343  // is no keyword provider active, lest it appear first and break the user
1344  // out of keyword mode.  We also must have received the navsuggestion before
1345  // the last keystroke, to prevent asynchronous inline autocompletions changes.
1346  // The navsuggestion can also only be default if either the inline
1347  // autocompletion is empty or we're not preventing inline autocompletion.
1348  // Finally, if we have an inlineable navsuggestion with an inline completion
1349  // that we're not preventing, make sure we didn't trim any whitespace.
1350  // We don't want to claim http://foo.com/bar is inlineable against the
1351  // input "foo.com/b ".
1352  match.allowed_to_be_default_match =
1353      (prefix != NULL) &&
1354      (providers_.GetKeywordProviderURL() == NULL) &&
1355      !navigation.received_after_last_keystroke() &&
1356      (match.inline_autocompletion.empty() ||
1357      (!input_.prevent_inline_autocomplete() && !trimmed_whitespace));
1358  match.EnsureUWYTIsAllowedToBeDefault(
1359      input_.canonicalized_url(), providers_.template_url_service());
1360
1361  match.contents = navigation.match_contents();
1362  match.contents_class = navigation.match_contents_class();
1363  match.description = navigation.description();
1364  AutocompleteMatch::ClassifyMatchInString(input, match.description,
1365      ACMatchClassification::NONE, &match.description_class);
1366
1367  match.RecordAdditionalInfo(
1368      kRelevanceFromServerKey,
1369      navigation.relevance_from_server() ? kTrue : kFalse);
1370  match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse);
1371
1372  return match;
1373}
1374
1375void SearchProvider::UpdateDone() {
1376  // We're done when the timer isn't running, there are no suggest queries
1377  // pending, and we're not waiting on Instant.
1378  done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0);
1379}
1380
1381std::string SearchProvider::GetSessionToken() {
1382  base::TimeTicks current_time(base::TimeTicks::Now());
1383  // Renew token if it expired.
1384  if (current_time > token_expiration_time_) {
1385    const size_t kTokenBytes = 12;
1386    std::string raw_data;
1387    base::RandBytes(WriteInto(&raw_data, kTokenBytes + 1), kTokenBytes);
1388    base::Base64Encode(raw_data, &current_token_);
1389
1390    // Make the base64 encoded value URL and filename safe(see RFC 3548).
1391    std::replace(current_token_.begin(), current_token_.end(), '+', '-');
1392    std::replace(current_token_.begin(), current_token_.end(), '/', '_');
1393  }
1394
1395  // Extend expiration time another 60 seconds.
1396  token_expiration_time_ = current_time + base::TimeDelta::FromSeconds(60);
1397
1398  return current_token_;
1399}
1400
1401void SearchProvider::RegisterDisplayedAnswers(
1402    const AutocompleteResult& result) {
1403  if (result.empty())
1404    return;
1405
1406  // The answer must be in the first or second slot to be considered. It should
1407  // only be in the second slot if AutocompleteController ranked a local search
1408  // history or a verbatim item higher than the answer.
1409  AutocompleteResult::const_iterator match = result.begin();
1410  if (match->answer_contents.empty() && result.size() > 1)
1411    ++match;
1412  if (match->answer_contents.empty() || match->answer_type.empty() ||
1413      match->fill_into_edit.empty())
1414    return;
1415
1416  // Valid answer encountered, cache it for further queries.
1417  answers_cache_.UpdateRecentAnswers(match->fill_into_edit, match->answer_type);
1418}
1419
1420AnswersQueryData SearchProvider::FindAnswersPrefetchData() {
1421  // Retrieve the top entry from scored history results.
1422  MatchMap map;
1423  AddTransformedHistoryResultsToMap(transformed_keyword_history_results_,
1424                                    TemplateURLRef::NO_SUGGESTIONS_AVAILABLE,
1425                                    &map);
1426  AddTransformedHistoryResultsToMap(transformed_default_history_results_,
1427                                    TemplateURLRef::NO_SUGGESTIONS_AVAILABLE,
1428                                    &map);
1429
1430  ACMatches matches;
1431  for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
1432    matches.push_back(i->second);
1433  std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant);
1434
1435  // If there is a top scoring entry, find the corresponding answer.
1436  if (!matches.empty())
1437    return answers_cache_.GetTopAnswerEntry(matches[0].contents);
1438
1439  return AnswersQueryData();
1440}
1441