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.
5 #include "chrome/browser/autocomplete/shortcuts_provider.h"
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/url_prefix.h"
27 #include "chrome/browser/history/history_notifications.h"
28 #include "chrome/browser/history/history_service.h"
29 #include "chrome/browser/history/history_service_factory.h"
30 #include "chrome/browser/history/shortcuts_backend_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"
40 class DestinationURLEqualsURL {
42 explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {}
43 bool operator()(const AutocompleteMatch& match) const {
44 return match.destination_url == url_;
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.
57 const 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;
73 ShortcutsProvider::ShortcutsProvider(AutocompleteProviderListener* listener,
75 : AutocompleteProvider(listener, profile,
76 AutocompleteProvider::TYPE_SHORTCUTS),
77 languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)),
79 scoped_refptr<history::ShortcutsBackend> backend =
80 ShortcutsBackendFactory::GetForProfile(profile_);
82 backend->AddObserver(this);
83 if (backend->initialized())
88 void ShortcutsProvider::Start(const AutocompleteInput& input,
89 bool minimal_changes) {
92 if ((input.type() == AutocompleteInput::INVALID) ||
93 (input.type() == AutocompleteInput::FORCED_QUERY))
96 if (input.text().empty())
102 base::TimeTicks start_time = base::TimeTicks::Now();
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()));
112 UpdateStarredStateOfMatches();
115 void ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) {
116 // Copy the URL since DeleteMatchesWithURLs() will invalidate |match|.
117 GURL url(match.destination_url);
119 // When a user deletes a match, he probably means for the URL to disappear out
120 // of history entirely. So nuke all shortcuts that map to this URL.
121 scoped_refptr<history::ShortcutsBackend> backend =
122 ShortcutsBackendFactory::GetForProfileIfExists(profile_);
123 if (backend) // Can be NULL in Incognito.
124 backend->DeleteShortcutsWithUrl(url);
125 matches_.erase(std::remove_if(matches_.begin(), matches_.end(),
126 DestinationURLEqualsURL(url)),
128 // NOTE: |match| is now dead!
129 listener_->OnProviderUpdate(true);
131 // Delete the match from the history DB. This will eventually result in a
132 // second call to DeleteShortcutsWithURLs(), which is harmless.
133 HistoryService* const history_service =
134 HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
136 DCHECK(history_service && url.is_valid());
137 history_service->DeleteURL(url);
140 ShortcutsProvider::~ShortcutsProvider() {
141 scoped_refptr<history::ShortcutsBackend> backend =
142 ShortcutsBackendFactory::GetForProfileIfExists(profile_);
144 backend->RemoveObserver(this);
147 void ShortcutsProvider::OnShortcutsLoaded() {
151 void ShortcutsProvider::GetMatches(const AutocompleteInput& input) {
152 scoped_refptr<history::ShortcutsBackend> backend =
153 ShortcutsBackendFactory::GetForProfileIfExists(profile_);
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());
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();
167 if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance(
168 input.current_page_classification(), &max_relevance))
169 max_relevance = AutocompleteResult::kLowestDefaultScore - 1;
171 for (history::ShortcutsBackend::ShortcutMap::const_iterator it =
172 FindFirstMatch(term_string, backend.get());
173 it != backend->shortcuts_map().end() &&
174 StartsWith(it->first, term_string, true); ++it) {
175 // Don't return shortcuts with zero relevance.
176 int relevance = CalculateScore(term_string, it->second, max_relevance);
178 matches_.push_back(ShortcutToACMatch(
179 it->second, relevance, term_string, fixed_up_term_string,
180 input.prevent_inline_autocomplete()));
181 matches_.back().ComputeStrippedDestinationURL(profile_);
184 // Remove duplicates.
185 std::sort(matches_.begin(), matches_.end(),
186 &AutocompleteMatch::DestinationSortFunc);
187 matches_.erase(std::unique(matches_.begin(), matches_.end(),
188 &AutocompleteMatch::DestinationsEqual),
190 // Find best matches.
191 std::partial_sort(matches_.begin(),
193 std::min(AutocompleteProvider::kMaxMatches, matches_.size()),
194 matches_.end(), &AutocompleteMatch::MoreRelevant);
195 if (matches_.size() > AutocompleteProvider::kMaxMatches) {
196 matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches,
199 // Reset relevance scores to guarantee no match is given a score that may
200 // allow it to become the highest ranked match (i.e., the default match)
201 // unless either it is a legal default match (i.e., inlineable) or the
202 // omnibox will reorder matches as necessary to correct the problem. In
203 // the process of resetting scores, guarantee that all scores are decreasing
204 // (but do not assign any scores below 1).
205 if (!OmniboxFieldTrial::ReorderForLegalDefaultMatch(
206 input.current_page_classification()) &&
207 (matches_.empty() || !matches_.front().allowed_to_be_default_match)) {
208 max_relevance = std::min(max_relevance,
209 AutocompleteResult::kLowestDefaultScore - 1);
211 for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) {
212 max_relevance = std::min(max_relevance, it->relevance);
213 it->relevance = max_relevance;
214 if (max_relevance > 1)
219 AutocompleteMatch ShortcutsProvider::ShortcutToACMatch(
220 const history::ShortcutsBackend::Shortcut& shortcut,
222 const base::string16& term_string,
223 const base::string16& fixed_up_term_string,
224 const bool prevent_inline_autocomplete) {
225 DCHECK(!term_string.empty());
226 AutocompleteMatch match(shortcut.match_core.ToMatch());
227 match.provider = this;
228 match.relevance = relevance;
229 match.deletable = true;
230 DCHECK(match.destination_url.is_valid());
231 match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits);
232 match.RecordAdditionalInfo("last access time", shortcut.last_access_time);
233 match.RecordAdditionalInfo("original input text",
234 base::UTF16ToUTF8(shortcut.text));
236 // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible.
237 // If the match is a search query this is easy: simply check whether the
238 // user text is a prefix of the query. If the match is a navigation, we
239 // assume the fill_into_edit looks something like a URL, so we use
240 // BestURLPrefix() to try and strip off any prefixes that the user might
241 // not think would change the meaning, but would otherwise prevent inline
242 // autocompletion. This allows, for example, the input of "foo.c" to
243 // autocomplete to "foo.com" for a fill_into_edit of "http://foo.com".
244 if (AutocompleteMatch::IsSearchType(match.type)) {
245 if (StartsWith(match.fill_into_edit, term_string, false)) {
246 match.inline_autocompletion =
247 match.fill_into_edit.substr(term_string.length());
248 match.allowed_to_be_default_match =
249 !prevent_inline_autocomplete || match.inline_autocompletion.empty();
252 const URLPrefix* best_prefix =
253 BestURLPrefixWithWWWCase(match.fill_into_edit, term_string);
254 const base::string16* matching_string = &term_string;
255 // If we failed to find a best_prefix initially, try again using a
256 // fixed-up version of the user input. This is especially useful to
257 // get about: URLs to inline against chrome:// shortcuts. (about:
258 // URLs are fixed up to the chrome:// scheme.)
259 if ((best_prefix == NULL) && !fixed_up_term_string.empty() &&
260 (fixed_up_term_string != term_string)) {
261 best_prefix = BestURLPrefixWithWWWCase(
262 match.fill_into_edit, fixed_up_term_string);
263 matching_string = &fixed_up_term_string;
265 if (best_prefix != NULL) {
266 match.inline_autocompletion = match.fill_into_edit.substr(
267 best_prefix->prefix.length() + matching_string->length());
268 match.allowed_to_be_default_match =
269 !prevent_inline_autocomplete || match.inline_autocompletion.empty();
273 // Try to mark pieces of the contents and description as matches if they
274 // appear in |term_string|.
275 WordMap terms_map(CreateWordMapForString(term_string));
276 if (!terms_map.empty()) {
277 match.contents_class = ClassifyAllMatchesInString(term_string, terms_map,
278 match.contents, match.contents_class);
279 match.description_class = ClassifyAllMatchesInString(term_string, terms_map,
280 match.description, match.description_class);
286 ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString(
287 const base::string16& text) {
288 // First, convert |text| to a vector of the unique words in it.
290 base::i18n::BreakIterator word_iter(text,
291 base::i18n::BreakIterator::BREAK_WORD);
292 if (!word_iter.Init())
294 std::vector<base::string16> words;
295 while (word_iter.Advance()) {
296 if (word_iter.IsWord())
297 words.push_back(word_iter.GetString());
301 std::sort(words.begin(), words.end());
302 words.erase(std::unique(words.begin(), words.end()), words.end());
304 // Now create a map from (first character) to (words beginning with that
305 // character). We insert in reverse lexicographical order and rely on the
306 // multimap preserving insertion order for values with the same key. (This
307 // is mandated in C++11, and part of that decision was based on a survey of
308 // existing implementations that found that it was already true everywhere.)
309 std::reverse(words.begin(), words.end());
310 for (std::vector<base::string16>::const_iterator i(words.begin());
311 i != words.end(); ++i)
312 word_map.insert(std::make_pair((*i)[0], *i));
317 ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString(
318 const base::string16& find_text,
319 const WordMap& find_words,
320 const base::string16& text,
321 const ACMatchClassifications& original_class) {
322 DCHECK(!find_text.empty());
323 DCHECK(!find_words.empty());
325 // The code below assumes |text| is nonempty and therefore the resulting
326 // classification vector should always be nonempty as well. Returning early
327 // if |text| is empty assures we'll return the (correct) empty vector rather
328 // than a vector with a single (0, NONE) match.
330 return original_class;
332 // First check whether |text| begins with |find_text| and mark that whole
333 // section as a match if so.
334 base::string16 text_lowercase(base::i18n::ToLower(text));
335 ACMatchClassifications match_class;
336 size_t last_position = 0;
337 if (StartsWith(text_lowercase, find_text, true)) {
338 match_class.push_back(
339 ACMatchClassification(0, ACMatchClassification::MATCH));
340 last_position = find_text.length();
341 // If |text_lowercase| is actually equal to |find_text|, we don't need to
342 // (and in fact shouldn't) put a trailing NONE classification after the end
344 if (last_position < text_lowercase.length()) {
345 match_class.push_back(
346 ACMatchClassification(last_position, ACMatchClassification::NONE));
349 // |match_class| should start at position 0. If the first matching word is
350 // found at position 0, this will be popped from the vector further down.
351 match_class.push_back(
352 ACMatchClassification(0, ACMatchClassification::NONE));
355 // Now, starting with |last_position|, check each character in
356 // |text_lowercase| to see if we have words starting with that character in
357 // |find_words|. If so, check each of them to see if they match the portion
358 // of |text_lowercase| beginning with |last_position|. Accept the first
359 // matching word found (which should be the longest possible match at this
360 // location, given the construction of |find_words|) and add a MATCH region to
361 // |match_class|, moving |last_position| to be after the matching word. If we
362 // found no matching words, move to the next character and repeat.
363 while (last_position < text_lowercase.length()) {
364 std::pair<WordMap::const_iterator, WordMap::const_iterator> range(
365 find_words.equal_range(text_lowercase[last_position]));
366 size_t next_character = last_position + 1;
367 for (WordMap::const_iterator i(range.first); i != range.second; ++i) {
368 const base::string16& word = i->second;
369 size_t word_end = last_position + word.length();
370 if ((word_end <= text_lowercase.length()) &&
371 !text_lowercase.compare(last_position, word.length(), word)) {
372 // Collapse adjacent ranges into one.
373 if (match_class.back().offset == last_position)
374 match_class.pop_back();
376 AutocompleteMatch::AddLastClassificationIfNecessary(&match_class,
377 last_position, ACMatchClassification::MATCH);
378 if (word_end < text_lowercase.length()) {
379 match_class.push_back(
380 ACMatchClassification(word_end, ACMatchClassification::NONE));
382 last_position = word_end;
386 last_position = std::max(last_position, next_character);
389 return AutocompleteMatch::MergeClassifications(original_class, match_class);
392 history::ShortcutsBackend::ShortcutMap::const_iterator
393 ShortcutsProvider::FindFirstMatch(const base::string16& keyword,
394 history::ShortcutsBackend* backend) {
396 history::ShortcutsBackend::ShortcutMap::const_iterator it =
397 backend->shortcuts_map().lower_bound(keyword);
398 // Lower bound not necessarily matches the keyword, check for item pointed by
399 // the lower bound iterator to at least start with keyword.
400 return ((it == backend->shortcuts_map().end()) ||
401 StartsWith(it->first, keyword, true)) ? it :
402 backend->shortcuts_map().end();
405 int ShortcutsProvider::CalculateScore(
406 const base::string16& terms,
407 const history::ShortcutsBackend::Shortcut& shortcut,
409 DCHECK(!terms.empty());
410 DCHECK_LE(terms.length(), shortcut.text.length());
412 // The initial score is based on how much of the shortcut the user has typed.
413 // Using the square root of the typed fraction boosts the base score rapidly
414 // as characters are typed, compared with simply using the typed fraction
415 // directly. This makes sense since the first characters typed are much more
416 // important for determining how likely it is a user wants a particular
417 // shortcut than are the remaining continued characters.
418 double base_score = max_relevance *
419 sqrt(static_cast<double>(terms.length()) / shortcut.text.length());
421 // Then we decay this by half each week.
422 const double kLn2 = 0.6931471805599453;
423 base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time;
424 // Clamp to 0 in case time jumps backwards (e.g. due to DST).
425 double decay_exponent = std::max(0.0, kLn2 * static_cast<double>(
426 time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek);
428 // We modulate the decay factor based on how many times the shortcut has been
429 // used. Newly created shortcuts decay at full speed; otherwise, decaying by
430 // half takes |n| times as much time, where n increases by
431 // (1.0 / each 5 additional hits), up to a maximum of 5x as long.
432 const double kMaxDecaySpeedDivisor = 5.0;
433 const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0;
434 double decay_divisor = std::min(kMaxDecaySpeedDivisor,
435 (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) /
436 kNumUsesPerDecaySpeedDivisorIncrement);
438 return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) +