history_url_provider.cc revision 1e9bf3e0803691d0a228da41fc608347b6db4340
1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/autocomplete/history_url_provider.h"
6
7#include <algorithm>
8
9#include "base/basictypes.h"
10#include "base/bind.h"
11#include "base/command_line.h"
12#include "base/message_loop/message_loop.h"
13#include "base/metrics/histogram.h"
14#include "base/prefs/pref_service.h"
15#include "base/strings/string_util.h"
16#include "base/strings/utf_string_conversions.h"
17#include "chrome/browser/autocomplete/autocomplete_match.h"
18#include "chrome/browser/autocomplete/autocomplete_provider_listener.h"
19#include "chrome/browser/history/history_backend.h"
20#include "chrome/browser/history/history_database.h"
21#include "chrome/browser/history/history_service.h"
22#include "chrome/browser/history/history_service_factory.h"
23#include "chrome/browser/history/history_types.h"
24#include "chrome/browser/omnibox/omnibox_field_trial.h"
25#include "chrome/browser/profiles/profile.h"
26#include "chrome/browser/search_engines/template_url_service.h"
27#include "chrome/browser/search_engines/template_url_service_factory.h"
28#include "chrome/common/chrome_switches.h"
29#include "chrome/common/net/url_fixer_upper.h"
30#include "chrome/common/pref_names.h"
31#include "chrome/common/url_constants.h"
32#include "net/base/net_util.h"
33#include "net/base/registry_controlled_domains/registry_controlled_domain.h"
34#include "url/gurl.h"
35#include "url/url_parse.h"
36#include "url/url_util.h"
37
38namespace {
39
40// If |create_if_necessary| is true, ensures that |matches| contains an
41// entry for |info|, creating a new such entry if necessary (using
42// |input_location| and |match_in_scheme|).
43//
44// If |promote| is true, this also ensures the entry is the first element in
45// |matches|, moving or adding it to the front as appropriate.  When |promote|
46// is false, existing matches are left in place, and newly added matches are
47// placed at the back.
48//
49// It's OK to call this function with both |create_if_necessary| and
50// |promote| false, in which case we'll do nothing.
51//
52// Returns whether the match exists regardless if it was promoted/created.
53bool CreateOrPromoteMatch(const history::URLRow& info,
54                          size_t input_location,
55                          bool match_in_scheme,
56                          history::HistoryMatches* matches,
57                          bool create_if_necessary,
58                          bool promote) {
59  // |matches| may already have an entry for this.
60  for (history::HistoryMatches::iterator i(matches->begin());
61       i != matches->end(); ++i) {
62    if (i->url_info.url() == info.url()) {
63      // Rotate it to the front if the caller wishes.
64      if (promote)
65        std::rotate(matches->begin(), i, i + 1);
66      return true;
67    }
68  }
69
70  if (!create_if_necessary)
71    return false;
72
73  // No entry, so create one.
74  history::HistoryMatch match(info, input_location, match_in_scheme, true);
75  if (promote)
76    matches->push_front(match);
77  else
78    matches->push_back(match);
79
80  return true;
81}
82
83// Given the user's |input| and a |match| created from it, reduce the match's
84// URL to just a host.  If this host still matches the user input, return it.
85// Returns the empty string on failure.
86GURL ConvertToHostOnly(const history::HistoryMatch& match,
87                       const string16& input) {
88  // See if we should try to do host-only suggestions for this URL. Nonstandard
89  // schemes means there's no authority section, so suggesting the host name
90  // is useless. File URLs are standard, but host suggestion is not useful for
91  // them either.
92  const GURL& url = match.url_info.url();
93  if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile())
94    return GURL();
95
96  // Transform to a host-only match.  Bail if the host no longer matches the
97  // user input (e.g. because the user typed more than just a host).
98  GURL host = url.GetWithEmptyPath();
99  if ((host.spec().length() < (match.input_location + input.length())))
100    return GURL();  // User typing is longer than this host suggestion.
101
102  const string16 spec = UTF8ToUTF16(host.spec());
103  if (spec.compare(match.input_location, input.length(), input))
104    return GURL();  // User typing is no longer a prefix.
105
106  return host;
107}
108
109// Acts like the > operator for URLInfo classes.
110bool CompareHistoryMatch(const history::HistoryMatch& a,
111                         const history::HistoryMatch& b) {
112  // A promoted match is better than non-promoted.
113  if (a.promoted != b.promoted)
114    return a.promoted;
115
116  // A URL that has been typed at all is better than one that has never been
117  // typed.  (Note "!"s on each side)
118  if (!a.url_info.typed_count() != !b.url_info.typed_count())
119    return a.url_info.typed_count() > b.url_info.typed_count();
120
121  // Innermost matches (matches after any scheme or "www.") are better than
122  // non-innermost matches.
123  if (a.innermost_match != b.innermost_match)
124    return a.innermost_match;
125
126  // URLs that have been typed more often are better.
127  if (a.url_info.typed_count() != b.url_info.typed_count())
128    return a.url_info.typed_count() > b.url_info.typed_count();
129
130  // For URLs that have each been typed once, a host (alone) is better than a
131  // page inside.
132  if ((a.url_info.typed_count() == 1) && (a.IsHostOnly() != b.IsHostOnly()))
133    return a.IsHostOnly();
134
135  // URLs that have been visited more often are better.
136  if (a.url_info.visit_count() != b.url_info.visit_count())
137    return a.url_info.visit_count() > b.url_info.visit_count();
138
139  // URLs that have been visited more recently are better.
140  return a.url_info.last_visit() > b.url_info.last_visit();
141}
142
143// Sorts and dedups the given list of matches.
144void SortAndDedupMatches(history::HistoryMatches* matches) {
145  // Sort by quality, best first.
146  std::sort(matches->begin(), matches->end(), &CompareHistoryMatch);
147
148  // Remove duplicate matches (caused by the search string appearing in one of
149  // the prefixes as well as after it).  Consider the following scenario:
150  //
151  // User has visited "http://http.com" once and "http://htaccess.com" twice.
152  // User types "http".  The autocomplete search with prefix "http://" returns
153  // the first host, while the search with prefix "" returns both hosts.  Now
154  // we sort them into rank order:
155  //   http://http.com     (innermost_match)
156  //   http://htaccess.com (!innermost_match, url_info.visit_count == 2)
157  //   http://http.com     (!innermost_match, url_info.visit_count == 1)
158  //
159  // The above scenario tells us we can't use std::unique(), since our
160  // duplicates are not always sequential.  It also tells us we should remove
161  // the lower-quality duplicate(s), since otherwise the returned results won't
162  // be ordered correctly.  This is easy to do: we just always remove the later
163  // element of a duplicate pair.
164  // Be careful!  Because the vector contents may change as we remove elements,
165  // we use an index instead of an iterator in the outer loop, and don't
166  // precalculate the ending position.
167  for (size_t i = 0; i < matches->size(); ++i) {
168    for (history::HistoryMatches::iterator j(matches->begin() + i + 1);
169         j != matches->end(); ) {
170      if ((*matches)[i].url_info.url() == j->url_info.url())
171        j = matches->erase(j);
172      else
173        ++j;
174    }
175  }
176}
177
178// Extracts typed_count, visit_count, and last_visited time from the
179// URLRow and puts them in the additional info field of the |match|
180// for display in about:omnibox.
181void RecordAdditionalInfoFromUrlRow(const history::URLRow& info,
182                                    AutocompleteMatch* match) {
183  match->RecordAdditionalInfo("typed count", info.typed_count());
184  match->RecordAdditionalInfo("visit count", info.visit_count());
185  match->RecordAdditionalInfo("last visit", info.last_visit());
186}
187
188}  // namespace
189
190// -----------------------------------------------------------------
191// SearchTermsDataSnapshot
192
193// Implementation of SearchTermsData that takes a snapshot of another
194// SearchTermsData by copying all the responses to the different getters into
195// member strings, then returning those strings when its own getters are called.
196// This will typically be constructed on the UI thread from
197// UIThreadSearchTermsData but is subsequently safe to use on any thread.
198class SearchTermsDataSnapshot : public SearchTermsData {
199 public:
200  explicit SearchTermsDataSnapshot(const SearchTermsData& search_terms_data);
201  virtual ~SearchTermsDataSnapshot();
202
203  virtual std::string GoogleBaseURLValue() const OVERRIDE;
204  virtual std::string GetApplicationLocale() const OVERRIDE;
205  virtual string16 GetRlzParameterValue() const OVERRIDE;
206  virtual std::string GetSearchClient() const OVERRIDE;
207  virtual std::string ForceInstantResultsParam(
208      bool for_prerender) const OVERRIDE;
209  virtual std::string InstantExtendedEnabledParam() const OVERRIDE;
210  virtual std::string NTPIsThemedParam() const OVERRIDE;
211
212 private:
213  std::string google_base_url_value_;
214  std::string application_locale_;
215  string16 rlz_parameter_value_;
216  std::string search_client_;
217  std::string force_instant_results_param_;
218  std::string instant_extended_enabled_param_;
219  std::string ntp_is_themed_param_;
220
221  DISALLOW_COPY_AND_ASSIGN(SearchTermsDataSnapshot);
222};
223
224SearchTermsDataSnapshot::SearchTermsDataSnapshot(
225    const SearchTermsData& search_terms_data)
226    : google_base_url_value_(search_terms_data.GoogleBaseURLValue()),
227      application_locale_(search_terms_data.GetApplicationLocale()),
228      rlz_parameter_value_(search_terms_data.GetRlzParameterValue()),
229      search_client_(search_terms_data.GetSearchClient()),
230      force_instant_results_param_(
231          search_terms_data.ForceInstantResultsParam(false)),
232      instant_extended_enabled_param_(
233          search_terms_data.InstantExtendedEnabledParam()),
234      ntp_is_themed_param_(search_terms_data.NTPIsThemedParam()) {}
235
236SearchTermsDataSnapshot::~SearchTermsDataSnapshot() {
237}
238
239std::string SearchTermsDataSnapshot::GoogleBaseURLValue() const {
240  return google_base_url_value_;
241}
242
243std::string SearchTermsDataSnapshot::GetApplicationLocale() const {
244  return application_locale_;
245}
246
247string16 SearchTermsDataSnapshot::GetRlzParameterValue() const {
248  return rlz_parameter_value_;
249}
250
251std::string SearchTermsDataSnapshot::GetSearchClient() const {
252  return search_client_;
253}
254
255std::string SearchTermsDataSnapshot::ForceInstantResultsParam(
256    bool for_prerender) const {
257  return force_instant_results_param_;
258}
259
260std::string SearchTermsDataSnapshot::InstantExtendedEnabledParam() const {
261  return instant_extended_enabled_param_;
262}
263
264std::string SearchTermsDataSnapshot::NTPIsThemedParam() const {
265  return ntp_is_themed_param_;
266}
267
268// -----------------------------------------------------------------
269// HistoryURLProvider
270
271// These ugly magic numbers will go away once we switch all scoring
272// behavior (including URL-what-you-typed) to HistoryQuick provider.
273const int HistoryURLProvider::kScoreForBestInlineableResult = 1413;
274const int HistoryURLProvider::kScoreForUnvisitedIntranetResult = 1403;
275const int HistoryURLProvider::kScoreForWhatYouTypedResult = 1203;
276const int HistoryURLProvider::kBaseScoreForNonInlineableResult = 900;
277
278// VisitClassifier is used to classify the type of visit to a particular url.
279class HistoryURLProvider::VisitClassifier {
280 public:
281  enum Type {
282    INVALID,             // Navigations to the URL are not allowed.
283    UNVISITED_INTRANET,  // A navigable URL for which we have no visit data but
284                         // which is known to refer to a visited intranet host.
285    VISITED,             // The site has been previously visited.
286  };
287
288  VisitClassifier(HistoryURLProvider* provider,
289                  const AutocompleteInput& input,
290                  history::URLDatabase* db);
291
292  // Returns the type of visit for the specified input.
293  Type type() const { return type_; }
294
295  // Returns the URLRow for the visit.
296  const history::URLRow& url_row() const { return url_row_; }
297
298 private:
299  HistoryURLProvider* provider_;
300  history::URLDatabase* db_;
301  Type type_;
302  history::URLRow url_row_;
303
304  DISALLOW_COPY_AND_ASSIGN(VisitClassifier);
305};
306
307HistoryURLProvider::VisitClassifier::VisitClassifier(
308    HistoryURLProvider* provider,
309    const AutocompleteInput& input,
310    history::URLDatabase* db)
311    : provider_(provider),
312      db_(db),
313      type_(INVALID) {
314  const GURL& url = input.canonicalized_url();
315  // Detect email addresses.  These cases will look like "http://user@site/",
316  // and because the history backend strips auth creds, we'll get a bogus exact
317  // match below if the user has visited "site".
318  if (!url.is_valid() ||
319      ((input.type() == AutocompleteInput::UNKNOWN) &&
320       input.parts().username.is_nonempty() &&
321       !input.parts().password.is_nonempty() &&
322       !input.parts().path.is_nonempty()))
323    return;
324
325  if (db_->GetRowForURL(url, &url_row_)) {
326    type_ = VISITED;
327    return;
328  }
329
330  if (provider_->CanFindIntranetURL(db_, input)) {
331    // The user typed an intranet hostname that they've visited (albeit with a
332    // different port and/or path) before.
333    url_row_ = history::URLRow(url);
334    type_ = UNVISITED_INTRANET;
335  }
336}
337
338HistoryURLProviderParams::HistoryURLProviderParams(
339    const AutocompleteInput& input,
340    bool trim_http,
341    const std::string& languages,
342    TemplateURL* default_search_provider,
343    const SearchTermsData& search_terms_data)
344    : message_loop(base::MessageLoop::current()),
345      input(input),
346      prevent_inline_autocomplete(input.prevent_inline_autocomplete()),
347      trim_http(trim_http),
348      failed(false),
349      languages(languages),
350      dont_suggest_exact_input(false),
351      default_search_provider(default_search_provider ?
352          new TemplateURL(default_search_provider->profile(),
353                          default_search_provider->data()) : NULL),
354      search_terms_data(new SearchTermsDataSnapshot(search_terms_data)) {
355}
356
357HistoryURLProviderParams::~HistoryURLProviderParams() {
358}
359
360HistoryURLProvider::HistoryURLProvider(AutocompleteProviderListener* listener,
361                                       Profile* profile)
362    : HistoryProvider(listener, profile,
363          AutocompleteProvider::TYPE_HISTORY_URL),
364      params_(NULL),
365      cull_redirects_(
366          !OmniboxFieldTrial::InHUPCullRedirectsFieldTrial() ||
367          !OmniboxFieldTrial::InHUPCullRedirectsFieldTrialExperimentGroup()),
368      create_shorter_match_(
369          !OmniboxFieldTrial::InHUPCreateShorterMatchFieldTrial() ||
370          !OmniboxFieldTrial::
371              InHUPCreateShorterMatchFieldTrialExperimentGroup()),
372      search_url_database_(true) {
373}
374
375// static
376AutocompleteMatch HistoryURLProvider::SuggestExactInput(
377    AutocompleteProvider* provider,
378    const AutocompleteInput& input,
379    bool trim_http) {
380  AutocompleteMatch match(provider, 0, false,
381                          AutocompleteMatchType::URL_WHAT_YOU_TYPED);
382
383  const GURL& url = input.canonicalized_url();
384  if (url.is_valid()) {
385    match.destination_url = url;
386
387    // Trim off "http://" if the user didn't type it.
388    // NOTE: We use TrimHttpPrefix() here rather than StringForURLDisplay() to
389    // strip the scheme as we need to know the offset so we can adjust the
390    // |match_location| below.  StringForURLDisplay() and TrimHttpPrefix() have
391    // slightly different behavior as well (the latter will strip even without
392    // two slashes after the scheme).
393    DCHECK(!trim_http || !HasHTTPScheme(input.text()));
394    string16 display_string(provider->StringForURLDisplay(url, false, false));
395    const size_t offset = trim_http ? TrimHttpPrefix(&display_string) : 0;
396    match.fill_into_edit =
397        AutocompleteInput::FormattedStringWithEquivalentMeaning(url,
398                                                                display_string);
399    match.allowed_to_be_default_match = true;
400    // NOTE: Don't set match.inline_autocompletion to something non-empty here;
401    // it's surprising and annoying.
402
403    // Try to highlight "innermost" match location.  If we fix up "w" into
404    // "www.w.com", we want to highlight the fifth character, not the first.
405    // This relies on match.destination_url being the non-prefix-trimmed version
406    // of match.contents.
407    match.contents = display_string;
408    const URLPrefix* best_prefix = URLPrefix::BestURLPrefix(
409        UTF8ToUTF16(match.destination_url.spec()), input.text());
410    // It's possible for match.destination_url to not contain the user's input
411    // at all (so |best_prefix| is NULL), for example if the input is
412    // "view-source:x" and |destination_url| has an inserted "http://" in the
413    // middle.
414    if (best_prefix == NULL) {
415      AutocompleteMatch::ClassifyMatchInString(input.text(), match.contents,
416                                               ACMatchClassification::URL,
417                                               &match.contents_class);
418    } else {
419      AutocompleteMatch::ClassifyLocationInString(
420          best_prefix->prefix.length() - offset, input.text().length(),
421          match.contents.length(), ACMatchClassification::URL,
422          &match.contents_class);
423    }
424
425    match.is_history_what_you_typed_match = true;
426  }
427
428  return match;
429}
430
431void HistoryURLProvider::Start(const AutocompleteInput& input,
432                               bool minimal_changes) {
433  // NOTE: We could try hard to do less work in the |minimal_changes| case
434  // here; some clever caching would let us reuse the raw matches from the
435  // history DB without re-querying.  However, we'd still have to go back to
436  // the history thread to mark these up properly, and if pass 2 is currently
437  // running, we'd need to wait for it to return to the main thread before
438  // doing this (we can't just write new data for it to read due to thread
439  // safety issues).  At that point it's just as fast, and easier, to simply
440  // re-run the query from scratch and ignore |minimal_changes|.
441
442  // Cancel any in-progress query.
443  Stop(false);
444
445  RunAutocompletePasses(input, true);
446}
447
448void HistoryURLProvider::Stop(bool clear_cached_results) {
449  done_ = true;
450
451  if (params_)
452    params_->cancel_flag.Set();
453}
454
455// Called on the history thread.
456void HistoryURLProvider::ExecuteWithDB(history::HistoryBackend* backend,
457                                       history::URLDatabase* db,
458                                       HistoryURLProviderParams* params) {
459  // We may get called with a NULL database if it couldn't be properly
460  // initialized.
461  if (!db) {
462    params->failed = true;
463  } else if (!params->cancel_flag.IsSet()) {
464    base::TimeTicks beginning_time = base::TimeTicks::Now();
465
466    DoAutocomplete(backend, db, params);
467
468    UMA_HISTOGRAM_TIMES("Autocomplete.HistoryAsyncQueryTime",
469                        base::TimeTicks::Now() - beginning_time);
470  }
471
472  // Return the results (if any) to the main thread.
473  params->message_loop->PostTask(FROM_HERE, base::Bind(
474      &HistoryURLProvider::QueryComplete, this, params));
475}
476
477// Used by both autocomplete passes, and therefore called on multiple different
478// threads (though not simultaneously).
479void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend,
480                                        history::URLDatabase* db,
481                                        HistoryURLProviderParams* params) {
482  VisitClassifier classifier(this, params->input, db);
483  // Create a What You Typed match, which we'll need below.
484  //
485  // We display this to the user when there's a reasonable chance they actually
486  // care:
487  // * Their input can be opened as a URL, and
488  // * We parsed the input as a URL, or it starts with an explicit "http:" or
489  //   "https:".
490  //  that is when their input can be opened as a URL.
491  // Otherwise, this is just low-quality noise.  In the cases where we've parsed
492  // as UNKNOWN, we'll still show an accidental search infobar if need be.
493  bool have_what_you_typed_match =
494      params->input.canonicalized_url().is_valid() &&
495      (params->input.type() != AutocompleteInput::QUERY) &&
496      ((params->input.type() != AutocompleteInput::UNKNOWN) ||
497       (classifier.type() == VisitClassifier::UNVISITED_INTRANET) ||
498       !params->trim_http ||
499       (AutocompleteInput::NumNonHostComponents(params->input.parts()) > 0));
500  AutocompleteMatch what_you_typed_match(
501      SuggestExactInput(this, params->input, params->trim_http));
502  what_you_typed_match.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0);
503
504  // Get the matching URLs from the DB
505  history::URLRows url_matches;
506  history::HistoryMatches history_matches;
507
508  if (search_url_database_) {
509    const URLPrefixes& prefixes = URLPrefix::GetURLPrefixes();
510    for (URLPrefixes::const_iterator i(prefixes.begin()); i != prefixes.end();
511         ++i) {
512      if (params->cancel_flag.IsSet())
513        return;  // Canceled in the middle of a query, give up.
514      // We only need kMaxMatches results in the end, but before we
515      // get there we need to promote lower-quality matches that are
516      // prefixes of higher-quality matches, and remove lower-quality
517      // redirects.  So we ask for more results than we need, of every
518      // prefix type, in hopes this will give us far more than enough
519      // to work with.  CullRedirects() will then reduce the list to
520      // the best kMaxMatches results.
521      db->AutocompleteForPrefix(
522          UTF16ToUTF8(i->prefix + params->input.text()),
523          kMaxMatches * 2,
524          (backend == NULL),
525          &url_matches);
526      for (history::URLRows::const_iterator j(url_matches.begin());
527           j != url_matches.end(); ++j) {
528        const URLPrefix* best_prefix =
529            URLPrefix::BestURLPrefix(UTF8ToUTF16(j->url().spec()), string16());
530        DCHECK(best_prefix != NULL);
531        history_matches.push_back(history::HistoryMatch(*j, i->prefix.length(),
532            i->num_components == 0,
533            i->num_components >= best_prefix->num_components));
534      }
535    }
536  }
537
538  // Create sorted list of suggestions.
539  CullPoorMatches(*params, &history_matches);
540  SortAndDedupMatches(&history_matches);
541  PromoteOrCreateShorterSuggestion(db, *params, have_what_you_typed_match,
542                                   what_you_typed_match, &history_matches);
543
544  // Try to promote a match as an exact/inline autocomplete match.  This also
545  // moves it to the front of |history_matches|, so skip over it when
546  // converting the rest of the matches.
547  size_t first_match = 1;
548  size_t exact_suggestion = 0;
549  // Checking |is_history_what_you_typed_match| tells us whether
550  // SuggestExactInput() succeeded in constructing a valid match.
551  if (what_you_typed_match.is_history_what_you_typed_match &&
552      (!backend || !params->dont_suggest_exact_input) &&
553      FixupExactSuggestion(db, params->input, classifier, &what_you_typed_match,
554                           &history_matches)) {
555    // Got an exact match for the user's input.  Treat it as the best match
556    // regardless of the input type.
557    exact_suggestion = 1;
558    params->matches.push_back(what_you_typed_match);
559  } else if (params->prevent_inline_autocomplete ||
560      history_matches.empty() ||
561      !PromoteMatchForInlineAutocomplete(history_matches.front(), params)) {
562    // Failed to promote any URLs for inline autocompletion.  Use the What You
563    // Typed match, if we have it.
564    first_match = 0;
565    if (have_what_you_typed_match)
566      params->matches.push_back(what_you_typed_match);
567  }
568
569  // This is the end of the synchronous pass.
570  if (!backend)
571    return;
572  // If search_url_database_ is false, we shouldn't have scheduled a second
573  // pass.
574  DCHECK(search_url_database_);
575
576  // Determine relevancy of highest scoring match, if any.
577  int relevance = -1;
578  for (ACMatches::const_iterator it = params->matches.begin();
579       it != params->matches.end(); ++it) {
580    relevance = std::max(relevance, it->relevance);
581  }
582
583  if (cull_redirects_) {
584    // Remove redirects and trim list to size.  We want to provide up to
585    // kMaxMatches results plus the What You Typed result, if it was added to
586    // |history_matches| above.
587    CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion);
588  } else {
589    // Simply trim the list to size.
590    if (history_matches.size() > kMaxMatches + exact_suggestion)
591      history_matches.resize(kMaxMatches + exact_suggestion);
592  }
593
594  // Convert the history matches to autocomplete matches.
595  for (size_t i = first_match; i < history_matches.size(); ++i) {
596    const history::HistoryMatch& match = history_matches[i];
597    DCHECK(!have_what_you_typed_match ||
598           (match.url_info.url() !=
599            GURL(params->matches.front().destination_url)));
600    // If we've assigned a score already, all later matches score one
601    // less than the previous match.
602    relevance = (relevance > 0) ? (relevance - 1) :
603       CalculateRelevance(NORMAL, history_matches.size() - 1 - i);
604    AutocompleteMatch ac_match = HistoryMatchToACMatch(*params, match,
605        NORMAL, relevance);
606    params->matches.push_back(ac_match);
607  }
608}
609
610// Called on the main thread when the query is complete.
611void HistoryURLProvider::QueryComplete(
612    HistoryURLProviderParams* params_gets_deleted) {
613  // Ensure |params_gets_deleted| gets deleted on exit.
614  scoped_ptr<HistoryURLProviderParams> params(params_gets_deleted);
615
616  // If the user hasn't already started another query, clear our member pointer
617  // so we can't write into deleted memory.
618  if (params_ == params_gets_deleted)
619    params_ = NULL;
620
621  // Don't send responses for queries that have been canceled.
622  if (params->cancel_flag.IsSet())
623    return;  // Already set done_ when we canceled, no need to set it again.
624
625  // Don't modify |matches_| if the query failed, since it might have a default
626  // match in it, whereas |params->matches| will be empty.
627  if (!params->failed) {
628    matches_.swap(params->matches);
629    UpdateStarredStateOfMatches();
630  }
631
632  done_ = true;
633  listener_->OnProviderUpdate(true);
634}
635
636HistoryURLProvider::~HistoryURLProvider() {
637  // Note: This object can get leaked on shutdown if there are pending
638  // requests on the database (which hold a reference to us). Normally, these
639  // messages get flushed for each thread. We do a round trip from main, to
640  // history, back to main while holding a reference. If the main thread
641  // completes before the history thread, the message to delegate back to the
642  // main thread will not run and the reference will leak. Therefore, don't do
643  // anything on destruction.
644}
645
646int HistoryURLProvider::CalculateRelevance(MatchType match_type,
647                                           size_t match_number) const {
648  switch (match_type) {
649    case INLINE_AUTOCOMPLETE:
650      return kScoreForBestInlineableResult;
651
652    case UNVISITED_INTRANET:
653      return kScoreForUnvisitedIntranetResult;
654
655    case WHAT_YOU_TYPED:
656      return kScoreForWhatYouTypedResult;
657
658    default:  // NORMAL
659      return kBaseScoreForNonInlineableResult +
660          static_cast<int>(match_number);
661  }
662}
663
664void HistoryURLProvider::RunAutocompletePasses(
665    const AutocompleteInput& input,
666    bool fixup_input_and_run_pass_1) {
667  matches_.clear();
668
669  if ((input.type() == AutocompleteInput::INVALID) ||
670      (input.type() == AutocompleteInput::FORCED_QUERY))
671    return;
672
673  // Create a match for exactly what the user typed.  This will only be used as
674  // a fallback in case we can't get the history service or URL DB; otherwise,
675  // we'll run this again in DoAutocomplete() and use that result instead.
676  const bool trim_http = !HasHTTPScheme(input.text());
677  // Don't do this for queries -- while we can sometimes mark up a match for
678  // this, it's not what the user wants, and just adds noise.
679  if ((input.type() != AutocompleteInput::QUERY) &&
680      input.canonicalized_url().is_valid()) {
681    AutocompleteMatch what_you_typed(SuggestExactInput(this, input, trim_http));
682    what_you_typed.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0);
683    matches_.push_back(what_you_typed);
684  }
685
686  // We'll need the history service to run both passes, so try to obtain it.
687  if (!profile_)
688    return;
689  HistoryService* const history_service =
690      HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
691  if (!history_service)
692    return;
693
694  // Get the default search provider and search terms data now since we have to
695  // retrieve these on the UI thread, and the second pass runs on the history
696  // thread. |template_url_service| can be NULL when testing.
697  TemplateURLService* template_url_service =
698      TemplateURLServiceFactory::GetForProfile(profile_);
699  TemplateURL* default_search_provider = template_url_service ?
700      template_url_service->GetDefaultSearchProvider() : NULL;
701  UIThreadSearchTermsData data(profile_);
702
703  // Create the data structure for the autocomplete passes.  We'll save this off
704  // onto the |params_| member for later deletion below if we need to run pass
705  // 2.
706  scoped_ptr<HistoryURLProviderParams> params(
707      new HistoryURLProviderParams(
708          input, trim_http,
709          profile_->GetPrefs()->GetString(prefs::kAcceptLanguages),
710          default_search_provider, data));
711
712  params->prevent_inline_autocomplete =
713      PreventInlineAutocomplete(input);
714
715  if (fixup_input_and_run_pass_1) {
716    // Do some fixup on the user input before matching against it, so we provide
717    // good results for local file paths, input with spaces, etc.
718    if (!FixupUserInput(&params->input))
719      return;
720
721    // Pass 1: Get the in-memory URL database, and use it to find and promote
722    // the inline autocomplete match, if any.
723    history::URLDatabase* url_db = history_service->InMemoryDatabase();
724    // url_db can be NULL if it hasn't finished initializing (or failed to
725    // initialize).  In this case all we can do is fall back on the second
726    // pass.
727    //
728    // TODO(pkasting): We should just block here until this loads.  Any time
729    // someone unloads the history backend, we'll get inconsistent inline
730    // autocomplete behavior here.
731    if (url_db) {
732      DoAutocomplete(NULL, url_db, params.get());
733      // params->matches now has the matches we should expose to the provider.
734      // Pass 2 expects a "clean slate" set of matches.
735      matches_.clear();
736      matches_.swap(params->matches);
737      UpdateStarredStateOfMatches();
738    }
739  }
740
741  // Pass 2: Ask the history service to call us back on the history thread,
742  // where we can read the full on-disk DB.
743  if (search_url_database_ &&
744      (input.matches_requested() == AutocompleteInput::ALL_MATCHES)) {
745    done_ = false;
746    params_ = params.release();  // This object will be destroyed in
747                                 // QueryComplete() once we're done with it.
748    history_service->ScheduleAutocomplete(this, params_);
749  }
750}
751
752bool HistoryURLProvider::FixupExactSuggestion(
753    history::URLDatabase* db,
754    const AutocompleteInput& input,
755    const VisitClassifier& classifier,
756    AutocompleteMatch* match,
757    history::HistoryMatches* matches) const {
758  DCHECK(match != NULL);
759  DCHECK(matches != NULL);
760
761  MatchType type = INLINE_AUTOCOMPLETE;
762  switch (classifier.type()) {
763    case VisitClassifier::INVALID:
764      return false;
765    case VisitClassifier::UNVISITED_INTRANET:
766      type = UNVISITED_INTRANET;
767      break;
768    default:
769      DCHECK_EQ(VisitClassifier::VISITED, classifier.type());
770      // We have data for this match, use it.
771      match->deletable = true;
772      match->description = classifier.url_row().title();
773      RecordAdditionalInfoFromUrlRow(classifier.url_row(), match);
774      AutocompleteMatch::ClassifyMatchInString(
775          input.text(),
776          classifier.url_row().title(),
777          ACMatchClassification::NONE, &match->description_class);
778      if (!classifier.url_row().typed_count()) {
779        // If we reach here, we must be in the second pass, and we must not have
780        // this row's data available during the first pass.  That means we
781        // either scored it as WHAT_YOU_TYPED or UNVISITED_INTRANET, and to
782        // maintain the ordering between passes consistent, we need to score it
783        // the same way here.
784        type = CanFindIntranetURL(db, input) ?
785            UNVISITED_INTRANET : WHAT_YOU_TYPED;
786      }
787      break;
788  }
789
790  const GURL& url = match->destination_url;
791  const url_parse::Parsed& parsed = url.parsed_for_possibly_invalid_spec();
792  // If the what-you-typed result looks like a single word (which can be
793  // interpreted as an intranet address) followed by a pound sign ("#"),
794  // leave the score for the url-what-you-typed result as is.  It will be
795  // outscored by a search query from the SearchProvider. This test fixes
796  // cases such as "c#" and "c# foo" where the user has visited an intranet
797  // site "c".  We want the search-what-you-typed score to beat the
798  // URL-what-you-typed score in this case.  Most of the below test tries to
799  // make sure that this code does not trigger if the user did anything to
800  // indicate the desired match is a URL.  For instance, "c/# foo" will not
801  // pass the test because that will be classified as input type URL.  The
802  // parsed.CountCharactersBefore() in the test looks for the presence of a
803  // reference fragment in the URL by checking whether the position differs
804  // included the delimiter (pound sign) versus not including the delimiter.
805  // (One cannot simply check url.ref() because it will not distinguish
806  // between the input "c" and the input "c#", both of which will have empty
807  // reference fragments.)
808  if ((type == UNVISITED_INTRANET) &&
809      (input.type() != AutocompleteInput::URL) &&
810      url.username().empty() && url.password().empty() && url.port().empty() &&
811      (url.path() == "/") && url.query().empty() &&
812      (parsed.CountCharactersBefore(url_parse::Parsed::REF, true) !=
813       parsed.CountCharactersBefore(url_parse::Parsed::REF, false))) {
814    return false;
815  }
816
817  match->relevance = CalculateRelevance(type, 0);
818
819  // If there are any other matches, then don't promote this match here, in
820  // hopes the caller will be able to inline autocomplete a better suggestion.
821  // DoAutocomplete() will fall back on this match if inline autocompletion
822  // fails.  This matches how we react to never-visited URL inputs in the non-
823  // intranet case.
824  if (type == UNVISITED_INTRANET && !matches->empty())
825    return false;
826
827  // Put it on the front of the HistoryMatches for redirect culling.
828  CreateOrPromoteMatch(classifier.url_row(), string16::npos, false, matches,
829                       true, true);
830  return true;
831}
832
833bool HistoryURLProvider::CanFindIntranetURL(
834    history::URLDatabase* db,
835    const AutocompleteInput& input) const {
836  // Normally passing the first two conditions below ought to guarantee the
837  // third condition, but because FixupUserInput() can run and modify the
838  // input's text and parts between Parse() and here, it seems better to be
839  // paranoid and check.
840  if ((input.type() != AutocompleteInput::UNKNOWN) ||
841      !LowerCaseEqualsASCII(input.scheme(), content::kHttpScheme) ||
842      !input.parts().host.is_nonempty())
843    return false;
844  const std::string host(UTF16ToUTF8(
845      input.text().substr(input.parts().host.begin, input.parts().host.len)));
846  const size_t registry_length =
847      net::registry_controlled_domains::GetRegistryLength(
848          host,
849          net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
850          net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
851  return registry_length == 0 && db->IsTypedHost(host);
852}
853
854bool HistoryURLProvider::PromoteMatchForInlineAutocomplete(
855    const history::HistoryMatch& match,
856    HistoryURLProviderParams* params) {
857  // Promote the first match if it's been marked for promotion or typed at least
858  // n times, where n == 1 for "simple" (host-only) URLs and n == 2 for others.
859  // We set a higher bar for these long URLs because it's less likely that users
860  // will want to visit them again.  Even though we don't increment the
861  // typed_count for pasted-in URLs, if the user manually edits the URL or types
862  // some long thing in by hand, we wouldn't want to immediately start
863  // autocompleting it.
864  if (!match.promoted &&
865      (!match.url_info.typed_count() ||
866       ((match.url_info.typed_count() == 1) &&
867        !match.IsHostOnly())))
868    return false;
869
870  // In the case where the user has typed "foo.com" and visited (but not typed)
871  // "foo/", and the input is "foo", we can reach here for "foo.com" during the
872  // first pass but have the second pass suggest the exact input as a better
873  // URL.  Since we need both passes to agree, and since during the first pass
874  // there's no way to know about "foo/", make reaching this point prevent any
875  // future pass from suggesting the exact input as a better match.
876  if (params) {
877    params->dont_suggest_exact_input = true;
878    params->matches.push_back(HistoryMatchToACMatch(*params, match,
879        INLINE_AUTOCOMPLETE, CalculateRelevance(INLINE_AUTOCOMPLETE, 0)));
880  }
881  return true;
882}
883
884// See if a shorter version of the best match should be created, and if so place
885// it at the front of |matches|.  This can suggest history URLs that are
886// prefixes of the best match (if they've been visited enough, compared to the
887// best match), or create host-only suggestions even when they haven't been
888// visited before: if the user visited http://example.com/asdf once, we'll
889// suggest http://example.com/ even if they've never been to it.
890void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
891    history::URLDatabase* db,
892    const HistoryURLProviderParams& params,
893    bool have_what_you_typed_match,
894    const AutocompleteMatch& what_you_typed_match,
895    history::HistoryMatches* matches) {
896  if (matches->empty())
897    return;  // No matches, nothing to do.
898
899  // Determine the base URL from which to search, and whether that URL could
900  // itself be added as a match.  We can add the base iff it's not "effectively
901  // the same" as any "what you typed" match.
902  const history::HistoryMatch& match = matches->front();
903  GURL search_base = ConvertToHostOnly(match, params.input.text());
904  bool can_add_search_base_to_matches = !have_what_you_typed_match;
905  if (search_base.is_empty()) {
906    // Search from what the user typed when we couldn't reduce the best match
907    // to a host.  Careful: use a substring of |match| here, rather than the
908    // first match in |params|, because they might have different prefixes.  If
909    // the user typed "google.com", |what_you_typed_match| will hold
910    // "http://google.com/", but |match| might begin with
911    // "http://www.google.com/".
912    // TODO: this should be cleaned up, and is probably incorrect for IDN.
913    std::string new_match = match.url_info.url().possibly_invalid_spec().
914        substr(0, match.input_location + params.input.text().length());
915    search_base = GURL(new_match);
916    // TODO(mrossetti): There is a degenerate case where the following may
917    // cause a failure: http://www/~someword/fubar.html. Diagnose.
918    // See: http://crbug.com/50101
919    if (search_base.is_empty())
920      return;  // Can't construct a valid URL from which to start a search.
921  } else if (!can_add_search_base_to_matches) {
922    can_add_search_base_to_matches =
923        (search_base != what_you_typed_match.destination_url);
924  }
925  if (search_base == match.url_info.url())
926    return;  // Couldn't shorten |match|, so no range of URLs to search over.
927
928  // Search the DB for short URLs between our base and |match|.
929  history::URLRow info(search_base);
930  bool promote = true;
931  // A short URL is only worth suggesting if it's been visited at least a third
932  // as often as the longer URL.
933  const int min_visit_count = ((match.url_info.visit_count() - 1) / 3) + 1;
934  // For stability between the in-memory and on-disk autocomplete passes, when
935  // the long URL has been typed before, only suggest shorter URLs that have
936  // also been typed.  Otherwise, the on-disk pass could suggest a shorter URL
937  // (which hasn't been typed) that the in-memory pass doesn't know about,
938  // thereby making the top match, and thus the behavior of inline
939  // autocomplete, unstable.
940  const int min_typed_count = match.url_info.typed_count() ? 1 : 0;
941  if (!db->FindShortestURLFromBase(search_base.possibly_invalid_spec(),
942          match.url_info.url().possibly_invalid_spec(), min_visit_count,
943          min_typed_count, can_add_search_base_to_matches, &info)) {
944    if (!can_add_search_base_to_matches)
945      return;  // Couldn't find anything and can't add the search base, bail.
946
947    // Try to get info on the search base itself.  Promote it to the top if the
948    // original best match isn't good enough to autocomplete.
949    db->GetRowForURL(search_base, &info);
950    promote = match.url_info.typed_count() <= 1;
951  }
952
953  // Promote or add the desired URL to the list of matches.
954  bool ensure_can_inline =
955      promote && PromoteMatchForInlineAutocomplete(match, NULL);
956  ensure_can_inline &= CreateOrPromoteMatch(info, match.input_location,
957      match.match_in_scheme, matches, create_shorter_match_, promote);
958  if (ensure_can_inline)
959    matches->front().promoted = true;
960}
961
962void HistoryURLProvider::CullPoorMatches(
963    const HistoryURLProviderParams& params,
964    history::HistoryMatches* matches) const {
965  const base::Time& threshold(history::AutocompleteAgeThreshold());
966  for (history::HistoryMatches::iterator i(matches->begin());
967       i != matches->end(); ) {
968    if (RowQualifiesAsSignificant(i->url_info, threshold) &&
969        !(params.default_search_provider &&
970            params.default_search_provider->IsSearchURLUsingTermsData(
971                i->url_info.url(), *params.search_terms_data.get()))) {
972      ++i;
973    } else {
974      i = matches->erase(i);
975    }
976  }
977}
978
979void HistoryURLProvider::CullRedirects(history::HistoryBackend* backend,
980                                       history::HistoryMatches* matches,
981                                       size_t max_results) const {
982  for (size_t source = 0;
983       (source < matches->size()) && (source < max_results); ) {
984    const GURL& url = (*matches)[source].url_info.url();
985    // TODO(brettw) this should go away when everything uses GURL.
986    history::RedirectList redirects;
987    backend->GetMostRecentRedirectsFrom(url, &redirects);
988    if (!redirects.empty()) {
989      // Remove all but the first occurrence of any of these redirects in the
990      // search results. We also must add the URL we queried for, since it may
991      // not be the first match and we'd want to remove it.
992      //
993      // For example, when A redirects to B and our matches are [A, X, B],
994      // we'll get B as the redirects from, and we want to remove the second
995      // item of that pair, removing B. If A redirects to B and our matches are
996      // [B, X, A], we'll want to remove A instead.
997      redirects.push_back(url);
998      source = RemoveSubsequentMatchesOf(matches, source, redirects);
999    } else {
1000      // Advance to next item.
1001      source++;
1002    }
1003  }
1004
1005  if (matches->size() > max_results)
1006    matches->resize(max_results);
1007}
1008
1009size_t HistoryURLProvider::RemoveSubsequentMatchesOf(
1010    history::HistoryMatches* matches,
1011    size_t source_index,
1012    const std::vector<GURL>& remove) const {
1013  size_t next_index = source_index + 1;  // return value = item after source
1014
1015  // Find the first occurrence of any URL in the redirect chain. We want to
1016  // keep this one since it is rated the highest.
1017  history::HistoryMatches::iterator first(std::find_first_of(
1018      matches->begin(), matches->end(), remove.begin(), remove.end(),
1019      history::HistoryMatch::EqualsGURL));
1020  DCHECK(first != matches->end()) << "We should have always found at least the "
1021      "original URL.";
1022
1023  // Find any following occurrences of any URL in the redirect chain, these
1024  // should be deleted.
1025  for (history::HistoryMatches::iterator next(std::find_first_of(first + 1,
1026           matches->end(), remove.begin(), remove.end(),
1027           history::HistoryMatch::EqualsGURL));
1028       next != matches->end(); next = std::find_first_of(next, matches->end(),
1029           remove.begin(), remove.end(), history::HistoryMatch::EqualsGURL)) {
1030    // Remove this item. When we remove an item before the source index, we
1031    // need to shift it to the right and remember that so we can return it.
1032    next = matches->erase(next);
1033    if (static_cast<size_t>(next - matches->begin()) < next_index)
1034      --next_index;
1035  }
1036  return next_index;
1037}
1038
1039AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch(
1040    const HistoryURLProviderParams& params,
1041    const history::HistoryMatch& history_match,
1042    MatchType match_type,
1043    int relevance) {
1044  const history::URLRow& info = history_match.url_info;
1045  AutocompleteMatch match(this, relevance,
1046      !!info.visit_count(), AutocompleteMatchType::HISTORY_URL);
1047  match.typed_count = info.typed_count();
1048  match.destination_url = info.url();
1049  DCHECK(match.destination_url.is_valid());
1050  size_t inline_autocomplete_offset =
1051      history_match.input_location + params.input.text().length();
1052  std::string languages = (match_type == WHAT_YOU_TYPED) ?
1053      std::string() : params.languages;
1054  const net::FormatUrlTypes format_types = net::kFormatUrlOmitAll &
1055      ~((params.trim_http && !history_match.match_in_scheme) ?
1056          0 : net::kFormatUrlOmitHTTP);
1057  match.fill_into_edit =
1058      AutocompleteInput::FormattedStringWithEquivalentMeaning(info.url(),
1059          net::FormatUrl(info.url(), languages, format_types,
1060                         net::UnescapeRule::SPACES, NULL, NULL,
1061                         &inline_autocomplete_offset));
1062  if (!params.prevent_inline_autocomplete &&
1063      (inline_autocomplete_offset != string16::npos)) {
1064    DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length());
1065    match.inline_autocompletion =
1066        match.fill_into_edit.substr(inline_autocomplete_offset);
1067  }
1068  // The latter part of the test effectively asks "is the inline completion
1069  // empty?" (i.e., is this match effectively the what-you-typed match?).
1070  match.allowed_to_be_default_match = !params.prevent_inline_autocomplete ||
1071      ((inline_autocomplete_offset != string16::npos) &&
1072       (inline_autocomplete_offset >= match.fill_into_edit.length()));
1073
1074  size_t match_start = history_match.input_location;
1075  match.contents = net::FormatUrl(info.url(), languages,
1076      format_types, net::UnescapeRule::SPACES, NULL, NULL, &match_start);
1077  if ((match_start != string16::npos) &&
1078      (inline_autocomplete_offset != string16::npos) &&
1079      (inline_autocomplete_offset != match_start)) {
1080    DCHECK(inline_autocomplete_offset > match_start);
1081    AutocompleteMatch::ClassifyLocationInString(match_start,
1082        inline_autocomplete_offset - match_start, match.contents.length(),
1083        ACMatchClassification::URL, &match.contents_class);
1084  } else {
1085    AutocompleteMatch::ClassifyLocationInString(string16::npos, 0,
1086        match.contents.length(), ACMatchClassification::URL,
1087        &match.contents_class);
1088  }
1089  match.description = info.title();
1090  AutocompleteMatch::ClassifyMatchInString(params.input.text(),
1091                                           info.title(),
1092                                           ACMatchClassification::NONE,
1093                                           &match.description_class);
1094  RecordAdditionalInfoFromUrlRow(info, &match);
1095  return match;
1096}
1097