1 // Copyright 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 "components/omnibox/search_provider.h" 6 7 #include <algorithm> 8 #include <cmath> 9 10 #include "base/base64.h" 11 #include "base/callback.h" 12 #include "base/i18n/break_iterator.h" 13 #include "base/i18n/case_conversion.h" 14 #include "base/json/json_string_value_serializer.h" 15 #include "base/metrics/histogram.h" 16 #include "base/metrics/user_metrics.h" 17 #include "base/rand_util.h" 18 #include "base/strings/string_util.h" 19 #include "base/strings/utf_string_conversions.h" 20 #include "components/history/core/browser/in_memory_database.h" 21 #include "components/history/core/browser/keyword_search_term.h" 22 #include "components/metrics/proto/omnibox_input_type.pb.h" 23 #include "components/omnibox/autocomplete_provider_client.h" 24 #include "components/omnibox/autocomplete_provider_listener.h" 25 #include "components/omnibox/autocomplete_result.h" 26 #include "components/omnibox/keyword_provider.h" 27 #include "components/omnibox/omnibox_field_trial.h" 28 #include "components/omnibox/url_prefix.h" 29 #include "components/search/search.h" 30 #include "components/search_engines/template_url_prepopulate_data.h" 31 #include "components/search_engines/template_url_service.h" 32 #include "components/variations/variations_http_header_provider.h" 33 #include "grit/components_strings.h" 34 #include "net/base/escape.h" 35 #include "net/base/load_flags.h" 36 #include "net/base/net_util.h" 37 #include "net/http/http_request_headers.h" 38 #include "net/url_request/url_fetcher.h" 39 #include "net/url_request/url_request_status.h" 40 #include "ui/base/l10n/l10n_util.h" 41 #include "url/url_constants.h" 42 #include "url/url_util.h" 43 44 // Helpers -------------------------------------------------------------------- 45 46 namespace { 47 48 // We keep track in a histogram how many suggest requests we send, how 49 // many suggest requests we invalidate (e.g., due to a user typing 50 // another character), and how many replies we receive. 51 // *** ADD NEW ENUMS AFTER ALL PREVIOUSLY DEFINED ONES! *** 52 // (excluding the end-of-list enum value) 53 // We do not want values of existing enums to change or else it screws 54 // up the statistics. 55 enum SuggestRequestsHistogramValue { 56 REQUEST_SENT = 1, 57 REQUEST_INVALIDATED, 58 REPLY_RECEIVED, 59 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE 60 }; 61 62 // The verbatim score for an input which is not an URL. 63 const int kNonURLVerbatimRelevance = 1300; 64 65 // Increments the appropriate value in the histogram by one. 66 void LogOmniboxSuggestRequest( 67 SuggestRequestsHistogramValue request_value) { 68 UMA_HISTOGRAM_ENUMERATION("Omnibox.SuggestRequests", request_value, 69 MAX_SUGGEST_REQUEST_HISTOGRAM_VALUE); 70 } 71 72 bool HasMultipleWords(const base::string16& text) { 73 base::i18n::BreakIterator i(text, base::i18n::BreakIterator::BREAK_WORD); 74 bool found_word = false; 75 if (i.Init()) { 76 while (i.Advance()) { 77 if (i.IsWord()) { 78 if (found_word) 79 return true; 80 found_word = true; 81 } 82 } 83 } 84 return false; 85 } 86 87 } // namespace 88 89 // SearchProvider::Providers -------------------------------------------------- 90 91 SearchProvider::Providers::Providers(TemplateURLService* template_url_service) 92 : template_url_service_(template_url_service) {} 93 94 const TemplateURL* SearchProvider::Providers::GetDefaultProviderURL() const { 95 return default_provider_.empty() ? NULL : 96 template_url_service_->GetTemplateURLForKeyword(default_provider_); 97 } 98 99 const TemplateURL* SearchProvider::Providers::GetKeywordProviderURL() const { 100 return keyword_provider_.empty() ? NULL : 101 template_url_service_->GetTemplateURLForKeyword(keyword_provider_); 102 } 103 104 105 // SearchProvider::CompareScoredResults --------------------------------------- 106 107 class SearchProvider::CompareScoredResults { 108 public: 109 bool operator()(const SearchSuggestionParser::Result& a, 110 const SearchSuggestionParser::Result& b) { 111 // Sort in descending relevance order. 112 return a.relevance() > b.relevance(); 113 } 114 }; 115 116 117 // SearchProvider ------------------------------------------------------------- 118 119 // static 120 int SearchProvider::kMinimumTimeBetweenSuggestQueriesMs = 100; 121 122 SearchProvider::SearchProvider( 123 AutocompleteProviderListener* listener, 124 TemplateURLService* template_url_service, 125 scoped_ptr<AutocompleteProviderClient> client) 126 : BaseSearchProvider(template_url_service, client.Pass(), 127 AutocompleteProvider::TYPE_SEARCH), 128 listener_(listener), 129 suggest_results_pending_(0), 130 providers_(template_url_service), 131 answers_cache_(10) { 132 } 133 134 // static 135 std::string SearchProvider::GetSuggestMetadata(const AutocompleteMatch& match) { 136 return match.GetAdditionalInfo(kSuggestMetadataKey); 137 } 138 139 void SearchProvider::ResetSession() { 140 field_trial_triggered_in_session_ = false; 141 } 142 143 SearchProvider::~SearchProvider() { 144 } 145 146 // static 147 int SearchProvider::CalculateRelevanceForKeywordVerbatim( 148 metrics::OmniboxInputType::Type type, 149 bool prefer_keyword) { 150 // This function is responsible for scoring verbatim query matches 151 // for non-extension keywords. KeywordProvider::CalculateRelevance() 152 // scores verbatim query matches for extension keywords, as well as 153 // for keyword matches (i.e., suggestions of a keyword itself, not a 154 // suggestion of a query on a keyword search engine). These two 155 // functions are currently in sync, but there's no reason we 156 // couldn't decide in the future to score verbatim matches 157 // differently for extension and non-extension keywords. If you 158 // make such a change, however, you should update this comment to 159 // describe it, so it's clear why the functions diverge. 160 if (prefer_keyword) 161 return 1500; 162 return (type == metrics::OmniboxInputType::QUERY) ? 1450 : 1100; 163 } 164 165 // static 166 void SearchProvider::UpdateOldResults( 167 bool minimal_changes, 168 SearchSuggestionParser::Results* results) { 169 // When called without |minimal_changes|, it likely means the user has 170 // pressed a key. Revise the cached results appropriately. 171 if (!minimal_changes) { 172 for (SearchSuggestionParser::SuggestResults::iterator sug_it = 173 results->suggest_results.begin(); 174 sug_it != results->suggest_results.end(); ++sug_it) { 175 sug_it->set_received_after_last_keystroke(false); 176 } 177 for (SearchSuggestionParser::NavigationResults::iterator nav_it = 178 results->navigation_results.begin(); 179 nav_it != results->navigation_results.end(); ++nav_it) { 180 nav_it->set_received_after_last_keystroke(false); 181 } 182 } 183 } 184 185 // static 186 ACMatches::iterator SearchProvider::FindTopMatch(ACMatches* matches) { 187 ACMatches::iterator it = matches->begin(); 188 while ((it != matches->end()) && !it->allowed_to_be_default_match) 189 ++it; 190 return it; 191 } 192 193 void SearchProvider::Start(const AutocompleteInput& input, 194 bool minimal_changes) { 195 // Do our best to load the model as early as possible. This will reduce 196 // odds of having the model not ready when really needed (a non-empty input). 197 TemplateURLService* model = providers_.template_url_service(); 198 DCHECK(model); 199 model->Load(); 200 201 matches_.clear(); 202 field_trial_triggered_ = false; 203 204 // Can't return search/suggest results for bogus input. 205 if (input.type() == metrics::OmniboxInputType::INVALID) { 206 Stop(true); 207 return; 208 } 209 210 keyword_input_ = input; 211 const TemplateURL* keyword_provider = 212 KeywordProvider::GetSubstitutingTemplateURLForInput(model, 213 &keyword_input_); 214 if (keyword_provider == NULL) 215 keyword_input_.Clear(); 216 else if (keyword_input_.text().empty()) 217 keyword_provider = NULL; 218 219 const TemplateURL* default_provider = model->GetDefaultSearchProvider(); 220 if (default_provider && 221 !default_provider->SupportsReplacement(model->search_terms_data())) 222 default_provider = NULL; 223 224 if (keyword_provider == default_provider) 225 default_provider = NULL; // No use in querying the same provider twice. 226 227 if (!default_provider && !keyword_provider) { 228 // No valid providers. 229 Stop(true); 230 return; 231 } 232 233 // If we're still running an old query but have since changed the query text 234 // or the providers, abort the query. 235 base::string16 default_provider_keyword(default_provider ? 236 default_provider->keyword() : base::string16()); 237 base::string16 keyword_provider_keyword(keyword_provider ? 238 keyword_provider->keyword() : base::string16()); 239 if (!minimal_changes || 240 !providers_.equal(default_provider_keyword, keyword_provider_keyword)) { 241 // Cancel any in-flight suggest requests. 242 if (!done_) 243 Stop(false); 244 } 245 246 providers_.set(default_provider_keyword, keyword_provider_keyword); 247 248 if (input.text().empty()) { 249 // User typed "?" alone. Give them a placeholder result indicating what 250 // this syntax does. 251 if (default_provider) { 252 AutocompleteMatch match; 253 match.provider = this; 254 match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE)); 255 match.contents_class.push_back( 256 ACMatchClassification(0, ACMatchClassification::NONE)); 257 match.keyword = providers_.default_provider(); 258 match.allowed_to_be_default_match = true; 259 matches_.push_back(match); 260 } 261 Stop(true); 262 return; 263 } 264 265 input_ = input; 266 267 DoHistoryQuery(minimal_changes); 268 // Answers needs scored history results before any suggest query has been 269 // started, since the query for answer-bearing results needs additional 270 // prefetch information based on the highest-scored local history result. 271 if (OmniboxFieldTrial::EnableAnswersInSuggest()) { 272 ScoreHistoryResults(raw_default_history_results_, 273 false, 274 &transformed_default_history_results_); 275 ScoreHistoryResults(raw_keyword_history_results_, 276 true, 277 &transformed_keyword_history_results_); 278 prefetch_data_ = FindAnswersPrefetchData(); 279 280 // Raw results are not needed any more. 281 raw_default_history_results_.clear(); 282 raw_keyword_history_results_.clear(); 283 } else { 284 transformed_default_history_results_.clear(); 285 transformed_keyword_history_results_.clear(); 286 } 287 288 StartOrStopSuggestQuery(minimal_changes); 289 UpdateMatches(); 290 } 291 292 void SearchProvider::Stop(bool clear_cached_results) { 293 StopSuggest(); 294 done_ = true; 295 296 if (clear_cached_results) 297 ClearAllResults(); 298 } 299 300 const TemplateURL* SearchProvider::GetTemplateURL(bool is_keyword) const { 301 return is_keyword ? providers_.GetKeywordProviderURL() 302 : providers_.GetDefaultProviderURL(); 303 } 304 305 const AutocompleteInput SearchProvider::GetInput(bool is_keyword) const { 306 return is_keyword ? keyword_input_ : input_; 307 } 308 309 bool SearchProvider::ShouldAppendExtraParams( 310 const SearchSuggestionParser::SuggestResult& result) const { 311 return !result.from_keyword_provider() || 312 providers_.default_provider().empty(); 313 } 314 315 void SearchProvider::RecordDeletionResult(bool success) { 316 if (success) { 317 base::RecordAction( 318 base::UserMetricsAction("Omnibox.ServerSuggestDelete.Success")); 319 } else { 320 base::RecordAction( 321 base::UserMetricsAction("Omnibox.ServerSuggestDelete.Failure")); 322 } 323 } 324 325 void SearchProvider::OnURLFetchComplete(const net::URLFetcher* source) { 326 DCHECK(!done_); 327 --suggest_results_pending_; 328 DCHECK_GE(suggest_results_pending_, 0); // Should never go negative. 329 330 const bool is_keyword = source == keyword_fetcher_.get(); 331 332 // Ensure the request succeeded and that the provider used is still available. 333 // A verbatim match cannot be generated without this provider, causing errors. 334 const bool request_succeeded = 335 source->GetStatus().is_success() && (source->GetResponseCode() == 200) && 336 GetTemplateURL(is_keyword); 337 338 LogFetchComplete(request_succeeded, is_keyword); 339 340 bool results_updated = false; 341 if (request_succeeded) { 342 scoped_ptr<base::Value> data(SearchSuggestionParser::DeserializeJsonData( 343 SearchSuggestionParser::ExtractJsonData(source))); 344 if (data) { 345 SearchSuggestionParser::Results* results = 346 is_keyword ? &keyword_results_ : &default_results_; 347 results_updated = ParseSuggestResults(*data, -1, is_keyword, results); 348 if (results_updated) 349 SortResults(is_keyword, results); 350 } 351 } 352 UpdateMatches(); 353 if (done_ || results_updated) 354 listener_->OnProviderUpdate(results_updated); 355 } 356 357 void SearchProvider::StopSuggest() { 358 // Increment the appropriate field in the histogram by the number of 359 // pending requests that were invalidated. 360 for (int i = 0; i < suggest_results_pending_; ++i) 361 LogOmniboxSuggestRequest(REQUEST_INVALIDATED); 362 suggest_results_pending_ = 0; 363 timer_.Stop(); 364 // Stop any in-progress URL fetches. 365 keyword_fetcher_.reset(); 366 default_fetcher_.reset(); 367 } 368 369 void SearchProvider::ClearAllResults() { 370 keyword_results_.Clear(); 371 default_results_.Clear(); 372 } 373 374 void SearchProvider::UpdateMatchContentsClass( 375 const base::string16& input_text, 376 SearchSuggestionParser::Results* results) { 377 for (SearchSuggestionParser::SuggestResults::iterator sug_it = 378 results->suggest_results.begin(); 379 sug_it != results->suggest_results.end(); ++sug_it) { 380 sug_it->ClassifyMatchContents(false, input_text); 381 } 382 const std::string languages(client_->AcceptLanguages()); 383 for (SearchSuggestionParser::NavigationResults::iterator nav_it = 384 results->navigation_results.begin(); 385 nav_it != results->navigation_results.end(); ++nav_it) { 386 nav_it->CalculateAndClassifyMatchContents(false, input_text, languages); 387 } 388 } 389 390 void SearchProvider::SortResults(bool is_keyword, 391 SearchSuggestionParser::Results* results) { 392 // Ignore suggested scores for non-keyword matches in keyword mode; if the 393 // server is allowed to score these, it could interfere with the user's 394 // ability to get good keyword results. 395 const bool abandon_suggested_scores = 396 !is_keyword && !providers_.keyword_provider().empty(); 397 // Apply calculated relevance scores to suggestions if valid relevances were 398 // not provided or we're abandoning suggested scores entirely. 399 if (!results->relevances_from_server || abandon_suggested_scores) { 400 ApplyCalculatedSuggestRelevance(&results->suggest_results); 401 ApplyCalculatedNavigationRelevance(&results->navigation_results); 402 // If abandoning scores entirely, also abandon the verbatim score. 403 if (abandon_suggested_scores) 404 results->verbatim_relevance = -1; 405 } 406 407 // Keep the result lists sorted. 408 const CompareScoredResults comparator = CompareScoredResults(); 409 std::stable_sort(results->suggest_results.begin(), 410 results->suggest_results.end(), 411 comparator); 412 std::stable_sort(results->navigation_results.begin(), 413 results->navigation_results.end(), 414 comparator); 415 } 416 417 void SearchProvider::LogFetchComplete(bool success, bool is_keyword) { 418 LogOmniboxSuggestRequest(REPLY_RECEIVED); 419 // Record response time for suggest requests sent to Google. We care 420 // only about the common case: the Google default provider used in 421 // non-keyword mode. 422 const TemplateURL* default_url = providers_.GetDefaultProviderURL(); 423 if (!is_keyword && default_url && 424 (TemplateURLPrepopulateData::GetEngineType( 425 *default_url, 426 providers_.template_url_service()->search_terms_data()) == 427 SEARCH_ENGINE_GOOGLE)) { 428 const base::TimeDelta elapsed_time = 429 base::TimeTicks::Now() - time_suggest_request_sent_; 430 if (success) { 431 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Success.GoogleResponseTime", 432 elapsed_time); 433 } else { 434 UMA_HISTOGRAM_TIMES("Omnibox.SuggestRequest.Failure.GoogleResponseTime", 435 elapsed_time); 436 } 437 } 438 } 439 440 void SearchProvider::UpdateMatches() { 441 PersistTopSuggestions(&default_results_); 442 PersistTopSuggestions(&keyword_results_); 443 ConvertResultsToAutocompleteMatches(); 444 445 // Check constraints that may be violated by suggested relevances. 446 if (!matches_.empty() && 447 (default_results_.HasServerProvidedScores() || 448 keyword_results_.HasServerProvidedScores())) { 449 // These blocks attempt to repair undesirable behavior by suggested 450 // relevances with minimal impact, preserving other suggested relevances. 451 452 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL(); 453 const bool is_extension_keyword = (keyword_url != NULL) && 454 (keyword_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION); 455 if ((keyword_url != NULL) && !is_extension_keyword && 456 (FindTopMatch() == matches_.end())) { 457 // In non-extension keyword mode, disregard the keyword verbatim suggested 458 // relevance if necessary, so at least one match is allowed to be default. 459 // (In extension keyword mode this is not necessary because the extension 460 // will return a default match.) Give keyword verbatim the lowest 461 // non-zero score to best reflect what the server desired. 462 DCHECK_EQ(0, keyword_results_.verbatim_relevance); 463 keyword_results_.verbatim_relevance = 1; 464 ConvertResultsToAutocompleteMatches(); 465 } 466 if (IsTopMatchSearchWithURLInput()) { 467 // Disregard the suggested search and verbatim relevances if the input 468 // type is URL and the top match is a highly-ranked search suggestion. 469 // For example, prevent a search for "foo.com" from outranking another 470 // provider's navigation for "foo.com" or "foo.com/url_from_history". 471 ApplyCalculatedSuggestRelevance(&keyword_results_.suggest_results); 472 ApplyCalculatedSuggestRelevance(&default_results_.suggest_results); 473 default_results_.verbatim_relevance = -1; 474 keyword_results_.verbatim_relevance = -1; 475 ConvertResultsToAutocompleteMatches(); 476 } 477 if (!is_extension_keyword && (FindTopMatch() == matches_.end())) { 478 // Guarantee that SearchProvider returns a legal default match (except 479 // when in extension-based keyword mode). The omnibox always needs at 480 // least one legal default match, and it relies on SearchProvider in 481 // combination with KeywordProvider (for extension-based keywords) to 482 // always return one. Give the verbatim suggestion the lowest non-zero 483 // scores to best reflect what the server desired. 484 DCHECK_EQ(0, default_results_.verbatim_relevance); 485 default_results_.verbatim_relevance = 1; 486 // We do not have to alter keyword_results_.verbatim_relevance here. 487 // If the user is in keyword mode, we already reverted (earlier in this 488 // function) the instructions to suppress keyword verbatim. 489 ConvertResultsToAutocompleteMatches(); 490 } 491 DCHECK(!IsTopMatchSearchWithURLInput()); 492 DCHECK(is_extension_keyword || (FindTopMatch() != matches_.end())); 493 } 494 UMA_HISTOGRAM_CUSTOM_COUNTS( 495 "Omnibox.SearchProviderMatches", matches_.size(), 1, 6, 7); 496 497 // Record the top suggestion (if any) for future use. 498 top_query_suggestion_match_contents_ = base::string16(); 499 top_navigation_suggestion_ = GURL(); 500 ACMatches::const_iterator first_match = FindTopMatch(); 501 if ((first_match != matches_.end()) && 502 !first_match->inline_autocompletion.empty()) { 503 // Identify if this match came from a query suggestion or a navsuggestion. 504 // In either case, extracts the identifying feature of the suggestion 505 // (query string or navigation url). 506 if (AutocompleteMatch::IsSearchType(first_match->type)) 507 top_query_suggestion_match_contents_ = first_match->contents; 508 else 509 top_navigation_suggestion_ = first_match->destination_url; 510 } 511 512 UpdateDone(); 513 } 514 515 void SearchProvider::Run() { 516 // Start a new request with the current input. 517 suggest_results_pending_ = 0; 518 time_suggest_request_sent_ = base::TimeTicks::Now(); 519 520 default_fetcher_.reset(CreateSuggestFetcher(kDefaultProviderURLFetcherID, 521 providers_.GetDefaultProviderURL(), input_)); 522 keyword_fetcher_.reset(CreateSuggestFetcher(kKeywordProviderURLFetcherID, 523 providers_.GetKeywordProviderURL(), keyword_input_)); 524 525 // Both the above can fail if the providers have been modified or deleted 526 // since the query began. 527 if (suggest_results_pending_ == 0) { 528 UpdateDone(); 529 // We only need to update the listener if we're actually done. 530 if (done_) 531 listener_->OnProviderUpdate(false); 532 } 533 } 534 535 void SearchProvider::DoHistoryQuery(bool minimal_changes) { 536 // The history query results are synchronous, so if minimal_changes is true, 537 // we still have the last results and don't need to do anything. 538 if (minimal_changes) 539 return; 540 541 raw_keyword_history_results_.clear(); 542 raw_default_history_results_.clear(); 543 544 if (OmniboxFieldTrial::SearchHistoryDisable( 545 input_.current_page_classification())) 546 return; 547 548 history::URLDatabase* url_db = client_->InMemoryDatabase(); 549 if (!url_db) 550 return; 551 552 // Request history for both the keyword and default provider. We grab many 553 // more matches than we'll ultimately clamp to so that if there are several 554 // recent multi-word matches who scores are lowered (see 555 // ScoreHistoryResults()), they won't crowd out older, higher-scoring 556 // matches. Note that this doesn't fix the problem entirely, but merely 557 // limits it to cases with a very large number of such multi-word matches; for 558 // now, this seems OK compared with the complexity of a real fix, which would 559 // require multiple searches and tracking of "single- vs. multi-word" in the 560 // database. 561 int num_matches = kMaxMatches * 5; 562 const TemplateURL* default_url = providers_.GetDefaultProviderURL(); 563 if (default_url) { 564 const base::TimeTicks start_time = base::TimeTicks::Now(); 565 url_db->GetMostRecentKeywordSearchTerms(default_url->id(), 566 input_.text(), 567 num_matches, 568 &raw_default_history_results_); 569 UMA_HISTOGRAM_TIMES( 570 "Omnibox.SearchProvider.GetMostRecentKeywordTermsDefaultProviderTime", 571 base::TimeTicks::Now() - start_time); 572 } 573 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL(); 574 if (keyword_url) { 575 url_db->GetMostRecentKeywordSearchTerms(keyword_url->id(), 576 keyword_input_.text(), 577 num_matches, 578 &raw_keyword_history_results_); 579 } 580 } 581 582 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) { 583 if (!IsQuerySuitableForSuggest()) { 584 StopSuggest(); 585 ClearAllResults(); 586 return; 587 } 588 589 // For the minimal_changes case, if we finished the previous query and still 590 // have its results, or are allowed to keep running it, just do that, rather 591 // than starting a new query. 592 if (minimal_changes && 593 (!default_results_.suggest_results.empty() || 594 !default_results_.navigation_results.empty() || 595 !keyword_results_.suggest_results.empty() || 596 !keyword_results_.navigation_results.empty() || 597 (!done_ && input_.want_asynchronous_matches()))) 598 return; 599 600 // We can't keep running any previous query, so halt it. 601 StopSuggest(); 602 603 UpdateAllOldResults(minimal_changes); 604 605 // Update the content classifications of remaining results so they look good 606 // against the current input. 607 UpdateMatchContentsClass(input_.text(), &default_results_); 608 if (!keyword_input_.text().empty()) 609 UpdateMatchContentsClass(keyword_input_.text(), &keyword_results_); 610 611 // We can't start a new query if we're only allowed synchronous results. 612 if (!input_.want_asynchronous_matches()) 613 return; 614 615 // To avoid flooding the suggest server, don't send a query until at 616 // least 100 ms since the last query. 617 base::TimeTicks next_suggest_time(time_suggest_request_sent_ + 618 base::TimeDelta::FromMilliseconds(kMinimumTimeBetweenSuggestQueriesMs)); 619 base::TimeTicks now(base::TimeTicks::Now()); 620 if (now >= next_suggest_time) { 621 Run(); 622 return; 623 } 624 timer_.Start(FROM_HERE, next_suggest_time - now, this, &SearchProvider::Run); 625 } 626 627 bool SearchProvider::IsQuerySuitableForSuggest() const { 628 // Don't run Suggest in incognito mode, if the engine doesn't support it, or 629 // if the user has disabled it. 630 const TemplateURL* default_url = providers_.GetDefaultProviderURL(); 631 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL(); 632 if (client_->IsOffTheRecord() || 633 ((!default_url || default_url->suggestions_url().empty()) && 634 (!keyword_url || keyword_url->suggestions_url().empty())) || 635 !client_->SearchSuggestEnabled()) 636 return false; 637 638 // If the input type might be a URL, we take extra care so that private data 639 // isn't sent to the server. 640 641 // FORCED_QUERY means the user is explicitly asking us to search for this, so 642 // we assume it isn't a URL and/or there isn't private data. 643 if (input_.type() == metrics::OmniboxInputType::FORCED_QUERY) 644 return true; 645 646 // Next we check the scheme. If this is UNKNOWN/URL with a scheme that isn't 647 // http/https/ftp, we shouldn't send it. Sending things like file: and data: 648 // is both a waste of time and a disclosure of potentially private, local 649 // data. Other "schemes" may actually be usernames, and we don't want to send 650 // passwords. If the scheme is OK, we still need to check other cases below. 651 // If this is QUERY, then the presence of these schemes means the user 652 // explicitly typed one, and thus this is probably a URL that's being entered 653 // and happens to currently be invalid -- in which case we again want to run 654 // our checks below. Other QUERY cases are less likely to be URLs and thus we 655 // assume we're OK. 656 if (!LowerCaseEqualsASCII(input_.scheme(), url::kHttpScheme) && 657 !LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) && 658 !LowerCaseEqualsASCII(input_.scheme(), url::kFtpScheme)) 659 return (input_.type() == metrics::OmniboxInputType::QUERY); 660 661 // Don't send URLs with usernames, queries or refs. Some of these are 662 // private, and the Suggest server is unlikely to have any useful results 663 // for any of them. Also don't send URLs with ports, as we may initially 664 // think that a username + password is a host + port (and we don't want to 665 // send usernames/passwords), and even if the port really is a port, the 666 // server is once again unlikely to have and useful results. 667 // Note that we only block based on refs if the input is URL-typed, as search 668 // queries can legitimately have #s in them which the URL parser 669 // overaggressively categorizes as a url with a ref. 670 const url::Parsed& parts = input_.parts(); 671 if (parts.username.is_nonempty() || parts.port.is_nonempty() || 672 parts.query.is_nonempty() || 673 (parts.ref.is_nonempty() && 674 (input_.type() == metrics::OmniboxInputType::URL))) 675 return false; 676 677 // Don't send anything for https except the hostname. Hostnames are OK 678 // because they are visible when the TCP connection is established, but the 679 // specific path may reveal private information. 680 if (LowerCaseEqualsASCII(input_.scheme(), url::kHttpsScheme) && 681 parts.path.is_nonempty()) 682 return false; 683 684 return true; 685 } 686 687 void SearchProvider::UpdateAllOldResults(bool minimal_changes) { 688 if (keyword_input_.text().empty()) { 689 // User is either in keyword mode with a blank input or out of 690 // keyword mode entirely. 691 keyword_results_.Clear(); 692 } 693 UpdateOldResults(minimal_changes, &default_results_); 694 UpdateOldResults(minimal_changes, &keyword_results_); 695 } 696 697 void SearchProvider::PersistTopSuggestions( 698 SearchSuggestionParser::Results* results) { 699 // Mark any results matching the current top results as having been received 700 // prior to the last keystroke. That prevents asynchronous updates from 701 // clobbering top results, which may be used for inline autocompletion. 702 // Other results don't need similar changes, because they shouldn't be 703 // displayed asynchronously anyway. 704 if (!top_query_suggestion_match_contents_.empty()) { 705 for (SearchSuggestionParser::SuggestResults::iterator sug_it = 706 results->suggest_results.begin(); 707 sug_it != results->suggest_results.end(); ++sug_it) { 708 if (sug_it->match_contents() == top_query_suggestion_match_contents_) 709 sug_it->set_received_after_last_keystroke(false); 710 } 711 } 712 if (top_navigation_suggestion_.is_valid()) { 713 for (SearchSuggestionParser::NavigationResults::iterator nav_it = 714 results->navigation_results.begin(); 715 nav_it != results->navigation_results.end(); ++nav_it) { 716 if (nav_it->url() == top_navigation_suggestion_) 717 nav_it->set_received_after_last_keystroke(false); 718 } 719 } 720 } 721 722 void SearchProvider::ApplyCalculatedSuggestRelevance( 723 SearchSuggestionParser::SuggestResults* list) { 724 for (size_t i = 0; i < list->size(); ++i) { 725 SearchSuggestionParser::SuggestResult& result = (*list)[i]; 726 result.set_relevance( 727 result.CalculateRelevance(input_, providers_.has_keyword_provider()) + 728 (list->size() - i - 1)); 729 result.set_relevance_from_server(false); 730 } 731 } 732 733 void SearchProvider::ApplyCalculatedNavigationRelevance( 734 SearchSuggestionParser::NavigationResults* list) { 735 for (size_t i = 0; i < list->size(); ++i) { 736 SearchSuggestionParser::NavigationResult& result = (*list)[i]; 737 result.set_relevance( 738 result.CalculateRelevance(input_, providers_.has_keyword_provider()) + 739 (list->size() - i - 1)); 740 result.set_relevance_from_server(false); 741 } 742 } 743 744 net::URLFetcher* SearchProvider::CreateSuggestFetcher( 745 int id, 746 const TemplateURL* template_url, 747 const AutocompleteInput& input) { 748 if (!template_url || template_url->suggestions_url().empty()) 749 return NULL; 750 751 // Bail if the suggestion URL is invalid with the given replacements. 752 TemplateURLRef::SearchTermsArgs search_term_args(input.text()); 753 search_term_args.input_type = input.type(); 754 search_term_args.cursor_position = input.cursor_position(); 755 search_term_args.page_classification = input.current_page_classification(); 756 if (OmniboxFieldTrial::EnableAnswersInSuggest()) { 757 search_term_args.session_token = GetSessionToken(); 758 if (!prefetch_data_.full_query_text.empty()) { 759 search_term_args.prefetch_query = 760 base::UTF16ToUTF8(prefetch_data_.full_query_text); 761 search_term_args.prefetch_query_type = 762 base::UTF16ToUTF8(prefetch_data_.query_type); 763 } 764 } 765 GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms( 766 search_term_args, 767 providers_.template_url_service()->search_terms_data())); 768 if (!suggest_url.is_valid()) 769 return NULL; 770 // Send the current page URL if user setting and URL requirements are met and 771 // the user is in the field trial. 772 if (CanSendURL(current_page_url_, suggest_url, template_url, 773 input.current_page_classification(), 774 template_url_service_->search_terms_data(), client_.get()) && 775 OmniboxFieldTrial::InZeroSuggestAfterTypingFieldTrial()) { 776 search_term_args.current_page_url = current_page_url_.spec(); 777 // Create the suggest URL again with the current page URL. 778 suggest_url = GURL(template_url->suggestions_url_ref().ReplaceSearchTerms( 779 search_term_args, 780 providers_.template_url_service()->search_terms_data())); 781 } 782 783 suggest_results_pending_++; 784 LogOmniboxSuggestRequest(REQUEST_SENT); 785 786 net::URLFetcher* fetcher = 787 net::URLFetcher::Create(id, suggest_url, net::URLFetcher::GET, this); 788 fetcher->SetRequestContext(client_->RequestContext()); 789 fetcher->SetLoadFlags(net::LOAD_DO_NOT_SAVE_COOKIES); 790 // Add Chrome experiment state to the request headers. 791 net::HttpRequestHeaders headers; 792 variations::VariationsHttpHeaderProvider::GetInstance()->AppendHeaders( 793 fetcher->GetOriginalURL(), client_->IsOffTheRecord(), false, &headers); 794 fetcher->SetExtraRequestHeaders(headers.ToString()); 795 fetcher->Start(); 796 return fetcher; 797 } 798 799 void SearchProvider::ConvertResultsToAutocompleteMatches() { 800 // Convert all the results to matches and add them to a map, so we can keep 801 // the most relevant match for each result. 802 base::TimeTicks start_time(base::TimeTicks::Now()); 803 MatchMap map; 804 const base::Time no_time; 805 int did_not_accept_keyword_suggestion = 806 keyword_results_.suggest_results.empty() ? 807 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE : 808 TemplateURLRef::NO_SUGGESTION_CHOSEN; 809 810 bool relevance_from_server; 811 int verbatim_relevance = GetVerbatimRelevance(&relevance_from_server); 812 int did_not_accept_default_suggestion = 813 default_results_.suggest_results.empty() ? 814 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE : 815 TemplateURLRef::NO_SUGGESTION_CHOSEN; 816 const TemplateURL* keyword_url = providers_.GetKeywordProviderURL(); 817 if (verbatim_relevance > 0) { 818 const base::string16& trimmed_verbatim = 819 base::CollapseWhitespace(input_.text(), false); 820 821 // Verbatim results don't get suggestions and hence, answers. 822 // Scan previous matches if the last answer-bearing suggestion matches 823 // verbatim, and if so, copy over answer contents. 824 base::string16 answer_contents; 825 base::string16 answer_type; 826 for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); 827 ++it) { 828 if (!it->answer_contents.empty() && 829 it->fill_into_edit == trimmed_verbatim) { 830 answer_contents = it->answer_contents; 831 answer_type = it->answer_type; 832 break; 833 } 834 } 835 836 SearchSuggestionParser::SuggestResult verbatim( 837 trimmed_verbatim, AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED, 838 trimmed_verbatim, base::string16(), base::string16(), answer_contents, 839 answer_type, std::string(), std::string(), false, verbatim_relevance, 840 relevance_from_server, false, trimmed_verbatim); 841 AddMatchToMap(verbatim, std::string(), did_not_accept_default_suggestion, 842 false, keyword_url != NULL, &map); 843 } 844 if (!keyword_input_.text().empty()) { 845 // We only create the verbatim search query match for a keyword 846 // if it's not an extension keyword. Extension keywords are handled 847 // in KeywordProvider::Start(). (Extensions are complicated...) 848 // Note: in this provider, SEARCH_OTHER_ENGINE must correspond 849 // to the keyword verbatim search query. Do not create other matches 850 // of type SEARCH_OTHER_ENGINE. 851 if (keyword_url && 852 (keyword_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) { 853 bool keyword_relevance_from_server; 854 const int keyword_verbatim_relevance = 855 GetKeywordVerbatimRelevance(&keyword_relevance_from_server); 856 if (keyword_verbatim_relevance > 0) { 857 const base::string16& trimmed_verbatim = 858 base::CollapseWhitespace(keyword_input_.text(), false); 859 SearchSuggestionParser::SuggestResult verbatim( 860 trimmed_verbatim, AutocompleteMatchType::SEARCH_OTHER_ENGINE, 861 trimmed_verbatim, base::string16(), base::string16(), 862 base::string16(), base::string16(), std::string(), std::string(), 863 true, keyword_verbatim_relevance, keyword_relevance_from_server, 864 false, trimmed_verbatim); 865 AddMatchToMap(verbatim, std::string(), 866 did_not_accept_keyword_suggestion, false, true, &map); 867 } 868 } 869 } 870 AddRawHistoryResultsToMap(true, did_not_accept_keyword_suggestion, &map); 871 AddRawHistoryResultsToMap(false, did_not_accept_default_suggestion, &map); 872 873 AddSuggestResultsToMap(keyword_results_.suggest_results, 874 keyword_results_.metadata, &map); 875 AddSuggestResultsToMap(default_results_.suggest_results, 876 default_results_.metadata, &map); 877 878 ACMatches matches; 879 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i) 880 matches.push_back(i->second); 881 882 AddNavigationResultsToMatches(keyword_results_.navigation_results, &matches); 883 AddNavigationResultsToMatches(default_results_.navigation_results, &matches); 884 885 // Now add the most relevant matches to |matches_|. We take up to kMaxMatches 886 // suggest/navsuggest matches, regardless of origin. We always include in 887 // that set a legal default match if possible. If Instant Extended is enabled 888 // and we have server-provided (and thus hopefully more accurate) scores for 889 // some suggestions, we allow more of those, until we reach 890 // AutocompleteResult::kMaxMatches total matches (that is, enough to fill the 891 // whole popup). 892 // 893 // We will always return any verbatim matches, no matter how we obtained their 894 // scores, unless we have already accepted AutocompleteResult::kMaxMatches 895 // higher-scoring matches under the conditions above. 896 std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant); 897 898 // Guarantee that if there's a legal default match anywhere in the result 899 // set that it'll get returned. The rotate() call does this by moving the 900 // default match to the front of the list. 901 ACMatches::iterator default_match = FindTopMatch(&matches); 902 if (default_match != matches.end()) 903 std::rotate(matches.begin(), default_match, default_match + 1); 904 905 // It's possible to get a copy of an answer from previous matches and get the 906 // same or a different answer to another server-provided suggestion. In the 907 // future we may decide that we want to have answers attached to multiple 908 // suggestions, but the current assumption is that there should only ever be 909 // one suggestion with an answer. To maintain this assumption, remove any 910 // answers after the first. 911 RemoveExtraAnswers(&matches); 912 913 matches_.clear(); 914 size_t num_suggestions = 0; 915 for (ACMatches::const_iterator i(matches.begin()); 916 (i != matches.end()) && 917 (matches_.size() < AutocompleteResult::kMaxMatches); 918 ++i) { 919 // SEARCH_OTHER_ENGINE is only used in the SearchProvider for the keyword 920 // verbatim result, so this condition basically means "if this match is a 921 // suggestion of some sort". 922 if ((i->type != AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED) && 923 (i->type != AutocompleteMatchType::SEARCH_OTHER_ENGINE)) { 924 // If we've already hit the limit on non-server-scored suggestions, and 925 // this isn't a server-scored suggestion we can add, skip it. 926 if ((num_suggestions >= kMaxMatches) && 927 (!chrome::IsInstantExtendedAPIEnabled() || 928 (i->GetAdditionalInfo(kRelevanceFromServerKey) != kTrue))) { 929 continue; 930 } 931 932 ++num_suggestions; 933 } 934 935 matches_.push_back(*i); 936 } 937 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.ConvertResultsTime", 938 base::TimeTicks::Now() - start_time); 939 } 940 941 void SearchProvider::RemoveExtraAnswers(ACMatches* matches) { 942 bool answer_seen = false; 943 for (ACMatches::iterator it = matches->begin(); it != matches->end(); ++it) { 944 if (!it->answer_contents.empty()) { 945 if (!answer_seen) { 946 answer_seen = true; 947 } else { 948 it->answer_contents.clear(); 949 it->answer_type.clear(); 950 } 951 } 952 } 953 } 954 955 ACMatches::const_iterator SearchProvider::FindTopMatch() const { 956 ACMatches::const_iterator it = matches_.begin(); 957 while ((it != matches_.end()) && !it->allowed_to_be_default_match) 958 ++it; 959 return it; 960 } 961 962 bool SearchProvider::IsTopMatchSearchWithURLInput() const { 963 ACMatches::const_iterator first_match = FindTopMatch(); 964 return (input_.type() == metrics::OmniboxInputType::URL) && 965 (first_match != matches_.end()) && 966 (first_match->relevance > CalculateRelevanceForVerbatim()) && 967 (first_match->type != AutocompleteMatchType::NAVSUGGEST) && 968 (first_match->type != AutocompleteMatchType::NAVSUGGEST_PERSONALIZED); 969 } 970 971 void SearchProvider::AddNavigationResultsToMatches( 972 const SearchSuggestionParser::NavigationResults& navigation_results, 973 ACMatches* matches) { 974 for (SearchSuggestionParser::NavigationResults::const_iterator it = 975 navigation_results.begin(); it != navigation_results.end(); ++it) { 976 matches->push_back(NavigationToMatch(*it)); 977 // In the absence of suggested relevance scores, use only the single 978 // highest-scoring result. (The results are already sorted by relevance.) 979 if (!it->relevance_from_server()) 980 return; 981 } 982 } 983 984 void SearchProvider::AddRawHistoryResultsToMap(bool is_keyword, 985 int did_not_accept_suggestion, 986 MatchMap* map) { 987 const HistoryResults& raw_results = 988 is_keyword ? raw_keyword_history_results_ : raw_default_history_results_; 989 if (!OmniboxFieldTrial::EnableAnswersInSuggest() && raw_results.empty()) 990 return; 991 992 base::TimeTicks start_time(base::TimeTicks::Now()); 993 994 // Until Answers becomes default, scoring of history results will still happen 995 // here for non-Answers Chrome, to prevent scoring performance regressions 996 // resulting from moving the scoring code before the suggest request is sent. 997 // For users with Answers enabled, the history results have already been 998 // scored earlier, right after calling DoHistoryQuery(). 999 SearchSuggestionParser::SuggestResults local_transformed_results; 1000 const SearchSuggestionParser::SuggestResults* transformed_results = NULL; 1001 if (!OmniboxFieldTrial::EnableAnswersInSuggest()) { 1002 ScoreHistoryResults(raw_results, is_keyword, &local_transformed_results); 1003 transformed_results = &local_transformed_results; 1004 } else { 1005 transformed_results = is_keyword ? &transformed_keyword_history_results_ 1006 : &transformed_default_history_results_; 1007 } 1008 DCHECK(transformed_results); 1009 AddTransformedHistoryResultsToMap( 1010 *transformed_results, did_not_accept_suggestion, map); 1011 UMA_HISTOGRAM_TIMES("Omnibox.SearchProvider.AddHistoryResultsTime", 1012 base::TimeTicks::Now() - start_time); 1013 } 1014 1015 void SearchProvider::AddTransformedHistoryResultsToMap( 1016 const SearchSuggestionParser::SuggestResults& transformed_results, 1017 int did_not_accept_suggestion, 1018 MatchMap* map) { 1019 for (SearchSuggestionParser::SuggestResults::const_iterator i( 1020 transformed_results.begin()); 1021 i != transformed_results.end(); 1022 ++i) { 1023 AddMatchToMap(*i, std::string(), did_not_accept_suggestion, true, 1024 providers_.GetKeywordProviderURL() != NULL, map); 1025 } 1026 } 1027 1028 SearchSuggestionParser::SuggestResults 1029 SearchProvider::ScoreHistoryResultsHelper(const HistoryResults& results, 1030 bool base_prevent_inline_autocomplete, 1031 bool input_multiple_words, 1032 const base::string16& input_text, 1033 bool is_keyword) { 1034 SearchSuggestionParser::SuggestResults scored_results; 1035 // True if the user has asked this exact query previously. 1036 bool found_what_you_typed_match = false; 1037 const bool prevent_search_history_inlining = 1038 OmniboxFieldTrial::SearchHistoryPreventInlining( 1039 input_.current_page_classification()); 1040 const base::string16& trimmed_input = 1041 base::CollapseWhitespace(input_text, false); 1042 for (HistoryResults::const_iterator i(results.begin()); i != results.end(); 1043 ++i) { 1044 const base::string16& trimmed_suggestion = 1045 base::CollapseWhitespace(i->term, false); 1046 1047 // Don't autocomplete multi-word queries that have only been seen once 1048 // unless the user has typed more than one word. 1049 bool prevent_inline_autocomplete = base_prevent_inline_autocomplete || 1050 (!input_multiple_words && (i->visits < 2) && 1051 HasMultipleWords(trimmed_suggestion)); 1052 1053 int relevance = CalculateRelevanceForHistory( 1054 i->time, is_keyword, !prevent_inline_autocomplete, 1055 prevent_search_history_inlining); 1056 // Add the match to |scored_results| by putting the what-you-typed match 1057 // on the front and appending all other matches. We want the what-you- 1058 // typed match to always be first. 1059 SearchSuggestionParser::SuggestResults::iterator insertion_position = 1060 scored_results.end(); 1061 if (trimmed_suggestion == trimmed_input) { 1062 found_what_you_typed_match = true; 1063 insertion_position = scored_results.begin(); 1064 } 1065 SearchSuggestionParser::SuggestResult history_suggestion( 1066 trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY, 1067 trimmed_suggestion, base::string16(), base::string16(), 1068 base::string16(), base::string16(), std::string(), std::string(), 1069 is_keyword, relevance, false, false, trimmed_input); 1070 // History results are synchronous; they are received on the last keystroke. 1071 history_suggestion.set_received_after_last_keystroke(false); 1072 scored_results.insert(insertion_position, history_suggestion); 1073 } 1074 1075 // History returns results sorted for us. However, we may have docked some 1076 // results' scores, so things are no longer in order. While keeping the 1077 // what-you-typed match at the front (if it exists), do a stable sort to get 1078 // things back in order without otherwise disturbing results with equal 1079 // scores, then force the scores to be unique, so that the order in which 1080 // they're shown is deterministic. 1081 std::stable_sort(scored_results.begin() + 1082 (found_what_you_typed_match ? 1 : 0), 1083 scored_results.end(), 1084 CompareScoredResults()); 1085 1086 // Don't autocomplete to search terms that would normally be treated as URLs 1087 // when typed. For example, if the user searched for "google.com" and types 1088 // "goog", don't autocomplete to the search term "google.com". Otherwise, 1089 // the input will look like a URL but act like a search, which is confusing. 1090 // The 1200 relevance score threshold in the test below is the lowest 1091 // possible score in CalculateRelevanceForHistory()'s aggressive-scoring 1092 // curve. This is an appropriate threshold to use to decide if we're overly 1093 // aggressively inlining because, if we decide the answer is yes, the 1094 // way we resolve it it to not use the aggressive-scoring curve. 1095 // NOTE: We don't check for autocompleting to URLs in the following cases: 1096 // * When inline autocomplete is disabled, we won't be inline autocompleting 1097 // this term, so we don't need to worry about confusion as much. This 1098 // also prevents calling Classify() again from inside the classifier 1099 // (which will corrupt state and likely crash), since the classifier 1100 // always disables inline autocomplete. 1101 // * When the user has typed the whole string before as a query, then it's 1102 // likely the user has no expectation that term should be interpreted as 1103 // as a URL, so we need not do anything special to preserve user 1104 // expectation. 1105 int last_relevance = 0; 1106 if (!base_prevent_inline_autocomplete && !found_what_you_typed_match && 1107 scored_results.front().relevance() >= 1200) { 1108 AutocompleteMatch match; 1109 client_->Classify(scored_results.front().suggestion(), false, false, 1110 input_.current_page_classification(), &match, NULL); 1111 // Demote this match that would normally be interpreted as a URL to have 1112 // the highest score a previously-issued search query could have when 1113 // scoring with the non-aggressive method. A consequence of demoting 1114 // by revising |last_relevance| is that this match and all following 1115 // matches get demoted; the relative order of matches is preserved. 1116 // One could imagine demoting only those matches that might cause 1117 // confusion (which, by the way, might change the relative order of 1118 // matches. We have decided to go with the simple demote-all approach 1119 // because selective demotion requires multiple Classify() calls and 1120 // such calls can be expensive (as expensive as running the whole 1121 // autocomplete system). 1122 if (!AutocompleteMatch::IsSearchType(match.type)) { 1123 last_relevance = CalculateRelevanceForHistory( 1124 base::Time::Now(), is_keyword, false, 1125 prevent_search_history_inlining); 1126 } 1127 } 1128 1129 for (SearchSuggestionParser::SuggestResults::iterator i( 1130 scored_results.begin()); i != scored_results.end(); ++i) { 1131 if ((last_relevance != 0) && (i->relevance() >= last_relevance)) 1132 i->set_relevance(last_relevance - 1); 1133 last_relevance = i->relevance(); 1134 } 1135 1136 return scored_results; 1137 } 1138 1139 void SearchProvider::ScoreHistoryResults( 1140 const HistoryResults& results, 1141 bool is_keyword, 1142 SearchSuggestionParser::SuggestResults* scored_results) { 1143 DCHECK(scored_results); 1144 if (results.empty()) { 1145 scored_results->clear(); 1146 return; 1147 } 1148 1149 bool prevent_inline_autocomplete = input_.prevent_inline_autocomplete() || 1150 (input_.type() == metrics::OmniboxInputType::URL); 1151 const base::string16 input_text = GetInput(is_keyword).text(); 1152 bool input_multiple_words = HasMultipleWords(input_text); 1153 1154 if (!prevent_inline_autocomplete && input_multiple_words) { 1155 // ScoreHistoryResultsHelper() allows autocompletion of multi-word, 1-visit 1156 // queries if the input also has multiple words. But if we were already 1157 // scoring a multi-word, multi-visit query aggressively, and the current 1158 // input is still a prefix of it, then changing the suggestion suddenly 1159 // feels wrong. To detect this case, first score as if only one word has 1160 // been typed, then check if the best result came from aggressive search 1161 // history scoring. If it did, then just keep that score set. This 1162 // 1200 the lowest possible score in CalculateRelevanceForHistory()'s 1163 // aggressive-scoring curve. 1164 *scored_results = ScoreHistoryResultsHelper( 1165 results, prevent_inline_autocomplete, false, input_text, is_keyword); 1166 if ((scored_results->front().relevance() < 1200) || 1167 !HasMultipleWords(scored_results->front().suggestion())) 1168 scored_results->clear(); // Didn't detect the case above, score normally. 1169 } 1170 if (scored_results->empty()) { 1171 *scored_results = ScoreHistoryResultsHelper(results, 1172 prevent_inline_autocomplete, 1173 input_multiple_words, 1174 input_text, 1175 is_keyword); 1176 } 1177 } 1178 1179 void SearchProvider::AddSuggestResultsToMap( 1180 const SearchSuggestionParser::SuggestResults& results, 1181 const std::string& metadata, 1182 MatchMap* map) { 1183 for (size_t i = 0; i < results.size(); ++i) { 1184 AddMatchToMap(results[i], metadata, i, false, 1185 providers_.GetKeywordProviderURL() != NULL, map); 1186 } 1187 } 1188 1189 int SearchProvider::GetVerbatimRelevance(bool* relevance_from_server) const { 1190 // Use the suggested verbatim relevance score if it is non-negative (valid), 1191 // if inline autocomplete isn't prevented (always show verbatim on backspace), 1192 // and if it won't suppress verbatim, leaving no default provider matches. 1193 // Otherwise, if the default provider returned no matches and was still able 1194 // to suppress verbatim, the user would have no search/nav matches and may be 1195 // left unable to search using their default provider from the omnibox. 1196 // Check for results on each verbatim calculation, as results from older 1197 // queries (on previous input) may be trimmed for failing to inline new input. 1198 bool use_server_relevance = 1199 (default_results_.verbatim_relevance >= 0) && 1200 !input_.prevent_inline_autocomplete() && 1201 ((default_results_.verbatim_relevance > 0) || 1202 !default_results_.suggest_results.empty() || 1203 !default_results_.navigation_results.empty()); 1204 if (relevance_from_server) 1205 *relevance_from_server = use_server_relevance; 1206 return use_server_relevance ? 1207 default_results_.verbatim_relevance : CalculateRelevanceForVerbatim(); 1208 } 1209 1210 int SearchProvider::CalculateRelevanceForVerbatim() const { 1211 if (!providers_.keyword_provider().empty()) 1212 return 250; 1213 return CalculateRelevanceForVerbatimIgnoringKeywordModeState(); 1214 } 1215 1216 int SearchProvider:: 1217 CalculateRelevanceForVerbatimIgnoringKeywordModeState() const { 1218 switch (input_.type()) { 1219 case metrics::OmniboxInputType::UNKNOWN: 1220 case metrics::OmniboxInputType::QUERY: 1221 case metrics::OmniboxInputType::FORCED_QUERY: 1222 return kNonURLVerbatimRelevance; 1223 1224 case metrics::OmniboxInputType::URL: 1225 return 850; 1226 1227 default: 1228 NOTREACHED(); 1229 return 0; 1230 } 1231 } 1232 1233 int SearchProvider::GetKeywordVerbatimRelevance( 1234 bool* relevance_from_server) const { 1235 // Use the suggested verbatim relevance score if it is non-negative (valid), 1236 // if inline autocomplete isn't prevented (always show verbatim on backspace), 1237 // and if it won't suppress verbatim, leaving no keyword provider matches. 1238 // Otherwise, if the keyword provider returned no matches and was still able 1239 // to suppress verbatim, the user would have no search/nav matches and may be 1240 // left unable to search using their keyword provider from the omnibox. 1241 // Check for results on each verbatim calculation, as results from older 1242 // queries (on previous input) may be trimmed for failing to inline new input. 1243 bool use_server_relevance = 1244 (keyword_results_.verbatim_relevance >= 0) && 1245 !input_.prevent_inline_autocomplete() && 1246 ((keyword_results_.verbatim_relevance > 0) || 1247 !keyword_results_.suggest_results.empty() || 1248 !keyword_results_.navigation_results.empty()); 1249 if (relevance_from_server) 1250 *relevance_from_server = use_server_relevance; 1251 return use_server_relevance ? 1252 keyword_results_.verbatim_relevance : 1253 CalculateRelevanceForKeywordVerbatim(keyword_input_.type(), 1254 keyword_input_.prefer_keyword()); 1255 } 1256 1257 int SearchProvider::CalculateRelevanceForHistory( 1258 const base::Time& time, 1259 bool is_keyword, 1260 bool use_aggressive_method, 1261 bool prevent_search_history_inlining) const { 1262 // The relevance of past searches falls off over time. There are two distinct 1263 // equations used. If the first equation is used (searches to the primary 1264 // provider that we want to score aggressively), the score is in the range 1265 // 1300-1599 (unless |prevent_search_history_inlining|, in which case 1266 // it's in the range 1200-1299). If the second equation is used the 1267 // relevance of a search 15 minutes ago is discounted 50 points, while the 1268 // relevance of a search two weeks ago is discounted 450 points. 1269 double elapsed_time = std::max((base::Time::Now() - time).InSecondsF(), 0.0); 1270 bool is_primary_provider = is_keyword || !providers_.has_keyword_provider(); 1271 if (is_primary_provider && use_aggressive_method) { 1272 // Searches with the past two days get a different curve. 1273 const double autocomplete_time = 2 * 24 * 60 * 60; 1274 if (elapsed_time < autocomplete_time) { 1275 int max_score = is_keyword ? 1599 : 1399; 1276 if (prevent_search_history_inlining) 1277 max_score = 1299; 1278 return max_score - static_cast<int>(99 * 1279 std::pow(elapsed_time / autocomplete_time, 2.5)); 1280 } 1281 elapsed_time -= autocomplete_time; 1282 } 1283 1284 const int score_discount = 1285 static_cast<int>(6.5 * std::pow(elapsed_time, 0.3)); 1286 1287 // Don't let scores go below 0. Negative relevance scores are meaningful in 1288 // a different way. 1289 int base_score; 1290 if (is_primary_provider) 1291 base_score = (input_.type() == metrics::OmniboxInputType::URL) ? 750 : 1050; 1292 else 1293 base_score = 200; 1294 return std::max(0, base_score - score_discount); 1295 } 1296 1297 AutocompleteMatch SearchProvider::NavigationToMatch( 1298 const SearchSuggestionParser::NavigationResult& navigation) { 1299 base::string16 input; 1300 const bool trimmed_whitespace = base::TrimWhitespace( 1301 navigation.from_keyword_provider() ? 1302 keyword_input_.text() : input_.text(), 1303 base::TRIM_TRAILING, &input) != base::TRIM_NONE; 1304 AutocompleteMatch match(this, navigation.relevance(), false, 1305 navigation.type()); 1306 match.destination_url = navigation.url(); 1307 BaseSearchProvider::SetDeletionURL(navigation.deletion_url(), &match); 1308 // First look for the user's input inside the formatted url as it would be 1309 // without trimming the scheme, so we can find matches at the beginning of the 1310 // scheme. 1311 const URLPrefix* prefix = 1312 URLPrefix::BestURLPrefix(navigation.formatted_url(), input); 1313 size_t match_start = (prefix == NULL) ? 1314 navigation.formatted_url().find(input) : prefix->prefix.length(); 1315 bool trim_http = !AutocompleteInput::HasHTTPScheme(input) && 1316 (!prefix || (match_start != 0)); 1317 const net::FormatUrlTypes format_types = 1318 net::kFormatUrlOmitAll & ~(trim_http ? 0 : net::kFormatUrlOmitHTTP); 1319 1320 const std::string languages(client_->AcceptLanguages()); 1321 size_t inline_autocomplete_offset = (prefix == NULL) ? 1322 base::string16::npos : (match_start + input.length()); 1323 match.fill_into_edit += 1324 AutocompleteInput::FormattedStringWithEquivalentMeaning( 1325 navigation.url(), 1326 net::FormatUrl(navigation.url(), languages, format_types, 1327 net::UnescapeRule::SPACES, NULL, NULL, 1328 &inline_autocomplete_offset), 1329 client_->SchemeClassifier()); 1330 // Preserve the forced query '?' prefix in |match.fill_into_edit|. 1331 // Otherwise, user edits to a suggestion would show non-Search results. 1332 if (input_.type() == metrics::OmniboxInputType::FORCED_QUERY) { 1333 match.fill_into_edit.insert(0, base::ASCIIToUTF16("?")); 1334 if (inline_autocomplete_offset != base::string16::npos) 1335 ++inline_autocomplete_offset; 1336 } 1337 if (inline_autocomplete_offset != base::string16::npos) { 1338 DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length()); 1339 match.inline_autocompletion = 1340 match.fill_into_edit.substr(inline_autocomplete_offset); 1341 } 1342 // An inlineable navsuggestion can only be the default match when there 1343 // is no keyword provider active, lest it appear first and break the user 1344 // out of keyword mode. We also must have received the navsuggestion before 1345 // the last keystroke, to prevent asynchronous inline autocompletions changes. 1346 // The navsuggestion can also only be default if either the inline 1347 // autocompletion is empty or we're not preventing inline autocompletion. 1348 // Finally, if we have an inlineable navsuggestion with an inline completion 1349 // that we're not preventing, make sure we didn't trim any whitespace. 1350 // We don't want to claim http://foo.com/bar is inlineable against the 1351 // input "foo.com/b ". 1352 match.allowed_to_be_default_match = 1353 (prefix != NULL) && 1354 (providers_.GetKeywordProviderURL() == NULL) && 1355 !navigation.received_after_last_keystroke() && 1356 (match.inline_autocompletion.empty() || 1357 (!input_.prevent_inline_autocomplete() && !trimmed_whitespace)); 1358 match.EnsureUWYTIsAllowedToBeDefault( 1359 input_.canonicalized_url(), providers_.template_url_service()); 1360 1361 match.contents = navigation.match_contents(); 1362 match.contents_class = navigation.match_contents_class(); 1363 match.description = navigation.description(); 1364 AutocompleteMatch::ClassifyMatchInString(input, match.description, 1365 ACMatchClassification::NONE, &match.description_class); 1366 1367 match.RecordAdditionalInfo( 1368 kRelevanceFromServerKey, 1369 navigation.relevance_from_server() ? kTrue : kFalse); 1370 match.RecordAdditionalInfo(kShouldPrefetchKey, kFalse); 1371 1372 return match; 1373 } 1374 1375 void SearchProvider::UpdateDone() { 1376 // We're done when the timer isn't running, there are no suggest queries 1377 // pending, and we're not waiting on Instant. 1378 done_ = !timer_.IsRunning() && (suggest_results_pending_ == 0); 1379 } 1380 1381 std::string SearchProvider::GetSessionToken() { 1382 base::TimeTicks current_time(base::TimeTicks::Now()); 1383 // Renew token if it expired. 1384 if (current_time > token_expiration_time_) { 1385 const size_t kTokenBytes = 12; 1386 std::string raw_data; 1387 base::RandBytes(WriteInto(&raw_data, kTokenBytes + 1), kTokenBytes); 1388 base::Base64Encode(raw_data, ¤t_token_); 1389 1390 // Make the base64 encoded value URL and filename safe(see RFC 3548). 1391 std::replace(current_token_.begin(), current_token_.end(), '+', '-'); 1392 std::replace(current_token_.begin(), current_token_.end(), '/', '_'); 1393 } 1394 1395 // Extend expiration time another 60 seconds. 1396 token_expiration_time_ = current_time + base::TimeDelta::FromSeconds(60); 1397 1398 return current_token_; 1399 } 1400 1401 void SearchProvider::RegisterDisplayedAnswers( 1402 const AutocompleteResult& result) { 1403 if (result.empty()) 1404 return; 1405 1406 // The answer must be in the first or second slot to be considered. It should 1407 // only be in the second slot if AutocompleteController ranked a local search 1408 // history or a verbatim item higher than the answer. 1409 AutocompleteResult::const_iterator match = result.begin(); 1410 if (match->answer_contents.empty() && result.size() > 1) 1411 ++match; 1412 if (match->answer_contents.empty() || match->answer_type.empty() || 1413 match->fill_into_edit.empty()) 1414 return; 1415 1416 // Valid answer encountered, cache it for further queries. 1417 answers_cache_.UpdateRecentAnswers(match->fill_into_edit, match->answer_type); 1418 } 1419 1420 AnswersQueryData SearchProvider::FindAnswersPrefetchData() { 1421 // Retrieve the top entry from scored history results. 1422 MatchMap map; 1423 AddTransformedHistoryResultsToMap(transformed_keyword_history_results_, 1424 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE, 1425 &map); 1426 AddTransformedHistoryResultsToMap(transformed_default_history_results_, 1427 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE, 1428 &map); 1429 1430 ACMatches matches; 1431 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i) 1432 matches.push_back(i->second); 1433 std::sort(matches.begin(), matches.end(), &AutocompleteMatch::MoreRelevant); 1434 1435 // If there is a top scoring entry, find the corresponding answer. 1436 if (!matches.empty()) 1437 return answers_cache_.GetTopAnswerEntry(matches[0].contents); 1438 1439 return AnswersQueryData(); 1440 } 1441