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