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