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