history_url_provider.cc revision dc0f95d653279beabeb9817299e2902918ba123e
1// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "chrome/browser/autocomplete/history_url_provider.h" 6 7#include <algorithm> 8 9#include "base/basictypes.h" 10#include "base/message_loop.h" 11#include "base/metrics/histogram.h" 12#include "base/string_util.h" 13#include "base/utf_string_conversions.h" 14#include "chrome/browser/autocomplete/autocomplete_match.h" 15#include "chrome/browser/history/history.h" 16#include "chrome/browser/history/history_backend.h" 17#include "chrome/browser/history/history_database.h" 18#include "chrome/browser/history/history_types.h" 19#include "chrome/browser/net/url_fixer_upper.h" 20#include "chrome/browser/prefs/pref_service.h" 21#include "chrome/browser/profiles/profile.h" 22#include "chrome/common/pref_names.h" 23#include "chrome/common/url_constants.h" 24#include "googleurl/src/gurl.h" 25#include "googleurl/src/url_parse.h" 26#include "googleurl/src/url_util.h" 27#include "net/base/net_util.h" 28 29using base::Time; 30using base::TimeDelta; 31using base::TimeTicks; 32using history::Prefix; 33using history::Prefixes; 34using history::HistoryMatch; 35using history::HistoryMatches; 36 37namespace history { 38 39// Returns true if |url| is just a host (e.g. "http://www.google.com/") and 40// not some other subpage (e.g. "http://www.google.com/foo.html"). 41bool IsHostOnly(const GURL& url) { 42 DCHECK(url.is_valid()); 43 return (!url.has_path() || (url.path() == "/")) && !url.has_query() && 44 !url.has_ref(); 45} 46 47// Acts like the > operator for URLInfo classes. 48bool CompareHistoryMatch(const HistoryMatch& a, const HistoryMatch& b) { 49 // A URL that has been typed at all is better than one that has never been 50 // typed. (Note "!"s on each side) 51 if (!a.url_info.typed_count() != !b.url_info.typed_count()) 52 return a.url_info.typed_count() > b.url_info.typed_count(); 53 54 // Innermost matches (matches after any scheme or "www.") are better than 55 // non-innermost matches. 56 if (a.innermost_match != b.innermost_match) 57 return a.innermost_match; 58 59 // URLs that have been typed more often are better. 60 if (a.url_info.typed_count() != b.url_info.typed_count()) 61 return a.url_info.typed_count() > b.url_info.typed_count(); 62 63 // For URLs that have each been typed once, a host (alone) is better than a 64 // page inside. 65 if (a.url_info.typed_count() == 1) { 66 const bool a_is_host_only = history::IsHostOnly(a.url_info.url()); 67 if (a_is_host_only != history::IsHostOnly(b.url_info.url())) 68 return a_is_host_only; 69 } 70 71 // URLs that have been visited more often are better. 72 if (a.url_info.visit_count() != b.url_info.visit_count()) 73 return a.url_info.visit_count() > b.url_info.visit_count(); 74 75 // URLs that have been visited more recently are better. 76 return a.url_info.last_visit() > b.url_info.last_visit(); 77} 78 79// Given the user's |input| and a |match| created from it, reduce the 80// match's URL to just a host. If this host still matches the user input, 81// return it. Returns the empty string on failure. 82GURL ConvertToHostOnly(const HistoryMatch& match, const string16& input) { 83 // See if we should try to do host-only suggestions for this URL. Nonstandard 84 // schemes means there's no authority section, so suggesting the host name 85 // is useless. File URLs are standard, but host suggestion is not useful for 86 // them either. 87 const GURL& url = match.url_info.url(); 88 if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile()) 89 return GURL(); 90 91 // Transform to a host-only match. Bail if the host no longer matches the 92 // user input (e.g. because the user typed more than just a host). 93 GURL host = url.GetWithEmptyPath(); 94 if ((host.spec().length() < (match.input_location + input.length()))) 95 return GURL(); // User typing is longer than this host suggestion. 96 97 const string16 spec = UTF8ToUTF16(host.spec()); 98 if (spec.compare(match.input_location, input.length(), input)) 99 return GURL(); // User typing is no longer a prefix. 100 101 return host; 102} 103 104} // namespace history 105 106HistoryURLProviderParams::HistoryURLProviderParams( 107 const AutocompleteInput& input, 108 bool trim_http, 109 const std::string& languages) 110 : message_loop(MessageLoop::current()), 111 input(input), 112 trim_http(trim_http), 113 cancel(false), 114 failed(false), 115 languages(languages) { 116} 117 118HistoryURLProviderParams::~HistoryURLProviderParams() {} 119 120HistoryURLProvider::HistoryURLProvider(ACProviderListener* listener, 121 Profile* profile) 122 : HistoryProvider(listener, profile, "HistoryURL"), 123 prefixes_(GetPrefixes()), 124 params_(NULL) { 125} 126 127void HistoryURLProvider::Start(const AutocompleteInput& input, 128 bool minimal_changes) { 129 // NOTE: We could try hard to do less work in the |minimal_changes| case 130 // here; some clever caching would let us reuse the raw matches from the 131 // history DB without re-querying. However, we'd still have to go back to 132 // the history thread to mark these up properly, and if pass 2 is currently 133 // running, we'd need to wait for it to return to the main thread before 134 // doing this (we can't just write new data for it to read due to thread 135 // safety issues). At that point it's just as fast, and easier, to simply 136 // re-run the query from scratch and ignore |minimal_changes|. 137 138 // Cancel any in-progress query. 139 Stop(); 140 141 RunAutocompletePasses(input, true); 142} 143 144void HistoryURLProvider::Stop() { 145 done_ = true; 146 147 if (params_) 148 params_->cancel = true; 149} 150 151// Called on the history thread. 152void HistoryURLProvider::ExecuteWithDB(history::HistoryBackend* backend, 153 history::URLDatabase* db, 154 HistoryURLProviderParams* params) { 155 // We may get called with a NULL database if it couldn't be properly 156 // initialized. 157 if (!db) { 158 params->failed = true; 159 } else if (!params->cancel) { 160 TimeTicks beginning_time = TimeTicks::Now(); 161 162 DoAutocomplete(backend, db, params); 163 164 UMA_HISTOGRAM_TIMES("Autocomplete.HistoryAsyncQueryTime", 165 TimeTicks::Now() - beginning_time); 166 } 167 168 // Return the results (if any) to the main thread. 169 params->message_loop->PostTask(FROM_HERE, NewRunnableMethod( 170 this, &HistoryURLProvider::QueryComplete, params)); 171} 172 173// Used by both autocomplete passes, and therefore called on multiple different 174// threads (though not simultaneously). 175void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend, 176 history::URLDatabase* db, 177 HistoryURLProviderParams* params) { 178 // Create a What You Typed match, which we'll need below. 179 // 180 // We display this to the user when there's a reasonable chance they actually 181 // care: 182 // * Their input can be opened as a URL, and 183 // * They hit ctrl-enter, or we parsed the input as a URL, or it starts with 184 // an explicit "http:" or "https:". 185 // Otherwise, this is just low-quality noise. In the cases where we've parsed 186 // as UNKNOWN, we'll still show an accidental search infobar if need be. 187 bool have_what_you_typed_match = 188 params->input.canonicalized_url().is_valid() && 189 (params->input.type() != AutocompleteInput::QUERY) && 190 ((params->input.type() != AutocompleteInput::UNKNOWN) || 191 !params->trim_http || 192 url_util::FindAndCompareScheme(UTF16ToUTF8(params->input.text()), 193 chrome::kHttpsScheme, NULL)); 194 AutocompleteMatch what_you_typed_match(SuggestExactInput(params->input, 195 params->trim_http)); 196 197 // Get the matching URLs from the DB 198 typedef std::vector<history::URLRow> URLRowVector; 199 URLRowVector url_matches; 200 HistoryMatches history_matches; 201 202 for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end(); 203 ++i) { 204 if (params->cancel) 205 return; // Canceled in the middle of a query, give up. 206 // We only need kMaxMatches results in the end, but before we get there we 207 // need to promote lower-quality matches that are prefixes of 208 // higher-quality matches, and remove lower-quality redirects. So we ask 209 // for more results than we need, of every prefix type, in hopes this will 210 // give us far more than enough to work with. CullRedirects() will then 211 // reduce the list to the best kMaxMatches results. 212 db->AutocompleteForPrefix(i->prefix + params->input.text(), 213 kMaxMatches * 2, (backend == NULL), &url_matches); 214 for (URLRowVector::const_iterator j(url_matches.begin()); 215 j != url_matches.end(); ++j) { 216 const Prefix* best_prefix = BestPrefix(j->url(), string16()); 217 DCHECK(best_prefix != NULL); 218 history_matches.push_back(HistoryMatch(*j, i->prefix.length(), 219 !i->num_components, 220 i->num_components >= best_prefix->num_components)); 221 } 222 } 223 224 // Create sorted list of suggestions. 225 CullPoorMatches(&history_matches); 226 SortMatches(&history_matches); 227 PromoteOrCreateShorterSuggestion(db, *params, have_what_you_typed_match, 228 what_you_typed_match, &history_matches); 229 230 // Try to promote a match as an exact/inline autocomplete match. This also 231 // moves it to the front of |history_matches|, so skip over it when 232 // converting the rest of the matches. 233 size_t first_match = 1; 234 size_t exact_suggestion = 0; 235 // Checking |is_history_what_you_typed_match| tells us whether 236 // SuggestExactInput() succeeded in constructing a valid match. 237 if (what_you_typed_match.is_history_what_you_typed_match && 238 FixupExactSuggestion(db, params->input, &what_you_typed_match, 239 &history_matches)) { 240 // Got an exact match for the user's input. Treat it as the best match 241 // regardless of the input type. 242 exact_suggestion = 1; 243 params->matches.push_back(what_you_typed_match); 244 } else if (params->input.prevent_inline_autocomplete() || 245 history_matches.empty() || 246 !PromoteMatchForInlineAutocomplete(params, history_matches.front())) { 247 // Failed to promote any URLs for inline autocompletion. Use the What You 248 // Typed match, if we have it. 249 first_match = 0; 250 if (have_what_you_typed_match) 251 params->matches.push_back(what_you_typed_match); 252 } 253 254 // This is the end of the synchronous pass. 255 if (!backend) 256 return; 257 258 // Remove redirects and trim list to size. We want to provide up to 259 // kMaxMatches results plus the What You Typed result, if it was added to 260 // |history_matches| above. 261 CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion); 262 263 // Convert the history matches to autocomplete matches. 264 for (size_t i = first_match; i < history_matches.size(); ++i) { 265 const HistoryMatch& match = history_matches[i]; 266 DCHECK(!have_what_you_typed_match || 267 (match.url_info.url() != 268 GURL(params->matches.front().destination_url))); 269 params->matches.push_back(HistoryMatchToACMatch(params, match, NORMAL, 270 history_matches.size() - 1 - i)); 271 } 272} 273 274// Called on the main thread when the query is complete. 275void HistoryURLProvider::QueryComplete( 276 HistoryURLProviderParams* params_gets_deleted) { 277 // Ensure |params_gets_deleted| gets deleted on exit. 278 scoped_ptr<HistoryURLProviderParams> params(params_gets_deleted); 279 280 // If the user hasn't already started another query, clear our member pointer 281 // so we can't write into deleted memory. 282 if (params_ == params_gets_deleted) 283 params_ = NULL; 284 285 // Don't send responses for queries that have been canceled. 286 if (params->cancel) 287 return; // Already set done_ when we canceled, no need to set it again. 288 289 // Don't modify |matches_| if the query failed, since it might have a default 290 // match in it, whereas |params->matches| will be empty. 291 if (!params->failed) { 292 matches_.swap(params->matches); 293 UpdateStarredStateOfMatches(); 294 } 295 296 done_ = true; 297 listener_->OnProviderUpdate(true); 298} 299 300AutocompleteMatch HistoryURLProvider::SuggestExactInput( 301 const AutocompleteInput& input, 302 bool trim_http) { 303 AutocompleteMatch match(this, 304 CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), false, 305 AutocompleteMatch::URL_WHAT_YOU_TYPED); 306 307 const GURL& url = input.canonicalized_url(); 308 if (url.is_valid()) { 309 match.destination_url = url; 310 311 // Trim off "http://" if the user didn't type it. 312 // NOTE: We use TrimHttpPrefix() here rather than StringForURLDisplay() to 313 // strip the scheme as we need to know the offset so we can adjust the 314 // |match_location| below. StringForURLDisplay() and TrimHttpPrefix() have 315 // slightly different behavior as well (the latter will strip even without 316 // two slashes after the scheme). 317 string16 display_string(StringForURLDisplay(url, false, false)); 318 const size_t offset = trim_http ? TrimHttpPrefix(&display_string) : 0; 319 match.fill_into_edit = 320 AutocompleteInput::FormattedStringWithEquivalentMeaning(url, 321 display_string); 322 // NOTE: Don't set match.input_location (to allow inline autocompletion) 323 // here, it's surprising and annoying. 324 325 // Try to highlight "innermost" match location. If we fix up "w" into 326 // "www.w.com", we want to highlight the fifth character, not the first. 327 // This relies on match.destination_url being the non-prefix-trimmed version 328 // of match.contents. 329 match.contents = display_string; 330 const Prefix* best_prefix = BestPrefix(match.destination_url, input.text()); 331 // Because of the vagaries of GURL, it's possible for match.destination_url 332 // to not contain the user's input at all. In this case don't mark anything 333 // as a match. 334 const size_t match_location = (best_prefix == NULL) ? 335 string16::npos : best_prefix->prefix.length() - offset; 336 AutocompleteMatch::ClassifyLocationInString(match_location, 337 input.text().length(), 338 match.contents.length(), 339 ACMatchClassification::URL, 340 &match.contents_class); 341 342 match.is_history_what_you_typed_match = true; 343 } 344 345 return match; 346} 347 348bool HistoryURLProvider::FixupExactSuggestion(history::URLDatabase* db, 349 const AutocompleteInput& input, 350 AutocompleteMatch* match, 351 HistoryMatches* matches) const { 352 DCHECK(match != NULL); 353 DCHECK(matches != NULL); 354 355 // Tricky corner case: The user has visited intranet site "foo", but not 356 // internet site "www.foo.com". He types in foo (getting an exact match), 357 // then tries to hit ctrl-enter. When pressing ctrl, the what-you-typed 358 // match ("www.foo.com") doesn't show up in history, and thus doesn't get a 359 // promoted relevance, but a different match from the input ("foo") does, and 360 // gets promoted for inline autocomplete. Thus instead of getting 361 // "www.foo.com", the user still gets "foo" (and, before hitting enter, 362 // probably gets an odd-looking inline autocomplete of "/"). 363 // 364 // We detect this crazy case as follows: 365 // * If the what-you-typed match is not in the history DB, 366 // * and the user has specified a TLD, 367 // * and the input _without_ the TLD _is_ in the history DB, 368 // * ...then just before pressing "ctrl" the best match we supplied was the 369 // what-you-typed match, so stick with it by promoting this. 370 history::URLRow info; 371 MatchType type = INLINE_AUTOCOMPLETE; 372 if (!db->GetRowForURL(match->destination_url, &info)) { 373 if (input.desired_tld().empty()) 374 return false; 375 GURL destination_url(URLFixerUpper::FixupURL(UTF16ToUTF8(input.text()), 376 std::string())); 377 if (!db->GetRowForURL(destination_url, NULL)) 378 return false; 379 380 // If we got here, then we hit the tricky corner case. Make sure that 381 // |info| corresponds to the right URL. 382 info = history::URLRow(match->destination_url); 383 } else { 384 // We have data for this match, use it. 385 match->deletable = true; 386 match->description = info.title(); 387 AutocompleteMatch::ClassifyMatchInString(input.text(), 388 info.title(), 389 ACMatchClassification::NONE, &match->description_class); 390 if (!info.typed_count()) { 391 // If we reach here, we must be in the second pass, and we must not have 392 // promoted this match as an exact match during the first pass. That 393 // means it will have been outscored by the "search what you typed match". 394 // We need to maintain that ordering in order to not make the destination 395 // for the user's typing change depending on when they hit enter. So 396 // lower the score here enough to let the search provider continue to 397 // outscore this match. 398 type = WHAT_YOU_TYPED; 399 } 400 } 401 402 // Promote as an exact match. 403 match->relevance = CalculateRelevance(input.type(), type, 0); 404 405 // Put it on the front of the HistoryMatches for redirect culling. 406 EnsureMatchPresent(info, string16::npos, false, matches, true); 407 return true; 408} 409 410bool HistoryURLProvider::PromoteMatchForInlineAutocomplete( 411 HistoryURLProviderParams* params, 412 const HistoryMatch& match) { 413 // Promote the first match if it's been typed at least n times, where n == 1 414 // for "simple" (host-only) URLs and n == 2 for others. We set a higher bar 415 // for these long URLs because it's less likely that users will want to visit 416 // them again. Even though we don't increment the typed_count for pasted-in 417 // URLs, if the user manually edits the URL or types some long thing in by 418 // hand, we wouldn't want to immediately start autocompleting it. 419 if (!match.url_info.typed_count() || 420 ((match.url_info.typed_count() == 1) && 421 !history::IsHostOnly(match.url_info.url()))) 422 return false; 423 424 params->matches.push_back(HistoryMatchToACMatch(params, match, 425 INLINE_AUTOCOMPLETE, 0)); 426 return true; 427} 428 429HistoryURLProvider::~HistoryURLProvider() {} 430 431// static 432history::Prefixes HistoryURLProvider::GetPrefixes() { 433 // We'll complete text following these prefixes. 434 // NOTE: There's no requirement that these be in any particular order. 435 Prefixes prefixes; 436 prefixes.push_back(Prefix(ASCIIToUTF16("https://www."), 2)); 437 prefixes.push_back(Prefix(ASCIIToUTF16("http://www."), 2)); 438 prefixes.push_back(Prefix(ASCIIToUTF16("ftp://ftp."), 2)); 439 prefixes.push_back(Prefix(ASCIIToUTF16("ftp://www."), 2)); 440 prefixes.push_back(Prefix(ASCIIToUTF16("https://"), 1)); 441 prefixes.push_back(Prefix(ASCIIToUTF16("http://"), 1)); 442 prefixes.push_back(Prefix(ASCIIToUTF16("ftp://"), 1)); 443 // Empty string catches within-scheme matches as well. 444 prefixes.push_back(Prefix(string16(), 0)); 445 return prefixes; 446} 447 448// static 449int HistoryURLProvider::CalculateRelevance(AutocompleteInput::Type input_type, 450 MatchType match_type, 451 size_t match_number) { 452 switch (match_type) { 453 case INLINE_AUTOCOMPLETE: 454 return 1400; 455 456 case WHAT_YOU_TYPED: 457 return 1200; 458 459 default: 460 return 900 + static_cast<int>(match_number); 461 } 462} 463 464// static 465void HistoryURLProvider::PromoteOrCreateShorterSuggestion( 466 history::URLDatabase* db, 467 const HistoryURLProviderParams& params, 468 bool have_what_you_typed_match, 469 const AutocompleteMatch& what_you_typed_match, 470 HistoryMatches* matches) { 471 if (matches->empty()) 472 return; // No matches, nothing to do. 473 474 // Determine the base URL from which to search, and whether that URL could 475 // itself be added as a match. We can add the base iff it's not "effectively 476 // the same" as any "what you typed" match. 477 const HistoryMatch& match = matches->front(); 478 GURL search_base = history::ConvertToHostOnly(match, params.input.text()); 479 bool can_add_search_base_to_matches = !have_what_you_typed_match; 480 if (search_base.is_empty()) { 481 // Search from what the user typed when we couldn't reduce the best match 482 // to a host. Careful: use a substring of |match| here, rather than the 483 // first match in |params|, because they might have different prefixes. If 484 // the user typed "google.com", |what_you_typed_match| will hold 485 // "http://google.com/", but |match| might begin with 486 // "http://www.google.com/". 487 // TODO: this should be cleaned up, and is probably incorrect for IDN. 488 std::string new_match = match.url_info.url().possibly_invalid_spec(). 489 substr(0, match.input_location + params.input.text().length()); 490 search_base = GURL(new_match); 491 // TODO(mrossetti): There is a degenerate case where the following may 492 // cause a failure: http://www/~someword/fubar.html. Diagnose. 493 // See: http://crbug.com/50101 494 if (search_base.is_empty()) 495 return; // Can't construct a valid URL from which to start a search. 496 } else if (!can_add_search_base_to_matches) { 497 can_add_search_base_to_matches = 498 (search_base != what_you_typed_match.destination_url); 499 } 500 if (search_base == match.url_info.url()) 501 return; // Couldn't shorten |match|, so no range of URLs to search over. 502 503 // Search the DB for short URLs between our base and |match|. 504 history::URLRow info(search_base); 505 bool promote = true; 506 // A short URL is only worth suggesting if it's been visited at least a third 507 // as often as the longer URL. 508 const int min_visit_count = ((match.url_info.visit_count() - 1) / 3) + 1; 509 // For stability between the in-memory and on-disk autocomplete passes, when 510 // the long URL has been typed before, only suggest shorter URLs that have 511 // also been typed. Otherwise, the on-disk pass could suggest a shorter URL 512 // (which hasn't been typed) that the in-memory pass doesn't know about, 513 // thereby making the top match, and thus the behavior of inline 514 // autocomplete, unstable. 515 const int min_typed_count = match.url_info.typed_count() ? 1 : 0; 516 if (!db->FindShortestURLFromBase(search_base.possibly_invalid_spec(), 517 match.url_info.url().possibly_invalid_spec(), min_visit_count, 518 min_typed_count, can_add_search_base_to_matches, &info)) { 519 if (!can_add_search_base_to_matches) 520 return; // Couldn't find anything and can't add the search base, bail. 521 522 // Try to get info on the search base itself. Promote it to the top if the 523 // original best match isn't good enough to autocomplete. 524 db->GetRowForURL(search_base, &info); 525 promote = match.url_info.typed_count() <= 1; 526 } 527 528 // Promote or add the desired URL to the list of matches. 529 EnsureMatchPresent(info, match.input_location, match.match_in_scheme, 530 matches, promote); 531} 532 533// static 534void HistoryURLProvider::EnsureMatchPresent( 535 const history::URLRow& info, 536 string16::size_type input_location, 537 bool match_in_scheme, 538 HistoryMatches* matches, 539 bool promote) { 540 // |matches| may already have an entry for this. 541 for (HistoryMatches::iterator i(matches->begin()); i != matches->end(); 542 ++i) { 543 if (i->url_info.url() == info.url()) { 544 // Rotate it to the front if the caller wishes. 545 if (promote) 546 std::rotate(matches->begin(), i, i + 1); 547 return; 548 } 549 } 550 551 // No entry, so create one. 552 HistoryMatch match(info, input_location, match_in_scheme, true); 553 if (promote) 554 matches->push_front(match); 555 else 556 matches->push_back(match); 557} 558 559void HistoryURLProvider::RunAutocompletePasses( 560 const AutocompleteInput& input, 561 bool fixup_input_and_run_pass_1) { 562 matches_.clear(); 563 564 if ((input.type() == AutocompleteInput::INVALID) || 565 (input.type() == AutocompleteInput::FORCED_QUERY)) 566 return; 567 568 // Create a match for exactly what the user typed. This will only be used as 569 // a fallback in case we can't get the history service or URL DB; otherwise, 570 // we'll run this again in DoAutocomplete() and use that result instead. 571 const bool trim_http = !HasHTTPScheme(input.text()); 572 // Don't do this for queries -- while we can sometimes mark up a match for 573 // this, it's not what the user wants, and just adds noise. 574 if ((input.type() != AutocompleteInput::QUERY) && 575 input.canonicalized_url().is_valid()) 576 matches_.push_back(SuggestExactInput(input, trim_http)); 577 578 // We'll need the history service to run both passes, so try to obtain it. 579 HistoryService* const history_service = 580 profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); 581 if (!history_service) 582 return; 583 584 // Create the data structure for the autocomplete passes. We'll save this off 585 // onto the |params_| member for later deletion below if we need to run pass 586 // 2. 587 std::string languages(languages_); 588 if (languages.empty() && profile_) { 589 languages = 590 profile_->GetPrefs()->GetString(prefs::kAcceptLanguages); 591 } 592 scoped_ptr<HistoryURLProviderParams> params( 593 new HistoryURLProviderParams(input, trim_http, languages)); 594 595 if (fixup_input_and_run_pass_1) { 596 // Do some fixup on the user input before matching against it, so we provide 597 // good results for local file paths, input with spaces, etc. 598 // NOTE: This purposefully doesn't take input.desired_tld() into account; if 599 // it did, then holding "ctrl" would change all the results from the 600 // HistoryURLProvider provider, not just the What You Typed Result. 601 const string16 fixed_text(FixupUserInput(input)); 602 if (fixed_text.empty()) { 603 // Conceivably fixup could result in an empty string (although I don't 604 // have cases where this happens offhand). We can't do anything with 605 // empty input, so just bail; otherwise we'd crash later. 606 return; 607 } 608 params->input.set_text(fixed_text); 609 610 // Pass 1: Get the in-memory URL database, and use it to find and promote 611 // the inline autocomplete match, if any. 612 history::URLDatabase* url_db = history_service->InMemoryDatabase(); 613 // url_db can be NULL if it hasn't finished initializing (or failed to 614 // initialize). In this case all we can do is fall back on the second 615 // pass. 616 // 617 // TODO(pkasting): We should just block here until this loads. Any time 618 // someone unloads the history backend, we'll get inconsistent inline 619 // autocomplete behavior here. 620 if (url_db) { 621 DoAutocomplete(NULL, url_db, params.get()); 622 // params->matches now has the matches we should expose to the provider. 623 // Pass 2 expects a "clean slate" set of matches. 624 matches_.clear(); 625 matches_.swap(params->matches); 626 UpdateStarredStateOfMatches(); 627 } 628 } 629 630 // Pass 2: Ask the history service to call us back on the history thread, 631 // where we can read the full on-disk DB. 632 if (!input.synchronous_only()) { 633 done_ = false; 634 params_ = params.release(); // This object will be destroyed in 635 // QueryComplete() once we're done with it. 636 history_service->ScheduleAutocomplete(this, params_); 637 } 638} 639 640const history::Prefix* HistoryURLProvider::BestPrefix( 641 const GURL& url, 642 const string16& prefix_suffix) const { 643 const Prefix* best_prefix = NULL; 644 const string16 text(UTF8ToUTF16(url.spec())); 645 for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end(); 646 ++i) { 647 if ((best_prefix == NULL) || 648 (i->num_components > best_prefix->num_components)) { 649 string16 prefix_with_suffix(i->prefix + prefix_suffix); 650 if ((text.length() >= prefix_with_suffix.length()) && 651 !text.compare(0, prefix_with_suffix.length(), prefix_with_suffix)) 652 best_prefix = &(*i); 653 } 654 } 655 return best_prefix; 656} 657 658void HistoryURLProvider::SortMatches(HistoryMatches* matches) const { 659 // Sort by quality, best first. 660 std::sort(matches->begin(), matches->end(), &history::CompareHistoryMatch); 661 662 // Remove duplicate matches (caused by the search string appearing in one of 663 // the prefixes as well as after it). Consider the following scenario: 664 // 665 // User has visited "http://http.com" once and "http://htaccess.com" twice. 666 // User types "http". The autocomplete search with prefix "http://" returns 667 // the first host, while the search with prefix "" returns both hosts. Now 668 // we sort them into rank order: 669 // http://http.com (innermost_match) 670 // http://htaccess.com (!innermost_match, url_info.visit_count == 2) 671 // http://http.com (!innermost_match, url_info.visit_count == 1) 672 // 673 // The above scenario tells us we can't use std::unique(), since our 674 // duplicates are not always sequential. It also tells us we should remove 675 // the lower-quality duplicate(s), since otherwise the returned results won't 676 // be ordered correctly. This is easy to do: we just always remove the later 677 // element of a duplicate pair. 678 // Be careful! Because the vector contents may change as we remove elements, 679 // we use an index instead of an iterator in the outer loop, and don't 680 // precalculate the ending position. 681 for (size_t i = 0; i < matches->size(); ++i) { 682 HistoryMatches::iterator j(matches->begin() + i + 1); 683 while (j != matches->end()) { 684 if ((*matches)[i].url_info.url() == j->url_info.url()) 685 j = matches->erase(j); 686 else 687 ++j; 688 } 689 } 690} 691 692void HistoryURLProvider::CullPoorMatches(HistoryMatches* matches) const { 693 const base::Time& threshold(history::AutocompleteAgeThreshold()); 694 for (HistoryMatches::iterator i(matches->begin()); i != matches->end();) { 695 if (RowQualifiesAsSignificant(i->url_info, threshold)) 696 ++i; 697 else 698 i = matches->erase(i); 699 } 700} 701 702void HistoryURLProvider::CullRedirects(history::HistoryBackend* backend, 703 HistoryMatches* matches, 704 size_t max_results) const { 705 for (size_t source = 0; 706 (source < matches->size()) && (source < max_results); ) { 707 const GURL& url = (*matches)[source].url_info.url(); 708 // TODO(brettw) this should go away when everything uses GURL. 709 history::RedirectList redirects; 710 backend->GetMostRecentRedirectsFrom(url, &redirects); 711 if (!redirects.empty()) { 712 // Remove all but the first occurrence of any of these redirects in the 713 // search results. We also must add the URL we queried for, since it may 714 // not be the first match and we'd want to remove it. 715 // 716 // For example, when A redirects to B and our matches are [A, X, B], 717 // we'll get B as the redirects from, and we want to remove the second 718 // item of that pair, removing B. If A redirects to B and our matches are 719 // [B, X, A], we'll want to remove A instead. 720 redirects.push_back(url); 721 source = RemoveSubsequentMatchesOf(matches, source, redirects); 722 } else { 723 // Advance to next item. 724 source++; 725 } 726 } 727 728 if (matches->size() > max_results) 729 matches->resize(max_results); 730} 731 732size_t HistoryURLProvider::RemoveSubsequentMatchesOf( 733 HistoryMatches* matches, 734 size_t source_index, 735 const std::vector<GURL>& remove) const { 736 size_t next_index = source_index + 1; // return value = item after source 737 738 // Find the first occurrence of any URL in the redirect chain. We want to 739 // keep this one since it is rated the highest. 740 HistoryMatches::iterator first(std::find_first_of( 741 matches->begin(), matches->end(), remove.begin(), remove.end())); 742 DCHECK(first != matches->end()) << 743 "We should have always found at least the original URL."; 744 745 // Find any following occurrences of any URL in the redirect chain, these 746 // should be deleted. 747 HistoryMatches::iterator next(first); 748 next++; // Start searching immediately after the one we found already. 749 while (next != matches->end() && 750 (next = std::find_first_of(next, matches->end(), remove.begin(), 751 remove.end())) != matches->end()) { 752 // Remove this item. When we remove an item before the source index, we 753 // need to shift it to the right and remember that so we can return it. 754 next = matches->erase(next); 755 if (static_cast<size_t>(next - matches->begin()) < next_index) 756 next_index--; 757 } 758 return next_index; 759} 760 761AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch( 762 HistoryURLProviderParams* params, 763 const HistoryMatch& history_match, 764 MatchType match_type, 765 size_t match_number) { 766 const history::URLRow& info = history_match.url_info; 767 AutocompleteMatch match(this, 768 CalculateRelevance(params->input.type(), match_type, match_number), 769 !!info.visit_count(), AutocompleteMatch::HISTORY_URL); 770 match.destination_url = info.url(); 771 DCHECK(match.destination_url.is_valid()); 772 size_t inline_autocomplete_offset = 773 history_match.input_location + params->input.text().length(); 774 std::string languages = (match_type == WHAT_YOU_TYPED) ? 775 std::string() : params->languages; 776 const net::FormatUrlTypes format_types = net::kFormatUrlOmitAll & 777 ~((params->trim_http && !history_match.match_in_scheme) ? 778 0 : net::kFormatUrlOmitHTTP); 779 match.fill_into_edit = 780 AutocompleteInput::FormattedStringWithEquivalentMeaning(info.url(), 781 net::FormatUrl(info.url(), languages, format_types, 782 UnescapeRule::SPACES, NULL, NULL, 783 &inline_autocomplete_offset)); 784 if (!params->input.prevent_inline_autocomplete()) 785 match.inline_autocomplete_offset = inline_autocomplete_offset; 786 DCHECK((match.inline_autocomplete_offset == string16::npos) || 787 (match.inline_autocomplete_offset <= match.fill_into_edit.length())); 788 789 size_t match_start = history_match.input_location; 790 match.contents = net::FormatUrl(info.url(), languages, 791 format_types, UnescapeRule::SPACES, NULL, NULL, &match_start); 792 if ((match_start != string16::npos) && 793 (inline_autocomplete_offset != string16::npos) && 794 (inline_autocomplete_offset != match_start)) { 795 DCHECK(inline_autocomplete_offset > match_start); 796 AutocompleteMatch::ClassifyLocationInString(match_start, 797 inline_autocomplete_offset - match_start, match.contents.length(), 798 ACMatchClassification::URL, &match.contents_class); 799 } else { 800 AutocompleteMatch::ClassifyLocationInString(string16::npos, 0, 801 match.contents.length(), ACMatchClassification::URL, 802 &match.contents_class); 803 } 804 match.description = info.title(); 805 AutocompleteMatch::ClassifyMatchInString(params->input.text(), 806 info.title(), 807 ACMatchClassification::NONE, 808 &match.description_class); 809 810 return match; 811} 812