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