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