1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/autocomplete/autocomplete_match.h" 6 7 #include "base/i18n/time_formatting.h" 8 #include "base/logging.h" 9 #include "base/strings/string16.h" 10 #include "base/strings/string_number_conversions.h" 11 #include "base/strings/string_util.h" 12 #include "base/strings/utf_string_conversions.h" 13 #include "base/time/time.h" 14 #include "chrome/browser/autocomplete/autocomplete_provider.h" 15 #include "chrome/browser/search_engines/template_url.h" 16 #include "chrome/browser/search_engines/template_url_service.h" 17 #include "chrome/browser/search_engines/template_url_service_factory.h" 18 #include "chrome/browser/search_engines/ui_thread_search_terms_data.h" 19 #include "content/public/common/url_constants.h" 20 #include "grit/theme_resources.h" 21 22 namespace { 23 24 bool IsTrivialClassification(const ACMatchClassifications& classifications) { 25 return classifications.empty() || 26 ((classifications.size() == 1) && 27 (classifications.back().style == ACMatchClassification::NONE)); 28 } 29 30 } // namespace 31 32 // AutocompleteMatch ---------------------------------------------------------- 33 34 // static 35 const base::char16 AutocompleteMatch::kInvalidChars[] = { 36 '\n', '\r', '\t', 37 0x2028, // Line separator 38 0x2029, // Paragraph separator 39 0 40 }; 41 42 AutocompleteMatch::AutocompleteMatch() 43 : provider(NULL), 44 relevance(0), 45 typed_count(-1), 46 deletable(false), 47 allowed_to_be_default_match(false), 48 transition(content::PAGE_TRANSITION_GENERATED), 49 is_history_what_you_typed_match(false), 50 type(AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED), 51 starred(false), 52 from_previous(false) { 53 } 54 55 AutocompleteMatch::AutocompleteMatch(AutocompleteProvider* provider, 56 int relevance, 57 bool deletable, 58 Type type) 59 : provider(provider), 60 relevance(relevance), 61 typed_count(-1), 62 deletable(deletable), 63 allowed_to_be_default_match(false), 64 transition(content::PAGE_TRANSITION_TYPED), 65 is_history_what_you_typed_match(false), 66 type(type), 67 starred(false), 68 from_previous(false) { 69 } 70 71 AutocompleteMatch::AutocompleteMatch(const AutocompleteMatch& match) 72 : provider(match.provider), 73 relevance(match.relevance), 74 typed_count(match.typed_count), 75 deletable(match.deletable), 76 fill_into_edit(match.fill_into_edit), 77 inline_autocompletion(match.inline_autocompletion), 78 allowed_to_be_default_match(match.allowed_to_be_default_match), 79 destination_url(match.destination_url), 80 stripped_destination_url(match.stripped_destination_url), 81 contents(match.contents), 82 contents_class(match.contents_class), 83 description(match.description), 84 description_class(match.description_class), 85 answer_contents(match.answer_contents), 86 answer_type(match.answer_type), 87 transition(match.transition), 88 is_history_what_you_typed_match(match.is_history_what_you_typed_match), 89 type(match.type), 90 associated_keyword(match.associated_keyword.get() ? 91 new AutocompleteMatch(*match.associated_keyword) : NULL), 92 keyword(match.keyword), 93 starred(match.starred), 94 from_previous(match.from_previous), 95 search_terms_args(match.search_terms_args.get() ? 96 new TemplateURLRef::SearchTermsArgs(*match.search_terms_args) : 97 NULL), 98 additional_info(match.additional_info), 99 duplicate_matches(match.duplicate_matches) { 100 } 101 102 AutocompleteMatch::~AutocompleteMatch() { 103 } 104 105 AutocompleteMatch& AutocompleteMatch::operator=( 106 const AutocompleteMatch& match) { 107 if (this == &match) 108 return *this; 109 110 provider = match.provider; 111 relevance = match.relevance; 112 typed_count = match.typed_count; 113 deletable = match.deletable; 114 fill_into_edit = match.fill_into_edit; 115 inline_autocompletion = match.inline_autocompletion; 116 allowed_to_be_default_match = match.allowed_to_be_default_match; 117 destination_url = match.destination_url; 118 stripped_destination_url = match.stripped_destination_url; 119 contents = match.contents; 120 contents_class = match.contents_class; 121 description = match.description; 122 description_class = match.description_class; 123 answer_contents = match.answer_contents; 124 answer_type = match.answer_type; 125 transition = match.transition; 126 is_history_what_you_typed_match = match.is_history_what_you_typed_match; 127 type = match.type; 128 associated_keyword.reset(match.associated_keyword.get() ? 129 new AutocompleteMatch(*match.associated_keyword) : NULL); 130 keyword = match.keyword; 131 starred = match.starred; 132 from_previous = match.from_previous; 133 search_terms_args.reset(match.search_terms_args.get() ? 134 new TemplateURLRef::SearchTermsArgs(*match.search_terms_args) : NULL); 135 additional_info = match.additional_info; 136 duplicate_matches = match.duplicate_matches; 137 return *this; 138 } 139 140 // static 141 int AutocompleteMatch::TypeToIcon(Type type) { 142 int icons[] = { 143 IDR_OMNIBOX_HTTP, 144 IDR_OMNIBOX_HTTP, 145 IDR_OMNIBOX_HTTP, 146 IDR_OMNIBOX_HTTP, 147 IDR_OMNIBOX_HTTP, 148 IDR_OMNIBOX_HTTP, 149 IDR_OMNIBOX_SEARCH, 150 IDR_OMNIBOX_SEARCH, 151 IDR_OMNIBOX_SEARCH, 152 IDR_OMNIBOX_SEARCH, 153 IDR_OMNIBOX_SEARCH, 154 IDR_OMNIBOX_SEARCH, 155 IDR_OMNIBOX_SEARCH, 156 IDR_OMNIBOX_SEARCH, 157 IDR_OMNIBOX_EXTENSION_APP, 158 IDR_OMNIBOX_SEARCH, 159 IDR_OMNIBOX_HTTP, 160 IDR_OMNIBOX_HTTP, 161 IDR_OMNIBOX_SEARCH, 162 }; 163 COMPILE_ASSERT(arraysize(icons) == AutocompleteMatchType::NUM_TYPES, 164 icons_array_must_match_type_enum); 165 return icons[type]; 166 } 167 168 // static 169 int AutocompleteMatch::TypeToLocationBarIcon(Type type) { 170 int id = TypeToIcon(type); 171 if (id == IDR_OMNIBOX_HTTP) 172 return IDR_LOCATION_BAR_HTTP; 173 return id; 174 } 175 176 // static 177 bool AutocompleteMatch::MoreRelevant(const AutocompleteMatch& elem1, 178 const AutocompleteMatch& elem2) { 179 // For equal-relevance matches, we sort alphabetically, so that providers 180 // who return multiple elements at the same priority get a "stable" sort 181 // across multiple updates. 182 return (elem1.relevance == elem2.relevance) ? 183 (elem1.contents < elem2.contents) : (elem1.relevance > elem2.relevance); 184 } 185 186 // static 187 bool AutocompleteMatch::DestinationsEqual(const AutocompleteMatch& elem1, 188 const AutocompleteMatch& elem2) { 189 if (elem1.stripped_destination_url.is_empty() && 190 elem2.stripped_destination_url.is_empty()) 191 return false; 192 return elem1.stripped_destination_url == elem2.stripped_destination_url; 193 } 194 195 // static 196 void AutocompleteMatch::ClassifyMatchInString( 197 const base::string16& find_text, 198 const base::string16& text, 199 int style, 200 ACMatchClassifications* classification) { 201 ClassifyLocationInString(text.find(find_text), find_text.length(), 202 text.length(), style, classification); 203 } 204 205 // static 206 void AutocompleteMatch::ClassifyLocationInString( 207 size_t match_location, 208 size_t match_length, 209 size_t overall_length, 210 int style, 211 ACMatchClassifications* classification) { 212 classification->clear(); 213 214 // Don't classify anything about an empty string 215 // (AutocompleteMatch::Validate() checks this). 216 if (overall_length == 0) 217 return; 218 219 // Mark pre-match portion of string (if any). 220 if (match_location != 0) { 221 classification->push_back(ACMatchClassification(0, style)); 222 } 223 224 // Mark matching portion of string. 225 if (match_location == base::string16::npos) { 226 // No match, above classification will suffice for whole string. 227 return; 228 } 229 // Classifying an empty match makes no sense and will lead to validation 230 // errors later. 231 DCHECK_GT(match_length, 0U); 232 classification->push_back(ACMatchClassification(match_location, 233 (style | ACMatchClassification::MATCH) & ~ACMatchClassification::DIM)); 234 235 // Mark post-match portion of string (if any). 236 const size_t after_match(match_location + match_length); 237 if (after_match < overall_length) { 238 classification->push_back(ACMatchClassification(after_match, style)); 239 } 240 } 241 242 // static 243 AutocompleteMatch::ACMatchClassifications 244 AutocompleteMatch::MergeClassifications( 245 const ACMatchClassifications& classifications1, 246 const ACMatchClassifications& classifications2) { 247 // We must return the empty vector only if both inputs are truly empty. 248 // The result of merging an empty vector with a single (0, NONE) 249 // classification is the latter one-entry vector. 250 if (IsTrivialClassification(classifications1)) 251 return classifications2.empty() ? classifications1 : classifications2; 252 if (IsTrivialClassification(classifications2)) 253 return classifications1; 254 255 ACMatchClassifications output; 256 for (ACMatchClassifications::const_iterator i = classifications1.begin(), 257 j = classifications2.begin(); i != classifications1.end();) { 258 AutocompleteMatch::AddLastClassificationIfNecessary(&output, 259 std::max(i->offset, j->offset), i->style | j->style); 260 const size_t next_i_offset = (i + 1) == classifications1.end() ? 261 static_cast<size_t>(-1) : (i + 1)->offset; 262 const size_t next_j_offset = (j + 1) == classifications2.end() ? 263 static_cast<size_t>(-1) : (j + 1)->offset; 264 if (next_i_offset >= next_j_offset) 265 ++j; 266 if (next_j_offset >= next_i_offset) 267 ++i; 268 } 269 270 return output; 271 } 272 273 // static 274 std::string AutocompleteMatch::ClassificationsToString( 275 const ACMatchClassifications& classifications) { 276 std::string serialized_classifications; 277 for (size_t i = 0; i < classifications.size(); ++i) { 278 if (i) 279 serialized_classifications += ','; 280 serialized_classifications += base::IntToString(classifications[i].offset) + 281 ',' + base::IntToString(classifications[i].style); 282 } 283 return serialized_classifications; 284 } 285 286 // static 287 ACMatchClassifications AutocompleteMatch::ClassificationsFromString( 288 const std::string& serialized_classifications) { 289 ACMatchClassifications classifications; 290 std::vector<std::string> tokens; 291 Tokenize(serialized_classifications, ",", &tokens); 292 DCHECK(!(tokens.size() & 1)); // The number of tokens should be even. 293 for (size_t i = 0; i < tokens.size(); i += 2) { 294 int classification_offset = 0; 295 int classification_style = ACMatchClassification::NONE; 296 if (!base::StringToInt(tokens[i], &classification_offset) || 297 !base::StringToInt(tokens[i + 1], &classification_style)) { 298 NOTREACHED(); 299 return classifications; 300 } 301 classifications.push_back(ACMatchClassification(classification_offset, 302 classification_style)); 303 } 304 return classifications; 305 } 306 307 // static 308 void AutocompleteMatch::AddLastClassificationIfNecessary( 309 ACMatchClassifications* classifications, 310 size_t offset, 311 int style) { 312 DCHECK(classifications); 313 if (classifications->empty() || classifications->back().style != style) { 314 DCHECK(classifications->empty() || 315 (offset > classifications->back().offset)); 316 classifications->push_back(ACMatchClassification(offset, style)); 317 } 318 } 319 320 // static 321 base::string16 AutocompleteMatch::SanitizeString(const base::string16& text) { 322 // NOTE: This logic is mirrored by |sanitizeString()| in 323 // omnibox_custom_bindings.js. 324 base::string16 result; 325 base::TrimWhitespace(text, base::TRIM_LEADING, &result); 326 base::RemoveChars(result, kInvalidChars, &result); 327 return result; 328 } 329 330 // static 331 bool AutocompleteMatch::IsSearchType(Type type) { 332 return type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED || 333 type == AutocompleteMatchType::SEARCH_HISTORY || 334 type == AutocompleteMatchType::SEARCH_SUGGEST || 335 type == AutocompleteMatchType::SEARCH_OTHER_ENGINE || 336 IsSpecializedSearchType(type); 337 } 338 339 // static 340 bool AutocompleteMatch::IsSpecializedSearchType(Type type) { 341 return type == AutocompleteMatchType::SEARCH_SUGGEST_ENTITY || 342 type == AutocompleteMatchType::SEARCH_SUGGEST_INFINITE || 343 type == AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED || 344 type == AutocompleteMatchType::SEARCH_SUGGEST_PROFILE || 345 type == AutocompleteMatchType::SEARCH_SUGGEST_ANSWER; 346 } 347 348 void AutocompleteMatch::ComputeStrippedDestinationURL(Profile* profile) { 349 stripped_destination_url = destination_url; 350 if (!stripped_destination_url.is_valid()) 351 return; 352 353 // If the destination URL looks like it was generated from a TemplateURL, 354 // remove all substitutions other than the search terms. This allows us 355 // to eliminate cases like past search URLs from history that differ only 356 // by some obscure query param from each other or from the search/keyword 357 // provider matches. 358 TemplateURL* template_url = GetTemplateURL(profile, true); 359 UIThreadSearchTermsData search_terms_data(profile); 360 if (template_url != NULL && 361 template_url->SupportsReplacement(search_terms_data)) { 362 base::string16 search_terms; 363 if (template_url->ExtractSearchTermsFromURL(stripped_destination_url, 364 search_terms_data, 365 &search_terms)) { 366 stripped_destination_url = 367 GURL(template_url->url_ref().ReplaceSearchTerms( 368 TemplateURLRef::SearchTermsArgs(search_terms), 369 search_terms_data)); 370 } 371 } 372 373 // |replacements| keeps all the substitions we're going to make to 374 // from {destination_url} to {stripped_destination_url}. |need_replacement| 375 // is a helper variable that helps us keep track of whether we need 376 // to apply the replacement. 377 bool needs_replacement = false; 378 GURL::Replacements replacements; 379 380 // Remove the www. prefix from the host. 381 static const char prefix[] = "www."; 382 static const size_t prefix_len = arraysize(prefix) - 1; 383 std::string host = stripped_destination_url.host(); 384 if (host.compare(0, prefix_len, prefix) == 0) { 385 host = host.substr(prefix_len); 386 replacements.SetHostStr(host); 387 needs_replacement = true; 388 } 389 390 // Replace https protocol with http protocol. 391 if (stripped_destination_url.SchemeIs(url::kHttpsScheme)) { 392 replacements.SetScheme(url::kHttpScheme, 393 url::Component(0, strlen(url::kHttpScheme))); 394 needs_replacement = true; 395 } 396 397 if (needs_replacement) 398 stripped_destination_url = stripped_destination_url.ReplaceComponents( 399 replacements); 400 } 401 402 void AutocompleteMatch::GetKeywordUIState(Profile* profile, 403 base::string16* keyword, 404 bool* is_keyword_hint) const { 405 *is_keyword_hint = associated_keyword.get() != NULL; 406 keyword->assign(*is_keyword_hint ? associated_keyword->keyword : 407 GetSubstitutingExplicitlyInvokedKeyword(profile)); 408 } 409 410 base::string16 AutocompleteMatch::GetSubstitutingExplicitlyInvokedKeyword( 411 Profile* profile) const { 412 if (transition != content::PAGE_TRANSITION_KEYWORD) 413 return base::string16(); 414 const TemplateURL* t_url = GetTemplateURL(profile, false); 415 return (t_url && 416 t_url->SupportsReplacement(UIThreadSearchTermsData(profile))) ? 417 keyword : base::string16(); 418 } 419 420 TemplateURL* AutocompleteMatch::GetTemplateURL( 421 Profile* profile, bool allow_fallback_to_destination_host) const { 422 DCHECK(profile); 423 TemplateURLService* template_url_service = 424 TemplateURLServiceFactory::GetForProfile(profile); 425 if (template_url_service == NULL) 426 return NULL; 427 TemplateURL* template_url = keyword.empty() ? NULL : 428 template_url_service->GetTemplateURLForKeyword(keyword); 429 if (template_url == NULL && allow_fallback_to_destination_host) { 430 template_url = template_url_service->GetTemplateURLForHost( 431 destination_url.host()); 432 } 433 return template_url; 434 } 435 436 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property, 437 const std::string& value) { 438 DCHECK(!property.empty()); 439 DCHECK(!value.empty()); 440 additional_info[property] = value; 441 } 442 443 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property, 444 int value) { 445 RecordAdditionalInfo(property, base::IntToString(value)); 446 } 447 448 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property, 449 const base::Time& value) { 450 RecordAdditionalInfo(property, 451 base::UTF16ToUTF8( 452 base::TimeFormatShortDateAndTime(value))); 453 } 454 455 std::string AutocompleteMatch::GetAdditionalInfo( 456 const std::string& property) const { 457 AdditionalInfo::const_iterator i(additional_info.find(property)); 458 return (i == additional_info.end()) ? std::string() : i->second; 459 } 460 461 bool AutocompleteMatch::IsVerbatimType() const { 462 const bool is_keyword_verbatim_match = 463 (type == AutocompleteMatchType::SEARCH_OTHER_ENGINE && 464 provider != NULL && 465 provider->type() == AutocompleteProvider::TYPE_SEARCH); 466 return type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED || 467 type == AutocompleteMatchType::URL_WHAT_YOU_TYPED || 468 is_keyword_verbatim_match; 469 } 470 471 bool AutocompleteMatch::SupportsDeletion() const { 472 if (deletable) 473 return true; 474 475 for (ACMatches::const_iterator it(duplicate_matches.begin()); 476 it != duplicate_matches.end(); ++it) { 477 if (it->deletable) 478 return true; 479 } 480 return false; 481 } 482 483 #ifndef NDEBUG 484 void AutocompleteMatch::Validate() const { 485 ValidateClassifications(contents, contents_class); 486 ValidateClassifications(description, description_class); 487 } 488 489 void AutocompleteMatch::ValidateClassifications( 490 const base::string16& text, 491 const ACMatchClassifications& classifications) const { 492 if (text.empty()) { 493 DCHECK(classifications.empty()); 494 return; 495 } 496 497 // The classifications should always cover the whole string. 498 DCHECK(!classifications.empty()) << "No classification for \"" << text << '"'; 499 DCHECK_EQ(0U, classifications[0].offset) 500 << "Classification misses beginning for \"" << text << '"'; 501 if (classifications.size() == 1) 502 return; 503 504 // The classifications should always be sorted. 505 size_t last_offset = classifications[0].offset; 506 for (ACMatchClassifications::const_iterator i(classifications.begin() + 1); 507 i != classifications.end(); ++i) { 508 const char* provider_name = provider ? provider->GetName() : "None"; 509 DCHECK_GT(i->offset, last_offset) 510 << " Classification for \"" << text << "\" with offset of " << i->offset 511 << " is unsorted in relation to last offset of " << last_offset 512 << ". Provider: " << provider_name << "."; 513 DCHECK_LT(i->offset, text.length()) 514 << " Classification of [" << i->offset << "," << text.length() 515 << "] is out of bounds for \"" << text << "\". Provider: " 516 << provider_name << "."; 517 last_offset = i->offset; 518 } 519 } 520 #endif 521