shortcuts_provider.cc revision a02191e04bc25c4935f804f2c080ae28663d096d
1904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom// Use of this source code is governed by a BSD-style license that can be 3904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom// found in the LICENSE file. 4904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 5904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/shortcuts_provider.h" 6904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 7904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include <algorithm> 8904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include <cmath> 9904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include <map> 10904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include <vector> 11904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 12904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/i18n/break_iterator.h" 13904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/i18n/case_conversion.h" 14904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/logging.h" 15904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/metrics/histogram.h" 16904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/prefs/pref_service.h" 17904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/strings/string_number_conversions.h" 18904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/strings/string_util.h" 19904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/strings/utf_string_conversions.h" 20904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "base/time/time.h" 21904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/autocomplete_input.h" 22904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/autocomplete_match.h" 23904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/autocomplete_provider_listener.h" 24904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/autocomplete_result.h" 25904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/history_provider.h" 26904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/shortcuts_backend_factory.h" 27904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/autocomplete/url_prefix.h" 28904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/history/history_notifications.h" 29904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/history/history_service.h" 30904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/history/history_service_factory.h" 31904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/omnibox/omnibox_field_trial.h" 32904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/browser/profiles/profile.h" 33904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/common/net/url_fixer_upper.h" 34904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/common/pref_names.h" 35904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "chrome/common/url_constants.h" 36904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom#include "url/url_parse.h" 37904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 38904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromnamespace { 39904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 40904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromclass DestinationURLEqualsURL { 41904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom public: 42904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {} 43904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom bool operator()(const AutocompleteMatch& match) const { 44904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return match.destination_url == url_; 45904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 46904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom private: 47904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const GURL url_; 48904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom}; 49904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 50904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} // namespace 51904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 52904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromShortcutsProvider::ShortcutsProvider(AutocompleteProviderListener* listener, 53904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom Profile* profile) 54904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom : AutocompleteProvider(listener, profile, 55904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom AutocompleteProvider::TYPE_SHORTCUTS), 56904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)), 57904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom initialized_(false) { 58904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom scoped_refptr<ShortcutsBackend> backend = 59904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackendFactory::GetForProfile(profile_); 60904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (backend.get()) { 61904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom backend->AddObserver(this); 62904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (backend->initialized()) 63904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom initialized_ = true; 64904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 65904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 66904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 67904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromvoid ShortcutsProvider::Start(const AutocompleteInput& input, 68904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom bool minimal_changes) { 69904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.clear(); 70904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 71904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if ((input.type() == AutocompleteInput::INVALID) || 72904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom (input.type() == AutocompleteInput::FORCED_QUERY)) 73904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return; 74904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 75904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (input.text().empty()) 76904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return; 77904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 78904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (!initialized_) 79904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return; 80904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 81904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::TimeTicks start_time = base::TimeTicks::Now(); 82904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom GetMatches(input); 83904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (input.text().length() < 6) { 84904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::TimeTicks end_time = base::TimeTicks::Now(); 85904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::string name = "ShortcutsProvider.QueryIndexTime." + 86904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::IntToString(input.text().size()); 87904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::HistogramBase* counter = base::Histogram::FactoryGet( 88904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag); 89904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom counter->Add(static_cast<int>((end_time - start_time).InMilliseconds())); 90904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 91ff41a4bc41ae1e1391f9b05117623ff70b985983Kenny Root UpdateStarredStateOfMatches(); 92904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 93904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 94904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromvoid ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) { 95904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Copy the URL since deleting from |matches_| will invalidate |match|. 96904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom GURL url(match.destination_url); 97904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(url.is_valid()); 98904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 99904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // When a user deletes a match, he probably means for the URL to disappear out 100904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // of history entirely. So nuke all shortcuts that map to this URL. 101904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom scoped_refptr<ShortcutsBackend> backend = 102904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackendFactory::GetForProfileIfExists(profile_); 103904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (backend) // Can be NULL in Incognito. 104904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom backend->DeleteShortcutsWithURL(url); 105904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 106904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.erase(std::remove_if(matches_.begin(), matches_.end(), 107904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DestinationURLEqualsURL(url)), 108904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.end()); 109904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // NOTE: |match| is now dead! 110904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 111904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Delete the match from the history DB. This will eventually result in a 112904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // second call to DeleteShortcutsWithURL(), which is harmless. 113904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom HistoryService* const history_service = 114904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS); 115904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(history_service); 116904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom history_service->DeleteURL(url); 117904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 118904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 119904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromShortcutsProvider::~ShortcutsProvider() { 120904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom scoped_refptr<ShortcutsBackend> backend = 121904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackendFactory::GetForProfileIfExists(profile_); 122904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (backend.get()) 123904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom backend->RemoveObserver(this); 124904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 125904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 126904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromvoid ShortcutsProvider::OnShortcutsLoaded() { 127904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom initialized_ = true; 128904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 129904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 130904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromvoid ShortcutsProvider::GetMatches(const AutocompleteInput& input) { 131904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom scoped_refptr<ShortcutsBackend> backend = 132904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackendFactory::GetForProfileIfExists(profile_); 133904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (!backend.get()) 134904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return; 135904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Get the URLs from the shortcuts database with keys that partially or 136904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // completely match the search term. 137904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::string16 term_string(base::i18n::ToLower(input.text())); 138904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(!term_string.empty()); 139904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 140904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom AutocompleteInput fixed_up_input(input); 141904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom FixupUserInput(&fixed_up_input); 142904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const GURL& input_as_gurl = URLFixerUpper::FixupURL( 143904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::UTF16ToUTF8(input.text()), std::string()); 144904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 145904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom int max_relevance; 146904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance( 147904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom input.current_page_classification(), &max_relevance)) 148904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom max_relevance = 1199; 149904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 150904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom for (ShortcutsBackend::ShortcutMap::const_iterator it = 151904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom FindFirstMatch(term_string, backend.get()); 152904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom it != backend->shortcuts_map().end() && 153904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom StartsWith(it->first, term_string, true); ++it) { 154904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Don't return shortcuts with zero relevance. 155904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom int relevance = CalculateScore(term_string, it->second, max_relevance); 156904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (relevance) { 157904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.push_back(ShortcutToACMatch( 158904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom it->second, relevance, input, fixed_up_input, input_as_gurl)); 159904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.back().ComputeStrippedDestinationURL(profile_); 160904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 161904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 162904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Remove duplicates. 163904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // TODO(hfung): Check whether the false below, which does not store duplicates 164904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // in the matches, is correct. 165904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom AutocompleteResult::DedupMatchesByDestination( 166904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom input.current_page_classification(), false, &matches_); 167904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Find best matches. 168904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::partial_sort(matches_.begin(), 169904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.begin() + 170904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::min(AutocompleteProvider::kMaxMatches, matches_.size()), 171904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.end(), &AutocompleteMatch::MoreRelevant); 172904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (matches_.size() > AutocompleteProvider::kMaxMatches) { 173904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches, 174904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom matches_.end()); 175904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 176904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Guarantee that all scores are decreasing (but do not assign any scores 177904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // below 1). 178904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) { 179904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom max_relevance = std::min(max_relevance, it->relevance); 180904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom it->relevance = max_relevance; 181904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (max_relevance > 1) 182904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom --max_relevance; 183904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 184904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 185904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 186904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromAutocompleteMatch ShortcutsProvider::ShortcutToACMatch( 187904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const history::ShortcutsDatabase::Shortcut& shortcut, 188904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom int relevance, 189904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const AutocompleteInput& input, 190904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const AutocompleteInput& fixed_up_input, 191904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const GURL& input_as_gurl) { 192904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(!input.text().empty()); 193904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom AutocompleteMatch match; 194904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.provider = this; 195904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.relevance = relevance; 196904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.deletable = true; 197904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.fill_into_edit = shortcut.match_core.fill_into_edit; 198904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.destination_url = shortcut.match_core.destination_url; 199904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(match.destination_url.is_valid()); 200904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.contents = shortcut.match_core.contents; 201904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.contents_class = AutocompleteMatch::ClassificationsFromString( 202904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom shortcut.match_core.contents_class); 203904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.description = shortcut.match_core.description; 204904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.description_class = AutocompleteMatch::ClassificationsFromString( 205904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom shortcut.match_core.description_class); 206904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.transition = 207904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom static_cast<content::PageTransition>(shortcut.match_core.transition); 208904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type); 209904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.keyword = shortcut.match_core.keyword; 210904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits); 211904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.RecordAdditionalInfo("last access time", shortcut.last_access_time); 212904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.RecordAdditionalInfo("original input text", 213904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::UTF16ToUTF8(shortcut.text)); 214904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 215904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible. 216904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // If the match is a search query this is easy: simply check whether the 217904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // user text is a prefix of the query. If the match is a navigation, we 218904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // assume the fill_into_edit looks something like a URL, so we use 219904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // URLPrefix::ComputeMatchStartAndInlineAutocompleteOffset() to try and strip 220904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // off any prefixes that the user might not think would change the meaning, 221904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // but would otherwise prevent inline autocompletion. This allows, for 222904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // example, the input of "foo.c" to autocomplete to "foo.com" for a 223904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // fill_into_edit of "http://foo.com". 224904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (AutocompleteMatch::IsSearchType(match.type)) { 225904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (StartsWith(match.fill_into_edit, input.text(), false)) { 226904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.inline_autocompletion = 227904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.fill_into_edit.substr(input.text().length()); 228904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.allowed_to_be_default_match = 229904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom !input.prevent_inline_autocomplete() || 230904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.inline_autocompletion.empty(); 231904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 232904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } else { 233904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom size_t match_start, inline_autocomplete_offset; 234904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom URLPrefix::ComputeMatchStartAndInlineAutocompleteOffset( 235904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom input, fixed_up_input, true, match.fill_into_edit, 236904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom &match_start, &inline_autocomplete_offset); 237904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (inline_autocomplete_offset != base::string16::npos) { 238904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.inline_autocompletion = 239904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.fill_into_edit.substr(inline_autocomplete_offset); 240904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.allowed_to_be_default_match = 241904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom !HistoryProvider::PreventInlineAutocomplete(input) || 242904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.inline_autocompletion.empty(); 243904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } else { 244904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Also allow a user's input to be marked as default if it would be fixed 245904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // up to the same thing as the fill_into_edit. This handles cases like 246904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // the user input containing a trailing slash absent in fill_into_edit. 247904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.allowed_to_be_default_match = (input_as_gurl == 248904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom URLFixerUpper::FixupURL(base::UTF16ToUTF8(match.fill_into_edit), 249904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::string())); 250904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 251904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 252904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 253904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Try to mark pieces of the contents and description as matches if they 254904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // appear in |input.text()|. 255904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16 term_string = base::i18n::ToLower(input.text()); 256904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom WordMap terms_map(CreateWordMapForString(term_string)); 257904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (!terms_map.empty()) { 258904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, 259904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.contents, match.contents_class); 260904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.description_class = ClassifyAllMatchesInString(term_string, terms_map, 261904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match.description, match.description_class); 262904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 263904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return match; 264904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 265904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 266904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom// static 267904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( 268904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16& text) { 269904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // First, convert |text| to a vector of the unique words in it. 270904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom WordMap word_map; 271904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::i18n::BreakIterator word_iter(text, 272904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::i18n::BreakIterator::BREAK_WORD); 273904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (!word_iter.Init()) 274904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return word_map; 275904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::vector<base::string16> words; 276904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom while (word_iter.Advance()) { 277904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (word_iter.IsWord()) 278904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom words.push_back(word_iter.GetString()); 279904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 280904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (words.empty()) 281904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return word_map; 282904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::sort(words.begin(), words.end()); 283904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom words.erase(std::unique(words.begin(), words.end()), words.end()); 284904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 285904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Now create a map from (first character) to (words beginning with that 286904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // character). We insert in reverse lexicographical order and rely on the 287904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // multimap preserving insertion order for values with the same key. (This 288904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // is mandated in C++11, and part of that decision was based on a survey of 289904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // existing implementations that found that it was already true everywhere.) 290904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::reverse(words.begin(), words.end()); 291904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom for (std::vector<base::string16>::const_iterator i(words.begin()); 292904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom i != words.end(); ++i) 293904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom word_map.insert(std::make_pair((*i)[0], *i)); 294904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return word_map; 295904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 296904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 297904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom// static 298904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( 299904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16& find_text, 300904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const WordMap& find_words, 301904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16& text, 302904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const ACMatchClassifications& original_class) { 303904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(!find_text.empty()); 304904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(!find_words.empty()); 305904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 306904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // The code below assumes |text| is nonempty and therefore the resulting 307904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // classification vector should always be nonempty as well. Returning early 308904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // if |text| is empty assures we'll return the (correct) empty vector rather 309904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // than a vector with a single (0, NONE) match. 310904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (text.empty()) 311904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return original_class; 312904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 313904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // First check whether |text| begins with |find_text| and mark that whole 314904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // section as a match if so. 315904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::string16 text_lowercase(base::i18n::ToLower(text)); 316904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ACMatchClassifications match_class; 317904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom size_t last_position = 0; 318904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (StartsWith(text_lowercase, find_text, true)) { 319904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match_class.push_back( 320904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ACMatchClassification(0, ACMatchClassification::MATCH)); 321904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom last_position = find_text.length(); 322904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // If |text_lowercase| is actually equal to |find_text|, we don't need to 323904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // (and in fact shouldn't) put a trailing NONE classification after the end 324904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // of the string. 325904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (last_position < text_lowercase.length()) { 326904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match_class.push_back( 327904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ACMatchClassification(last_position, ACMatchClassification::NONE)); 328904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 329904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } else { 330904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // |match_class| should start at position 0. If the first matching word is 331904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // found at position 0, this will be popped from the vector further down. 332904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match_class.push_back( 333904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ACMatchClassification(0, ACMatchClassification::NONE)); 334904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 335904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 336904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Now, starting with |last_position|, check each character in 337904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // |text_lowercase| to see if we have words starting with that character in 338904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // |find_words|. If so, check each of them to see if they match the portion 339904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // of |text_lowercase| beginning with |last_position|. Accept the first 340904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // matching word found (which should be the longest possible match at this 341904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // location, given the construction of |find_words|) and add a MATCH region to 342904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // |match_class|, moving |last_position| to be after the matching word. If we 343904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // found no matching words, move to the next character and repeat. 344904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom while (last_position < text_lowercase.length()) { 345904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom std::pair<WordMap::const_iterator, WordMap::const_iterator> range( 346904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom find_words.equal_range(text_lowercase[last_position])); 347904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom size_t next_character = last_position + 1; 348904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom for (WordMap::const_iterator i(range.first); i != range.second; ++i) { 349904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16& word = i->second; 350904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom size_t word_end = last_position + word.length(); 351904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if ((word_end <= text_lowercase.length()) && 352904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom !text_lowercase.compare(last_position, word.length(), word)) { 353904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Collapse adjacent ranges into one. 354904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (match_class.back().offset == last_position) 35577c6be7176c48d2ce4d5979a84876d34204eedafKenny Root match_class.pop_back(); 356904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 357904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, 358904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom last_position, ACMatchClassification::MATCH); 359904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom if (word_end < text_lowercase.length()) { 360904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom match_class.push_back( 361904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ACMatchClassification(word_end, ACMatchClassification::NONE)); 362904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 363904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom last_position = word_end; 364904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom break; 365904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 366904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 367904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom last_position = std::max(last_position, next_character); 368904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom } 369904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 370904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return AutocompleteMatch::MergeClassifications(original_class, match_class); 371904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 372904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 373904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian CarlstromShortcutsBackend::ShortcutMap::const_iterator 374904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsProvider::FindFirstMatch(const base::string16& keyword, 375904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackend* backend) { 376904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(backend); 377904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom ShortcutsBackend::ShortcutMap::const_iterator it = 378904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom backend->shortcuts_map().lower_bound(keyword); 379904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Lower bound not necessarily matches the keyword, check for item pointed by 380904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // the lower bound iterator to at least start with keyword. 381904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return ((it == backend->shortcuts_map().end()) || 382904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom StartsWith(it->first, keyword, true)) ? it : 383904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom backend->shortcuts_map().end(); 384904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 385904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 386904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstromint ShortcutsProvider::CalculateScore( 387904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const base::string16& terms, 388904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const history::ShortcutsDatabase::Shortcut& shortcut, 389904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom int max_relevance) { 390904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK(!terms.empty()); 391904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom DCHECK_LE(terms.length(), shortcut.text.length()); 392904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 393904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // The initial score is based on how much of the shortcut the user has typed. 394904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Using the square root of the typed fraction boosts the base score rapidly 395904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // as characters are typed, compared with simply using the typed fraction 396904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // directly. This makes sense since the first characters typed are much more 397904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // important for determining how likely it is a user wants a particular 398904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // shortcut than are the remaining continued characters. 399904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom double base_score = max_relevance * 400904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom sqrt(static_cast<double>(terms.length()) / shortcut.text.length()); 401904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 402904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Then we decay this by half each week. 403904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const double kLn2 = 0.6931471805599453; 404904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time; 405904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // Clamp to 0 in case time jumps backwards (e.g. due to DST). 406904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom double decay_exponent = std::max(0.0, kLn2 * static_cast<double>( 407904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek); 408904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 409904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // We modulate the decay factor based on how many times the shortcut has been 410904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // used. Newly created shortcuts decay at full speed; otherwise, decaying by 411904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // half takes |n| times as much time, where n increases by 412904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom // (1.0 / each 5 additional hits), up to a maximum of 5x as long. 413904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const double kMaxDecaySpeedDivisor = 5.0; 414904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; 415904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom double decay_divisor = std::min(kMaxDecaySpeedDivisor, 416904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / 417904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom kNumUsesPerDecaySpeedDivisorIncrement); 418904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 419904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + 420904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom 0.5); 421904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom} 422904c5bb06deb8e0b17c3673c0ceb7d80420c16f3Brian Carlstrom