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