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