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