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 "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