history_url_provider.cc revision f2477e01787aa58f445919b809d89e252beef54f
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/history/in_memory_url_index_types.h" 25#include "chrome/browser/history/scored_history_match.h" 26#include "chrome/browser/omnibox/omnibox_field_trial.h" 27#include "chrome/browser/profiles/profile.h" 28#include "chrome/browser/search_engines/template_url_service.h" 29#include "chrome/browser/search_engines/template_url_service_factory.h" 30#include "chrome/common/chrome_switches.h" 31#include "chrome/common/net/url_fixer_upper.h" 32#include "chrome/common/pref_names.h" 33#include "chrome/common/url_constants.h" 34#include "net/base/net_util.h" 35#include "net/base/registry_controlled_domains/registry_controlled_domain.h" 36#include "url/gurl.h" 37#include "url/url_parse.h" 38#include "url/url_util.h" 39 40namespace { 41 42// If |create_if_necessary| is true, ensures that |matches| contains an 43// entry for |info|, creating a new such entry if necessary (using 44// |input_location| and |match_in_scheme|). 45// 46// If |promote| is true, this also ensures the entry is the first element in 47// |matches|, moving or adding it to the front as appropriate. When |promote| 48// is false, existing matches are left in place, and newly added matches are 49// placed at the back. 50// 51// It's OK to call this function with both |create_if_necessary| and 52// |promote| false, in which case we'll do nothing. 53// 54// Returns whether the match exists regardless if it was promoted/created. 55bool CreateOrPromoteMatch(const history::URLRow& info, 56 size_t input_location, 57 bool match_in_scheme, 58 history::HistoryMatches* matches, 59 bool create_if_necessary, 60 bool promote) { 61 // |matches| may already have an entry for this. 62 for (history::HistoryMatches::iterator i(matches->begin()); 63 i != matches->end(); ++i) { 64 if (i->url_info.url() == info.url()) { 65 // Rotate it to the front if the caller wishes. 66 if (promote) 67 std::rotate(matches->begin(), i, i + 1); 68 return true; 69 } 70 } 71 72 if (!create_if_necessary) 73 return false; 74 75 // No entry, so create one. 76 history::HistoryMatch match(info, input_location, match_in_scheme, true); 77 if (promote) 78 matches->push_front(match); 79 else 80 matches->push_back(match); 81 82 return true; 83} 84 85// Given the user's |input| and a |match| created from it, reduce the match's 86// URL to just a host. If this host still matches the user input, return it. 87// Returns the empty string on failure. 88GURL ConvertToHostOnly(const history::HistoryMatch& match, 89 const string16& input) { 90 // See if we should try to do host-only suggestions for this URL. Nonstandard 91 // schemes means there's no authority section, so suggesting the host name 92 // is useless. File URLs are standard, but host suggestion is not useful for 93 // them either. 94 const GURL& url = match.url_info.url(); 95 if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile()) 96 return GURL(); 97 98 // Transform to a host-only match. Bail if the host no longer matches the 99 // user input (e.g. because the user typed more than just a host). 100 GURL host = url.GetWithEmptyPath(); 101 if ((host.spec().length() < (match.input_location + input.length()))) 102 return GURL(); // User typing is longer than this host suggestion. 103 104 const string16 spec = UTF8ToUTF16(host.spec()); 105 if (spec.compare(match.input_location, input.length(), input)) 106 return GURL(); // User typing is no longer a prefix. 107 108 return host; 109} 110 111// Acts like the > operator for URLInfo classes. 112bool CompareHistoryMatch(const history::HistoryMatch& a, 113 const history::HistoryMatch& b) { 114 // A promoted match is better than non-promoted. 115 if (a.promoted != b.promoted) 116 return a.promoted; 117 118 // A URL that has been typed at all is better than one that has never been 119 // typed. (Note "!"s on each side) 120 if (!a.url_info.typed_count() != !b.url_info.typed_count()) 121 return a.url_info.typed_count() > b.url_info.typed_count(); 122 123 // Innermost matches (matches after any scheme or "www.") are better than 124 // non-innermost matches. 125 if (a.innermost_match != b.innermost_match) 126 return a.innermost_match; 127 128 // URLs that have been typed more often are better. 129 if (a.url_info.typed_count() != b.url_info.typed_count()) 130 return a.url_info.typed_count() > b.url_info.typed_count(); 131 132 // For URLs that have each been typed once, a host (alone) is better than a 133 // page inside. 134 if ((a.url_info.typed_count() == 1) && (a.IsHostOnly() != b.IsHostOnly())) 135 return a.IsHostOnly(); 136 137 // URLs that have been visited more often are better. 138 if (a.url_info.visit_count() != b.url_info.visit_count()) 139 return a.url_info.visit_count() > b.url_info.visit_count(); 140 141 // URLs that have been visited more recently are better. 142 return a.url_info.last_visit() > b.url_info.last_visit(); 143} 144 145// Sorts and dedups the given list of matches. 146void SortAndDedupMatches(history::HistoryMatches* matches) { 147 // Sort by quality, best first. 148 std::sort(matches->begin(), matches->end(), &CompareHistoryMatch); 149 150 // Remove duplicate matches (caused by the search string appearing in one of 151 // the prefixes as well as after it). Consider the following scenario: 152 // 153 // User has visited "http://http.com" once and "http://htaccess.com" twice. 154 // User types "http". The autocomplete search with prefix "http://" returns 155 // the first host, while the search with prefix "" returns both hosts. Now 156 // we sort them into rank order: 157 // http://http.com (innermost_match) 158 // http://htaccess.com (!innermost_match, url_info.visit_count == 2) 159 // http://http.com (!innermost_match, url_info.visit_count == 1) 160 // 161 // The above scenario tells us we can't use std::unique(), since our 162 // duplicates are not always sequential. It also tells us we should remove 163 // the lower-quality duplicate(s), since otherwise the returned results won't 164 // be ordered correctly. This is easy to do: we just always remove the later 165 // element of a duplicate pair. 166 // Be careful! Because the vector contents may change as we remove elements, 167 // we use an index instead of an iterator in the outer loop, and don't 168 // precalculate the ending position. 169 for (size_t i = 0; i < matches->size(); ++i) { 170 for (history::HistoryMatches::iterator j(matches->begin() + i + 1); 171 j != matches->end(); ) { 172 if ((*matches)[i].url_info.url() == j->url_info.url()) 173 j = matches->erase(j); 174 else 175 ++j; 176 } 177 } 178} 179 180// Extracts typed_count, visit_count, and last_visited time from the 181// URLRow and puts them in the additional info field of the |match| 182// for display in about:omnibox. 183void RecordAdditionalInfoFromUrlRow(const history::URLRow& info, 184 AutocompleteMatch* match) { 185 match->RecordAdditionalInfo("typed count", info.typed_count()); 186 match->RecordAdditionalInfo("visit count", info.visit_count()); 187 match->RecordAdditionalInfo("last visit", info.last_visit()); 188} 189 190} // namespace 191 192// ----------------------------------------------------------------- 193// SearchTermsDataSnapshot 194 195// Implementation of SearchTermsData that takes a snapshot of another 196// SearchTermsData by copying all the responses to the different getters into 197// member strings, then returning those strings when its own getters are called. 198// This will typically be constructed on the UI thread from 199// UIThreadSearchTermsData but is subsequently safe to use on any thread. 200class SearchTermsDataSnapshot : public SearchTermsData { 201 public: 202 explicit SearchTermsDataSnapshot(const SearchTermsData& search_terms_data); 203 virtual ~SearchTermsDataSnapshot(); 204 205 virtual std::string GoogleBaseURLValue() const OVERRIDE; 206 virtual std::string GetApplicationLocale() const OVERRIDE; 207 virtual string16 GetRlzParameterValue() const OVERRIDE; 208 virtual std::string GetSearchClient() const OVERRIDE; 209 virtual std::string ForceInstantResultsParam( 210 bool for_prerender) const OVERRIDE; 211 virtual std::string InstantExtendedEnabledParam() const OVERRIDE; 212 virtual std::string NTPIsThemedParam() const OVERRIDE; 213 214 private: 215 std::string google_base_url_value_; 216 std::string application_locale_; 217 string16 rlz_parameter_value_; 218 std::string search_client_; 219 std::string force_instant_results_param_; 220 std::string instant_extended_enabled_param_; 221 std::string ntp_is_themed_param_; 222 223 DISALLOW_COPY_AND_ASSIGN(SearchTermsDataSnapshot); 224}; 225 226SearchTermsDataSnapshot::SearchTermsDataSnapshot( 227 const SearchTermsData& search_terms_data) 228 : google_base_url_value_(search_terms_data.GoogleBaseURLValue()), 229 application_locale_(search_terms_data.GetApplicationLocale()), 230 rlz_parameter_value_(search_terms_data.GetRlzParameterValue()), 231 search_client_(search_terms_data.GetSearchClient()), 232 force_instant_results_param_( 233 search_terms_data.ForceInstantResultsParam(false)), 234 instant_extended_enabled_param_( 235 search_terms_data.InstantExtendedEnabledParam()), 236 ntp_is_themed_param_(search_terms_data.NTPIsThemedParam()) {} 237 238SearchTermsDataSnapshot::~SearchTermsDataSnapshot() { 239} 240 241std::string SearchTermsDataSnapshot::GoogleBaseURLValue() const { 242 return google_base_url_value_; 243} 244 245std::string SearchTermsDataSnapshot::GetApplicationLocale() const { 246 return application_locale_; 247} 248 249string16 SearchTermsDataSnapshot::GetRlzParameterValue() const { 250 return rlz_parameter_value_; 251} 252 253std::string SearchTermsDataSnapshot::GetSearchClient() const { 254 return search_client_; 255} 256 257std::string SearchTermsDataSnapshot::ForceInstantResultsParam( 258 bool for_prerender) const { 259 return force_instant_results_param_; 260} 261 262std::string SearchTermsDataSnapshot::InstantExtendedEnabledParam() const { 263 return instant_extended_enabled_param_; 264} 265 266std::string SearchTermsDataSnapshot::NTPIsThemedParam() const { 267 return ntp_is_themed_param_; 268} 269 270// ----------------------------------------------------------------- 271// HistoryURLProvider 272 273// These ugly magic numbers will go away once we switch all scoring 274// behavior (including URL-what-you-typed) to HistoryQuick provider. 275const int HistoryURLProvider::kScoreForBestInlineableResult = 1413; 276const int HistoryURLProvider::kScoreForUnvisitedIntranetResult = 1403; 277const int HistoryURLProvider::kScoreForWhatYouTypedResult = 1203; 278const int HistoryURLProvider::kBaseScoreForNonInlineableResult = 900; 279 280// VisitClassifier is used to classify the type of visit to a particular url. 281class HistoryURLProvider::VisitClassifier { 282 public: 283 enum Type { 284 INVALID, // Navigations to the URL are not allowed. 285 UNVISITED_INTRANET, // A navigable URL for which we have no visit data but 286 // which is known to refer to a visited intranet host. 287 VISITED, // The site has been previously visited. 288 }; 289 290 VisitClassifier(HistoryURLProvider* provider, 291 const AutocompleteInput& input, 292 history::URLDatabase* db); 293 294 // Returns the type of visit for the specified input. 295 Type type() const { return type_; } 296 297 // Returns the URLRow for the visit. 298 const history::URLRow& url_row() const { return url_row_; } 299 300 private: 301 HistoryURLProvider* provider_; 302 history::URLDatabase* db_; 303 Type type_; 304 history::URLRow url_row_; 305 306 DISALLOW_COPY_AND_ASSIGN(VisitClassifier); 307}; 308 309HistoryURLProvider::VisitClassifier::VisitClassifier( 310 HistoryURLProvider* provider, 311 const AutocompleteInput& input, 312 history::URLDatabase* db) 313 : provider_(provider), 314 db_(db), 315 type_(INVALID) { 316 const GURL& url = input.canonicalized_url(); 317 // Detect email addresses. These cases will look like "http://user@site/", 318 // and because the history backend strips auth creds, we'll get a bogus exact 319 // match below if the user has visited "site". 320 if (!url.is_valid() || 321 ((input.type() == AutocompleteInput::UNKNOWN) && 322 input.parts().username.is_nonempty() && 323 !input.parts().password.is_nonempty() && 324 !input.parts().path.is_nonempty())) 325 return; 326 327 if (db_->GetRowForURL(url, &url_row_)) { 328 type_ = VISITED; 329 return; 330 } 331 332 if (provider_->CanFindIntranetURL(db_, input)) { 333 // The user typed an intranet hostname that they've visited (albeit with a 334 // different port and/or path) before. 335 url_row_ = history::URLRow(url); 336 type_ = UNVISITED_INTRANET; 337 } 338} 339 340HistoryURLProviderParams::HistoryURLProviderParams( 341 const AutocompleteInput& input, 342 bool trim_http, 343 const std::string& languages, 344 TemplateURL* default_search_provider, 345 const SearchTermsData& search_terms_data) 346 : message_loop(base::MessageLoop::current()), 347 input(input), 348 prevent_inline_autocomplete(input.prevent_inline_autocomplete()), 349 trim_http(trim_http), 350 failed(false), 351 languages(languages), 352 dont_suggest_exact_input(false), 353 default_search_provider(default_search_provider ? 354 new TemplateURL(default_search_provider->profile(), 355 default_search_provider->data()) : NULL), 356 search_terms_data(new SearchTermsDataSnapshot(search_terms_data)) { 357} 358 359HistoryURLProviderParams::~HistoryURLProviderParams() { 360} 361 362HistoryURLProvider::HistoryURLProvider(AutocompleteProviderListener* listener, 363 Profile* profile) 364 : HistoryProvider(listener, profile, 365 AutocompleteProvider::TYPE_HISTORY_URL), 366 params_(NULL), 367 cull_redirects_( 368 !OmniboxFieldTrial::InHUPCullRedirectsFieldTrial() || 369 !OmniboxFieldTrial::InHUPCullRedirectsFieldTrialExperimentGroup()), 370 create_shorter_match_( 371 !OmniboxFieldTrial::InHUPCreateShorterMatchFieldTrial() || 372 !OmniboxFieldTrial:: 373 InHUPCreateShorterMatchFieldTrialExperimentGroup()), 374 search_url_database_(true) { 375} 376 377void HistoryURLProvider::Start(const AutocompleteInput& input, 378 bool minimal_changes) { 379 // NOTE: We could try hard to do less work in the |minimal_changes| case 380 // here; some clever caching would let us reuse the raw matches from the 381 // history DB without re-querying. However, we'd still have to go back to 382 // the history thread to mark these up properly, and if pass 2 is currently 383 // running, we'd need to wait for it to return to the main thread before 384 // doing this (we can't just write new data for it to read due to thread 385 // safety issues). At that point it's just as fast, and easier, to simply 386 // re-run the query from scratch and ignore |minimal_changes|. 387 388 // Cancel any in-progress query. 389 Stop(false); 390 391 RunAutocompletePasses(input, true); 392} 393 394void HistoryURLProvider::Stop(bool clear_cached_results) { 395 done_ = true; 396 397 if (params_) 398 params_->cancel_flag.Set(); 399} 400 401AutocompleteMatch HistoryURLProvider::SuggestExactInput( 402 const string16& text, 403 const GURL& destination_url, 404 bool trim_http) { 405 AutocompleteMatch match(this, 0, false, 406 AutocompleteMatchType::URL_WHAT_YOU_TYPED); 407 408 if (destination_url.is_valid()) { 409 match.destination_url = destination_url; 410 411 // Trim off "http://" if the user didn't type it. 412 // NOTE: We use TrimHttpPrefix() here rather than StringForURLDisplay() to 413 // strip the scheme as we need to know the offset so we can adjust the 414 // |match_location| below. StringForURLDisplay() and TrimHttpPrefix() have 415 // slightly different behavior as well (the latter will strip even without 416 // two slashes after the scheme). 417 DCHECK(!trim_http || !AutocompleteInput::HasHTTPScheme(text)); 418 string16 display_string(StringForURLDisplay(destination_url, false, false)); 419 const size_t offset = trim_http ? TrimHttpPrefix(&display_string) : 0; 420 match.fill_into_edit = 421 AutocompleteInput::FormattedStringWithEquivalentMeaning(destination_url, 422 display_string); 423 match.allowed_to_be_default_match = true; 424 // NOTE: Don't set match.inline_autocompletion to something non-empty here; 425 // it's surprising and annoying. 426 427 // Try to highlight "innermost" match location. If we fix up "w" into 428 // "www.w.com", we want to highlight the fifth character, not the first. 429 // This relies on match.destination_url being the non-prefix-trimmed version 430 // of match.contents. 431 match.contents = display_string; 432 const URLPrefix* best_prefix = 433 URLPrefix::BestURLPrefix(UTF8ToUTF16(destination_url.spec()), text); 434 // It's possible for match.destination_url to not contain the user's input 435 // at all (so |best_prefix| is NULL), for example if the input is 436 // "view-source:x" and |destination_url| has an inserted "http://" in the 437 // middle. 438 if (best_prefix == NULL) { 439 AutocompleteMatch::ClassifyMatchInString(text, match.contents, 440 ACMatchClassification::URL, 441 &match.contents_class); 442 } else { 443 AutocompleteMatch::ClassifyLocationInString( 444 best_prefix->prefix.length() - offset, text.length(), 445 match.contents.length(), ACMatchClassification::URL, 446 &match.contents_class); 447 } 448 449 match.is_history_what_you_typed_match = true; 450 } 451 452 return match; 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(SuggestExactInput( 501 params->input.text(), params->input.canonicalized_url(), 502 params->trim_http)); 503 what_you_typed_match.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0); 504 505 // Get the matching URLs from the DB 506 history::URLRows url_matches; 507 history::HistoryMatches history_matches; 508 509 if (search_url_database_) { 510 const URLPrefixes& prefixes = URLPrefix::GetURLPrefixes(); 511 for (URLPrefixes::const_iterator i(prefixes.begin()); i != prefixes.end(); 512 ++i) { 513 if (params->cancel_flag.IsSet()) 514 return; // Canceled in the middle of a query, give up. 515 // We only need kMaxMatches results in the end, but before we 516 // get there we need to promote lower-quality matches that are 517 // prefixes of higher-quality matches, and remove lower-quality 518 // redirects. So we ask for more results than we need, of every 519 // prefix type, in hopes this will give us far more than enough 520 // to work with. CullRedirects() will then reduce the list to 521 // the best kMaxMatches results. 522 db->AutocompleteForPrefix( 523 UTF16ToUTF8(i->prefix + params->input.text()), 524 kMaxMatches * 2, 525 (backend == NULL), 526 &url_matches); 527 for (history::URLRows::const_iterator j(url_matches.begin()); 528 j != url_matches.end(); ++j) { 529 const URLPrefix* best_prefix = 530 URLPrefix::BestURLPrefix(UTF8ToUTF16(j->url().spec()), string16()); 531 DCHECK(best_prefix != NULL); 532 history_matches.push_back(history::HistoryMatch(*j, i->prefix.length(), 533 i->num_components == 0, 534 i->num_components >= best_prefix->num_components)); 535 } 536 } 537 } 538 539 // Create sorted list of suggestions. 540 CullPoorMatches(*params, &history_matches); 541 SortAndDedupMatches(&history_matches); 542 PromoteOrCreateShorterSuggestion(db, *params, have_what_you_typed_match, 543 what_you_typed_match, &history_matches); 544 545 // Try to promote a match as an exact/inline autocomplete match. This also 546 // moves it to the front of |history_matches|, so skip over it when 547 // converting the rest of the matches. 548 size_t first_match = 1; 549 size_t exact_suggestion = 0; 550 // Checking |is_history_what_you_typed_match| tells us whether 551 // SuggestExactInput() succeeded in constructing a valid match. 552 if (what_you_typed_match.is_history_what_you_typed_match && 553 (!backend || !params->dont_suggest_exact_input) && 554 FixupExactSuggestion(db, params->input, classifier, &what_you_typed_match, 555 &history_matches)) { 556 // Got an exact match for the user's input. Treat it as the best match 557 // regardless of the input type. 558 exact_suggestion = 1; 559 params->matches.push_back(what_you_typed_match); 560 } else if (params->prevent_inline_autocomplete || 561 history_matches.empty() || 562 !PromoteMatchForInlineAutocomplete(history_matches.front(), params)) { 563 // Failed to promote any URLs for inline autocompletion. Use the What You 564 // Typed match, if we have it. 565 first_match = 0; 566 if (have_what_you_typed_match) 567 params->matches.push_back(what_you_typed_match); 568 } 569 570 // This is the end of the synchronous pass. 571 if (!backend) 572 return; 573 // If search_url_database_ is false, we shouldn't have scheduled a second 574 // pass. 575 DCHECK(search_url_database_); 576 577 // Determine relevancy of highest scoring match, if any. 578 int relevance = -1; 579 for (ACMatches::const_iterator it = params->matches.begin(); 580 it != params->matches.end(); ++it) { 581 relevance = std::max(relevance, it->relevance); 582 } 583 584 if (cull_redirects_) { 585 // Remove redirects and trim list to size. We want to provide up to 586 // kMaxMatches results plus the What You Typed result, if it was added to 587 // |history_matches| above. 588 CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion); 589 } else { 590 // Simply trim the list to size. 591 if (history_matches.size() > kMaxMatches + exact_suggestion) 592 history_matches.resize(kMaxMatches + exact_suggestion); 593 } 594 595 // Convert the history matches to autocomplete matches. 596 for (size_t i = first_match; i < history_matches.size(); ++i) { 597 const history::HistoryMatch& match = history_matches[i]; 598 DCHECK(!have_what_you_typed_match || 599 (match.url_info.url() != 600 GURL(params->matches.front().destination_url))); 601 // If we've assigned a score already, all later matches score one 602 // less than the previous match. 603 relevance = (relevance > 0) ? (relevance - 1) : 604 CalculateRelevance(NORMAL, history_matches.size() - 1 - i); 605 AutocompleteMatch ac_match = HistoryMatchToACMatch(*params, match, 606 NORMAL, relevance); 607 params->matches.push_back(ac_match); 608 } 609} 610 611// Called on the main thread when the query is complete. 612void HistoryURLProvider::QueryComplete( 613 HistoryURLProviderParams* params_gets_deleted) { 614 // Ensure |params_gets_deleted| gets deleted on exit. 615 scoped_ptr<HistoryURLProviderParams> params(params_gets_deleted); 616 617 // If the user hasn't already started another query, clear our member pointer 618 // so we can't write into deleted memory. 619 if (params_ == params_gets_deleted) 620 params_ = NULL; 621 622 // Don't send responses for queries that have been canceled. 623 if (params->cancel_flag.IsSet()) 624 return; // Already set done_ when we canceled, no need to set it again. 625 626 // Don't modify |matches_| if the query failed, since it might have a default 627 // match in it, whereas |params->matches| will be empty. 628 if (!params->failed) { 629 matches_.swap(params->matches); 630 UpdateStarredStateOfMatches(); 631 } 632 633 done_ = true; 634 listener_->OnProviderUpdate(true); 635} 636 637HistoryURLProvider::~HistoryURLProvider() { 638 // Note: This object can get leaked on shutdown if there are pending 639 // requests on the database (which hold a reference to us). Normally, these 640 // messages get flushed for each thread. We do a round trip from main, to 641 // history, back to main while holding a reference. If the main thread 642 // completes before the history thread, the message to delegate back to the 643 // main thread will not run and the reference will leak. Therefore, don't do 644 // anything on destruction. 645} 646 647int HistoryURLProvider::CalculateRelevance(MatchType match_type, 648 size_t match_number) const { 649 switch (match_type) { 650 case INLINE_AUTOCOMPLETE: 651 return kScoreForBestInlineableResult; 652 653 case UNVISITED_INTRANET: 654 return kScoreForUnvisitedIntranetResult; 655 656 case WHAT_YOU_TYPED: 657 return kScoreForWhatYouTypedResult; 658 659 default: // NORMAL 660 return kBaseScoreForNonInlineableResult + 661 static_cast<int>(match_number); 662 } 663} 664 665void HistoryURLProvider::RunAutocompletePasses( 666 const AutocompleteInput& input, 667 bool fixup_input_and_run_pass_1) { 668 matches_.clear(); 669 670 if ((input.type() == AutocompleteInput::INVALID) || 671 (input.type() == AutocompleteInput::FORCED_QUERY)) 672 return; 673 674 // Create a match for exactly what the user typed. This will only be used as 675 // a fallback in case we can't get the history service or URL DB; otherwise, 676 // we'll run this again in DoAutocomplete() and use that result instead. 677 const bool trim_http = !AutocompleteInput::HasHTTPScheme(input.text()); 678 // Don't do this for queries -- while we can sometimes mark up a match for 679 // this, it's not what the user wants, and just adds noise. 680 if ((input.type() != AutocompleteInput::QUERY) && 681 input.canonicalized_url().is_valid()) { 682 AutocompleteMatch what_you_typed(SuggestExactInput( 683 input.text(), input.canonicalized_url(), trim_http)); 684 what_you_typed.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0); 685 matches_.push_back(what_you_typed); 686 } 687 688 // We'll need the history service to run both passes, so try to obtain it. 689 if (!profile_) 690 return; 691 HistoryService* const history_service = 692 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS); 693 if (!history_service) 694 return; 695 696 // Get the default search provider and search terms data now since we have to 697 // retrieve these on the UI thread, and the second pass runs on the history 698 // thread. |template_url_service| can be NULL when testing. 699 TemplateURLService* template_url_service = 700 TemplateURLServiceFactory::GetForProfile(profile_); 701 TemplateURL* default_search_provider = template_url_service ? 702 template_url_service->GetDefaultSearchProvider() : NULL; 703 UIThreadSearchTermsData data(profile_); 704 705 // Create the data structure for the autocomplete passes. We'll save this off 706 // onto the |params_| member for later deletion below if we need to run pass 707 // 2. 708 scoped_ptr<HistoryURLProviderParams> params( 709 new HistoryURLProviderParams( 710 input, trim_http, 711 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages), 712 default_search_provider, data)); 713 714 params->prevent_inline_autocomplete = 715 PreventInlineAutocomplete(input); 716 717 if (fixup_input_and_run_pass_1) { 718 // Do some fixup on the user input before matching against it, so we provide 719 // good results for local file paths, input with spaces, etc. 720 if (!FixupUserInput(¶ms->input)) 721 return; 722 723 // Pass 1: Get the in-memory URL database, and use it to find and promote 724 // the inline autocomplete match, if any. 725 history::URLDatabase* url_db = history_service->InMemoryDatabase(); 726 // url_db can be NULL if it hasn't finished initializing (or failed to 727 // initialize). In this case all we can do is fall back on the second 728 // pass. 729 // 730 // TODO(pkasting): We should just block here until this loads. Any time 731 // someone unloads the history backend, we'll get inconsistent inline 732 // autocomplete behavior here. 733 if (url_db) { 734 DoAutocomplete(NULL, url_db, params.get()); 735 // params->matches now has the matches we should expose to the provider. 736 // Pass 2 expects a "clean slate" set of matches. 737 matches_.clear(); 738 matches_.swap(params->matches); 739 UpdateStarredStateOfMatches(); 740 } 741 } 742 743 // Pass 2: Ask the history service to call us back on the history thread, 744 // where we can read the full on-disk DB. 745 if (search_url_database_ && 746 (input.matches_requested() == AutocompleteInput::ALL_MATCHES)) { 747 done_ = false; 748 params_ = params.release(); // This object will be destroyed in 749 // QueryComplete() once we're done with it. 750 history_service->ScheduleAutocomplete(this, params_); 751 } 752} 753 754bool HistoryURLProvider::FixupExactSuggestion( 755 history::URLDatabase* db, 756 const AutocompleteInput& input, 757 const VisitClassifier& classifier, 758 AutocompleteMatch* match, 759 history::HistoryMatches* matches) const { 760 DCHECK(match != NULL); 761 DCHECK(matches != NULL); 762 763 MatchType type = INLINE_AUTOCOMPLETE; 764 switch (classifier.type()) { 765 case VisitClassifier::INVALID: 766 return false; 767 case VisitClassifier::UNVISITED_INTRANET: 768 type = UNVISITED_INTRANET; 769 break; 770 default: 771 DCHECK_EQ(VisitClassifier::VISITED, classifier.type()); 772 // We have data for this match, use it. 773 match->deletable = true; 774 match->description = classifier.url_row().title(); 775 RecordAdditionalInfoFromUrlRow(classifier.url_row(), match); 776 match->description_class = 777 ClassifyDescription(input.text(), match->description); 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 match.description_class = 1091 ClassifyDescription(params.input.text(), match.description); 1092 RecordAdditionalInfoFromUrlRow(info, &match); 1093 return match; 1094} 1095 1096// static 1097ACMatchClassifications HistoryURLProvider::ClassifyDescription( 1098 const string16& input_text, 1099 const string16& description) { 1100 string16 clean_description = history::CleanUpTitleForMatching(description); 1101 history::TermMatches description_matches(SortAndDeoverlapMatches( 1102 history::MatchTermInString(input_text, clean_description, 0))); 1103 history::WordStarts description_word_starts; 1104 history::String16VectorFromString16( 1105 clean_description, false, &description_word_starts); 1106 description_matches = 1107 history::ScoredHistoryMatch::FilterTermMatchesByWordStarts( 1108 description_matches, description_word_starts, 0); 1109 return SpansFromTermMatch( 1110 description_matches, clean_description.length(), false); 1111} 1112