1// Copyright (c) 2011 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/icu_string_conversions.h"
12#include "base/message_loop.h"
13#include "base/string16.h"
14#include "base/utf_string_conversions.h"
15#include "chrome/browser/autocomplete/autocomplete_classifier.h"
16#include "chrome/browser/autocomplete/keyword_provider.h"
17#include "chrome/browser/autocomplete/autocomplete_match.h"
18#include "chrome/browser/google/google_util.h"
19#include "chrome/browser/history/history.h"
20#include "chrome/browser/instant/instant_controller.h"
21#include "chrome/browser/net/url_fixer_upper.h"
22#include "chrome/browser/prefs/pref_service.h"
23#include "chrome/browser/profiles/profile.h"
24#include "chrome/browser/history/in_memory_database.h"
25#include "chrome/browser/search_engines/template_url_model.h"
26#include "chrome/common/pref_names.h"
27#include "chrome/common/url_constants.h"
28#include "content/common/json_value_serializer.h"
29#include "googleurl/src/url_util.h"
30#include "grit/generated_resources.h"
31#include "net/base/escape.h"
32#include "net/http/http_response_headers.h"
33#include "net/url_request/url_request_status.h"
34#include "ui/base/l10n/l10n_util.h"
35
36using base::Time;
37using base::TimeDelta;
38
39// static
40const int SearchProvider::kDefaultProviderURLFetcherID = 1;
41// static
42const int SearchProvider::kKeywordProviderURLFetcherID = 2;
43
44// static
45bool SearchProvider::query_suggest_immediately_ = false;
46
47void SearchProvider::Providers::Set(const TemplateURL* default_provider,
48                                    const TemplateURL* keyword_provider) {
49  // TODO(pkasting): http://b/1162970  We shouldn't need to structure-copy
50  // this. Nor should we need |default_provider_| and |keyword_provider_|
51  // just to know whether the provider changed.
52  default_provider_ = default_provider;
53  if (default_provider)
54    cached_default_provider_ = *default_provider;
55  keyword_provider_ = keyword_provider;
56  if (keyword_provider)
57    cached_keyword_provider_ = *keyword_provider;
58}
59
60SearchProvider::SearchProvider(ACProviderListener* listener, Profile* profile)
61    : AutocompleteProvider(listener, profile, "Search"),
62      suggest_results_pending_(0),
63      have_suggest_results_(false),
64      instant_finalized_(false) {
65}
66
67void SearchProvider::FinalizeInstantQuery(const string16& input_text,
68                                          const string16& suggest_text) {
69  if (done_ || instant_finalized_)
70    return;
71
72  instant_finalized_ = true;
73  UpdateDone();
74
75  if (input_text.empty()) {
76    // We only need to update the listener if we're actually done.
77    if (done_)
78      listener_->OnProviderUpdate(false);
79    return;
80  }
81
82  default_provider_suggest_text_ = suggest_text;
83
84  string16 adjusted_input_text(input_text);
85  AutocompleteInput::RemoveForcedQueryStringIfNecessary(input_.type(),
86                                                        &adjusted_input_text);
87
88  const string16 text = adjusted_input_text + suggest_text;
89  // Remove any matches that are identical to |text|. We don't use the
90  // destination_url for comparison as it varies depending upon the index passed
91  // to TemplateURL::ReplaceSearchTerms.
92  for (ACMatches::iterator i = matches_.begin(); i != matches_.end();) {
93    // Reset the description/description_class of all searches. We'll set the
94    // description of the new first match in the call to
95    // UpdateFirstSearchMatchDescription() below.
96    if ((i->type == AutocompleteMatch::SEARCH_HISTORY) ||
97        (i->type == AutocompleteMatch::SEARCH_SUGGEST) ||
98        (i->type == AutocompleteMatch::SEARCH_WHAT_YOU_TYPED)) {
99      i->description.clear();
100      i->description_class.clear();
101    }
102
103    if (((i->type == AutocompleteMatch::SEARCH_HISTORY) ||
104         (i->type == AutocompleteMatch::SEARCH_SUGGEST)) &&
105        (i->fill_into_edit == text)) {
106      i = matches_.erase(i);
107    } else {
108      ++i;
109    }
110  }
111
112  // Add the new suggest result. We give it a rank higher than
113  // SEARCH_WHAT_YOU_TYPED so that it gets autocompleted.
114  int did_not_accept_default_suggestion = default_suggest_results_.empty() ?
115        TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
116        TemplateURLRef::NO_SUGGESTION_CHOSEN;
117  MatchMap match_map;
118  AddMatchToMap(text, adjusted_input_text,
119                CalculateRelevanceForWhatYouTyped() + 1,
120                AutocompleteMatch::SEARCH_SUGGEST,
121                did_not_accept_default_suggestion, false,
122                input_.initial_prevent_inline_autocomplete(), &match_map);
123  DCHECK_EQ(1u, match_map.size());
124  matches_.push_back(match_map.begin()->second);
125  // Sort the results so that UpdateFirstSearchDescription does the right thing.
126  std::sort(matches_.begin(), matches_.end(), &AutocompleteMatch::MoreRelevant);
127
128  UpdateFirstSearchMatchDescription();
129
130  listener_->OnProviderUpdate(true);
131}
132
133void SearchProvider::Start(const AutocompleteInput& input,
134                           bool minimal_changes) {
135  matches_.clear();
136
137  instant_finalized_ =
138      (input.matches_requested() != AutocompleteInput::ALL_MATCHES);
139
140  // Can't return search/suggest results for bogus input or without a profile.
141  if (!profile_ || (input.type() == AutocompleteInput::INVALID)) {
142    Stop();
143    return;
144  }
145
146  keyword_input_text_.clear();
147  const TemplateURL* keyword_provider =
148      KeywordProvider::GetSubstitutingTemplateURLForInput(profile_, input,
149                                                          &keyword_input_text_);
150  if (keyword_input_text_.empty())
151    keyword_provider = NULL;
152
153  const TemplateURL* default_provider =
154      profile_->GetTemplateURLModel()->GetDefaultSearchProvider();
155  if (!TemplateURL::SupportsReplacement(default_provider))
156    default_provider = NULL;
157
158  if (keyword_provider == default_provider)
159    keyword_provider = NULL;  // No use in querying the same provider twice.
160
161  if (!default_provider && !keyword_provider) {
162    // No valid providers.
163    Stop();
164    return;
165  }
166
167  // If we're still running an old query but have since changed the query text
168  // or the providers, abort the query.
169  if (!minimal_changes ||
170      !providers_.equals(default_provider, keyword_provider)) {
171    if (done_)
172      default_provider_suggest_text_.clear();
173    else
174      Stop();
175  } else if (minimal_changes &&
176             (input_.original_text() != input.original_text())) {
177    default_provider_suggest_text_.clear();
178  }
179
180  providers_.Set(default_provider, keyword_provider);
181
182  if (input.text().empty()) {
183    // User typed "?" alone.  Give them a placeholder result indicating what
184    // this syntax does.
185    if (default_provider) {
186      AutocompleteMatch match;
187      match.provider = this;
188      match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE));
189      match.contents_class.push_back(
190          ACMatchClassification(0, ACMatchClassification::NONE));
191      matches_.push_back(match);
192      UpdateFirstSearchMatchDescription();
193    }
194    Stop();
195    return;
196  }
197
198  input_ = input;
199
200  DoHistoryQuery(minimal_changes);
201  StartOrStopSuggestQuery(minimal_changes);
202  ConvertResultsToAutocompleteMatches();
203}
204
205void SearchProvider::Run() {
206  // Start a new request with the current input.
207  DCHECK(!done_);
208  suggest_results_pending_ = 0;
209  if (providers_.valid_suggest_for_keyword_provider()) {
210    suggest_results_pending_++;
211    keyword_fetcher_.reset(
212        CreateSuggestFetcher(kKeywordProviderURLFetcherID,
213                             providers_.keyword_provider(),
214                             keyword_input_text_));
215  }
216  if (providers_.valid_suggest_for_default_provider()) {
217    suggest_results_pending_++;
218    default_fetcher_.reset(
219        CreateSuggestFetcher(kDefaultProviderURLFetcherID,
220                             providers_.default_provider(), input_.text()));
221  }
222  // We should only get here if we have a suggest url for the keyword or default
223  // providers.
224  DCHECK_GT(suggest_results_pending_, 0);
225}
226
227void SearchProvider::Stop() {
228  StopSuggest();
229  done_ = true;
230  default_provider_suggest_text_.clear();
231}
232
233void SearchProvider::OnURLFetchComplete(const URLFetcher* source,
234                                        const GURL& url,
235                                        const net::URLRequestStatus& status,
236                                        int response_code,
237                                        const ResponseCookies& cookie,
238                                        const std::string& data) {
239  DCHECK(!done_);
240  suggest_results_pending_--;
241  DCHECK_GE(suggest_results_pending_, 0);  // Should never go negative.
242  const net::HttpResponseHeaders* const response_headers =
243      source->response_headers();
244  std::string json_data(data);
245  // JSON is supposed to be UTF-8, but some suggest service providers send JSON
246  // files in non-UTF-8 encodings.  The actual encoding is usually specified in
247  // the Content-Type header field.
248  if (response_headers) {
249    std::string charset;
250    if (response_headers->GetCharset(&charset)) {
251      string16 data_16;
252      // TODO(jungshik): Switch to CodePageToUTF8 after it's added.
253      if (base::CodepageToUTF16(data, charset.c_str(),
254                                base::OnStringConversionError::FAIL,
255                                &data_16))
256        json_data = UTF16ToUTF8(data_16);
257    }
258  }
259
260  bool is_keyword_results = (source == keyword_fetcher_.get());
261  SuggestResults* suggest_results = is_keyword_results ?
262      &keyword_suggest_results_ : &default_suggest_results_;
263
264  if (status.is_success() && response_code == 200) {
265    JSONStringValueSerializer deserializer(json_data);
266    deserializer.set_allow_trailing_comma(true);
267    scoped_ptr<Value> root_val(deserializer.Deserialize(NULL, NULL));
268    const string16& input_text =
269        is_keyword_results ? keyword_input_text_ : input_.text();
270    have_suggest_results_ =
271        root_val.get() &&
272        ParseSuggestResults(root_val.get(), is_keyword_results, input_text,
273                            suggest_results);
274  }
275
276  ConvertResultsToAutocompleteMatches();
277  listener_->OnProviderUpdate(!suggest_results->empty());
278}
279
280SearchProvider::~SearchProvider() {
281}
282
283void SearchProvider::DoHistoryQuery(bool minimal_changes) {
284  // The history query results are synchronous, so if minimal_changes is true,
285  // we still have the last results and don't need to do anything.
286  if (minimal_changes)
287    return;
288
289  keyword_history_results_.clear();
290  default_history_results_.clear();
291
292  HistoryService* const history_service =
293      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
294  history::URLDatabase* url_db = history_service ?
295      history_service->InMemoryDatabase() : NULL;
296  if (!url_db)
297    return;
298
299  // Request history for both the keyword and default provider.
300  if (providers_.valid_keyword_provider()) {
301    url_db->GetMostRecentKeywordSearchTerms(
302        providers_.keyword_provider().id(),
303        keyword_input_text_,
304        static_cast<int>(kMaxMatches),
305        &keyword_history_results_);
306  }
307  if (providers_.valid_default_provider()) {
308    url_db->GetMostRecentKeywordSearchTerms(
309        providers_.default_provider().id(),
310        input_.text(),
311        static_cast<int>(kMaxMatches),
312        &default_history_results_);
313  }
314}
315
316void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) {
317  // Don't send any queries to the server until some time has elapsed after
318  // the last keypress, to avoid flooding the server with requests we are
319  // likely to end up throwing away anyway.
320  static const int kQueryDelayMs = 200;
321
322  if (!IsQuerySuitableForSuggest()) {
323    StopSuggest();
324    return;
325  }
326
327  // For the minimal_changes case, if we finished the previous query and still
328  // have its results, or are allowed to keep running it, just do that, rather
329  // than starting a new query.
330  if (minimal_changes &&
331      (have_suggest_results_ ||
332       (!done_ &&
333        input_.matches_requested() == AutocompleteInput::ALL_MATCHES)))
334    return;
335
336  // We can't keep running any previous query, so halt it.
337  StopSuggest();
338
339  // We can't start a new query if we're only allowed synchronous results.
340  if (input_.matches_requested() != AutocompleteInput::ALL_MATCHES)
341    return;
342
343  // We'll have at least one pending fetch. Set it to 1 now, but the value is
344  // correctly set in Run. As Run isn't invoked immediately we need to set this
345  // now, else we won't think we're waiting on results from the server when we
346  // really are.
347  suggest_results_pending_ = 1;
348
349  // Kick off a timer that will start the URL fetch if it completes before
350  // the user types another character.
351  int delay = query_suggest_immediately_ ? 0 : kQueryDelayMs;
352  timer_.Start(TimeDelta::FromMilliseconds(delay), this, &SearchProvider::Run);
353}
354
355bool SearchProvider::IsQuerySuitableForSuggest() const {
356  // Don't run Suggest in incognito mode, the engine doesn't support it, or
357  // the user has disabled it.
358  if (profile_->IsOffTheRecord() ||
359      (!providers_.valid_suggest_for_keyword_provider() &&
360       !providers_.valid_suggest_for_default_provider()) ||
361      !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled))
362    return false;
363
364  // If the input type might be a URL, we take extra care so that private data
365  // isn't sent to the server.
366
367  // FORCED_QUERY means the user is explicitly asking us to search for this, so
368  // we assume it isn't a URL and/or there isn't private data.
369  if (input_.type() == AutocompleteInput::FORCED_QUERY)
370    return true;
371
372  // Next we check the scheme.  If this is UNKNOWN/REQUESTED_URL/URL with a
373  // scheme that isn't http/https/ftp, we shouldn't send it.  Sending things
374  // like file: and data: is both a waste of time and a disclosure of
375  // potentially private, local data.  Other "schemes" may actually be
376  // usernames, and we don't want to send passwords.  If the scheme is OK, we
377  // still need to check other cases below.  If this is QUERY, then the presence
378  // of these schemes means the user explicitly typed one, and thus this is
379  // probably a URL that's being entered and happens to currently be invalid --
380  // in which case we again want to run our checks below.  Other QUERY cases are
381  // less likely to be URLs and thus we assume we're OK.
382  if (!LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpScheme) &&
383      !LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpsScheme) &&
384      !LowerCaseEqualsASCII(input_.scheme(), chrome::kFtpScheme))
385    return (input_.type() == AutocompleteInput::QUERY);
386
387  // Don't send URLs with usernames, queries or refs.  Some of these are
388  // private, and the Suggest server is unlikely to have any useful results
389  // for any of them.  Also don't send URLs with ports, as we may initially
390  // think that a username + password is a host + port (and we don't want to
391  // send usernames/passwords), and even if the port really is a port, the
392  // server is once again unlikely to have and useful results.
393  const url_parse::Parsed& parts = input_.parts();
394  if (parts.username.is_nonempty() || parts.port.is_nonempty() ||
395      parts.query.is_nonempty() || parts.ref.is_nonempty())
396    return false;
397
398  // Don't send anything for https except the hostname.  Hostnames are OK
399  // because they are visible when the TCP connection is established, but the
400  // specific path may reveal private information.
401  if (LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpsScheme) &&
402      parts.path.is_nonempty())
403    return false;
404
405  return true;
406}
407
408void SearchProvider::StopSuggest() {
409  suggest_results_pending_ = 0;
410  timer_.Stop();
411  // Stop any in-progress URL fetches.
412  keyword_fetcher_.reset();
413  default_fetcher_.reset();
414  keyword_suggest_results_.clear();
415  default_suggest_results_.clear();
416  keyword_navigation_results_.clear();
417  default_navigation_results_.clear();
418  have_suggest_results_ = false;
419}
420
421URLFetcher* SearchProvider::CreateSuggestFetcher(int id,
422                                                 const TemplateURL& provider,
423                                                 const string16& text) {
424  const TemplateURLRef* const suggestions_url = provider.suggestions_url();
425  DCHECK(suggestions_url->SupportsReplacement());
426  URLFetcher* fetcher = URLFetcher::Create(id,
427      GURL(suggestions_url->ReplaceSearchTerms(
428           provider, text,
429           TemplateURLRef::NO_SUGGESTIONS_AVAILABLE, string16())),
430      URLFetcher::GET, this);
431  fetcher->set_request_context(profile_->GetRequestContext());
432  fetcher->Start();
433  return fetcher;
434}
435
436bool SearchProvider::ParseSuggestResults(Value* root_val,
437                                         bool is_keyword,
438                                         const string16& input_text,
439                                         SuggestResults* suggest_results) {
440  if (!root_val->IsType(Value::TYPE_LIST))
441    return false;
442  ListValue* root_list = static_cast<ListValue*>(root_val);
443
444  Value* query_val;
445  string16 query_str;
446  Value* result_val;
447  if ((root_list->GetSize() < 2) || !root_list->Get(0, &query_val) ||
448      !query_val->GetAsString(&query_str) ||
449      (query_str != input_text) ||
450      !root_list->Get(1, &result_val) || !result_val->IsType(Value::TYPE_LIST))
451    return false;
452
453  ListValue* description_list = NULL;
454  if (root_list->GetSize() > 2) {
455    // 3rd element: Description list.
456    Value* description_val;
457    if (root_list->Get(2, &description_val) &&
458        description_val->IsType(Value::TYPE_LIST))
459      description_list = static_cast<ListValue*>(description_val);
460  }
461
462  // We don't care about the query URL list (the fourth element in the
463  // response) for now.
464
465  // Parse optional data in the results from the Suggest server if any.
466  ListValue* type_list = NULL;
467  // 5th argument: Optional key-value pairs.
468  // TODO: We may iterate the 5th+ arguments of the root_list if any other
469  // optional data are defined.
470  if (root_list->GetSize() > 4) {
471    Value* optional_val;
472    if (root_list->Get(4, &optional_val) &&
473        optional_val->IsType(Value::TYPE_DICTIONARY)) {
474      DictionaryValue* dict_val = static_cast<DictionaryValue*>(optional_val);
475
476      // Parse Google Suggest specific type extension.
477      static const std::string kGoogleSuggestType("google:suggesttype");
478      if (dict_val->HasKey(kGoogleSuggestType))
479        dict_val->GetList(kGoogleSuggestType, &type_list);
480    }
481  }
482
483  ListValue* result_list = static_cast<ListValue*>(result_val);
484  for (size_t i = 0; i < result_list->GetSize(); ++i) {
485    Value* suggestion_val;
486    string16 suggestion_str;
487    if (!result_list->Get(i, &suggestion_val) ||
488        !suggestion_val->GetAsString(&suggestion_str))
489      return false;
490
491    // Google search may return empty suggestions for weird input characters,
492    // they make no sense at all and can cause problem in our code.
493    // See http://crbug.com/56214
494    if (!suggestion_str.length())
495      continue;
496
497    Value* type_val;
498    std::string type_str;
499    if (type_list && type_list->Get(i, &type_val) &&
500        type_val->GetAsString(&type_str) && (type_str == "NAVIGATION")) {
501      Value* site_val;
502      string16 site_name;
503      NavigationResults& navigation_results =
504          is_keyword ? keyword_navigation_results_ :
505                       default_navigation_results_;
506      if ((navigation_results.size() < kMaxMatches) &&
507          description_list && description_list->Get(i, &site_val) &&
508          site_val->IsType(Value::TYPE_STRING) &&
509          site_val->GetAsString(&site_name)) {
510        // We can't blindly trust the URL coming from the server to be valid.
511        GURL result_url(URLFixerUpper::FixupURL(UTF16ToUTF8(suggestion_str),
512                                                std::string()));
513        if (result_url.is_valid()) {
514          navigation_results.push_back(NavigationResult(result_url, site_name));
515        }
516      }
517    } else {
518      // TODO(kochi): Currently we treat a calculator result as a query, but it
519      // is better to have better presentation for caluculator results.
520      if (suggest_results->size() < kMaxMatches)
521        suggest_results->push_back(suggestion_str);
522    }
523  }
524
525  return true;
526}
527
528void SearchProvider::ConvertResultsToAutocompleteMatches() {
529  // Convert all the results to matches and add them to a map, so we can keep
530  // the most relevant match for each result.
531  MatchMap map;
532  const Time no_time;
533  int did_not_accept_keyword_suggestion = keyword_suggest_results_.empty() ?
534      TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
535      TemplateURLRef::NO_SUGGESTION_CHOSEN;
536  // Keyword what you typed results are handled by the KeywordProvider.
537
538  int did_not_accept_default_suggestion = default_suggest_results_.empty() ?
539        TemplateURLRef::NO_SUGGESTIONS_AVAILABLE :
540        TemplateURLRef::NO_SUGGESTION_CHOSEN;
541  if (providers_.valid_default_provider()) {
542    AddMatchToMap(input_.text(), input_.text(),
543                  CalculateRelevanceForWhatYouTyped(),
544                  AutocompleteMatch::SEARCH_WHAT_YOU_TYPED,
545                  did_not_accept_default_suggestion, false,
546                  input_.initial_prevent_inline_autocomplete(), &map);
547    if (!default_provider_suggest_text_.empty()) {
548      AddMatchToMap(input_.text() + default_provider_suggest_text_,
549                    input_.text(), CalculateRelevanceForWhatYouTyped() + 1,
550                    AutocompleteMatch::SEARCH_SUGGEST,
551                    did_not_accept_default_suggestion, false,
552                    input_.initial_prevent_inline_autocomplete(), &map);
553    }
554  }
555
556  AddHistoryResultsToMap(keyword_history_results_, true,
557                         did_not_accept_keyword_suggestion, &map);
558  AddHistoryResultsToMap(default_history_results_, false,
559                         did_not_accept_default_suggestion, &map);
560
561  AddSuggestResultsToMap(keyword_suggest_results_, true,
562                         did_not_accept_keyword_suggestion, &map);
563  AddSuggestResultsToMap(default_suggest_results_, false,
564                         did_not_accept_default_suggestion, &map);
565
566  // Now add the most relevant matches from the map to |matches_|.
567  matches_.clear();
568  for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i)
569    matches_.push_back(i->second);
570
571  AddNavigationResultsToMatches(keyword_navigation_results_, true);
572  AddNavigationResultsToMatches(default_navigation_results_, false);
573
574  const size_t max_total_matches = kMaxMatches + 1;  // 1 for "what you typed"
575  std::partial_sort(matches_.begin(),
576      matches_.begin() + std::min(max_total_matches, matches_.size()),
577      matches_.end(), &AutocompleteMatch::MoreRelevant);
578  if (matches_.size() > max_total_matches)
579    matches_.erase(matches_.begin() + max_total_matches, matches_.end());
580
581  UpdateFirstSearchMatchDescription();
582
583  UpdateStarredStateOfMatches();
584
585  UpdateDone();
586}
587
588void SearchProvider::AddNavigationResultsToMatches(
589    const NavigationResults& navigation_results,
590    bool is_keyword) {
591  if (!navigation_results.empty()) {
592    // TODO(kochi): http://b/1170574  We add only one results for navigational
593    // suggestions. If we can get more useful information about the score,
594    // consider adding more results.
595    const size_t num_results = is_keyword ?
596        keyword_navigation_results_.size() : default_navigation_results_.size();
597    matches_.push_back(NavigationToMatch(navigation_results.front(),
598        CalculateRelevanceForNavigation(num_results, 0, is_keyword),
599        is_keyword));
600  }
601}
602
603void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results,
604                                            bool is_keyword,
605                                            int did_not_accept_suggestion,
606                                            MatchMap* map) {
607  int last_relevance = 0;
608  AutocompleteClassifier* classifier = profile_->GetAutocompleteClassifier();
609  for (HistoryResults::const_iterator i(results.begin()); i != results.end();
610       ++i) {
611    // History returns results sorted for us. We force the relevance to decrease
612    // so that the sort from history is honored. We should never end up with a
613    // match having a relevance greater than the previous, but they might be
614    // equal. If we didn't force the relevance to decrease and we ended up in a
615    // situation where the relevance was equal, then which was shown first would
616    // be random.
617    // This uses >= to handle the case where 3 or more results have the same
618    // relevance.
619    bool term_looks_like_url = false;
620    // Don't autocomplete search terms that would normally be treated as URLs
621    // when typed. For example, if the user searched for google.com and types
622    // goog, don't autocomplete to the search term google.com. Otherwise, the
623    // input will look like a URL but act like a search, which is confusing.
624    // NOTE: We don't check this in the following cases:
625    //  * When inline autocomplete is disabled, we won't be inline
626    //    autocompleting this term, so we don't need to worry about confusion as
627    //    much.  This also prevents calling Classify() again from inside the
628    //    classifier (which will corrupt state and likely crash), since the
629    //    classifier always disabled inline autocomplete.
630    //  * When the user has typed the whole term, the "what you typed" history
631    //    match will outrank us for URL-like inputs anyway, so we need not do
632    //    anything special.
633    if (!input_.prevent_inline_autocomplete() && classifier &&
634        i->term != input_.text()) {
635      AutocompleteMatch match;
636      classifier->Classify(i->term, string16(), false, &match, NULL);
637      term_looks_like_url = match.transition == PageTransition::TYPED;
638    }
639    int relevance = CalculateRelevanceForHistory(i->time, term_looks_like_url,
640                                                 is_keyword);
641    if (i != results.begin() && relevance >= last_relevance)
642      relevance = last_relevance - 1;
643    last_relevance = relevance;
644    AddMatchToMap(i->term,
645                  is_keyword ? keyword_input_text_ : input_.text(),
646                  relevance,
647                  AutocompleteMatch::SEARCH_HISTORY, did_not_accept_suggestion,
648                  is_keyword, input_.initial_prevent_inline_autocomplete(),
649                  map);
650  }
651}
652
653void SearchProvider::AddSuggestResultsToMap(
654    const SuggestResults& suggest_results,
655    bool is_keyword,
656    int did_not_accept_suggestion,
657    MatchMap* map) {
658  for (size_t i = 0; i < suggest_results.size(); ++i) {
659    AddMatchToMap(suggest_results[i],
660                  is_keyword ? keyword_input_text_ : input_.text(),
661                  CalculateRelevanceForSuggestion(suggest_results.size(), i,
662                                                  is_keyword),
663                  AutocompleteMatch::SEARCH_SUGGEST,
664                  static_cast<int>(i), is_keyword,
665                  input_.initial_prevent_inline_autocomplete(), map);
666  }
667}
668
669int SearchProvider::CalculateRelevanceForWhatYouTyped() const {
670  if (providers_.valid_keyword_provider())
671    return 250;
672
673  switch (input_.type()) {
674    case AutocompleteInput::UNKNOWN:
675    case AutocompleteInput::QUERY:
676    case AutocompleteInput::FORCED_QUERY:
677      return 1300;
678
679    case AutocompleteInput::REQUESTED_URL:
680      return 1150;
681
682    case AutocompleteInput::URL:
683      return 850;
684
685    default:
686      NOTREACHED();
687      return 0;
688  }
689}
690
691int SearchProvider::CalculateRelevanceForHistory(const Time& time,
692                                                 bool looks_like_url,
693                                                 bool is_keyword) const {
694  // The relevance of past searches falls off over time. There are two distinct
695  // equations used. If the first equation is used (searches to the primary
696  // provider with a type other than URL that don't autocomplete to a url) the
697  // score starts at 1399 and falls to 1300. If the second equation is used the
698  // relevance of a search 15 minutes ago is discounted about 50 points, while
699  // the relevance of a search two weeks ago is discounted about 450 points.
700  double elapsed_time = std::max((Time::Now() - time).InSecondsF(), 0.);
701
702  if (providers_.is_primary_provider(is_keyword) &&
703      input_.type() != AutocompleteInput::URL &&
704      !input_.prevent_inline_autocomplete() && !looks_like_url) {
705    // Searches with the past two days get a different curve.
706    const double autocomplete_time= 2 * 24 * 60 * 60;
707    if (elapsed_time < autocomplete_time) {
708      return 1399 - static_cast<int>(99 *
709          std::pow(elapsed_time / autocomplete_time, 2.5));
710    }
711    elapsed_time -= autocomplete_time;
712  }
713
714  const int score_discount =
715      static_cast<int>(6.5 * std::pow(elapsed_time, 0.3));
716
717  // Don't let scores go below 0.  Negative relevance scores are meaningful in
718  // a different way.
719  int base_score;
720  if (!providers_.is_primary_provider(is_keyword))
721    base_score = 200;
722  else
723    base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050;
724  return std::max(0, base_score - score_discount);
725}
726
727int SearchProvider::CalculateRelevanceForSuggestion(size_t num_results,
728                                                    size_t result_number,
729                                                    bool is_keyword) const {
730  DCHECK(result_number < num_results);
731  int base_score;
732  if (!providers_.is_primary_provider(is_keyword))
733    base_score = 100;
734  else
735    base_score = (input_.type() == AutocompleteInput::URL) ? 300 : 600;
736  return base_score +
737      static_cast<int>(num_results - 1 - result_number);
738}
739
740int SearchProvider::CalculateRelevanceForNavigation(size_t num_results,
741                                                    size_t result_number,
742                                                    bool is_keyword) const {
743  DCHECK(result_number < num_results);
744  // TODO(kochi): http://b/784900  Use relevance score from the NavSuggest
745  // server if possible.
746  return (providers_.is_primary_provider(is_keyword) ? 800 : 150) +
747      static_cast<int>(num_results - 1 - result_number);
748}
749
750void SearchProvider::AddMatchToMap(const string16& query_string,
751                                   const string16& input_text,
752                                   int relevance,
753                                   AutocompleteMatch::Type type,
754                                   int accepted_suggestion,
755                                   bool is_keyword,
756                                   bool prevent_inline_autocomplete,
757                                   MatchMap* map) {
758  AutocompleteMatch match(this, relevance, false, type);
759  std::vector<size_t> content_param_offsets;
760  const TemplateURL& provider = is_keyword ? providers_.keyword_provider() :
761                                             providers_.default_provider();
762  match.contents.assign(query_string);
763  // We do intra-string highlighting for suggestions - the suggested segment
764  // will be highlighted, e.g. for input_text = "you" the suggestion may be
765  // "youtube", so we'll bold the "tube" section: you*tube*.
766  if (input_text != query_string) {
767    size_t input_position = match.contents.find(input_text);
768    if (input_position == string16::npos) {
769      // The input text is not a substring of the query string, e.g. input
770      // text is "slasdot" and the query string is "slashdot", so we bold the
771      // whole thing.
772      match.contents_class.push_back(
773          ACMatchClassification(0, ACMatchClassification::MATCH));
774    } else {
775      // TODO(beng): ACMatchClassification::MATCH now seems to just mean
776      //             "bold" this. Consider modifying the terminology.
777      // We don't iterate over the string here annotating all matches because
778      // it looks odd to have every occurrence of a substring that may be as
779      // short as a single character highlighted in a query suggestion result,
780      // e.g. for input text "s" and query string "southwest airlines", it
781      // looks odd if both the first and last s are highlighted.
782      if (input_position != 0) {
783        match.contents_class.push_back(
784            ACMatchClassification(0, ACMatchClassification::NONE));
785      }
786      match.contents_class.push_back(
787          ACMatchClassification(input_position, ACMatchClassification::DIM));
788      size_t next_fragment_position = input_position + input_text.length();
789      if (next_fragment_position < query_string.length()) {
790        match.contents_class.push_back(
791            ACMatchClassification(next_fragment_position,
792                                  ACMatchClassification::NONE));
793      }
794    }
795  } else {
796    // Otherwise, we're dealing with the "default search" result which has no
797    // completion.
798    match.contents_class.push_back(
799        ACMatchClassification(0, ACMatchClassification::NONE));
800  }
801
802  // When the user forced a query, we need to make sure all the fill_into_edit
803  // values preserve that property.  Otherwise, if the user starts editing a
804  // suggestion, non-Search results will suddenly appear.
805  size_t search_start = 0;
806  if (input_.type() == AutocompleteInput::FORCED_QUERY) {
807    match.fill_into_edit.assign(ASCIIToUTF16("?"));
808    ++search_start;
809  }
810  if (is_keyword) {
811    match.fill_into_edit.append(
812        providers_.keyword_provider().keyword() + char16(' '));
813    match.template_url = &providers_.keyword_provider();
814  }
815  match.fill_into_edit.append(query_string);
816  // Not all suggestions start with the original input.
817  if (!prevent_inline_autocomplete &&
818      !match.fill_into_edit.compare(search_start, input_text.length(),
819                                   input_text))
820    match.inline_autocomplete_offset = search_start + input_text.length();
821
822  const TemplateURLRef* const search_url = provider.url();
823  DCHECK(search_url->SupportsReplacement());
824  match.destination_url =
825      GURL(search_url->ReplaceSearchTerms(provider,
826                                          query_string,
827                                          accepted_suggestion,
828                                          input_text));
829
830  // Search results don't look like URLs.
831  match.transition =
832      is_keyword ? PageTransition::KEYWORD : PageTransition::GENERATED;
833
834  // Try to add |match| to |map|.  If a match for |query_string| is already in
835  // |map|, replace it if |match| is more relevant.
836  // NOTE: Keep this ToLower() call in sync with url_database.cc.
837  const std::pair<MatchMap::iterator, bool> i = map->insert(
838      std::pair<string16, AutocompleteMatch>(
839          l10n_util::ToLower(query_string), match));
840  // NOTE: We purposefully do a direct relevance comparison here instead of
841  // using AutocompleteMatch::MoreRelevant(), so that we'll prefer "items added
842  // first" rather than "items alphabetically first" when the scores are equal.
843  // The only case this matters is when a user has results with the same score
844  // that differ only by capitalization; because the history system returns
845  // results sorted by recency, this means we'll pick the most recent such
846  // result even if the precision of our relevance score is too low to
847  // distinguish the two.
848  if (!i.second && (match.relevance > i.first->second.relevance))
849    i.first->second = match;
850}
851
852AutocompleteMatch SearchProvider::NavigationToMatch(
853    const NavigationResult& navigation,
854    int relevance,
855    bool is_keyword) {
856  const string16& input_text =
857      is_keyword ? keyword_input_text_ : input_.text();
858  AutocompleteMatch match(this, relevance, false,
859                          AutocompleteMatch::NAVSUGGEST);
860  match.destination_url = navigation.url;
861  match.contents =
862      StringForURLDisplay(navigation.url, true, !HasHTTPScheme(input_text));
863  AutocompleteMatch::ClassifyMatchInString(input_text, match.contents,
864                                           ACMatchClassification::URL,
865                                           &match.contents_class);
866
867  match.description = navigation.site_name;
868  AutocompleteMatch::ClassifyMatchInString(input_text, navigation.site_name,
869                                           ACMatchClassification::NONE,
870                                           &match.description_class);
871
872  // When the user forced a query, we need to make sure all the fill_into_edit
873  // values preserve that property.  Otherwise, if the user starts editing a
874  // suggestion, non-Search results will suddenly appear.
875  if (input_.type() == AutocompleteInput::FORCED_QUERY)
876    match.fill_into_edit.assign(ASCIIToUTF16("?"));
877  match.fill_into_edit.append(
878      AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url,
879                                                              match.contents));
880  // TODO(pkasting): http://b/1112879 These should perhaps be
881  // inline-autocompletable?
882
883  return match;
884}
885
886void SearchProvider::UpdateDone() {
887  // We're done when there are no more suggest queries pending (this is set to 1
888  // when the timer is started) and we're not waiting on instant.
889  done_ = ((suggest_results_pending_ == 0) &&
890           (instant_finalized_ || !InstantController::IsEnabled(profile_)));
891}
892
893void SearchProvider::UpdateFirstSearchMatchDescription() {
894  if (!providers_.valid_default_provider() || matches_.empty())
895    return;
896
897  for (ACMatches::iterator i = matches_.begin(); i != matches_.end(); ++i) {
898    AutocompleteMatch& match = *i;
899    switch (match.type) {
900      case AutocompleteMatch::SEARCH_WHAT_YOU_TYPED:
901      case AutocompleteMatch::SEARCH_HISTORY:
902      case AutocompleteMatch::SEARCH_SUGGEST:
903        match.description.assign(l10n_util::GetStringFUTF16(
904            IDS_AUTOCOMPLETE_SEARCH_DESCRIPTION,
905            providers_.default_provider().
906                AdjustedShortNameForLocaleDirection()));
907        match.description_class.push_back(
908            ACMatchClassification(0, ACMatchClassification::DIM));
909        // Only the first search match gets a description.
910        return;
911
912      default:
913        break;
914    }
915  }
916}
917