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