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