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