history_url_provider.h revision 731df977c0511bca2206b5f333555b1205ff1f43
1// Copyright (c) 2010 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef CHROME_BROWSER_AUTOCOMPLETE_HISTORY_URL_PROVIDER_H_ 6#define CHROME_BROWSER_AUTOCOMPLETE_HISTORY_URL_PROVIDER_H_ 7#pragma once 8 9#include <string> 10 11#include "chrome/browser/autocomplete/history_provider.h" 12#include "chrome/browser/autocomplete/history_provider_util.h" 13 14class MessageLoop; 15class Profile; 16 17namespace history { 18 19class HistoryBackend; 20class URLDatabase; 21class URLRow; 22 23} // namespace history 24 25// How history autocomplete works 26// ============================== 27// 28// Read down this diagram for temporal ordering. 29// 30// Main thread History thread 31// ----------- -------------- 32// AutocompleteController::Start 33// -> HistoryURLProvider::Start 34// -> RunAutocompletePasses 35// -> SuggestExactInput 36// [params_ allocated] 37// -> DoAutocomplete (for inline autocomplete) 38// -> URLDatabase::AutocompleteForPrefix (on in-memory DB) 39// -> HistoryService::ScheduleAutocomplete 40// (return to controller) ---- 41// / 42// HistoryBackend::ScheduleAutocomplete 43// -> HistoryURLProvider::ExecuteWithDB 44// -> DoAutocomplete 45// -> URLDatabase::AutocompleteForPrefix 46// / 47// HistoryService::QueryComplete 48// [params_ destroyed] 49// -> AutocompleteProvider::Listener::OnProviderUpdate 50// 51// The autocomplete controller calls us, and must be called back, on the main 52// thread. When called, we run two autocomplete passes. The first pass runs 53// synchronously on the main thread and queries the in-memory URL database. 54// This pass promotes matches for inline autocomplete if applicable. We do 55// this synchronously so that users get consistent behavior when they type 56// quickly and hit enter, no matter how loaded the main history database is. 57// Doing this synchronously also prevents inline autocomplete from being 58// "flickery" in the AutocompleteEdit. Because the in-memory DB does not have 59// redirect data, results other than the top match might change between the 60// two passes, so we can't just decide to use this pass' matches as the final 61// results. 62// 63// The second autocomplete pass uses the full history database, which must be 64// queried on the history thread. Start() asks the history service schedule to 65// callback on the history thread with a pointer to the main database. When we 66// are done doing queries, we schedule a task on the main thread that notifies 67// the AutocompleteController that we're done. 68// 69// The communication between these threads is done using a 70// HistoryURLProviderParams object. This is allocated in the main thread, and 71// normally deleted in QueryComplete(). So that both autocomplete passes can 72// use the same code, we also use this to hold results during the first 73// autocomplete pass. 74// 75// While the second pass is running, the AutocompleteController may cancel the 76// request. This can happen frequently when the user is typing quickly. In 77// this case, the main thread sets params_->cancel, which the background thread 78// checks periodically. If it finds the flag set, it stops what it's doing 79// immediately and calls back to the main thread. (We don't delete the params 80// on the history thread, because we should only do that when we can safely 81// NULL out params_, and that must be done on the main thread.) 82 83// Used to communicate autocomplete parameters between threads via the history 84// service. 85struct HistoryURLProviderParams { 86 HistoryURLProviderParams(const AutocompleteInput& input, 87 bool trim_http, 88 const std::string& languages); 89 ~HistoryURLProviderParams(); 90 91 MessageLoop* message_loop; 92 93 // A copy of the autocomplete input. We need the copy since this object will 94 // live beyond the original query while it runs on the history thread. 95 AutocompleteInput input; 96 97 // Set when "http://" should be trimmed from the beginning of the URLs. 98 bool trim_http; 99 100 // Set by the main thread to cancel this request. READ ONLY when running in 101 // ExecuteWithDB() on the history thread to prevent deadlock. If this flag is 102 // set when the query runs, the query will be abandoned. This allows us to 103 // avoid running queries that are no longer needed. Since we don't care if 104 // we run the extra queries, the lack of signaling is not a problem. 105 bool cancel; 106 107 // Set by ExecuteWithDB() on the history thread when the query could not be 108 // performed because the history system failed to properly init the database. 109 // If this is set when the main thread is called back, it avoids changing 110 // |matches_| at all, so it won't delete the default match 111 // RunAutocompletePasses() creates. 112 bool failed; 113 114 // List of matches written by the history thread. We keep this separate list 115 // to avoid having the main thread read the provider's matches while the 116 // history thread is manipulating them. The provider copies this list back 117 // to matches_ on the main thread in QueryComplete(). 118 ACMatches matches; 119 120 // Languages we should pass to gfx::GetCleanStringFromUrl. 121 std::string languages; 122 123 private: 124 DISALLOW_COPY_AND_ASSIGN(HistoryURLProviderParams); 125}; 126 127// This class is an autocomplete provider and is also a pseudo-internal 128// component of the history system. See comments above. 129// 130// Note: This object can get leaked on shutdown if there are pending 131// requests on the database (which hold a reference to us). Normally, these 132// messages get flushed for each thread. We do a round trip from main, to 133// history, back to main while holding a reference. If the main thread 134// completes before the history thread, the message to delegate back to the 135// main thread will not run and the reference will leak. Therefore, don't do 136// anything on destruction. 137class HistoryURLProvider : public HistoryProvider { 138 public: 139 HistoryURLProvider(ACProviderListener* listener, Profile* profile); 140 141#ifdef UNIT_TEST 142 HistoryURLProvider(ACProviderListener* listener, 143 Profile* profile, 144 const std::string& languages) 145 : HistoryProvider(listener, profile, "History"), 146 prefixes_(GetPrefixes()), 147 params_(NULL), 148 languages_(languages) {} 149#endif 150 // no destructor (see note above) 151 152 // AutocompleteProvider 153 virtual void Start(const AutocompleteInput& input, 154 bool minimal_changes); 155 virtual void Stop(); 156 virtual void DeleteMatch(const AutocompleteMatch& match); 157 158 // Runs the history query on the history thread, called by the history 159 // system. The history database MAY BE NULL in which case it is not 160 // available and we should return no data. Also schedules returning the 161 // results to the main thread 162 void ExecuteWithDB(history::HistoryBackend* backend, 163 history::URLDatabase* db, 164 HistoryURLProviderParams* params); 165 166 // Actually runs the autocomplete job on the given database, which is 167 // guaranteed not to be NULL. 168 void DoAutocomplete(history::HistoryBackend* backend, 169 history::URLDatabase* db, 170 HistoryURLProviderParams* params); 171 172 // Dispatches the results to the autocomplete controller. Called on the 173 // main thread by ExecuteWithDB when the results are available. 174 // Frees params_gets_deleted on exit. 175 void QueryComplete(HistoryURLProviderParams* params_gets_deleted); 176 177 private: 178 ~HistoryURLProvider() {} 179 180 // Returns the set of prefixes to use for prefixes_. 181 static history::Prefixes GetPrefixes(); 182 183 // Determines the relevance for some input, given its type and which match it 184 // is. If |match_type| is NORMAL, |match_number| is a number 185 // [0, kMaxSuggestions) indicating the relevance of the match (higher == more 186 // relevant). For other values of |match_type|, |match_number| is ignored. 187 static int CalculateRelevance(AutocompleteInput::Type input_type, 188 MatchType match_type, 189 size_t match_number); 190 191 // Given the user's |input| and a |match| created from it, reduce the 192 // match's URL to just a host. If this host still matches the user input, 193 // return it. Returns the empty string on failure. 194 static GURL ConvertToHostOnly(const history::HistoryMatch& match, 195 const std::wstring& input); 196 197 // See if a shorter version of the best match should be created, and if so 198 // place it at the front of |matches|. This can suggest history URLs that 199 // are prefixes of the best match (if they've been visited enough, compared 200 // to the best match), or create host-only suggestions even when they haven't 201 // been visited before: if the user visited http://example.com/asdf once, 202 // we'll suggest http://example.com/ even if they've never been to it. See 203 // the function body for the exact heuristics used. 204 static void PromoteOrCreateShorterSuggestion( 205 history::URLDatabase* db, 206 const HistoryURLProviderParams& params, 207 bool have_what_you_typed_match, 208 const AutocompleteMatch& what_you_typed_match, 209 history::HistoryMatches* matches); 210 211 // Ensures that |matches| contains an entry for |info|, which may mean adding 212 // a new such entry (using |input_location| and |match_in_scheme|). 213 // 214 // If |promote| is true, this also ensures the entry is the first element in 215 // |matches|, moving or adding it to the front as appropriate. When 216 // |promote| is false, existing matches are left in place, and newly added 217 // matches are placed at the back. 218 static void EnsureMatchPresent(const history::URLRow& info, 219 std::wstring::size_type input_location, 220 bool match_in_scheme, 221 history::HistoryMatches* matches, 222 bool promote); 223 224 // Helper function that actually launches the two autocomplete passes. 225 void RunAutocompletePasses(const AutocompleteInput& input, 226 bool fixup_input_and_run_pass_1); 227 228 // Returns the best prefix that begins |text|. "Best" means "greatest number 229 // of components". This may return NULL if no prefix begins |text|. 230 // 231 // |prefix_suffix| (which may be empty) is appended to every attempted 232 // prefix. This is useful when you need to figure out the innermost match 233 // for some user input in a URL. 234 const history::Prefix* BestPrefix(const GURL& text, 235 const std::wstring& prefix_suffix) const; 236 237 // Returns a match corresponding to exactly what the user has typed. 238 AutocompleteMatch SuggestExactInput(const AutocompleteInput& input, 239 bool trim_http); 240 241 // Given a |match| containing the "what you typed" suggestion created by 242 // SuggestExactInput(), looks up its info in the DB. If found, fills in the 243 // title from the DB, promotes the match's priority to that of an inline 244 // autocomplete match (maybe it should be slightly better?), and places it on 245 // the front of |matches| (so we pick the right matches to throw away 246 // when culling redirects to/from it). Returns whether a match was promoted. 247 bool FixupExactSuggestion(history::URLDatabase* db, 248 const AutocompleteInput& input, 249 AutocompleteMatch* match, 250 history::HistoryMatches* matches) const; 251 252 // Determines if |match| is suitable for inline autocomplete, and promotes it 253 // if so. 254 bool PromoteMatchForInlineAutocomplete(HistoryURLProviderParams* params, 255 const history::HistoryMatch& match); 256 257 // Sorts the given list of matches. 258 void SortMatches(history::HistoryMatches* matches) const; 259 260 // Removes results that have been rarely typed or visited, and not any time 261 // recently. The exact parameters for this heuristic can be found in the 262 // function body. 263 void CullPoorMatches(history::HistoryMatches* matches) const; 264 265 // Removes results that redirect to each other, leaving at most |max_results| 266 // results. 267 void CullRedirects(history::HistoryBackend* backend, 268 history::HistoryMatches* matches, 269 size_t max_results) const; 270 271 // Helper function for CullRedirects, this removes all but the first 272 // occurance of [any of the set of strings in |remove|] from the |matches| 273 // list. 274 // 275 // The return value is the index of the item that is after the item in the 276 // input identified by |source_index|. If |source_index| or an item before 277 // is removed, the next item will be shifted, and this allows the caller to 278 // pick up on the next one when this happens. 279 size_t RemoveSubsequentMatchesOf(history::HistoryMatches* matches, 280 size_t source_index, 281 const std::vector<GURL>& remove) const; 282 283 // Converts a line from the database into an autocomplete match for display. 284 AutocompleteMatch HistoryMatchToACMatch( 285 HistoryURLProviderParams* params, 286 const history::HistoryMatch& history_match, 287 MatchType match_type, 288 size_t match_number); 289 290 // Prefixes to try appending to user input when looking for a match. 291 const history::Prefixes prefixes_; 292 293 // Params for the current query. The provider should not free this directly; 294 // instead, it is passed as a parameter through the history backend, and the 295 // parameter itself is freed once it's no longer needed. The only reason we 296 // keep this member is so we can set the cancel bit on it. 297 HistoryURLProviderParams* params_; 298 299 // Only used by unittests; if non-empty, overrides accept-languages in the 300 // profile's pref system. 301 std::string languages_; 302}; 303 304#endif // CHROME_BROWSER_AUTOCOMPLETE_HISTORY_URL_PROVIDER_H_ 305