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