shortcuts_provider.cc revision 46d4c2bc3267f3f028f39e7e311b0f89aba2e4fd
12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/autocomplete/shortcuts_provider.h" 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include <algorithm> 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <cmath> 91320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include <map> 107dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch#include <vector> 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/i18n/break_iterator.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/i18n/case_conversion.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 1590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "base/metrics/histogram.h" 1603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include "base/prefs/pref_service.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/strings/string_number_conversions.h" 18eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/strings/string_util.h" 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/utf_string_conversions.h" 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/time/time.h" 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/autocomplete/autocomplete_input.h" 2223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)#include "chrome/browser/autocomplete/autocomplete_match.h" 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "chrome/browser/autocomplete/autocomplete_provider_listener.h" 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/autocomplete/autocomplete_result.h" 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "chrome/browser/autocomplete/history_provider.h" 2603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include "chrome/browser/autocomplete/shortcuts_backend_factory.h" 275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "chrome/browser/autocomplete/url_prefix.h" 285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "chrome/browser/history/history_notifications.h" 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/history/history_service.h" 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/history/history_service_factory.h" 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/omnibox/omnibox_field_trial.h" 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/profiles/profile.h" 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/common/net/url_fixer_upper.h" 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/common/pref_names.h" 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/common/url_constants.h" 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "url/url_parse.h" 37eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 38eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochnamespace { 39eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 40eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochclass DestinationURLEqualsURL { 41eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch public: 42eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {} 43eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch bool operator()(const AutocompleteMatch& match) const { 44eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return match.destination_url == url_; 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const GURL url_; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const int ShortcutsProvider::kShortcutsProviderDefaultMaxRelevance = 1199; 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ShortcutsProvider::ShortcutsProvider(AutocompleteProviderListener* listener, 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Profile* profile) 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : AutocompleteProvider(listener, profile, 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AutocompleteProvider::TYPE_SHORTCUTS), 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)), 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) initialized_(false) { 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsBackendFactory::GetForProfile(profile_); 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (backend.get()) { 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) backend->AddObserver(this); 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (backend->initialized()) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) initialized_ = true; 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ShortcutsProvider::Start(const AutocompleteInput& input, 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool minimal_changes) { 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.clear(); 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 73558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch if ((input.type() == AutocompleteInput::INVALID) || 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (input.type() == AutocompleteInput::FORCED_QUERY)) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (input.text().empty()) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!initialized_) 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::TimeTicks start_time = base::TimeTicks::Now(); 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GetMatches(input); 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (input.text().length() < 6) { 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::TimeTicks end_time = base::TimeTicks::Now(); 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string name = "ShortcutsProvider.QueryIndexTime." + 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::IntToString(input.text().size()); 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::HistogramBase* counter = base::Histogram::FactoryGet( 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag); 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) counter->Add(static_cast<int>((end_time - start_time).InMilliseconds())); 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 93ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch UpdateStarredStateOfMatches(); 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 96ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdochvoid ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) { 97ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch // Copy the URL since deleting from |matches_| will invalidate |match|. 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GURL url(match.destination_url); 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(url.is_valid()); 100ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch 101ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch // When a user deletes a match, he probably means for the URL to disappear out 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // of history entirely. So nuke all shortcuts that map to this URL. 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 105cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) if (backend) // Can be NULL in Incognito. 106cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) backend->DeleteShortcutsWithURL(url); 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.erase(std::remove_if(matches_.begin(), matches_.end(), 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DestinationURLEqualsURL(url)), 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.end()); 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // NOTE: |match| is now dead! 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Delete the match from the history DB. This will eventually result in a 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // second call to DeleteShortcutsWithURL(), which is harmless. 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) HistoryService* const history_service = 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS); 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(history_service); 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) history_service->DeleteURL(url); 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ShortcutsProvider::~ShortcutsProvider() { 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (backend.get()) 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) backend->RemoveObserver(this); 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ShortcutsProvider::OnShortcutsLoaded() { 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) initialized_ = true; 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 131eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 1327d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)void ShortcutsProvider::GetMatches(const AutocompleteInput& input) { 1337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!backend.get()) 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Get the URLs from the shortcuts database with keys that partially or 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // completely match the search term. 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::string16 term_string(base::i18n::ToLower(input.text())); 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!term_string.empty()); 141ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const GURL& input_as_gurl = URLFixerUpper::FixupURL( 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::UTF16ToUTF8(input.text()), std::string()); 144ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch const base::string16 fixed_up_input(FixupUserInput(input).second); 145ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int max_relevance; 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance( 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) input.current_page_classification(), &max_relevance)) 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) max_relevance = kShortcutsProviderDefaultMaxRelevance; 15068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (ShortcutsBackend::ShortcutMap::const_iterator it = 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FindFirstMatch(term_string, backend.get()); 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it != backend->shortcuts_map().end() && 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) StartsWith(it->first, term_string, true); ++it) { 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Don't return shortcuts with zero relevance. 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int relevance = CalculateScore(term_string, it->second, max_relevance); 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (relevance) { 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.push_back(ShortcutToACMatch(it->second, relevance, input, 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) fixed_up_input, input_as_gurl)); 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.back().ComputeStrippedDestinationURL(profile_); 161ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch } 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Remove duplicates. Duplicates don't need to be preserved in the matches 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // because they are only used for deletions, and shortcuts deletes matches 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // based on the URL. 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AutocompleteResult::DedupMatchesByDestination( 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) input.current_page_classification(), false, &matches_); 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Find best matches. 169ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch std::partial_sort(matches_.begin(), 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.begin() + 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::min(AutocompleteProvider::kMaxMatches, matches_.size()), 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.end(), &AutocompleteMatch::MoreRelevant); 17368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (matches_.size() > AutocompleteProvider::kMaxMatches) { 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches, 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) matches_.end()); 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Guarantee that all scores are decreasing (but do not assign any scores 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // below 1). 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) { 180ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch max_relevance = std::min(max_relevance, it->relevance); 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it->relevance = max_relevance; 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (max_relevance > 1) 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) --max_relevance; 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)AutocompleteMatch ShortcutsProvider::ShortcutToACMatch( 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const history::ShortcutsDatabase::Shortcut& shortcut, 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int relevance, 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const AutocompleteInput& input, 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const base::string16& fixed_up_input_text, 192ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch const GURL& input_as_gurl) { 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!input.text().empty()); 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AutocompleteMatch match; 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.provider = this; 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.relevance = relevance; 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.deletable = true; 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.fill_into_edit = shortcut.match_core.fill_into_edit; 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.destination_url = shortcut.match_core.destination_url; 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(match.destination_url.is_valid()); 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.contents = shortcut.match_core.contents; 20268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) match.contents_class = AutocompleteMatch::ClassificationsFromString( 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) shortcut.match_core.contents_class); 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.description = shortcut.match_core.description; 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.description_class = AutocompleteMatch::ClassificationsFromString( 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) shortcut.match_core.description_class); 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.transition = 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<content::PageTransition>(shortcut.match_core.transition); 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type); 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.keyword = shortcut.match_core.keyword; 2112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits); 2122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.RecordAdditionalInfo("last access time", shortcut.last_access_time); 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.RecordAdditionalInfo("original input text", 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::UTF16ToUTF8(shortcut.text)); 215ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible. 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If the match is a search query this is easy: simply check whether the 218ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch // user text is a prefix of the query. If the match is a navigation, we 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // assume the fill_into_edit looks something like a URL, so we use 22068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // URLPrefix::GetInlineAutocompleteOffset() to try and strip off any prefixes 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // that the user might not think would change the meaning, but would 222eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // otherwise prevent inline autocompletion. This allows, for example, the 223eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // input of "foo.c" to autocomplete to "foo.com" for a fill_into_edit of 224eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // "http://foo.com". 225eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (AutocompleteMatch::IsSearchType(match.type)) { 226eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (StartsWith(match.fill_into_edit, input.text(), false)) { 227eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch match.inline_autocompletion = 228ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch match.fill_into_edit.substr(input.text().length()); 229eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch match.allowed_to_be_default_match = 230ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch !input.prevent_inline_autocomplete() || 2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.inline_autocompletion.empty(); 2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 2342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const size_t inline_autocomplete_offset = 2357d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) URLPrefix::GetInlineAutocompleteOffset( 2367d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) input.text(), fixed_up_input_text, true, match.fill_into_edit); 2377d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) if (inline_autocomplete_offset != base::string16::npos) { 2382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.inline_autocompletion = 2392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.fill_into_edit.substr(inline_autocomplete_offset); 24090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) match.allowed_to_be_default_match = 2412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) !HistoryProvider::PreventInlineAutocomplete(input) || 2422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.inline_autocompletion.empty(); 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Also allow a user's input to be marked as default if it would be fixed 2452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // up to the same thing as the fill_into_edit. This handles cases like 24690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // the user input containing a trailing slash absent in fill_into_edit. 2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.allowed_to_be_default_match = (input_as_gurl == 2482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) URLFixerUpper::FixupURL(base::UTF16ToUTF8(match.fill_into_edit), 2492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string())); 2502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 25190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 2522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Try to mark pieces of the contents and description as matches if they 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // appear in |input.text()|. 2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const base::string16 term_string = base::i18n::ToLower(input.text()); 2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WordMap terms_map(CreateWordMapForString(term_string)); 2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!terms_map.empty()) { 2587d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, 2597d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) match.contents, match.contents_class); 2607d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) match.description_class = ClassifyAllMatchesInString(term_string, terms_map, 2612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match.description, match.description_class); 2622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return match; 2642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// static 2672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( 2682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const base::string16& text) { 2692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // First, convert |text| to a vector of the unique words in it. 2702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WordMap word_map; 2712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::i18n::BreakIterator word_iter(text, 2722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::i18n::BreakIterator::BREAK_WORD); 27368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (!word_iter.Init()) 2742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return word_map; 2752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<base::string16> words; 27668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) while (word_iter.Advance()) { 2772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (word_iter.IsWord()) 2782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) words.push_back(word_iter.GetString()); 2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (words.empty()) 2812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return word_map; 2825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::sort(words.begin(), words.end()); 2832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) words.erase(std::unique(words.begin(), words.end()), words.end()); 2842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Now create a map from (first character) to (words beginning with that 2862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // character). We insert in reverse lexicographical order and rely on the 2872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // multimap preserving insertion order for values with the same key. (This 2882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // is mandated in C++11, and part of that decision was based on a survey of 28968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // existing implementations that found that it was already true everywhere.) 2902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::reverse(words.begin(), words.end()); 2912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (std::vector<base::string16>::const_iterator i(words.begin()); 29268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) i != words.end(); ++i) 2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) word_map.insert(std::make_pair((*i)[0], *i)); 2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return word_map; 2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// static 2982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( 2992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const base::string16& find_text, 3002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const WordMap& find_words, 30168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) const base::string16& text, 3022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const ACMatchClassifications& original_class) { 3032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!find_text.empty()); 3042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!find_words.empty()); 3052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The code below assumes |text| is nonempty and therefore the resulting 3072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // classification vector should always be nonempty as well. Returning early 3082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // if |text| is empty assures we'll return the (correct) empty vector rather 3092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // than a vector with a single (0, NONE) match. 3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (text.empty()) 3112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return original_class; 31268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 3132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // First check whether |text| begins with |find_text| and mark that whole 31468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // section as a match if so. 3152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::string16 text_lowercase(base::i18n::ToLower(text)); 3162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ACMatchClassifications match_class; 3172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t last_position = 0; 3182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (StartsWith(text_lowercase, find_text, true)) { 3192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match_class.push_back( 3202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ACMatchClassification(0, ACMatchClassification::MATCH)); 3212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_position = find_text.length(); 3222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If |text_lowercase| is actually equal to |find_text|, we don't need to 3232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // (and in fact shouldn't) put a trailing NONE classification after the end 32468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // of the string. 3252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (last_position < text_lowercase.length()) { 3262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match_class.push_back( 3272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ACMatchClassification(last_position, ACMatchClassification::NONE)); 3282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 3302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |match_class| should start at position 0. If the first matching word is 3312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // found at position 0, this will be popped from the vector further down. 3322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match_class.push_back( 3332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ACMatchClassification(0, ACMatchClassification::NONE)); 334ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch } 3352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 33668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Now, starting with |last_position|, check each character in 3372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |text_lowercase| to see if we have words starting with that character in 3382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |find_words|. If so, check each of them to see if they match the portion 33968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // of |text_lowercase| beginning with |last_position|. Accept the first 3402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // matching word found (which should be the longest possible match at this 3412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // location, given the construction of |find_words|) and add a MATCH region to 3422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |match_class|, moving |last_position| to be after the matching word. If we 3432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // found no matching words, move to the next character and repeat. 3442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (last_position < text_lowercase.length()) { 3452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<WordMap::const_iterator, WordMap::const_iterator> range( 3462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) find_words.equal_range(text_lowercase[last_position])); 3472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t next_character = last_position + 1; 3482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (WordMap::const_iterator i(range.first); i != range.second; ++i) { 3495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const base::string16& word = i->second; 3502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t word_end = last_position + word.length(); 3515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if ((word_end <= text_lowercase.length()) && 3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) !text_lowercase.compare(last_position, word.length(), word)) { 3535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Collapse adjacent ranges into one. 35468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (match_class.back().offset == last_position) 3552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match_class.pop_back(); 3562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 35768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, 3582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_position, ACMatchClassification::MATCH); 3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (word_end < text_lowercase.length()) { 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) match_class.push_back( 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ACMatchClassification(word_end, ACMatchClassification::NONE)); 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3637d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) last_position = word_end; 3647d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) break; 3657d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 3662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_position = std::max(last_position, next_character); 3682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 369ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch 3702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return AutocompleteMatch::MergeClassifications(original_class, match_class); 3712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ShortcutsBackend::ShortcutMap::const_iterator 3742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsProvider::FindFirstMatch(const base::string16& keyword, 3752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsBackend* backend) { 3762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(backend); 3772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ShortcutsBackend::ShortcutMap::const_iterator it = 3782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) backend->shortcuts_map().lower_bound(keyword); 3792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Lower bound not necessarily matches the keyword, check for item pointed by 3802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // the lower bound iterator to at least start with keyword. 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return ((it == backend->shortcuts_map().end()) || 3822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) StartsWith(it->first, keyword, true)) ? it : 3832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) backend->shortcuts_map().end(); 3842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int ShortcutsProvider::CalculateScore( 387eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch const base::string16& terms, 388eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch const history::ShortcutsDatabase::Shortcut& shortcut, 389eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch int max_relevance) { 3902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!terms.empty()); 391a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_LE(terms.length(), shortcut.text.length()); 392a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 3932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The initial score is based on how much of the shortcut the user has typed. 3942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Using the square root of the typed fraction boosts the base score rapidly 395cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // as characters are typed, compared with simply using the typed fraction 396cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // directly. This makes sense since the first characters typed are much more 3972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // important for determining how likely it is a user wants a particular 398a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // shortcut than are the remaining continued characters. 399cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) double base_score = max_relevance * 4002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) sqrt(static_cast<double>(terms.length()) / shortcut.text.length()); 4012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Then we decay this by half each week. 4032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const double kLn2 = 0.6931471805599453; 4042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time; 405eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // Clamp to 0 in case time jumps backwards (e.g. due to DST). 4062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) double decay_exponent = std::max(0.0, kLn2 * static_cast<double>( 4072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek); 4082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // We modulate the decay factor based on how many times the shortcut has been 4107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // used. Newly created shortcuts decay at full speed; otherwise, decaying by 411eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // half takes |n| times as much time, where n increases by 4122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // (1.0 / each 5 additional hits), up to a maximum of 5x as long. 4132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const double kMaxDecaySpeedDivisor = 5.0; 414c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; 415c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) double decay_divisor = std::min(kMaxDecaySpeedDivisor, 4162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / 417c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) kNumUsesPerDecaySpeedDivisorIncrement); 4182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + 420c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 0.5); 4212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 422c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)