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