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