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