components/omnibox/browser/shortcuts_provider.cc

   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 "components/omnibox/browser/shortcuts_provider.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <map>
  10 #include <vector>
  11
  12 #include "base/i18n/break_iterator.h"
  13 #include "base/i18n/case_conversion.h"
  14 #include "base/logging.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/prefs/pref_service.h"
  17 #include "base/strings/string_number_conversions.h"
  18 #include "base/strings/string_util.h"
  19 #include "base/strings/utf_string_conversions.h"
  20 #include "base/time/time.h"
  21 #include "components/history/core/browser/history_service.h"
  22 #include "components/metrics/proto/omnibox_input_type.pb.h"
  23 #include "components/omnibox/browser/autocomplete_i18n.h"
  24 #include "components/omnibox/browser/autocomplete_input.h"
  25 #include "components/omnibox/browser/autocomplete_match.h"
  26 #include "components/omnibox/browser/autocomplete_provider_client.h"
  27 #include "components/omnibox/browser/autocomplete_result.h"
  28 #include "components/omnibox/browser/history_provider.h"
  29 #include "components/omnibox/browser/omnibox_field_trial.h"
  30 #include "components/omnibox/browser/url_prefix.h"
  31 #include "components/url_formatter/url_fixer.h"
  32 #include "url/third_party/mozilla/url_parse.h"
  33
  34 namespace {
  35
  36 class DestinationURLEqualsURL {
  37  public:
  38   explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {}
  39   bool operator()(const AutocompleteMatch& match) const {
  40     return match.destination_url == url_;
  41   }
  42
  43  private:
  44   const GURL url_;
  45 };
  46
  47 }  // namespace
  48
  49 const int ShortcutsProvider::kShortcutsProviderDefaultMaxRelevance = 1199;
  50
  51 ShortcutsProvider::ShortcutsProvider(AutocompleteProviderClient* client)
  52     : AutocompleteProvider(AutocompleteProvider::TYPE_SHORTCUTS),
  53       client_(client),
  54       languages_(client_->GetAcceptLanguages()),
  55       initialized_(false) {
  56   scoped_refptr<ShortcutsBackend> backend = client_->GetShortcutsBackend();
  57   if (backend.get()) {
  58     backend->AddObserver(this);
  59     if (backend->initialized())
  60       initialized_ = true;
  61   }
  62 }
  63
  64 void ShortcutsProvider::Start(const AutocompleteInput& input,
  65                               bool minimal_changes) {
  66   matches_.clear();
  67
  68   if (input.from_omnibox_focus() ||
  69       (input.type() == metrics::OmniboxInputType::INVALID) ||
  70       (input.type() == metrics::OmniboxInputType::FORCED_QUERY) ||
  71       input.text().empty() || !initialized_)
  72     return;
  73
  74   base::TimeTicks start_time = base::TimeTicks::Now();
  75   GetMatches(input);
  76   if (input.text().length() < 6) {
  77     base::TimeTicks end_time = base::TimeTicks::Now();
  78     std::string name = "ShortcutsProvider.QueryIndexTime." +
  79                        base::IntToString(input.text().size());
  80     base::HistogramBase* counter = base::Histogram::FactoryGet(
  81         name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
  82     counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
  83   }
  84 }
  85
  86 void ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) {
  87   // Copy the URL since deleting from |matches_| will invalidate |match|.
  88   GURL url(match.destination_url);
  89   DCHECK(url.is_valid());
  90
  91   // When a user deletes a match, he probably means for the URL to disappear out
  92   // of history entirely. So nuke all shortcuts that map to this URL.
  93   scoped_refptr<ShortcutsBackend> backend =
  94       client_->GetShortcutsBackendIfExists();
  95   if (backend.get())  // Can be NULL in Incognito.
  96     backend->DeleteShortcutsWithURL(url);
  97
  98   matches_.erase(std::remove_if(matches_.begin(), matches_.end(),
  99                                 DestinationURLEqualsURL(url)),
 100                  matches_.end());
 101   // NOTE: |match| is now dead!
 102
 103   // Delete the match from the history DB. This will eventually result in a
 104   // second call to DeleteShortcutsWithURL(), which is harmless.
 105   history::HistoryService* const history_service = client_->GetHistoryService();
 106   DCHECK(history_service);
 107   history_service->DeleteURL(url);
 108 }
 109
 110 ShortcutsProvider::~ShortcutsProvider() {
 111   scoped_refptr<ShortcutsBackend> backend =
 112       client_->GetShortcutsBackendIfExists();
 113   if (backend.get())
 114     backend->RemoveObserver(this);
 115 }
 116
 117 void ShortcutsProvider::OnShortcutsLoaded() {
 118   initialized_ = true;
 119 }
 120
 121 void ShortcutsProvider::GetMatches(const AutocompleteInput& input) {
 122   scoped_refptr<ShortcutsBackend> backend =
 123       client_->GetShortcutsBackendIfExists();
 124   if (!backend.get())
 125     return;
 126   // Get the URLs from the shortcuts database with keys that partially or
 127   // completely match the search term.
 128   base::string16 term_string(base::i18n::ToLower(input.text()));
 129   DCHECK(!term_string.empty());
 130
 131   int max_relevance;
 132   if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance(
 133           input.current_page_classification(), &max_relevance))
 134     max_relevance = kShortcutsProviderDefaultMaxRelevance;
 135   TemplateURLService* template_url_service = client_->GetTemplateURLService();
 136   const base::string16 fixed_up_input(FixupUserInput(input).second);
 137   for (ShortcutsBackend::ShortcutMap::const_iterator it =
 138            FindFirstMatch(term_string, backend.get());
 139        it != backend->shortcuts_map().end() &&
 140            base::StartsWith(it->first, term_string,
 141                             base::CompareCase::SENSITIVE);
 142        ++it) {
 143     // Don't return shortcuts with zero relevance.
 144     int relevance = CalculateScore(term_string, it->second, max_relevance);
 145     if (relevance) {
 146       matches_.push_back(
 147           ShortcutToACMatch(it->second, relevance, input, fixed_up_input));
 148       matches_.back().ComputeStrippedDestinationURL(
 149           input, client_->GetAcceptLanguages(), template_url_service);
 150     }
 151   }
 152   // Remove duplicates.  This is important because it's common to have multiple
 153   // shortcuts pointing to the same URL, e.g., ma, mai, and mail all pointing
 154   // to mail.google.com, so typing "m" will return them all.  If we then simply
 155   // clamp to kMaxMatches and let the AutocompleteResult take care of
 156   // collapsing the duplicates, we'll effectively only be returning one match,
 157   // instead of several possibilities.
 158   //
 159   // Note that while removing duplicates, we don't populate a match's
 160   // |duplicate_matches| field--duplicates don't need to be preserved in the
 161   // matches because they are only used for deletions, and this provider
 162   // deletes matches based on the URL.
 163   AutocompleteResult::DedupMatchesByDestination(
 164       input.current_page_classification(), false, &matches_);
 165   // Find best matches.
 166   std::partial_sort(
 167       matches_.begin(),
 168       matches_.begin() +
 169           std::min(AutocompleteProvider::kMaxMatches, matches_.size()),
 170       matches_.end(), &AutocompleteMatch::MoreRelevant);
 171   if (matches_.size() > AutocompleteProvider::kMaxMatches) {
 172     matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches,
 173                    matches_.end());
 174   }
 175   // Guarantee that all scores are decreasing (but do not assign any scores
 176   // below 1).
 177   for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) {
 178     max_relevance = std::min(max_relevance, it->relevance);
 179     it->relevance = max_relevance;
 180     if (max_relevance > 1)
 181       --max_relevance;
 182   }
 183 }
 184
 185 AutocompleteMatch ShortcutsProvider::ShortcutToACMatch(
 186     const ShortcutsDatabase::Shortcut& shortcut,
 187     int relevance,
 188     const AutocompleteInput& input,
 189     const base::string16& fixed_up_input_text) {
 190   DCHECK(!input.text().empty());
 191   AutocompleteMatch match;
 192   match.provider = this;
 193   match.relevance = relevance;
 194   match.deletable = true;
 195   match.fill_into_edit = shortcut.match_core.fill_into_edit;
 196   match.destination_url = shortcut.match_core.destination_url;
 197   DCHECK(match.destination_url.is_valid());
 198   match.contents = shortcut.match_core.contents;
 199   match.contents_class = AutocompleteMatch::ClassificationsFromString(
 200       shortcut.match_core.contents_class);
 201   match.description = shortcut.match_core.description;
 202   match.description_class = AutocompleteMatch::ClassificationsFromString(
 203       shortcut.match_core.description_class);
 204   match.transition = ui::PageTransitionFromInt(shortcut.match_core.transition);
 205   match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type);
 206   match.keyword = shortcut.match_core.keyword;
 207   match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits);
 208   match.RecordAdditionalInfo("last access time", shortcut.last_access_time);
 209   match.RecordAdditionalInfo("original input text",
 210                              base::UTF16ToUTF8(shortcut.text));
 211
 212   // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible.
 213   // If the match is a search query this is easy: simply check whether the
 214   // user text is a prefix of the query.  If the match is a navigation, we
 215   // assume the fill_into_edit looks something like a URL, so we use
 216   // URLPrefix::GetInlineAutocompleteOffset() to try and strip off any prefixes
 217   // that the user might not think would change the meaning, but would
 218   // otherwise prevent inline autocompletion.  This allows, for example, the
 219   // input of "foo.c" to autocomplete to "foo.com" for a fill_into_edit of
 220   // "http://foo.com".
 221   if (AutocompleteMatch::IsSearchType(match.type)) {
 222     if (match.fill_into_edit.size() >= input.text().size() &&
 223         std::equal(match.fill_into_edit.begin(),
 224                    match.fill_into_edit.begin() + input.text().size(),
 225                    input.text().begin(),
 226                    SimpleCaseInsensitiveCompareUCS2())) {
 227       match.inline_autocompletion =
 228           match.fill_into_edit.substr(input.text().length());
 229       match.allowed_to_be_default_match =
 230           !input.prevent_inline_autocomplete() ||
 231           match.inline_autocompletion.empty();
 232     }
 233   } else {
 234     const size_t inline_autocomplete_offset =
 235         URLPrefix::GetInlineAutocompleteOffset(
 236             input.text(), fixed_up_input_text, true, match.fill_into_edit);
 237     if (inline_autocomplete_offset != base::string16::npos) {
 238       match.inline_autocompletion =
 239           match.fill_into_edit.substr(inline_autocomplete_offset);
 240       match.allowed_to_be_default_match =
 241           !HistoryProvider::PreventInlineAutocomplete(input) ||
 242           match.inline_autocompletion.empty();
 243     }
 244   }
 245   match.EnsureUWYTIsAllowedToBeDefault(input,
 246                                        client_->GetAcceptLanguages(),
 247                                        client_->GetTemplateURLService());
 248
 249   // Try to mark pieces of the contents and description as matches if they
 250   // appear in |input.text()|.
 251   const base::string16 term_string = base::i18n::ToLower(input.text());
 252   WordMap terms_map(CreateWordMapForString(term_string));
 253   if (!terms_map.empty()) {
 254     match.contents_class = ClassifyAllMatchesInString(
 255         term_string, terms_map, match.contents, match.contents_class);
 256     match.description_class = ClassifyAllMatchesInString(
 257         term_string, terms_map, match.description, match.description_class);
 258   }
 259   return match;
 260 }
 261
 262 // static
 263 ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString(
 264     const base::string16& text) {
 265   // First, convert |text| to a vector of the unique words in it.
 266   WordMap word_map;
 267   base::i18n::BreakIterator word_iter(text,
 268                                       base::i18n::BreakIterator::BREAK_WORD);
 269   if (!word_iter.Init())
 270     return word_map;
 271   std::vector<base::string16> words;
 272   while (word_iter.Advance()) {
 273     if (word_iter.IsWord())
 274       words.push_back(word_iter.GetString());
 275   }
 276   if (words.empty())
 277     return word_map;
 278   std::sort(words.begin(), words.end());
 279   words.erase(std::unique(words.begin(), words.end()), words.end());
 280
 281   // Now create a map from (first character) to (words beginning with that
 282   // character).  We insert in reverse lexicographical order and rely on the
 283   // multimap preserving insertion order for values with the same key.  (This
 284   // is mandated in C++11, and part of that decision was based on a survey of
 285   // existing implementations that found that it was already true everywhere.)
 286   std::reverse(words.begin(), words.end());
 287   for (std::vector<base::string16>::const_iterator i(words.begin());
 288        i != words.end(); ++i)
 289     word_map.insert(std::make_pair((*i)[0], *i));
 290   return word_map;
 291 }
 292
 293 // static
 294 ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString(
 295     const base::string16& find_text,
 296     const WordMap& find_words,
 297     const base::string16& text,
 298     const ACMatchClassifications& original_class) {
 299   DCHECK(!find_text.empty());
 300   DCHECK(!find_words.empty());
 301
 302   // The code below assumes |text| is nonempty and therefore the resulting
 303   // classification vector should always be nonempty as well.  Returning early
 304   // if |text| is empty assures we'll return the (correct) empty vector rather
 305   // than a vector with a single (0, NONE) match.
 306   if (text.empty())
 307     return original_class;
 308
 309   // First check whether |text| begins with |find_text| and mark that whole
 310   // section as a match if so.
 311   base::string16 text_lowercase(base::i18n::ToLower(text));
 312   ACMatchClassifications match_class;
 313   size_t last_position = 0;
 314   if (base::StartsWith(text_lowercase, find_text,
 315                        base::CompareCase::SENSITIVE)) {
 316     match_class.push_back(
 317         ACMatchClassification(0, ACMatchClassification::MATCH));
 318     last_position = find_text.length();
 319     // If |text_lowercase| is actually equal to |find_text|, we don't need to
 320     // (and in fact shouldn't) put a trailing NONE classification after the end
 321     // of the string.
 322     if (last_position < text_lowercase.length()) {
 323       match_class.push_back(
 324           ACMatchClassification(last_position, ACMatchClassification::NONE));
 325     }
 326   } else {
 327     // |match_class| should start at position 0.  If the first matching word is
 328     // found at position 0, this will be popped from the vector further down.
 329     match_class.push_back(
 330         ACMatchClassification(0, ACMatchClassification::NONE));
 331   }
 332
 333   // Now, starting with |last_position|, check each character in
 334   // |text_lowercase| to see if we have words starting with that character in
 335   // |find_words|.  If so, check each of them to see if they match the portion
 336   // of |text_lowercase| beginning with |last_position|.  Accept the first
 337   // matching word found (which should be the longest possible match at this
 338   // location, given the construction of |find_words|) and add a MATCH region to
 339   // |match_class|, moving |last_position| to be after the matching word.  If we
 340   // found no matching words, move to the next character and repeat.
 341   while (last_position < text_lowercase.length()) {
 342     std::pair<WordMap::const_iterator, WordMap::const_iterator> range(
 343         find_words.equal_range(text_lowercase[last_position]));
 344     size_t next_character = last_position + 1;
 345     for (WordMap::const_iterator i(range.first); i != range.second; ++i) {
 346       const base::string16& word = i->second;
 347       size_t word_end = last_position + word.length();
 348       if ((word_end <= text_lowercase.length()) &&
 349           !text_lowercase.compare(last_position, word.length(), word)) {
 350         // Collapse adjacent ranges into one.
 351         if (match_class.back().offset == last_position)
 352           match_class.pop_back();
 353
 354         AutocompleteMatch::AddLastClassificationIfNecessary(
 355             &match_class, last_position, ACMatchClassification::MATCH);
 356         if (word_end < text_lowercase.length()) {
 357           match_class.push_back(
 358               ACMatchClassification(word_end, ACMatchClassification::NONE));
 359         }
 360         last_position = word_end;
 361         break;
 362       }
 363     }
 364     last_position = std::max(last_position, next_character);
 365   }
 366
 367   return AutocompleteMatch::MergeClassifications(original_class, match_class);
 368 }
 369
 370 ShortcutsBackend::ShortcutMap::const_iterator ShortcutsProvider::FindFirstMatch(
 371     const base::string16& keyword,
 372     ShortcutsBackend* backend) {
 373   DCHECK(backend);
 374   ShortcutsBackend::ShortcutMap::const_iterator it =
 375       backend->shortcuts_map().lower_bound(keyword);
 376   // Lower bound not necessarily matches the keyword, check for item pointed by
 377   // the lower bound iterator to at least start with keyword.
 378   return ((it == backend->shortcuts_map().end()) ||
 379           base::StartsWith(it->first, keyword, base::CompareCase::SENSITIVE))
 380              ? it
 381              : backend->shortcuts_map().end();
 382 }
 383
 384 int ShortcutsProvider::CalculateScore(
 385     const base::string16& terms,
 386     const ShortcutsDatabase::Shortcut& shortcut,
 387     int max_relevance) {
 388   DCHECK(!terms.empty());
 389   DCHECK_LE(terms.length(), shortcut.text.length());
 390
 391   // The initial score is based on how much of the shortcut the user has typed.
 392   // Using the square root of the typed fraction boosts the base score rapidly
 393   // as characters are typed, compared with simply using the typed fraction
 394   // directly. This makes sense since the first characters typed are much more
 395   // important for determining how likely it is a user wants a particular
 396   // shortcut than are the remaining continued characters.
 397   double base_score = max_relevance * sqrt(static_cast<double>(terms.length()) /
 398                                            shortcut.text.length());
 399
 400   // Then we decay this by half each week.
 401   const double kLn2 = 0.6931471805599453;
 402   base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time;
 403   // Clamp to 0 in case time jumps backwards (e.g. due to DST).
 404   double decay_exponent =
 405       std::max(0.0, kLn2 * static_cast<double>(time_passed.InMicroseconds()) /
 406                         base::Time::kMicrosecondsPerWeek);
 407
 408   // We modulate the decay factor based on how many times the shortcut has been
 409   // used. Newly created shortcuts decay at full speed; otherwise, decaying by
 410   // half takes |n| times as much time, where n increases by
 411   // (1.0 / each 5 additional hits), up to a maximum of 5x as long.
 412   const double kMaxDecaySpeedDivisor = 5.0;
 413   const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0;
 414   double decay_divisor = std::min(
 415       kMaxDecaySpeedDivisor,
 416       (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) /
 417           kNumUsesPerDecaySpeedDivisorIncrement);
 418
 419   return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) +
 420                           0.5);
 421 }