15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/browser/autocomplete/shortcuts_provider.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <cmath> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/i18n/break_iterator.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/i18n/case_conversion.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/metrics/histogram.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/prefs/pref_service.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/strings/string_number_conversions.h" 18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/string_util.h" 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/utf_string_conversions.h" 20eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/time/time.h" 215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "chrome/browser/autocomplete/history_provider.h" 2223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)#include "chrome/browser/autocomplete/shortcuts_backend_factory.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/browser/history/history_notifications.h" 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/browser/history/history_service.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/browser/history/history_service_factory.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/browser/profiles/profile.h" 27116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "chrome/browser/search_engines/template_url_service_factory.h" 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/common/pref_names.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/common/url_constants.h" 30f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "components/metrics/proto/omnibox_input_type.pb.h" 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "components/omnibox/autocomplete_input.h" 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "components/omnibox/autocomplete_match.h" 336e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "components/omnibox/autocomplete_result.h" 346e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "components/omnibox/omnibox_field_trial.h" 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "components/omnibox/url_prefix.h" 36f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "components/url_fixer/url_fixer.h" 37eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "url/url_parse.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 414e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)class DestinationURLEqualsURL { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 434e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {} 444e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) bool operator()(const AutocompleteMatch& match) const { 454e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) return match.destination_url == url_; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 484e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) const GURL url_; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 530529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochconst int ShortcutsProvider::kShortcutsProviderDefaultMaxRelevance = 1199; 540529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch 55116680a4aac90f2aa7413d9095a592090648e557Ben MurdochShortcutsProvider::ShortcutsProvider(Profile* profile) 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch : AutocompleteProvider(AutocompleteProvider::TYPE_SHORTCUTS), 57116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch profile_(profile), 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)), 59ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch initialized_(false) { 6023730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ShortcutsBackendFactory::GetForProfile(profile_); 62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (backend.get()) { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend->AddObserver(this); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (backend->initialized()) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) initialized_ = true; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ShortcutsProvider::Start(const AutocompleteInput& input, 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool minimal_changes) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches_.clear(); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 73f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if ((input.type() == metrics::OmniboxInputType::INVALID) || 74f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) (input.type() == metrics::OmniboxInputType::FORCED_QUERY)) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (input.text().empty()) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!initialized_) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks start_time = base::TimeTicks::Now(); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GetMatches(input); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (input.text().length() < 6) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks end_time = base::TimeTicks::Now(); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string name = "ShortcutsProvider.QueryIndexTime." + 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::IntToString(input.text().size()); 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::HistogramBase* counter = base::Histogram::FactoryGet( 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter->Add(static_cast<int>((end_time - start_time).InMilliseconds())); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) { 96a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Copy the URL since deleting from |matches_| will invalidate |match|. 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GURL url(match.destination_url); 9823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) DCHECK(url.is_valid()); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // When a user deletes a match, he probably means for the URL to disappear out 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of history entirely. So nuke all shortcuts that map to this URL. 10223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1034e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 1041320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (backend.get()) // Can be NULL in Incognito. 10523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) backend->DeleteShortcutsWithURL(url); 106a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 1074e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) matches_.erase(std::remove_if(matches_.begin(), matches_.end(), 1084e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) DestinationURLEqualsURL(url)), 1094e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) matches_.end()); 1104e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) // NOTE: |match| is now dead! 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Delete the match from the history DB. This will eventually result in a 11323730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) // second call to DeleteShortcutsWithURL(), which is harmless. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HistoryService* const history_service = 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS); 11623730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) DCHECK(history_service); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) history_service->DeleteURL(url); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ShortcutsProvider::~ShortcutsProvider() { 12123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 123868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (backend.get()) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend->RemoveObserver(this); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ShortcutsProvider::OnShortcutsLoaded() { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) initialized_ = true; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ShortcutsProvider::GetMatches(const AutocompleteInput& input) { 13223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) scoped_refptr<ShortcutsBackend> backend = 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ShortcutsBackendFactory::GetForProfileIfExists(profile_); 134868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!backend.get()) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the URLs from the shortcuts database with keys that partially or 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // completely match the search term. 138a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) base::string16 term_string(base::i18n::ToLower(input.text())); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!term_string.empty()); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 141ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch int max_relevance; 142ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance( 143ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch input.current_page_classification(), &max_relevance)) 1440529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch max_relevance = kShortcutsProviderDefaultMaxRelevance; 145116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch TemplateURLService* template_url_service = 146116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch TemplateURLServiceFactory::GetForProfile(profile_); 147116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const base::string16 fixed_up_input(FixupUserInput(input).second); 14823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) for (ShortcutsBackend::ShortcutMap::const_iterator it = 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FindFirstMatch(term_string, backend.get()); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) it != backend->shortcuts_map().end() && 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StartsWith(it->first, term_string, true); ++it) { 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Don't return shortcuts with zero relevance. 153ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch int relevance = CalculateScore(term_string, it->second, max_relevance); 154a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (relevance) { 15546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) matches_.push_back(ShortcutToACMatch(it->second, relevance, input, 156116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch fixed_up_input)); 157116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch matches_.back().ComputeStrippedDestinationURL(template_url_service); 158a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1600529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // Remove duplicates. Duplicates don't need to be preserved in the matches 1610529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // because they are only used for deletions, and shortcuts deletes matches 1620529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // based on the URL. 163c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch AutocompleteResult::DedupMatchesByDestination( 164c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch input.current_page_classification(), false, &matches_); 1655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Find best matches. 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::partial_sort(matches_.begin(), 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches_.begin() + 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::min(AutocompleteProvider::kMaxMatches, matches_.size()), 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches_.end(), &AutocompleteMatch::MoreRelevant); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (matches_.size() > AutocompleteProvider::kMaxMatches) { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches, 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches_.end()); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 174a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Guarantee that all scores are decreasing (but do not assign any scores 175a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // below 1). 176a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) { 177a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) max_relevance = std::min(max_relevance, it->relevance); 178a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) it->relevance = max_relevance; 179a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (max_relevance > 1) 180a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) --max_relevance; 181eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)AutocompleteMatch ShortcutsProvider::ShortcutToACMatch( 18523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) const history::ShortcutsDatabase::Shortcut& shortcut, 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int relevance, 187a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const AutocompleteInput& input, 188116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const base::string16& fixed_up_input_text) { 189a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch DCHECK(!input.text().empty()); 19023730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) AutocompleteMatch match; 1914e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) match.provider = this; 1924e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) match.relevance = relevance; 1934e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) match.deletable = true; 19423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.fill_into_edit = shortcut.match_core.fill_into_edit; 19523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.destination_url = shortcut.match_core.destination_url; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(match.destination_url.is_valid()); 19723730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.contents = shortcut.match_core.contents; 19823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.contents_class = AutocompleteMatch::ClassificationsFromString( 19923730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) shortcut.match_core.contents_class); 20023730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.description = shortcut.match_core.description; 20123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.description_class = AutocompleteMatch::ClassificationsFromString( 20223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) shortcut.match_core.description_class); 2031320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci match.transition = ui::PageTransitionFromInt(shortcut.match_core.transition); 20423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type); 20523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) match.keyword = shortcut.match_core.keyword; 206eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits); 207eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch match.RecordAdditionalInfo("last access time", shortcut.last_access_time); 2085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) match.RecordAdditionalInfo("original input text", 2095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::UTF16ToUTF8(shortcut.text)); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 211a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible. 212a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // If the match is a search query this is easy: simply check whether the 213a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // user text is a prefix of the query. If the match is a navigation, we 214a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // assume the fill_into_edit looks something like a URL, so we use 2150529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // URLPrefix::GetInlineAutocompleteOffset() to try and strip off any prefixes 2160529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // that the user might not think would change the meaning, but would 2170529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // otherwise prevent inline autocompletion. This allows, for example, the 2180529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // input of "foo.c" to autocomplete to "foo.com" for a fill_into_edit of 2190529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // "http://foo.com". 220a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (AutocompleteMatch::IsSearchType(match.type)) { 221a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (StartsWith(match.fill_into_edit, input.text(), false)) { 222a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) match.inline_autocompletion = 223a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch match.fill_into_edit.substr(input.text().length()); 224a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) match.allowed_to_be_default_match = 225a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch !input.prevent_inline_autocomplete() || 226a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch match.inline_autocompletion.empty(); 227a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 228a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } else { 2290529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch const size_t inline_autocomplete_offset = 2300529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch URLPrefix::GetInlineAutocompleteOffset( 23146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) input.text(), fixed_up_input_text, true, match.fill_into_edit); 232a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (inline_autocomplete_offset != base::string16::npos) { 233a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch match.inline_autocompletion = 234a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch match.fill_into_edit.substr(inline_autocomplete_offset); 235a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) match.allowed_to_be_default_match = 236a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch !HistoryProvider::PreventInlineAutocomplete(input) || 237a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch match.inline_autocompletion.empty(); 238a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 239a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 240116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch match.EnsureUWYTIsAllowedToBeDefault( 241116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch input.canonicalized_url(), 242116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch TemplateURLServiceFactory::GetForProfile(profile_)); 243a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try to mark pieces of the contents and description as matches if they 245a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // appear in |input.text()|. 246a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const base::string16 term_string = base::i18n::ToLower(input.text()); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WordMap terms_map(CreateWordMapForString(term_string)); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!terms_map.empty()) { 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.contents, match.contents_class); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.description_class = ClassifyAllMatchesInString(term_string, terms_map, 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.description, match.description_class); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return match; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( 259a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& text) { 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First, convert |text| to a vector of the unique words in it. 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WordMap word_map; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::i18n::BreakIterator word_iter(text, 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::i18n::BreakIterator::BREAK_WORD); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!word_iter.Init()) 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return word_map; 2665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::vector<base::string16> words; 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (word_iter.Advance()) { 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (word_iter.IsWord()) 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) words.push_back(word_iter.GetString()); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (words.empty()) 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return word_map; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::sort(words.begin(), words.end()); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) words.erase(std::unique(words.begin(), words.end()), words.end()); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now create a map from (first character) to (words beginning with that 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // character). We insert in reverse lexicographical order and rely on the 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // multimap preserving insertion order for values with the same key. (This 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is mandated in C++11, and part of that decision was based on a survey of 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // existing implementations that found that it was already true everywhere.) 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::reverse(words.begin(), words.end()); 2825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (std::vector<base::string16>::const_iterator i(words.begin()); 2835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) i != words.end(); ++i) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) word_map.insert(std::make_pair((*i)[0], *i)); 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return word_map; 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( 290a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& find_text, 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WordMap& find_words, 292a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& text, 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ACMatchClassifications& original_class) { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!find_text.empty()); 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!find_words.empty()); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The code below assumes |text| is nonempty and therefore the resulting 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // classification vector should always be nonempty as well. Returning early 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if |text| is empty assures we'll return the (correct) empty vector rather 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // than a vector with a single (0, NONE) match. 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (text.empty()) 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return original_class; 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First check whether |text| begins with |find_text| and mark that whole 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // section as a match if so. 306a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) base::string16 text_lowercase(base::i18n::ToLower(text)); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ACMatchClassifications match_class; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t last_position = 0; 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (StartsWith(text_lowercase, find_text, true)) { 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_class.push_back( 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ACMatchClassification(0, ACMatchClassification::MATCH)); 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_position = find_text.length(); 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If |text_lowercase| is actually equal to |find_text|, we don't need to 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (and in fact shouldn't) put a trailing NONE classification after the end 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of the string. 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last_position < text_lowercase.length()) { 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_class.push_back( 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ACMatchClassification(last_position, ACMatchClassification::NONE)); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |match_class| should start at position 0. If the first matching word is 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // found at position 0, this will be popped from the vector further down. 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_class.push_back( 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ACMatchClassification(0, ACMatchClassification::NONE)); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now, starting with |last_position|, check each character in 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |text_lowercase| to see if we have words starting with that character in 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |find_words|. If so, check each of them to see if they match the portion 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of |text_lowercase| beginning with |last_position|. Accept the first 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // matching word found (which should be the longest possible match at this 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // location, given the construction of |find_words|) and add a MATCH region to 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |match_class|, moving |last_position| to be after the matching word. If we 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // found no matching words, move to the next character and repeat. 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (last_position < text_lowercase.length()) { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::pair<WordMap::const_iterator, WordMap::const_iterator> range( 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) find_words.equal_range(text_lowercase[last_position])); 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t next_character = last_position + 1; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (WordMap::const_iterator i(range.first); i != range.second; ++i) { 340a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& word = i->second; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t word_end = last_position + word.length(); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((word_end <= text_lowercase.length()) && 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !text_lowercase.compare(last_position, word.length(), word)) { 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Collapse adjacent ranges into one. 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (match_class.back().offset == last_position) 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_class.pop_back(); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_position, ACMatchClassification::MATCH); 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (word_end < text_lowercase.length()) { 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_class.push_back( 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ACMatchClassification(word_end, ACMatchClassification::NONE)); 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_position = word_end; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_position = std::max(last_position, next_character); 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AutocompleteMatch::MergeClassifications(original_class, match_class); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 36423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)ShortcutsBackend::ShortcutMap::const_iterator 365a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) ShortcutsProvider::FindFirstMatch(const base::string16& keyword, 36623730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) ShortcutsBackend* backend) { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(backend); 36823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) ShortcutsBackend::ShortcutMap::const_iterator it = 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend->shortcuts_map().lower_bound(keyword); 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Lower bound not necessarily matches the keyword, check for item pointed by 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the lower bound iterator to at least start with keyword. 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ((it == backend->shortcuts_map().end()) || 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StartsWith(it->first, keyword, true)) ? it : 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend->shortcuts_map().end(); 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ShortcutsProvider::CalculateScore( 378a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const base::string16& terms, 37923730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) const history::ShortcutsDatabase::Shortcut& shortcut, 380ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch int max_relevance) { 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!terms.empty()); 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(terms.length(), shortcut.text.length()); 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The initial score is based on how much of the shortcut the user has typed. 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Using the square root of the typed fraction boosts the base score rapidly 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // as characters are typed, compared with simply using the typed fraction 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // directly. This makes sense since the first characters typed are much more 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // important for determining how likely it is a user wants a particular 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // shortcut than are the remaining continued characters. 390ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch double base_score = max_relevance * 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqrt(static_cast<double>(terms.length()) / shortcut.text.length()); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Then we decay this by half each week. 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double kLn2 = 0.6931471805599453; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Clamp to 0 in case time jumps backwards (e.g. due to DST). 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double decay_exponent = std::max(0.0, kLn2 * static_cast<double>( 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) time_passed.InMicroseconds()) / base::Time::kMicrosecondsPerWeek); 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We modulate the decay factor based on how many times the shortcut has been 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // used. Newly created shortcuts decay at full speed; otherwise, decaying by 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // half takes |n| times as much time, where n increases by 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (1.0 / each 5 additional hits), up to a maximum of 5x as long. 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double kMaxDecaySpeedDivisor = 5.0; 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double decay_divisor = std::min(kMaxDecaySpeedDivisor, 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kNumUsesPerDecaySpeedDivisorIncrement); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0.5); 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 413