shortcuts_provider.cc revision 868fa2fe829687343ffae624259930155e16dbd8
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.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/profiles/profile.h" 29#include "chrome/common/pref_names.h" 30#include "chrome/common/url_constants.h" 31#include "googleurl/src/url_parse.h" 32 33namespace { 34 35class RemoveMatchPredicate { 36 public: 37 explicit RemoveMatchPredicate(const std::set<GURL>& urls) 38 : urls_(urls) { 39 } 40 bool operator()(const AutocompleteMatch& match) { 41 return urls_.find(match.destination_url) != urls_.end(); 42 } 43 private: 44 // Lifetime of the object is less than the lifetime of passed |urls|, so 45 // it is safe to store reference. 46 const std::set<GURL>& urls_; 47}; 48 49} // namespace 50 51ShortcutsProvider::ShortcutsProvider(AutocompleteProviderListener* listener, 52 Profile* profile) 53 : AutocompleteProvider(listener, profile, 54 AutocompleteProvider::TYPE_SHORTCUTS), 55 languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)), 56 initialized_(false) { 57 scoped_refptr<history::ShortcutsBackend> backend = 58 ShortcutsBackendFactory::GetForProfile(profile_); 59 if (backend.get()) { 60 backend->AddObserver(this); 61 if (backend->initialized()) 62 initialized_ = true; 63 } 64} 65 66void ShortcutsProvider::Start(const AutocompleteInput& input, 67 bool minimal_changes) { 68 matches_.clear(); 69 70 if ((input.type() == AutocompleteInput::INVALID) || 71 (input.type() == AutocompleteInput::FORCED_QUERY)) 72 return; 73 74 // None of our results are applicable for best match. 75 if (input.matches_requested() == AutocompleteInput::BEST_MATCH) 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 97void ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) { 98 // Copy the URL since DeleteMatchesWithURLs() will invalidate |match|. 99 GURL url(match.destination_url); 100 101 // When a user deletes a match, he probably means for the URL to disappear out 102 // of history entirely. So nuke all shortcuts that map to this URL. 103 std::set<GURL> urls; 104 urls.insert(url); 105 // Immediately delete matches and shortcuts with the URL, so we can update the 106 // controller synchronously. 107 DeleteShortcutsWithURLs(urls); 108 DeleteMatchesWithURLs(urls); // NOTE: |match| is now dead! 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::DeleteMatchesWithURLs(const std::set<GURL>& urls) { 131 std::remove_if(matches_.begin(), matches_.end(), RemoveMatchPredicate(urls)); 132 listener_->OnProviderUpdate(true); 133} 134 135void ShortcutsProvider::DeleteShortcutsWithURLs(const std::set<GURL>& urls) { 136 scoped_refptr<history::ShortcutsBackend> backend = 137 ShortcutsBackendFactory::GetForProfileIfExists(profile_); 138 if (!backend.get()) 139 return; // We are off the record. 140 for (std::set<GURL>::const_iterator url = urls.begin(); url != urls.end(); 141 ++url) 142 backend->DeleteShortcutsWithUrl(*url); 143} 144 145void ShortcutsProvider::GetMatches(const AutocompleteInput& input) { 146 scoped_refptr<history::ShortcutsBackend> backend = 147 ShortcutsBackendFactory::GetForProfileIfExists(profile_); 148 if (!backend.get()) 149 return; 150 // Get the URLs from the shortcuts database with keys that partially or 151 // completely match the search term. 152 string16 term_string(base::i18n::ToLower(input.text())); 153 DCHECK(!term_string.empty()); 154 155 for (history::ShortcutsBackend::ShortcutMap::const_iterator it = 156 FindFirstMatch(term_string, backend.get()); 157 it != backend->shortcuts_map().end() && 158 StartsWith(it->first, term_string, true); ++it) { 159 // Don't return shortcuts with zero relevance. 160 int relevance = CalculateScore(term_string, it->second); 161 if (relevance) 162 matches_.push_back(ShortcutToACMatch(relevance, term_string, it->second)); 163 } 164 std::partial_sort(matches_.begin(), 165 matches_.begin() + 166 std::min(AutocompleteProvider::kMaxMatches, matches_.size()), 167 matches_.end(), &AutocompleteMatch::MoreRelevant); 168 if (matches_.size() > AutocompleteProvider::kMaxMatches) { 169 matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches, 170 matches_.end()); 171 } 172} 173 174AutocompleteMatch ShortcutsProvider::ShortcutToACMatch( 175 int relevance, 176 const string16& term_string, 177 const history::ShortcutsBackend::Shortcut& shortcut) { 178 DCHECK(!term_string.empty()); 179 AutocompleteMatch match(this, relevance, true, 180 AutocompleteMatchType::HISTORY_TITLE); 181 match.destination_url = shortcut.url; 182 DCHECK(match.destination_url.is_valid()); 183 match.fill_into_edit = UTF8ToUTF16(shortcut.url.spec()); 184 match.contents = shortcut.contents; 185 match.contents_class = shortcut.contents_class; 186 match.description = shortcut.description; 187 match.description_class = shortcut.description_class; 188 189 // Try to mark pieces of the contents and description as matches if they 190 // appear in |term_string|. 191 WordMap terms_map(CreateWordMapForString(term_string)); 192 if (!terms_map.empty()) { 193 match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, 194 match.contents, match.contents_class); 195 match.description_class = ClassifyAllMatchesInString(term_string, terms_map, 196 match.description, match.description_class); 197 } 198 return match; 199} 200 201// static 202ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( 203 const string16& text) { 204 // First, convert |text| to a vector of the unique words in it. 205 WordMap word_map; 206 base::i18n::BreakIterator word_iter(text, 207 base::i18n::BreakIterator::BREAK_WORD); 208 if (!word_iter.Init()) 209 return word_map; 210 std::vector<string16> words; 211 while (word_iter.Advance()) { 212 if (word_iter.IsWord()) 213 words.push_back(word_iter.GetString()); 214 } 215 if (words.empty()) 216 return word_map; 217 std::sort(words.begin(), words.end()); 218 words.erase(std::unique(words.begin(), words.end()), words.end()); 219 220 // Now create a map from (first character) to (words beginning with that 221 // character). We insert in reverse lexicographical order and rely on the 222 // multimap preserving insertion order for values with the same key. (This 223 // is mandated in C++11, and part of that decision was based on a survey of 224 // existing implementations that found that it was already true everywhere.) 225 std::reverse(words.begin(), words.end()); 226 for (std::vector<string16>::const_iterator i(words.begin()); i != words.end(); 227 ++i) 228 word_map.insert(std::make_pair((*i)[0], *i)); 229 return word_map; 230} 231 232// static 233ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( 234 const string16& find_text, 235 const WordMap& find_words, 236 const string16& text, 237 const ACMatchClassifications& original_class) { 238 DCHECK(!find_text.empty()); 239 DCHECK(!find_words.empty()); 240 241 // The code below assumes |text| is nonempty and therefore the resulting 242 // classification vector should always be nonempty as well. Returning early 243 // if |text| is empty assures we'll return the (correct) empty vector rather 244 // than a vector with a single (0, NONE) match. 245 if (text.empty()) 246 return original_class; 247 248 // First check whether |text| begins with |find_text| and mark that whole 249 // section as a match if so. 250 string16 text_lowercase(base::i18n::ToLower(text)); 251 ACMatchClassifications match_class; 252 size_t last_position = 0; 253 if (StartsWith(text_lowercase, find_text, true)) { 254 match_class.push_back( 255 ACMatchClassification(0, ACMatchClassification::MATCH)); 256 last_position = find_text.length(); 257 // If |text_lowercase| is actually equal to |find_text|, we don't need to 258 // (and in fact shouldn't) put a trailing NONE classification after the end 259 // of the string. 260 if (last_position < text_lowercase.length()) { 261 match_class.push_back( 262 ACMatchClassification(last_position, ACMatchClassification::NONE)); 263 } 264 } else { 265 // |match_class| should start at position 0. If the first matching word is 266 // found at position 0, this will be popped from the vector further down. 267 match_class.push_back( 268 ACMatchClassification(0, ACMatchClassification::NONE)); 269 } 270 271 // Now, starting with |last_position|, check each character in 272 // |text_lowercase| to see if we have words starting with that character in 273 // |find_words|. If so, check each of them to see if they match the portion 274 // of |text_lowercase| beginning with |last_position|. Accept the first 275 // matching word found (which should be the longest possible match at this 276 // location, given the construction of |find_words|) and add a MATCH region to 277 // |match_class|, moving |last_position| to be after the matching word. If we 278 // found no matching words, move to the next character and repeat. 279 while (last_position < text_lowercase.length()) { 280 std::pair<WordMap::const_iterator, WordMap::const_iterator> range( 281 find_words.equal_range(text_lowercase[last_position])); 282 size_t next_character = last_position + 1; 283 for (WordMap::const_iterator i(range.first); i != range.second; ++i) { 284 const string16& word = i->second; 285 size_t word_end = last_position + word.length(); 286 if ((word_end <= text_lowercase.length()) && 287 !text_lowercase.compare(last_position, word.length(), word)) { 288 // Collapse adjacent ranges into one. 289 if (match_class.back().offset == last_position) 290 match_class.pop_back(); 291 292 AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, 293 last_position, ACMatchClassification::MATCH); 294 if (word_end < text_lowercase.length()) { 295 match_class.push_back( 296 ACMatchClassification(word_end, ACMatchClassification::NONE)); 297 } 298 last_position = word_end; 299 break; 300 } 301 } 302 last_position = std::max(last_position, next_character); 303 } 304 305 return AutocompleteMatch::MergeClassifications(original_class, match_class); 306} 307 308history::ShortcutsBackend::ShortcutMap::const_iterator 309 ShortcutsProvider::FindFirstMatch(const string16& keyword, 310 history::ShortcutsBackend* backend) { 311 DCHECK(backend); 312 history::ShortcutsBackend::ShortcutMap::const_iterator it = 313 backend->shortcuts_map().lower_bound(keyword); 314 // Lower bound not necessarily matches the keyword, check for item pointed by 315 // the lower bound iterator to at least start with keyword. 316 return ((it == backend->shortcuts_map().end()) || 317 StartsWith(it->first, keyword, true)) ? it : 318 backend->shortcuts_map().end(); 319} 320 321// static 322int ShortcutsProvider::CalculateScore( 323 const string16& terms, 324 const history::ShortcutsBackend::Shortcut& shortcut) { 325 DCHECK(!terms.empty()); 326 DCHECK_LE(terms.length(), shortcut.text.length()); 327 328 // The initial score is based on how much of the shortcut the user has typed. 329 // Using the square root of the typed fraction boosts the base score rapidly 330 // as characters are typed, compared with simply using the typed fraction 331 // directly. This makes sense since the first characters typed are much more 332 // important for determining how likely it is a user wants a particular 333 // shortcut than are the remaining continued characters. 334 double base_score = (AutocompleteResult::kLowestDefaultScore - 1) * 335 sqrt(static_cast<double>(terms.length()) / shortcut.text.length()); 336 337 // Then we decay this by half each week. 338 const double kLn2 = 0.6931471805599453; 339 base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time; 340 // Clamp to 0 in case time jumps backwards (e.g. due to DST). 341 double decay_exponent = std::max(0.0, kLn2 * static_cast<double>( 342 time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek); 343 344 // We modulate the decay factor based on how many times the shortcut has been 345 // used. Newly created shortcuts decay at full speed; otherwise, decaying by 346 // half takes |n| times as much time, where n increases by 347 // (1.0 / each 5 additional hits), up to a maximum of 5x as long. 348 const double kMaxDecaySpeedDivisor = 5.0; 349 const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; 350 double decay_divisor = std::min(kMaxDecaySpeedDivisor, 351 (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / 352 kNumUsesPerDecaySpeedDivisorIncrement); 353 354 return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + 355 0.5); 356} 357