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.
5 #include "chrome/browser/autocomplete/history_url_provider.h"
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"
35 #include "url/url_parse.h"
36 #include "url/url_util.h"
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|).
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.
49 // It's OK to call this function with both |create_if_necessary| and
50 // |promote| false, in which case we'll do nothing.
52 // Returns whether the match exists regardless if it was promoted/created.
53 bool CreateOrPromoteMatch(const history::URLRow& info,
54 size_t input_location,
56 history::HistoryMatches* matches,
57 bool create_if_necessary,
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.
65 std::rotate(matches->begin(), i, i + 1);
70 if (!create_if_necessary)
73 // No entry, so create one.
74 history::HistoryMatch match(info, input_location, match_in_scheme, true);
76 matches->push_front(match);
78 matches->push_back(match);
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.
86 GURL 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
92 const GURL& url = match.url_info.url();
93 if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile())
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.
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.
109 // Acts like the > operator for URLInfo classes.
110 bool 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)
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();
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;
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();
130 // For URLs that have each been typed once, a host (alone) is better than a
132 if ((a.url_info.typed_count() == 1) && (a.IsHostOnly() != b.IsHostOnly()))
133 return a.IsHostOnly();
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();
139 // URLs that have been visited more recently are better.
140 return a.url_info.last_visit() > b.url_info.last_visit();
143 // Sorts and dedups the given list of matches.
144 void SortAndDedupMatches(history::HistoryMatches* matches) {
145 // Sort by quality, best first.
146 std::sort(matches->begin(), matches->end(), &CompareHistoryMatch);
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:
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)
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);
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.
181 void 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());
190 // -----------------------------------------------------------------
191 // SearchTermsDataSnapshot
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.
198 class SearchTermsDataSnapshot : public SearchTermsData {
200 explicit SearchTermsDataSnapshot(const SearchTermsData& search_terms_data);
201 virtual ~SearchTermsDataSnapshot();
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;
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_;
221 DISALLOW_COPY_AND_ASSIGN(SearchTermsDataSnapshot);
224 SearchTermsDataSnapshot::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()) {}
236 SearchTermsDataSnapshot::~SearchTermsDataSnapshot() {
239 std::string SearchTermsDataSnapshot::GoogleBaseURLValue() const {
240 return google_base_url_value_;
243 std::string SearchTermsDataSnapshot::GetApplicationLocale() const {
244 return application_locale_;
247 string16 SearchTermsDataSnapshot::GetRlzParameterValue() const {
248 return rlz_parameter_value_;
251 std::string SearchTermsDataSnapshot::GetSearchClient() const {
252 return search_client_;
255 std::string SearchTermsDataSnapshot::ForceInstantResultsParam(
256 bool for_prerender) const {
257 return force_instant_results_param_;
260 std::string SearchTermsDataSnapshot::InstantExtendedEnabledParam() const {
261 return instant_extended_enabled_param_;
264 std::string SearchTermsDataSnapshot::NTPIsThemedParam() const {
265 return ntp_is_themed_param_;
268 // -----------------------------------------------------------------
269 // HistoryURLProvider
271 // These ugly magic numbers will go away once we switch all scoring
272 // behavior (including URL-what-you-typed) to HistoryQuick provider.
273 const int HistoryURLProvider::kScoreForBestInlineableResult = 1413;
274 const int HistoryURLProvider::kScoreForUnvisitedIntranetResult = 1403;
275 const int HistoryURLProvider::kScoreForWhatYouTypedResult = 1203;
276 const int HistoryURLProvider::kBaseScoreForNonInlineableResult = 900;
278 // VisitClassifier is used to classify the type of visit to a particular url.
279 class HistoryURLProvider::VisitClassifier {
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.
288 VisitClassifier(HistoryURLProvider* provider,
289 const AutocompleteInput& input,
290 history::URLDatabase* db);
292 // Returns the type of visit for the specified input.
293 Type type() const { return type_; }
295 // Returns the URLRow for the visit.
296 const history::URLRow& url_row() const { return url_row_; }
299 HistoryURLProvider* provider_;
300 history::URLDatabase* db_;
302 history::URLRow url_row_;
304 DISALLOW_COPY_AND_ASSIGN(VisitClassifier);
307 HistoryURLProvider::VisitClassifier::VisitClassifier(
308 HistoryURLProvider* provider,
309 const AutocompleteInput& input,
310 history::URLDatabase* db)
311 : provider_(provider),
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()))
325 if (db_->GetRowForURL(url, &url_row_)) {
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;
338 HistoryURLProviderParams::HistoryURLProviderParams(
339 const AutocompleteInput& input,
341 const std::string& languages,
342 TemplateURL* default_search_provider,
343 const SearchTermsData& search_terms_data)
344 : message_loop(base::MessageLoop::current()),
346 prevent_inline_autocomplete(input.prevent_inline_autocomplete()),
347 trim_http(trim_http),
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)) {
357 HistoryURLProviderParams::~HistoryURLProviderParams() {
360 HistoryURLProvider::HistoryURLProvider(AutocompleteProviderListener* listener,
362 : HistoryProvider(listener, profile,
363 AutocompleteProvider::TYPE_HISTORY_URL),
366 !OmniboxFieldTrial::InHUPCullRedirectsFieldTrial() ||
367 !OmniboxFieldTrial::InHUPCullRedirectsFieldTrialExperimentGroup()),
368 create_shorter_match_(
369 !OmniboxFieldTrial::InHUPCreateShorterMatchFieldTrial() ||
371 InHUPCreateShorterMatchFieldTrialExperimentGroup()),
372 search_url_database_(true) {
375 void HistoryURLProvider::Start(const AutocompleteInput& input,
376 bool minimal_changes) {
377 // NOTE: We could try hard to do less work in the |minimal_changes| case
378 // here; some clever caching would let us reuse the raw matches from the
379 // history DB without re-querying. However, we'd still have to go back to
380 // the history thread to mark these up properly, and if pass 2 is currently
381 // running, we'd need to wait for it to return to the main thread before
382 // doing this (we can't just write new data for it to read due to thread
383 // safety issues). At that point it's just as fast, and easier, to simply
384 // re-run the query from scratch and ignore |minimal_changes|.
386 // Cancel any in-progress query.
389 RunAutocompletePasses(input, true);
392 void HistoryURLProvider::Stop(bool clear_cached_results) {
396 params_->cancel_flag.Set();
399 AutocompleteMatch HistoryURLProvider::SuggestExactInput(
400 const string16& text,
401 const GURL& destination_url,
403 AutocompleteMatch match(this, 0, false,
404 AutocompleteMatchType::URL_WHAT_YOU_TYPED);
406 if (destination_url.is_valid()) {
407 match.destination_url = destination_url;
409 // Trim off "http://" if the user didn't type it.
410 // NOTE: We use TrimHttpPrefix() here rather than StringForURLDisplay() to
411 // strip the scheme as we need to know the offset so we can adjust the
412 // |match_location| below. StringForURLDisplay() and TrimHttpPrefix() have
413 // slightly different behavior as well (the latter will strip even without
414 // two slashes after the scheme).
415 DCHECK(!trim_http || !AutocompleteInput::HasHTTPScheme(text));
416 string16 display_string(StringForURLDisplay(destination_url, false, false));
417 const size_t offset = trim_http ? TrimHttpPrefix(&display_string) : 0;
418 match.fill_into_edit =
419 AutocompleteInput::FormattedStringWithEquivalentMeaning(destination_url,
421 match.allowed_to_be_default_match = true;
422 // NOTE: Don't set match.inline_autocompletion to something non-empty here;
423 // it's surprising and annoying.
425 // Try to highlight "innermost" match location. If we fix up "w" into
426 // "www.w.com", we want to highlight the fifth character, not the first.
427 // This relies on match.destination_url being the non-prefix-trimmed version
428 // of match.contents.
429 match.contents = display_string;
430 const URLPrefix* best_prefix =
431 URLPrefix::BestURLPrefix(UTF8ToUTF16(destination_url.spec()), text);
432 // It's possible for match.destination_url to not contain the user's input
433 // at all (so |best_prefix| is NULL), for example if the input is
434 // "view-source:x" and |destination_url| has an inserted "http://" in the
436 if (best_prefix == NULL) {
437 AutocompleteMatch::ClassifyMatchInString(text, match.contents,
438 ACMatchClassification::URL,
439 &match.contents_class);
441 AutocompleteMatch::ClassifyLocationInString(
442 best_prefix->prefix.length() - offset, text.length(),
443 match.contents.length(), ACMatchClassification::URL,
444 &match.contents_class);
447 match.is_history_what_you_typed_match = true;
453 // Called on the history thread.
454 void HistoryURLProvider::ExecuteWithDB(history::HistoryBackend* backend,
455 history::URLDatabase* db,
456 HistoryURLProviderParams* params) {
457 // We may get called with a NULL database if it couldn't be properly
460 params->failed = true;
461 } else if (!params->cancel_flag.IsSet()) {
462 base::TimeTicks beginning_time = base::TimeTicks::Now();
464 DoAutocomplete(backend, db, params);
466 UMA_HISTOGRAM_TIMES("Autocomplete.HistoryAsyncQueryTime",
467 base::TimeTicks::Now() - beginning_time);
470 // Return the results (if any) to the main thread.
471 params->message_loop->PostTask(FROM_HERE, base::Bind(
472 &HistoryURLProvider::QueryComplete, this, params));
475 // Used by both autocomplete passes, and therefore called on multiple different
476 // threads (though not simultaneously).
477 void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend,
478 history::URLDatabase* db,
479 HistoryURLProviderParams* params) {
480 VisitClassifier classifier(this, params->input, db);
481 // Create a What You Typed match, which we'll need below.
483 // We display this to the user when there's a reasonable chance they actually
485 // * Their input can be opened as a URL, and
486 // * We parsed the input as a URL, or it starts with an explicit "http:" or
488 // that is when their input can be opened as a URL.
489 // Otherwise, this is just low-quality noise. In the cases where we've parsed
490 // as UNKNOWN, we'll still show an accidental search infobar if need be.
491 bool have_what_you_typed_match =
492 params->input.canonicalized_url().is_valid() &&
493 (params->input.type() != AutocompleteInput::QUERY) &&
494 ((params->input.type() != AutocompleteInput::UNKNOWN) ||
495 (classifier.type() == VisitClassifier::UNVISITED_INTRANET) ||
496 !params->trim_http ||
497 (AutocompleteInput::NumNonHostComponents(params->input.parts()) > 0));
498 AutocompleteMatch what_you_typed_match(SuggestExactInput(
499 params->input.text(), params->input.canonicalized_url(),
501 what_you_typed_match.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0);
503 // Get the matching URLs from the DB
504 history::URLRows url_matches;
505 history::HistoryMatches history_matches;
507 if (search_url_database_) {
508 const URLPrefixes& prefixes = URLPrefix::GetURLPrefixes();
509 for (URLPrefixes::const_iterator i(prefixes.begin()); i != prefixes.end();
511 if (params->cancel_flag.IsSet())
512 return; // Canceled in the middle of a query, give up.
513 // We only need kMaxMatches results in the end, but before we
514 // get there we need to promote lower-quality matches that are
515 // prefixes of higher-quality matches, and remove lower-quality
516 // redirects. So we ask for more results than we need, of every
517 // prefix type, in hopes this will give us far more than enough
518 // to work with. CullRedirects() will then reduce the list to
519 // the best kMaxMatches results.
520 db->AutocompleteForPrefix(
521 UTF16ToUTF8(i->prefix + params->input.text()),
525 for (history::URLRows::const_iterator j(url_matches.begin());
526 j != url_matches.end(); ++j) {
527 const URLPrefix* best_prefix =
528 URLPrefix::BestURLPrefix(UTF8ToUTF16(j->url().spec()), string16());
529 DCHECK(best_prefix != NULL);
530 history_matches.push_back(history::HistoryMatch(*j, i->prefix.length(),
531 i->num_components == 0,
532 i->num_components >= best_prefix->num_components));
537 // Create sorted list of suggestions.
538 CullPoorMatches(*params, &history_matches);
539 SortAndDedupMatches(&history_matches);
540 PromoteOrCreateShorterSuggestion(db, *params, have_what_you_typed_match,
541 what_you_typed_match, &history_matches);
543 // Try to promote a match as an exact/inline autocomplete match. This also
544 // moves it to the front of |history_matches|, so skip over it when
545 // converting the rest of the matches.
546 size_t first_match = 1;
547 size_t exact_suggestion = 0;
548 // Checking |is_history_what_you_typed_match| tells us whether
549 // SuggestExactInput() succeeded in constructing a valid match.
550 if (what_you_typed_match.is_history_what_you_typed_match &&
551 (!backend || !params->dont_suggest_exact_input) &&
552 FixupExactSuggestion(db, params->input, classifier, &what_you_typed_match,
554 // Got an exact match for the user's input. Treat it as the best match
555 // regardless of the input type.
556 exact_suggestion = 1;
557 params->matches.push_back(what_you_typed_match);
558 } else if (params->prevent_inline_autocomplete ||
559 history_matches.empty() ||
560 !PromoteMatchForInlineAutocomplete(history_matches.front(), params)) {
561 // Failed to promote any URLs for inline autocompletion. Use the What You
562 // Typed match, if we have it.
564 if (have_what_you_typed_match)
565 params->matches.push_back(what_you_typed_match);
568 // This is the end of the synchronous pass.
571 // If search_url_database_ is false, we shouldn't have scheduled a second
573 DCHECK(search_url_database_);
575 // Determine relevancy of highest scoring match, if any.
577 for (ACMatches::const_iterator it = params->matches.begin();
578 it != params->matches.end(); ++it) {
579 relevance = std::max(relevance, it->relevance);
582 if (cull_redirects_) {
583 // Remove redirects and trim list to size. We want to provide up to
584 // kMaxMatches results plus the What You Typed result, if it was added to
585 // |history_matches| above.
586 CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion);
588 // Simply trim the list to size.
589 if (history_matches.size() > kMaxMatches + exact_suggestion)
590 history_matches.resize(kMaxMatches + exact_suggestion);
593 // Convert the history matches to autocomplete matches.
594 for (size_t i = first_match; i < history_matches.size(); ++i) {
595 const history::HistoryMatch& match = history_matches[i];
596 DCHECK(!have_what_you_typed_match ||
597 (match.url_info.url() !=
598 GURL(params->matches.front().destination_url)));
599 // If we've assigned a score already, all later matches score one
600 // less than the previous match.
601 relevance = (relevance > 0) ? (relevance - 1) :
602 CalculateRelevance(NORMAL, history_matches.size() - 1 - i);
603 AutocompleteMatch ac_match = HistoryMatchToACMatch(*params, match,
605 params->matches.push_back(ac_match);
609 // Called on the main thread when the query is complete.
610 void HistoryURLProvider::QueryComplete(
611 HistoryURLProviderParams* params_gets_deleted) {
612 // Ensure |params_gets_deleted| gets deleted on exit.
613 scoped_ptr<HistoryURLProviderParams> params(params_gets_deleted);
615 // If the user hasn't already started another query, clear our member pointer
616 // so we can't write into deleted memory.
617 if (params_ == params_gets_deleted)
620 // Don't send responses for queries that have been canceled.
621 if (params->cancel_flag.IsSet())
622 return; // Already set done_ when we canceled, no need to set it again.
624 // Don't modify |matches_| if the query failed, since it might have a default
625 // match in it, whereas |params->matches| will be empty.
626 if (!params->failed) {
627 matches_.swap(params->matches);
628 UpdateStarredStateOfMatches();
632 listener_->OnProviderUpdate(true);
635 HistoryURLProvider::~HistoryURLProvider() {
636 // Note: This object can get leaked on shutdown if there are pending
637 // requests on the database (which hold a reference to us). Normally, these
638 // messages get flushed for each thread. We do a round trip from main, to
639 // history, back to main while holding a reference. If the main thread
640 // completes before the history thread, the message to delegate back to the
641 // main thread will not run and the reference will leak. Therefore, don't do
642 // anything on destruction.
645 int HistoryURLProvider::CalculateRelevance(MatchType match_type,
646 size_t match_number) const {
647 switch (match_type) {
648 case INLINE_AUTOCOMPLETE:
649 return kScoreForBestInlineableResult;
651 case UNVISITED_INTRANET:
652 return kScoreForUnvisitedIntranetResult;
655 return kScoreForWhatYouTypedResult;
658 return kBaseScoreForNonInlineableResult +
659 static_cast<int>(match_number);
663 void HistoryURLProvider::RunAutocompletePasses(
664 const AutocompleteInput& input,
665 bool fixup_input_and_run_pass_1) {
668 if ((input.type() == AutocompleteInput::INVALID) ||
669 (input.type() == AutocompleteInput::FORCED_QUERY))
672 // Create a match for exactly what the user typed. This will only be used as
673 // a fallback in case we can't get the history service or URL DB; otherwise,
674 // we'll run this again in DoAutocomplete() and use that result instead.
675 const bool trim_http = !AutocompleteInput::HasHTTPScheme(input.text());
676 // Don't do this for queries -- while we can sometimes mark up a match for
677 // this, it's not what the user wants, and just adds noise.
678 if ((input.type() != AutocompleteInput::QUERY) &&
679 input.canonicalized_url().is_valid()) {
680 AutocompleteMatch what_you_typed(SuggestExactInput(
681 input.text(), input.canonicalized_url(), trim_http));
682 what_you_typed.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0);
683 matches_.push_back(what_you_typed);
686 // We'll need the history service to run both passes, so try to obtain it.
689 HistoryService* const history_service =
690 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
691 if (!history_service)
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_);
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
706 scoped_ptr<HistoryURLProviderParams> params(
707 new HistoryURLProviderParams(
709 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages),
710 default_search_provider, data));
712 params->prevent_inline_autocomplete =
713 PreventInlineAutocomplete(input);
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(¶ms->input))
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
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.
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.
736 matches_.swap(params->matches);
737 UpdateStarredStateOfMatches();
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)) {
746 params_ = params.release(); // This object will be destroyed in
747 // QueryComplete() once we're done with it.
748 history_service->ScheduleAutocomplete(this, params_);
752 bool 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);
761 MatchType type = INLINE_AUTOCOMPLETE;
762 switch (classifier.type()) {
763 case VisitClassifier::INVALID:
765 case VisitClassifier::UNVISITED_INTRANET:
766 type = UNVISITED_INTRANET;
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(
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;
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))) {
817 match->relevance = CalculateRelevance(type, 0);
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-
824 if (type == UNVISITED_INTRANET && !matches->empty())
827 // Put it on the front of the HistoryMatches for redirect culling.
828 CreateOrPromoteMatch(classifier.url_row(), string16::npos, false, matches,
833 bool 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())
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(
849 net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
850 net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
851 return registry_length == 0 && db->IsTypedHost(host);
854 bool 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())))
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.
877 params->dont_suggest_exact_input = true;
878 params->matches.push_back(HistoryMatchToACMatch(*params, match,
879 INLINE_AUTOCOMPLETE, CalculateRelevance(INLINE_AUTOCOMPLETE, 0)));
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.
890 void 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.
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);
925 if (search_base == match.url_info.url())
926 return; // Couldn't shorten |match|, so no range of URLs to search over.
928 // Search the DB for short URLs between our base and |match|.
929 history::URLRow info(search_base);
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.
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;
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;
962 void 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()))) {
974 i = matches->erase(i);
979 void 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.
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);
1000 // Advance to next item.
1005 if (matches->size() > max_results)
1006 matches->resize(max_results);
1009 size_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
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 "
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)
1039 AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch(
1040 const HistoryURLProviderParams& params,
1041 const history::HistoryMatch& history_match,
1042 MatchType match_type,
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);
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()));
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);
1085 AutocompleteMatch::ClassifyLocationInString(string16::npos, 0,
1086 match.contents.length(), ACMatchClassification::URL,
1087 &match.contents_class);
1089 match.description = info.title();
1090 AutocompleteMatch::ClassifyMatchInString(params.input.text(),
1092 ACMatchClassification::NONE,
1093 &match.description_class);
1094 RecordAdditionalInfoFromUrlRow(info, &match);