components/omnibox/autocomplete_match.cc

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