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