1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/autocomplete/search_provider.h" 6 7 #include <algorithm> 8 #include <cmath> 9 10 #include "base/callback.h" 11 #include "base/i18n/icu_string_conversions.h" 12 #include "base/message_loop.h" 13 #include "base/string16.h" 14 #include "base/utf_string_conversions.h" 15 #include "chrome/browser/autocomplete/autocomplete_classifier.h" 16 #include "chrome/browser/autocomplete/keyword_provider.h" 17 #include "chrome/browser/autocomplete/autocomplete_match.h" 18 #include "chrome/browser/google/google_util.h" 19 #include "chrome/browser/history/history.h" 20 #include "chrome/browser/instant/instant_controller.h" 21 #include "chrome/browser/net/url_fixer_upper.h" 22 #include "chrome/browser/prefs/pref_service.h" 23 #include "chrome/browser/profiles/profile.h" 24 #include "chrome/browser/history/in_memory_database.h" 25 #include "chrome/browser/search_engines/template_url_model.h" 26 #include "chrome/common/pref_names.h" 27 #include "chrome/common/url_constants.h" 28 #include "content/common/json_value_serializer.h" 29 #include "googleurl/src/url_util.h" 30 #include "grit/generated_resources.h" 31 #include "net/base/escape.h" 32 #include "net/http/http_response_headers.h" 33 #include "net/url_request/url_request_status.h" 34 #include "ui/base/l10n/l10n_util.h" 35 36 using base::Time; 37 using base::TimeDelta; 38 39 // static 40 const int SearchProvider::kDefaultProviderURLFetcherID = 1; 41 // static 42 const int SearchProvider::kKeywordProviderURLFetcherID = 2; 43 44 // static 45 bool SearchProvider::query_suggest_immediately_ = false; 46 47 void SearchProvider::Providers::Set(const TemplateURL* default_provider, 48 const TemplateURL* keyword_provider) { 49 // TODO(pkasting): http://b/1162970 We shouldn't need to structure-copy 50 // this. Nor should we need |default_provider_| and |keyword_provider_| 51 // just to know whether the provider changed. 52 default_provider_ = default_provider; 53 if (default_provider) 54 cached_default_provider_ = *default_provider; 55 keyword_provider_ = keyword_provider; 56 if (keyword_provider) 57 cached_keyword_provider_ = *keyword_provider; 58 } 59 60 SearchProvider::SearchProvider(ACProviderListener* listener, Profile* profile) 61 : AutocompleteProvider(listener, profile, "Search"), 62 suggest_results_pending_(0), 63 have_suggest_results_(false), 64 instant_finalized_(false) { 65 } 66 67 void SearchProvider::FinalizeInstantQuery(const string16& input_text, 68 const string16& suggest_text) { 69 if (done_ || instant_finalized_) 70 return; 71 72 instant_finalized_ = true; 73 UpdateDone(); 74 75 if (input_text.empty()) { 76 // We only need to update the listener if we're actually done. 77 if (done_) 78 listener_->OnProviderUpdate(false); 79 return; 80 } 81 82 default_provider_suggest_text_ = suggest_text; 83 84 string16 adjusted_input_text(input_text); 85 AutocompleteInput::RemoveForcedQueryStringIfNecessary(input_.type(), 86 &adjusted_input_text); 87 88 const string16 text = adjusted_input_text + suggest_text; 89 // Remove any matches that are identical to |text|. We don't use the 90 // destination_url for comparison as it varies depending upon the index passed 91 // to TemplateURL::ReplaceSearchTerms. 92 for (ACMatches::iterator i = matches_.begin(); i != matches_.end();) { 93 // Reset the description/description_class of all searches. We'll set the 94 // description of the new first match in the call to 95 // UpdateFirstSearchMatchDescription() below. 96 if ((i->type == AutocompleteMatch::SEARCH_HISTORY) || 97 (i->type == AutocompleteMatch::SEARCH_SUGGEST) || 98 (i->type == AutocompleteMatch::SEARCH_WHAT_YOU_TYPED)) { 99 i->description.clear(); 100 i->description_class.clear(); 101 } 102 103 if (((i->type == AutocompleteMatch::SEARCH_HISTORY) || 104 (i->type == AutocompleteMatch::SEARCH_SUGGEST)) && 105 (i->fill_into_edit == text)) { 106 i = matches_.erase(i); 107 } else { 108 ++i; 109 } 110 } 111 112 // Add the new suggest result. We give it a rank higher than 113 // SEARCH_WHAT_YOU_TYPED so that it gets autocompleted. 114 int did_not_accept_default_suggestion = default_suggest_results_.empty() ? 115 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE : 116 TemplateURLRef::NO_SUGGESTION_CHOSEN; 117 MatchMap match_map; 118 AddMatchToMap(text, adjusted_input_text, 119 CalculateRelevanceForWhatYouTyped() + 1, 120 AutocompleteMatch::SEARCH_SUGGEST, 121 did_not_accept_default_suggestion, false, 122 input_.initial_prevent_inline_autocomplete(), &match_map); 123 DCHECK_EQ(1u, match_map.size()); 124 matches_.push_back(match_map.begin()->second); 125 // Sort the results so that UpdateFirstSearchDescription does the right thing. 126 std::sort(matches_.begin(), matches_.end(), &AutocompleteMatch::MoreRelevant); 127 128 UpdateFirstSearchMatchDescription(); 129 130 listener_->OnProviderUpdate(true); 131 } 132 133 void SearchProvider::Start(const AutocompleteInput& input, 134 bool minimal_changes) { 135 matches_.clear(); 136 137 instant_finalized_ = 138 (input.matches_requested() != AutocompleteInput::ALL_MATCHES); 139 140 // Can't return search/suggest results for bogus input or without a profile. 141 if (!profile_ || (input.type() == AutocompleteInput::INVALID)) { 142 Stop(); 143 return; 144 } 145 146 keyword_input_text_.clear(); 147 const TemplateURL* keyword_provider = 148 KeywordProvider::GetSubstitutingTemplateURLForInput(profile_, input, 149 &keyword_input_text_); 150 if (keyword_input_text_.empty()) 151 keyword_provider = NULL; 152 153 const TemplateURL* default_provider = 154 profile_->GetTemplateURLModel()->GetDefaultSearchProvider(); 155 if (!TemplateURL::SupportsReplacement(default_provider)) 156 default_provider = NULL; 157 158 if (keyword_provider == default_provider) 159 keyword_provider = NULL; // No use in querying the same provider twice. 160 161 if (!default_provider && !keyword_provider) { 162 // No valid providers. 163 Stop(); 164 return; 165 } 166 167 // If we're still running an old query but have since changed the query text 168 // or the providers, abort the query. 169 if (!minimal_changes || 170 !providers_.equals(default_provider, keyword_provider)) { 171 if (done_) 172 default_provider_suggest_text_.clear(); 173 else 174 Stop(); 175 } else if (minimal_changes && 176 (input_.original_text() != input.original_text())) { 177 default_provider_suggest_text_.clear(); 178 } 179 180 providers_.Set(default_provider, keyword_provider); 181 182 if (input.text().empty()) { 183 // User typed "?" alone. Give them a placeholder result indicating what 184 // this syntax does. 185 if (default_provider) { 186 AutocompleteMatch match; 187 match.provider = this; 188 match.contents.assign(l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE)); 189 match.contents_class.push_back( 190 ACMatchClassification(0, ACMatchClassification::NONE)); 191 matches_.push_back(match); 192 UpdateFirstSearchMatchDescription(); 193 } 194 Stop(); 195 return; 196 } 197 198 input_ = input; 199 200 DoHistoryQuery(minimal_changes); 201 StartOrStopSuggestQuery(minimal_changes); 202 ConvertResultsToAutocompleteMatches(); 203 } 204 205 void SearchProvider::Run() { 206 // Start a new request with the current input. 207 DCHECK(!done_); 208 suggest_results_pending_ = 0; 209 if (providers_.valid_suggest_for_keyword_provider()) { 210 suggest_results_pending_++; 211 keyword_fetcher_.reset( 212 CreateSuggestFetcher(kKeywordProviderURLFetcherID, 213 providers_.keyword_provider(), 214 keyword_input_text_)); 215 } 216 if (providers_.valid_suggest_for_default_provider()) { 217 suggest_results_pending_++; 218 default_fetcher_.reset( 219 CreateSuggestFetcher(kDefaultProviderURLFetcherID, 220 providers_.default_provider(), input_.text())); 221 } 222 // We should only get here if we have a suggest url for the keyword or default 223 // providers. 224 DCHECK_GT(suggest_results_pending_, 0); 225 } 226 227 void SearchProvider::Stop() { 228 StopSuggest(); 229 done_ = true; 230 default_provider_suggest_text_.clear(); 231 } 232 233 void SearchProvider::OnURLFetchComplete(const URLFetcher* source, 234 const GURL& url, 235 const net::URLRequestStatus& status, 236 int response_code, 237 const ResponseCookies& cookie, 238 const std::string& data) { 239 DCHECK(!done_); 240 suggest_results_pending_--; 241 DCHECK_GE(suggest_results_pending_, 0); // Should never go negative. 242 const net::HttpResponseHeaders* const response_headers = 243 source->response_headers(); 244 std::string json_data(data); 245 // JSON is supposed to be UTF-8, but some suggest service providers send JSON 246 // files in non-UTF-8 encodings. The actual encoding is usually specified in 247 // the Content-Type header field. 248 if (response_headers) { 249 std::string charset; 250 if (response_headers->GetCharset(&charset)) { 251 string16 data_16; 252 // TODO(jungshik): Switch to CodePageToUTF8 after it's added. 253 if (base::CodepageToUTF16(data, charset.c_str(), 254 base::OnStringConversionError::FAIL, 255 &data_16)) 256 json_data = UTF16ToUTF8(data_16); 257 } 258 } 259 260 bool is_keyword_results = (source == keyword_fetcher_.get()); 261 SuggestResults* suggest_results = is_keyword_results ? 262 &keyword_suggest_results_ : &default_suggest_results_; 263 264 if (status.is_success() && response_code == 200) { 265 JSONStringValueSerializer deserializer(json_data); 266 deserializer.set_allow_trailing_comma(true); 267 scoped_ptr<Value> root_val(deserializer.Deserialize(NULL, NULL)); 268 const string16& input_text = 269 is_keyword_results ? keyword_input_text_ : input_.text(); 270 have_suggest_results_ = 271 root_val.get() && 272 ParseSuggestResults(root_val.get(), is_keyword_results, input_text, 273 suggest_results); 274 } 275 276 ConvertResultsToAutocompleteMatches(); 277 listener_->OnProviderUpdate(!suggest_results->empty()); 278 } 279 280 SearchProvider::~SearchProvider() { 281 } 282 283 void SearchProvider::DoHistoryQuery(bool minimal_changes) { 284 // The history query results are synchronous, so if minimal_changes is true, 285 // we still have the last results and don't need to do anything. 286 if (minimal_changes) 287 return; 288 289 keyword_history_results_.clear(); 290 default_history_results_.clear(); 291 292 HistoryService* const history_service = 293 profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); 294 history::URLDatabase* url_db = history_service ? 295 history_service->InMemoryDatabase() : NULL; 296 if (!url_db) 297 return; 298 299 // Request history for both the keyword and default provider. 300 if (providers_.valid_keyword_provider()) { 301 url_db->GetMostRecentKeywordSearchTerms( 302 providers_.keyword_provider().id(), 303 keyword_input_text_, 304 static_cast<int>(kMaxMatches), 305 &keyword_history_results_); 306 } 307 if (providers_.valid_default_provider()) { 308 url_db->GetMostRecentKeywordSearchTerms( 309 providers_.default_provider().id(), 310 input_.text(), 311 static_cast<int>(kMaxMatches), 312 &default_history_results_); 313 } 314 } 315 316 void SearchProvider::StartOrStopSuggestQuery(bool minimal_changes) { 317 // Don't send any queries to the server until some time has elapsed after 318 // the last keypress, to avoid flooding the server with requests we are 319 // likely to end up throwing away anyway. 320 static const int kQueryDelayMs = 200; 321 322 if (!IsQuerySuitableForSuggest()) { 323 StopSuggest(); 324 return; 325 } 326 327 // For the minimal_changes case, if we finished the previous query and still 328 // have its results, or are allowed to keep running it, just do that, rather 329 // than starting a new query. 330 if (minimal_changes && 331 (have_suggest_results_ || 332 (!done_ && 333 input_.matches_requested() == AutocompleteInput::ALL_MATCHES))) 334 return; 335 336 // We can't keep running any previous query, so halt it. 337 StopSuggest(); 338 339 // We can't start a new query if we're only allowed synchronous results. 340 if (input_.matches_requested() != AutocompleteInput::ALL_MATCHES) 341 return; 342 343 // We'll have at least one pending fetch. Set it to 1 now, but the value is 344 // correctly set in Run. As Run isn't invoked immediately we need to set this 345 // now, else we won't think we're waiting on results from the server when we 346 // really are. 347 suggest_results_pending_ = 1; 348 349 // Kick off a timer that will start the URL fetch if it completes before 350 // the user types another character. 351 int delay = query_suggest_immediately_ ? 0 : kQueryDelayMs; 352 timer_.Start(TimeDelta::FromMilliseconds(delay), this, &SearchProvider::Run); 353 } 354 355 bool SearchProvider::IsQuerySuitableForSuggest() const { 356 // Don't run Suggest in incognito mode, the engine doesn't support it, or 357 // the user has disabled it. 358 if (profile_->IsOffTheRecord() || 359 (!providers_.valid_suggest_for_keyword_provider() && 360 !providers_.valid_suggest_for_default_provider()) || 361 !profile_->GetPrefs()->GetBoolean(prefs::kSearchSuggestEnabled)) 362 return false; 363 364 // If the input type might be a URL, we take extra care so that private data 365 // isn't sent to the server. 366 367 // FORCED_QUERY means the user is explicitly asking us to search for this, so 368 // we assume it isn't a URL and/or there isn't private data. 369 if (input_.type() == AutocompleteInput::FORCED_QUERY) 370 return true; 371 372 // Next we check the scheme. If this is UNKNOWN/REQUESTED_URL/URL with a 373 // scheme that isn't http/https/ftp, we shouldn't send it. Sending things 374 // like file: and data: is both a waste of time and a disclosure of 375 // potentially private, local data. Other "schemes" may actually be 376 // usernames, and we don't want to send passwords. If the scheme is OK, we 377 // still need to check other cases below. If this is QUERY, then the presence 378 // of these schemes means the user explicitly typed one, and thus this is 379 // probably a URL that's being entered and happens to currently be invalid -- 380 // in which case we again want to run our checks below. Other QUERY cases are 381 // less likely to be URLs and thus we assume we're OK. 382 if (!LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpScheme) && 383 !LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpsScheme) && 384 !LowerCaseEqualsASCII(input_.scheme(), chrome::kFtpScheme)) 385 return (input_.type() == AutocompleteInput::QUERY); 386 387 // Don't send URLs with usernames, queries or refs. Some of these are 388 // private, and the Suggest server is unlikely to have any useful results 389 // for any of them. Also don't send URLs with ports, as we may initially 390 // think that a username + password is a host + port (and we don't want to 391 // send usernames/passwords), and even if the port really is a port, the 392 // server is once again unlikely to have and useful results. 393 const url_parse::Parsed& parts = input_.parts(); 394 if (parts.username.is_nonempty() || parts.port.is_nonempty() || 395 parts.query.is_nonempty() || parts.ref.is_nonempty()) 396 return false; 397 398 // Don't send anything for https except the hostname. Hostnames are OK 399 // because they are visible when the TCP connection is established, but the 400 // specific path may reveal private information. 401 if (LowerCaseEqualsASCII(input_.scheme(), chrome::kHttpsScheme) && 402 parts.path.is_nonempty()) 403 return false; 404 405 return true; 406 } 407 408 void SearchProvider::StopSuggest() { 409 suggest_results_pending_ = 0; 410 timer_.Stop(); 411 // Stop any in-progress URL fetches. 412 keyword_fetcher_.reset(); 413 default_fetcher_.reset(); 414 keyword_suggest_results_.clear(); 415 default_suggest_results_.clear(); 416 keyword_navigation_results_.clear(); 417 default_navigation_results_.clear(); 418 have_suggest_results_ = false; 419 } 420 421 URLFetcher* SearchProvider::CreateSuggestFetcher(int id, 422 const TemplateURL& provider, 423 const string16& text) { 424 const TemplateURLRef* const suggestions_url = provider.suggestions_url(); 425 DCHECK(suggestions_url->SupportsReplacement()); 426 URLFetcher* fetcher = URLFetcher::Create(id, 427 GURL(suggestions_url->ReplaceSearchTerms( 428 provider, text, 429 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE, string16())), 430 URLFetcher::GET, this); 431 fetcher->set_request_context(profile_->GetRequestContext()); 432 fetcher->Start(); 433 return fetcher; 434 } 435 436 bool SearchProvider::ParseSuggestResults(Value* root_val, 437 bool is_keyword, 438 const string16& input_text, 439 SuggestResults* suggest_results) { 440 if (!root_val->IsType(Value::TYPE_LIST)) 441 return false; 442 ListValue* root_list = static_cast<ListValue*>(root_val); 443 444 Value* query_val; 445 string16 query_str; 446 Value* result_val; 447 if ((root_list->GetSize() < 2) || !root_list->Get(0, &query_val) || 448 !query_val->GetAsString(&query_str) || 449 (query_str != input_text) || 450 !root_list->Get(1, &result_val) || !result_val->IsType(Value::TYPE_LIST)) 451 return false; 452 453 ListValue* description_list = NULL; 454 if (root_list->GetSize() > 2) { 455 // 3rd element: Description list. 456 Value* description_val; 457 if (root_list->Get(2, &description_val) && 458 description_val->IsType(Value::TYPE_LIST)) 459 description_list = static_cast<ListValue*>(description_val); 460 } 461 462 // We don't care about the query URL list (the fourth element in the 463 // response) for now. 464 465 // Parse optional data in the results from the Suggest server if any. 466 ListValue* type_list = NULL; 467 // 5th argument: Optional key-value pairs. 468 // TODO: We may iterate the 5th+ arguments of the root_list if any other 469 // optional data are defined. 470 if (root_list->GetSize() > 4) { 471 Value* optional_val; 472 if (root_list->Get(4, &optional_val) && 473 optional_val->IsType(Value::TYPE_DICTIONARY)) { 474 DictionaryValue* dict_val = static_cast<DictionaryValue*>(optional_val); 475 476 // Parse Google Suggest specific type extension. 477 static const std::string kGoogleSuggestType("google:suggesttype"); 478 if (dict_val->HasKey(kGoogleSuggestType)) 479 dict_val->GetList(kGoogleSuggestType, &type_list); 480 } 481 } 482 483 ListValue* result_list = static_cast<ListValue*>(result_val); 484 for (size_t i = 0; i < result_list->GetSize(); ++i) { 485 Value* suggestion_val; 486 string16 suggestion_str; 487 if (!result_list->Get(i, &suggestion_val) || 488 !suggestion_val->GetAsString(&suggestion_str)) 489 return false; 490 491 // Google search may return empty suggestions for weird input characters, 492 // they make no sense at all and can cause problem in our code. 493 // See http://crbug.com/56214 494 if (!suggestion_str.length()) 495 continue; 496 497 Value* type_val; 498 std::string type_str; 499 if (type_list && type_list->Get(i, &type_val) && 500 type_val->GetAsString(&type_str) && (type_str == "NAVIGATION")) { 501 Value* site_val; 502 string16 site_name; 503 NavigationResults& navigation_results = 504 is_keyword ? keyword_navigation_results_ : 505 default_navigation_results_; 506 if ((navigation_results.size() < kMaxMatches) && 507 description_list && description_list->Get(i, &site_val) && 508 site_val->IsType(Value::TYPE_STRING) && 509 site_val->GetAsString(&site_name)) { 510 // We can't blindly trust the URL coming from the server to be valid. 511 GURL result_url(URLFixerUpper::FixupURL(UTF16ToUTF8(suggestion_str), 512 std::string())); 513 if (result_url.is_valid()) { 514 navigation_results.push_back(NavigationResult(result_url, site_name)); 515 } 516 } 517 } else { 518 // TODO(kochi): Currently we treat a calculator result as a query, but it 519 // is better to have better presentation for caluculator results. 520 if (suggest_results->size() < kMaxMatches) 521 suggest_results->push_back(suggestion_str); 522 } 523 } 524 525 return true; 526 } 527 528 void SearchProvider::ConvertResultsToAutocompleteMatches() { 529 // Convert all the results to matches and add them to a map, so we can keep 530 // the most relevant match for each result. 531 MatchMap map; 532 const Time no_time; 533 int did_not_accept_keyword_suggestion = keyword_suggest_results_.empty() ? 534 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE : 535 TemplateURLRef::NO_SUGGESTION_CHOSEN; 536 // Keyword what you typed results are handled by the KeywordProvider. 537 538 int did_not_accept_default_suggestion = default_suggest_results_.empty() ? 539 TemplateURLRef::NO_SUGGESTIONS_AVAILABLE : 540 TemplateURLRef::NO_SUGGESTION_CHOSEN; 541 if (providers_.valid_default_provider()) { 542 AddMatchToMap(input_.text(), input_.text(), 543 CalculateRelevanceForWhatYouTyped(), 544 AutocompleteMatch::SEARCH_WHAT_YOU_TYPED, 545 did_not_accept_default_suggestion, false, 546 input_.initial_prevent_inline_autocomplete(), &map); 547 if (!default_provider_suggest_text_.empty()) { 548 AddMatchToMap(input_.text() + default_provider_suggest_text_, 549 input_.text(), CalculateRelevanceForWhatYouTyped() + 1, 550 AutocompleteMatch::SEARCH_SUGGEST, 551 did_not_accept_default_suggestion, false, 552 input_.initial_prevent_inline_autocomplete(), &map); 553 } 554 } 555 556 AddHistoryResultsToMap(keyword_history_results_, true, 557 did_not_accept_keyword_suggestion, &map); 558 AddHistoryResultsToMap(default_history_results_, false, 559 did_not_accept_default_suggestion, &map); 560 561 AddSuggestResultsToMap(keyword_suggest_results_, true, 562 did_not_accept_keyword_suggestion, &map); 563 AddSuggestResultsToMap(default_suggest_results_, false, 564 did_not_accept_default_suggestion, &map); 565 566 // Now add the most relevant matches from the map to |matches_|. 567 matches_.clear(); 568 for (MatchMap::const_iterator i(map.begin()); i != map.end(); ++i) 569 matches_.push_back(i->second); 570 571 AddNavigationResultsToMatches(keyword_navigation_results_, true); 572 AddNavigationResultsToMatches(default_navigation_results_, false); 573 574 const size_t max_total_matches = kMaxMatches + 1; // 1 for "what you typed" 575 std::partial_sort(matches_.begin(), 576 matches_.begin() + std::min(max_total_matches, matches_.size()), 577 matches_.end(), &AutocompleteMatch::MoreRelevant); 578 if (matches_.size() > max_total_matches) 579 matches_.erase(matches_.begin() + max_total_matches, matches_.end()); 580 581 UpdateFirstSearchMatchDescription(); 582 583 UpdateStarredStateOfMatches(); 584 585 UpdateDone(); 586 } 587 588 void SearchProvider::AddNavigationResultsToMatches( 589 const NavigationResults& navigation_results, 590 bool is_keyword) { 591 if (!navigation_results.empty()) { 592 // TODO(kochi): http://b/1170574 We add only one results for navigational 593 // suggestions. If we can get more useful information about the score, 594 // consider adding more results. 595 const size_t num_results = is_keyword ? 596 keyword_navigation_results_.size() : default_navigation_results_.size(); 597 matches_.push_back(NavigationToMatch(navigation_results.front(), 598 CalculateRelevanceForNavigation(num_results, 0, is_keyword), 599 is_keyword)); 600 } 601 } 602 603 void SearchProvider::AddHistoryResultsToMap(const HistoryResults& results, 604 bool is_keyword, 605 int did_not_accept_suggestion, 606 MatchMap* map) { 607 int last_relevance = 0; 608 AutocompleteClassifier* classifier = profile_->GetAutocompleteClassifier(); 609 for (HistoryResults::const_iterator i(results.begin()); i != results.end(); 610 ++i) { 611 // History returns results sorted for us. We force the relevance to decrease 612 // so that the sort from history is honored. We should never end up with a 613 // match having a relevance greater than the previous, but they might be 614 // equal. If we didn't force the relevance to decrease and we ended up in a 615 // situation where the relevance was equal, then which was shown first would 616 // be random. 617 // This uses >= to handle the case where 3 or more results have the same 618 // relevance. 619 bool term_looks_like_url = false; 620 // Don't autocomplete search terms that would normally be treated as URLs 621 // when typed. For example, if the user searched for google.com and types 622 // goog, don't autocomplete to the search term google.com. Otherwise, the 623 // input will look like a URL but act like a search, which is confusing. 624 // NOTE: We don't check this in the following cases: 625 // * When inline autocomplete is disabled, we won't be inline 626 // autocompleting this term, so we don't need to worry about confusion as 627 // much. This also prevents calling Classify() again from inside the 628 // classifier (which will corrupt state and likely crash), since the 629 // classifier always disabled inline autocomplete. 630 // * When the user has typed the whole term, the "what you typed" history 631 // match will outrank us for URL-like inputs anyway, so we need not do 632 // anything special. 633 if (!input_.prevent_inline_autocomplete() && classifier && 634 i->term != input_.text()) { 635 AutocompleteMatch match; 636 classifier->Classify(i->term, string16(), false, &match, NULL); 637 term_looks_like_url = match.transition == PageTransition::TYPED; 638 } 639 int relevance = CalculateRelevanceForHistory(i->time, term_looks_like_url, 640 is_keyword); 641 if (i != results.begin() && relevance >= last_relevance) 642 relevance = last_relevance - 1; 643 last_relevance = relevance; 644 AddMatchToMap(i->term, 645 is_keyword ? keyword_input_text_ : input_.text(), 646 relevance, 647 AutocompleteMatch::SEARCH_HISTORY, did_not_accept_suggestion, 648 is_keyword, input_.initial_prevent_inline_autocomplete(), 649 map); 650 } 651 } 652 653 void SearchProvider::AddSuggestResultsToMap( 654 const SuggestResults& suggest_results, 655 bool is_keyword, 656 int did_not_accept_suggestion, 657 MatchMap* map) { 658 for (size_t i = 0; i < suggest_results.size(); ++i) { 659 AddMatchToMap(suggest_results[i], 660 is_keyword ? keyword_input_text_ : input_.text(), 661 CalculateRelevanceForSuggestion(suggest_results.size(), i, 662 is_keyword), 663 AutocompleteMatch::SEARCH_SUGGEST, 664 static_cast<int>(i), is_keyword, 665 input_.initial_prevent_inline_autocomplete(), map); 666 } 667 } 668 669 int SearchProvider::CalculateRelevanceForWhatYouTyped() const { 670 if (providers_.valid_keyword_provider()) 671 return 250; 672 673 switch (input_.type()) { 674 case AutocompleteInput::UNKNOWN: 675 case AutocompleteInput::QUERY: 676 case AutocompleteInput::FORCED_QUERY: 677 return 1300; 678 679 case AutocompleteInput::REQUESTED_URL: 680 return 1150; 681 682 case AutocompleteInput::URL: 683 return 850; 684 685 default: 686 NOTREACHED(); 687 return 0; 688 } 689 } 690 691 int SearchProvider::CalculateRelevanceForHistory(const Time& time, 692 bool looks_like_url, 693 bool is_keyword) const { 694 // The relevance of past searches falls off over time. There are two distinct 695 // equations used. If the first equation is used (searches to the primary 696 // provider with a type other than URL that don't autocomplete to a url) the 697 // score starts at 1399 and falls to 1300. If the second equation is used the 698 // relevance of a search 15 minutes ago is discounted about 50 points, while 699 // the relevance of a search two weeks ago is discounted about 450 points. 700 double elapsed_time = std::max((Time::Now() - time).InSecondsF(), 0.); 701 702 if (providers_.is_primary_provider(is_keyword) && 703 input_.type() != AutocompleteInput::URL && 704 !input_.prevent_inline_autocomplete() && !looks_like_url) { 705 // Searches with the past two days get a different curve. 706 const double autocomplete_time= 2 * 24 * 60 * 60; 707 if (elapsed_time < autocomplete_time) { 708 return 1399 - static_cast<int>(99 * 709 std::pow(elapsed_time / autocomplete_time, 2.5)); 710 } 711 elapsed_time -= autocomplete_time; 712 } 713 714 const int score_discount = 715 static_cast<int>(6.5 * std::pow(elapsed_time, 0.3)); 716 717 // Don't let scores go below 0. Negative relevance scores are meaningful in 718 // a different way. 719 int base_score; 720 if (!providers_.is_primary_provider(is_keyword)) 721 base_score = 200; 722 else 723 base_score = (input_.type() == AutocompleteInput::URL) ? 750 : 1050; 724 return std::max(0, base_score - score_discount); 725 } 726 727 int SearchProvider::CalculateRelevanceForSuggestion(size_t num_results, 728 size_t result_number, 729 bool is_keyword) const { 730 DCHECK(result_number < num_results); 731 int base_score; 732 if (!providers_.is_primary_provider(is_keyword)) 733 base_score = 100; 734 else 735 base_score = (input_.type() == AutocompleteInput::URL) ? 300 : 600; 736 return base_score + 737 static_cast<int>(num_results - 1 - result_number); 738 } 739 740 int SearchProvider::CalculateRelevanceForNavigation(size_t num_results, 741 size_t result_number, 742 bool is_keyword) const { 743 DCHECK(result_number < num_results); 744 // TODO(kochi): http://b/784900 Use relevance score from the NavSuggest 745 // server if possible. 746 return (providers_.is_primary_provider(is_keyword) ? 800 : 150) + 747 static_cast<int>(num_results - 1 - result_number); 748 } 749 750 void SearchProvider::AddMatchToMap(const string16& query_string, 751 const string16& input_text, 752 int relevance, 753 AutocompleteMatch::Type type, 754 int accepted_suggestion, 755 bool is_keyword, 756 bool prevent_inline_autocomplete, 757 MatchMap* map) { 758 AutocompleteMatch match(this, relevance, false, type); 759 std::vector<size_t> content_param_offsets; 760 const TemplateURL& provider = is_keyword ? providers_.keyword_provider() : 761 providers_.default_provider(); 762 match.contents.assign(query_string); 763 // We do intra-string highlighting for suggestions - the suggested segment 764 // will be highlighted, e.g. for input_text = "you" the suggestion may be 765 // "youtube", so we'll bold the "tube" section: you*tube*. 766 if (input_text != query_string) { 767 size_t input_position = match.contents.find(input_text); 768 if (input_position == string16::npos) { 769 // The input text is not a substring of the query string, e.g. input 770 // text is "slasdot" and the query string is "slashdot", so we bold the 771 // whole thing. 772 match.contents_class.push_back( 773 ACMatchClassification(0, ACMatchClassification::MATCH)); 774 } else { 775 // TODO(beng): ACMatchClassification::MATCH now seems to just mean 776 // "bold" this. Consider modifying the terminology. 777 // We don't iterate over the string here annotating all matches because 778 // it looks odd to have every occurrence of a substring that may be as 779 // short as a single character highlighted in a query suggestion result, 780 // e.g. for input text "s" and query string "southwest airlines", it 781 // looks odd if both the first and last s are highlighted. 782 if (input_position != 0) { 783 match.contents_class.push_back( 784 ACMatchClassification(0, ACMatchClassification::NONE)); 785 } 786 match.contents_class.push_back( 787 ACMatchClassification(input_position, ACMatchClassification::DIM)); 788 size_t next_fragment_position = input_position + input_text.length(); 789 if (next_fragment_position < query_string.length()) { 790 match.contents_class.push_back( 791 ACMatchClassification(next_fragment_position, 792 ACMatchClassification::NONE)); 793 } 794 } 795 } else { 796 // Otherwise, we're dealing with the "default search" result which has no 797 // completion. 798 match.contents_class.push_back( 799 ACMatchClassification(0, ACMatchClassification::NONE)); 800 } 801 802 // When the user forced a query, we need to make sure all the fill_into_edit 803 // values preserve that property. Otherwise, if the user starts editing a 804 // suggestion, non-Search results will suddenly appear. 805 size_t search_start = 0; 806 if (input_.type() == AutocompleteInput::FORCED_QUERY) { 807 match.fill_into_edit.assign(ASCIIToUTF16("?")); 808 ++search_start; 809 } 810 if (is_keyword) { 811 match.fill_into_edit.append( 812 providers_.keyword_provider().keyword() + char16(' ')); 813 match.template_url = &providers_.keyword_provider(); 814 } 815 match.fill_into_edit.append(query_string); 816 // Not all suggestions start with the original input. 817 if (!prevent_inline_autocomplete && 818 !match.fill_into_edit.compare(search_start, input_text.length(), 819 input_text)) 820 match.inline_autocomplete_offset = search_start + input_text.length(); 821 822 const TemplateURLRef* const search_url = provider.url(); 823 DCHECK(search_url->SupportsReplacement()); 824 match.destination_url = 825 GURL(search_url->ReplaceSearchTerms(provider, 826 query_string, 827 accepted_suggestion, 828 input_text)); 829 830 // Search results don't look like URLs. 831 match.transition = 832 is_keyword ? PageTransition::KEYWORD : PageTransition::GENERATED; 833 834 // Try to add |match| to |map|. If a match for |query_string| is already in 835 // |map|, replace it if |match| is more relevant. 836 // NOTE: Keep this ToLower() call in sync with url_database.cc. 837 const std::pair<MatchMap::iterator, bool> i = map->insert( 838 std::pair<string16, AutocompleteMatch>( 839 l10n_util::ToLower(query_string), match)); 840 // NOTE: We purposefully do a direct relevance comparison here instead of 841 // using AutocompleteMatch::MoreRelevant(), so that we'll prefer "items added 842 // first" rather than "items alphabetically first" when the scores are equal. 843 // The only case this matters is when a user has results with the same score 844 // that differ only by capitalization; because the history system returns 845 // results sorted by recency, this means we'll pick the most recent such 846 // result even if the precision of our relevance score is too low to 847 // distinguish the two. 848 if (!i.second && (match.relevance > i.first->second.relevance)) 849 i.first->second = match; 850 } 851 852 AutocompleteMatch SearchProvider::NavigationToMatch( 853 const NavigationResult& navigation, 854 int relevance, 855 bool is_keyword) { 856 const string16& input_text = 857 is_keyword ? keyword_input_text_ : input_.text(); 858 AutocompleteMatch match(this, relevance, false, 859 AutocompleteMatch::NAVSUGGEST); 860 match.destination_url = navigation.url; 861 match.contents = 862 StringForURLDisplay(navigation.url, true, !HasHTTPScheme(input_text)); 863 AutocompleteMatch::ClassifyMatchInString(input_text, match.contents, 864 ACMatchClassification::URL, 865 &match.contents_class); 866 867 match.description = navigation.site_name; 868 AutocompleteMatch::ClassifyMatchInString(input_text, navigation.site_name, 869 ACMatchClassification::NONE, 870 &match.description_class); 871 872 // When the user forced a query, we need to make sure all the fill_into_edit 873 // values preserve that property. Otherwise, if the user starts editing a 874 // suggestion, non-Search results will suddenly appear. 875 if (input_.type() == AutocompleteInput::FORCED_QUERY) 876 match.fill_into_edit.assign(ASCIIToUTF16("?")); 877 match.fill_into_edit.append( 878 AutocompleteInput::FormattedStringWithEquivalentMeaning(navigation.url, 879 match.contents)); 880 // TODO(pkasting): http://b/1112879 These should perhaps be 881 // inline-autocompletable? 882 883 return match; 884 } 885 886 void SearchProvider::UpdateDone() { 887 // We're done when there are no more suggest queries pending (this is set to 1 888 // when the timer is started) and we're not waiting on instant. 889 done_ = ((suggest_results_pending_ == 0) && 890 (instant_finalized_ || !InstantController::IsEnabled(profile_))); 891 } 892 893 void SearchProvider::UpdateFirstSearchMatchDescription() { 894 if (!providers_.valid_default_provider() || matches_.empty()) 895 return; 896 897 for (ACMatches::iterator i = matches_.begin(); i != matches_.end(); ++i) { 898 AutocompleteMatch& match = *i; 899 switch (match.type) { 900 case AutocompleteMatch::SEARCH_WHAT_YOU_TYPED: 901 case AutocompleteMatch::SEARCH_HISTORY: 902 case AutocompleteMatch::SEARCH_SUGGEST: 903 match.description.assign(l10n_util::GetStringFUTF16( 904 IDS_AUTOCOMPLETE_SEARCH_DESCRIPTION, 905 providers_.default_provider(). 906 AdjustedShortNameForLocaleDirection())); 907 match.description_class.push_back( 908 ACMatchClassification(0, ACMatchClassification::DIM)); 909 // Only the first search match gets a description. 910 return; 911 912 default: 913 break; 914 } 915 } 916 } 917
