history_url_provider.h revision 5821806d5e7f356e8fa4b058a389a808ea183019
1// Copyright (c) 2012 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 8#include <string> 9#include <vector> 10 11#include "base/compiler_specific.h" 12#include "base/synchronization/cancellation_flag.h" 13#include "chrome/browser/autocomplete/autocomplete_input.h" 14#include "chrome/browser/autocomplete/history_provider.h" 15#include "chrome/browser/autocomplete/history_provider_util.h" 16#include "chrome/browser/autocomplete/url_prefix.h" 17 18class MessageLoop; 19class Profile; 20 21namespace history { 22class HistoryBackend; 23class URLDatabase; 24} 25 26// How history autocomplete works 27// ============================== 28// 29// Read down this diagram for temporal ordering. 30// 31// Main thread History thread 32// ----------- -------------- 33// AutocompleteController::Start 34// -> HistoryURLProvider::Start 35// -> RunAutocompletePasses 36// -> SuggestExactInput 37// [params_ allocated] 38// -> DoAutocomplete (for inline autocomplete) 39// -> URLDatabase::AutocompleteForPrefix (on in-memory DB) 40// -> HistoryService::ScheduleAutocomplete 41// (return to controller) ---- 42// / 43// HistoryBackend::ScheduleAutocomplete 44// -> HistoryURLProvider::ExecuteWithDB 45// -> DoAutocomplete 46// -> URLDatabase::AutocompleteForPrefix 47// / 48// HistoryService::QueryComplete 49// [params_ destroyed] 50// -> AutocompleteProviderListener::OnProviderUpdate 51// 52// The autocomplete controller calls us, and must be called back, on the main 53// thread. When called, we run two autocomplete passes. The first pass runs 54// synchronously on the main thread and queries the in-memory URL database. 55// This pass promotes matches for inline autocomplete if applicable. We do 56// this synchronously so that users get consistent behavior when they type 57// quickly and hit enter, no matter how loaded the main history database is. 58// Doing this synchronously also prevents inline autocomplete from being 59// "flickery" in the AutocompleteEdit. Because the in-memory DB does not have 60// redirect data, results other than the top match might change between the 61// two passes, so we can't just decide to use this pass' matches as the final 62// results. 63// 64// The second autocomplete pass uses the full history database, which must be 65// queried on the history thread. Start() asks the history service schedule to 66// callback on the history thread with a pointer to the main database. When we 67// are done doing queries, we schedule a task on the main thread that notifies 68// the AutocompleteController that we're done. 69// 70// The communication between these threads is done using a 71// HistoryURLProviderParams object. This is allocated in the main thread, and 72// normally deleted in QueryComplete(). So that both autocomplete passes can 73// use the same code, we also use this to hold results during the first 74// autocomplete pass. 75// 76// While the second pass is running, the AutocompleteController may cancel the 77// request. This can happen frequently when the user is typing quickly. In 78// this case, the main thread sets params_->cancel, which the background thread 79// checks periodically. If it finds the flag set, it stops what it's doing 80// immediately and calls back to the main thread. (We don't delete the params 81// on the history thread, because we should only do that when we can safely 82// NULL out params_, and that must be done on the main thread.) 83 84// Used to communicate autocomplete parameters between threads via the history 85// service. 86struct HistoryURLProviderParams { 87 HistoryURLProviderParams(const AutocompleteInput& input, 88 bool trim_http, 89 const std::string& languages); 90 ~HistoryURLProviderParams(); 91 92 MessageLoop* message_loop; 93 94 // A copy of the autocomplete input. We need the copy since this object will 95 // live beyond the original query while it runs on the history thread. 96 AutocompleteInput input; 97 98 // Should inline autocompletion be disabled? This is initalized from 99 // |input.prevent_inline_autocomplete()|, but set to false is the input 100 // contains trailing white space. 101 bool prevent_inline_autocomplete; 102 103 // Set when "http://" should be trimmed from the beginning of the URLs. 104 bool trim_http; 105 106 // Set by the main thread to cancel this request. If this flag is set when 107 // the query runs, the query will be abandoned. This allows us to avoid 108 // running queries that are no longer needed. Since we don't care if we run 109 // the extra queries, the lack of signaling is not a problem. 110 base::CancellationFlag cancel_flag; 111 112 // Set by ExecuteWithDB() on the history thread when the query could not be 113 // performed because the history system failed to properly init the database. 114 // If this is set when the main thread is called back, it avoids changing 115 // |matches_| at all, so it won't delete the default match 116 // RunAutocompletePasses() creates. 117 bool failed; 118 119 // List of matches written by the history thread. We keep this separate list 120 // to avoid having the main thread read the provider's matches while the 121 // history thread is manipulating them. The provider copies this list back 122 // to matches_ on the main thread in QueryComplete(). 123 ACMatches matches; 124 125 // Languages we should pass to gfx::GetCleanStringFromUrl. 126 std::string languages; 127 128 // When true, we should avoid calling SuggestExactInput(). 129 bool dont_suggest_exact_input; 130 131 private: 132 DISALLOW_COPY_AND_ASSIGN(HistoryURLProviderParams); 133}; 134 135// This class is an autocomplete provider and is also a pseudo-internal 136// component of the history system. See comments above. 137class HistoryURLProvider : public HistoryProvider { 138 public: 139 HistoryURLProvider(AutocompleteProviderListener* listener, Profile* profile); 140 141#ifdef UNIT_TEST 142 HistoryURLProvider(AutocompleteProviderListener* listener, 143 Profile* profile, 144 const std::string& languages) 145 : HistoryProvider(listener, profile, 146 AutocompleteProvider::TYPE_HISTORY_URL), 147 params_(NULL), 148 cull_redirects_(true), 149 create_shorter_match_(true), 150 search_url_database_(true), 151 languages_(languages) {} 152#endif 153 154 // Returns a match corresponding to exactly what the user has typed. 155 // NOTE: This does not set the relevance of the returned match, as different 156 // callers want different behavior. Callers must set this manually. 157 // This function is static so SearchProvider may construct similar matches. 158 static AutocompleteMatch SuggestExactInput(AutocompleteProvider* provider, 159 const AutocompleteInput& input, 160 bool trim_http); 161 162 // AutocompleteProvider 163 virtual void Start(const AutocompleteInput& input, 164 bool minimal_changes) OVERRIDE; 165 virtual void Stop(bool clear_cached_results) OVERRIDE; 166 167 // Runs the history query on the history thread, called by the history 168 // system. The history database MAY BE NULL in which case it is not 169 // available and we should return no data. Also schedules returning the 170 // results to the main thread 171 void ExecuteWithDB(history::HistoryBackend* backend, 172 history::URLDatabase* db, 173 HistoryURLProviderParams* params); 174 175 // Actually runs the autocomplete job on the given database, which is 176 // guaranteed not to be NULL. 177 void DoAutocomplete(history::HistoryBackend* backend, 178 history::URLDatabase* db, 179 HistoryURLProviderParams* params); 180 181 // Dispatches the results to the autocomplete controller. Called on the 182 // main thread by ExecuteWithDB when the results are available. 183 // Frees params_gets_deleted on exit. 184 void QueryComplete(HistoryURLProviderParams* params_gets_deleted); 185 186 private: 187 enum MatchType { 188 NORMAL, 189 WHAT_YOU_TYPED, 190 INLINE_AUTOCOMPLETE, 191 UNVISITED_INTRANET, // An intranet site that has never been visited. 192 }; 193 class VisitClassifier; 194 195 ~HistoryURLProvider(); 196 197 // Determines the relevance for a match, given its type. If 198 // |match_type| is NORMAL, |match_number| is a number [0, 199 // kMaxSuggestions) indicating the relevance of the match (higher == 200 // more relevant). For other values of |match_type|, |match_number| 201 // is ignored. Only called some of the time; for some matches, 202 // relevancy scores are assigned consecutively decreasing (1416, 203 // 1415, 1414, ...). 204 int CalculateRelevance(MatchType match_type, size_t match_number) const; 205 206 // Helper function that actually launches the two autocomplete passes. 207 void RunAutocompletePasses(const AutocompleteInput& input, 208 bool fixup_input_and_run_pass_1); 209 210 // Given a |match| containing the "what you typed" suggestion created by 211 // SuggestExactInput(), looks up its info in the DB. If found, fills in the 212 // title from the DB, promotes the match's priority to that of an inline 213 // autocomplete match (maybe it should be slightly better?), and places it on 214 // the front of |matches| (so we pick the right matches to throw away 215 // when culling redirects to/from it). Returns whether a match was promoted. 216 bool FixupExactSuggestion(history::URLDatabase* db, 217 const AutocompleteInput& input, 218 const VisitClassifier& classifier, 219 AutocompleteMatch* match, 220 history::HistoryMatches* matches) const; 221 222 // Helper function for FixupExactSuggestion, this returns true if the input 223 // corresponds to some intranet URL where the user has previously visited the 224 // host in question. In this case the input should be treated as a URL. 225 bool CanFindIntranetURL(history::URLDatabase* db, 226 const AutocompleteInput& input) const; 227 228 // Determines if |match| is suitable for inline autocomplete. If so, and if 229 // |params| is non-NULL, promotes the match. Returns whether |match| is 230 // suitable for inline autocomplete. 231 bool PromoteMatchForInlineAutocomplete(HistoryURLProviderParams* params, 232 const history::HistoryMatch& match); 233 234 // Sees if a shorter version of the best match should be created, and if so 235 // places it at the front of |matches|. This can suggest history URLs that 236 // are prefixes of the best match (if they've been visited enough, compared to 237 // the best match), or create host-only suggestions even when they haven't 238 // been visited before: if the user visited http://example.com/asdf once, 239 // we'll suggest http://example.com/ even if they've never been to it. 240 void PromoteOrCreateShorterSuggestion( 241 history::URLDatabase* db, 242 const HistoryURLProviderParams& params, 243 bool have_what_you_typed_match, 244 const AutocompleteMatch& what_you_typed_match, 245 history::HistoryMatches* matches); 246 247 // Sorts the given list of matches. 248 void SortMatches(history::HistoryMatches* matches) const; 249 250 // Removes results that have been rarely typed or visited, and not any time 251 // recently. The exact parameters for this heuristic can be found in the 252 // function body. 253 void CullPoorMatches(history::HistoryMatches* matches) const; 254 255 // Removes results that redirect to each other, leaving at most |max_results| 256 // results. 257 void CullRedirects(history::HistoryBackend* backend, 258 history::HistoryMatches* matches, 259 size_t max_results) const; 260 261 // Helper function for CullRedirects, this removes all but the first 262 // occurance of [any of the set of strings in |remove|] from the |matches| 263 // list. 264 // 265 // The return value is the index of the item that is after the item in the 266 // input identified by |source_index|. If |source_index| or an item before 267 // is removed, the next item will be shifted, and this allows the caller to 268 // pick up on the next one when this happens. 269 size_t RemoveSubsequentMatchesOf(history::HistoryMatches* matches, 270 size_t source_index, 271 const std::vector<GURL>& remove) const; 272 273 // Converts a line from the database into an autocomplete match for display. 274 AutocompleteMatch HistoryMatchToACMatch( 275 HistoryURLProviderParams* params, 276 const history::HistoryMatch& history_match, 277 MatchType match_type, 278 int relevance); 279 280 // Params for the current query. The provider should not free this directly; 281 // instead, it is passed as a parameter through the history backend, and the 282 // parameter itself is freed once it's no longer needed. The only reason we 283 // keep this member is so we can set the cancel bit on it. 284 HistoryURLProviderParams* params_; 285 286 // If true, HistoryURL provider should lookup and cull redirects. If 287 // false, it returns matches that may be redirects to each other and 288 // simply hopes the default AutoCompleteController behavior to remove 289 // URLs that are likely duplicates (http://google.com <-> 290 // https://www.google.com/, etc.) will do a good enough job. 291 bool cull_redirects_; 292 293 // Used in PromoteOrCreateShorterSuggestion(). If true, we may create 294 // shorter suggestions even when they haven't been visited before: 295 // if the user visited http://example.com/asdf once, we'll suggest 296 // http://example.com/ even if they've never been to it. 297 bool create_shorter_match_; 298 299 // Whether to query the history URL database to match. Even if 300 // false, we still use the URL database to decide if the 301 // URL-what-you-typed was visited before or not. If false, the only 302 // possible result that HistoryURL provider can return is 303 // URL-what-you-typed. This variable is not part of params_ because 304 // it never changes after the HistoryURLProvider is initialized. 305 // It's used to aid the transition to get all URLs from history to 306 // be scored in the HistoryQuick provider only. 307 bool search_url_database_; 308 309 // Only used by unittests; if non-empty, overrides accept-languages in the 310 // profile's pref system. 311 std::string languages_; 312}; 313 314#endif // CHROME_BROWSER_AUTOCOMPLETE_HISTORY_URL_PROVIDER_H_ 315