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