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