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/history_provider.h" 14 #include "components/history/core/browser/history_match.h" 15 #include "components/omnibox/autocomplete_input.h" 16 #include "components/omnibox/omnibox_field_trial.h" 17 #include "components/search_engines/template_url.h" 18 19 class AutocompleteProviderListener; 20 class Profile; 21 class SearchTermsData; 22 23 namespace base { 24 class MessageLoop; 25 } 26 27 namespace history { 28 class HistoryBackend; 29 class URLDatabase; 30 } 31 32 // How history autocomplete works 33 // ============================== 34 // 35 // Read down this diagram for temporal ordering. 36 // 37 // Main thread History thread 38 // ----------- -------------- 39 // AutocompleteController::Start 40 // -> HistoryURLProvider::Start 41 // -> SuggestExactInput 42 // [params_ allocated] 43 // -> DoAutocomplete (for inline autocomplete) 44 // -> URLDatabase::AutocompleteForPrefix (on in-memory DB) 45 // -> HistoryService::ScheduleAutocomplete 46 // (return to controller) ---- 47 // / 48 // HistoryBackend::ScheduleAutocomplete 49 // -> HistoryURLProvider::ExecuteWithDB 50 // -> DoAutocomplete 51 // -> URLDatabase::AutocompleteForPrefix 52 // / 53 // HistoryService::QueryComplete 54 // [params_ destroyed] 55 // -> AutocompleteProviderListener::OnProviderUpdate 56 // 57 // The autocomplete controller calls us, and must be called back, on the main 58 // thread. When called, we run two autocomplete passes. The first pass runs 59 // synchronously on the main thread and queries the in-memory URL database. 60 // This pass promotes matches for inline autocomplete if applicable. We do 61 // this synchronously so that users get consistent behavior when they type 62 // quickly and hit enter, no matter how loaded the main history database is. 63 // Doing this synchronously also prevents inline autocomplete from being 64 // "flickery" in the AutocompleteEdit. Because the in-memory DB does not have 65 // redirect data, results other than the top match might change between the 66 // two passes, so we can't just decide to use this pass' matches as the final 67 // results. 68 // 69 // The second autocomplete pass uses the full history database, which must be 70 // queried on the history thread. Start() asks the history service schedule to 71 // callback on the history thread with a pointer to the main database. When we 72 // are done doing queries, we schedule a task on the main thread that notifies 73 // the AutocompleteController that we're done. 74 // 75 // The communication between these threads is done using a 76 // HistoryURLProviderParams object. This is allocated in the main thread, and 77 // normally deleted in QueryComplete(). So that both autocomplete passes can 78 // use the same code, we also use this to hold results during the first 79 // autocomplete pass. 80 // 81 // While the second pass is running, the AutocompleteController may cancel the 82 // request. This can happen frequently when the user is typing quickly. In 83 // this case, the main thread sets params_->cancel, which the background thread 84 // checks periodically. If it finds the flag set, it stops what it's doing 85 // immediately and calls back to the main thread. (We don't delete the params 86 // on the history thread, because we should only do that when we can safely 87 // NULL out params_, and that must be done on the main thread.) 88 89 // Used to communicate autocomplete parameters between threads via the history 90 // service. 91 struct HistoryURLProviderParams { 92 // See comments on |promote_type| below. 93 enum PromoteType { 94 WHAT_YOU_TYPED_MATCH, 95 FRONT_HISTORY_MATCH, 96 NEITHER, 97 }; 98 99 HistoryURLProviderParams(const AutocompleteInput& input, 100 bool trim_http, 101 const AutocompleteMatch& what_you_typed_match, 102 const std::string& languages, 103 TemplateURL* default_search_provider, 104 const SearchTermsData& search_terms_data); 105 ~HistoryURLProviderParams(); 106 107 base::MessageLoop* message_loop; 108 109 // A copy of the autocomplete input. We need the copy since this object will 110 // live beyond the original query while it runs on the history thread. 111 AutocompleteInput input; 112 113 // Should inline autocompletion be disabled? This is initalized from 114 // |input.prevent_inline_autocomplete()|, but set to false is the input 115 // contains trailing white space. 116 bool prevent_inline_autocomplete; 117 118 // Set when "http://" should be trimmed from the beginning of the URLs. 119 bool trim_http; 120 121 // A match corresponding to what the user typed. 122 AutocompleteMatch what_you_typed_match; 123 124 // Set by the main thread to cancel this request. If this flag is set when 125 // the query runs, the query will be abandoned. This allows us to avoid 126 // running queries that are no longer needed. Since we don't care if we run 127 // the extra queries, the lack of signaling is not a problem. 128 base::CancellationFlag cancel_flag; 129 130 // Set by ExecuteWithDB() on the history thread when the query could not be 131 // performed because the history system failed to properly init the database. 132 // If this is set when the main thread is called back, it avoids changing 133 // |matches_| at all, so it won't delete the default match Start() creates. 134 bool failed; 135 136 // List of matches written by DoAutocomplete(). Upon its return the provider 137 // converts this list to ACMatches and places them in |matches_|. 138 history::HistoryMatches matches; 139 140 // True if the suggestion for exactly what the user typed appears as a known 141 // URL in the user's history. In this case, this will also be the first match 142 // in |matches|. 143 // 144 // NOTE: There are some complications related to keeping things consistent 145 // between passes and how we deal with intranet URLs, which are too complex to 146 // explain here; see the implementations of DoAutocomplete() and 147 // FixupExactSuggestion() for specific comments. 148 bool exact_suggestion_is_in_history; 149 150 // Tells the provider whether to promote the what you typed match, the first 151 // element of |matches|, or neither as the first AutocompleteMatch. If 152 // |exact_suggestion_is_in_history| is true (and thus "the what you typed 153 // match" and "the first element of |matches|" represent the same thing), this 154 // will be set to WHAT_YOU_TYPED_MATCH. 155 // 156 // NOTE: The second pass of DoAutocomplete() checks what the first pass set 157 // this to. See comments in DoAutocomplete(). 158 PromoteType promote_type; 159 160 // True if |what_you_typed_match| is eligible for display. If this is true, 161 // PromoteMatchesIfNecessary() may choose to place |what_you_typed_match| on 162 // |matches_| even when |promote_type| is not WHAT_YOU_TYPED_MATCH. 163 bool have_what_you_typed_match; 164 165 // Languages we should pass to gfx::GetCleanStringFromUrl. 166 std::string languages; 167 168 // The default search provider and search terms data necessary to cull results 169 // that correspond to searches (on the default engine). These can only be 170 // obtained on the UI thread, so we have to copy them into here to pass them 171 // to the history thread. We use a scoped_ptr<TemplateURL> for the DSP since 172 // TemplateURLs can't be copied by value. We use a scoped_ptr<SearchTermsData> 173 // so that we can store a snapshot of the SearchTermsData accessible from the 174 // history thread. 175 scoped_ptr<TemplateURL> default_search_provider; 176 scoped_ptr<SearchTermsData> search_terms_data; 177 178 private: 179 DISALLOW_COPY_AND_ASSIGN(HistoryURLProviderParams); 180 }; 181 182 // This class is an autocomplete provider and is also a pseudo-internal 183 // component of the history system. See comments above. 184 class HistoryURLProvider : public HistoryProvider { 185 public: 186 // Various values used in scoring, made public so other providers 187 // can insert results in appropriate ranges relative to these. 188 static const int kScoreForBestInlineableResult; 189 static const int kScoreForUnvisitedIntranetResult; 190 static const int kScoreForWhatYouTypedResult; 191 static const int kBaseScoreForNonInlineableResult; 192 193 HistoryURLProvider(AutocompleteProviderListener* listener, Profile* profile); 194 195 // HistoryProvider: 196 virtual void Start(const AutocompleteInput& input, 197 bool minimal_changes) OVERRIDE; 198 virtual void Stop(bool clear_cached_results) OVERRIDE; 199 200 // Returns a match representing a navigation to |destination_url| given user 201 // input of |text|. |trim_http| controls whether the match's |fill_into_edit| 202 // and |contents| should have any HTTP scheme stripped off, and should not be 203 // set to true if |text| contains an http prefix. 204 // NOTES: This does not set the relevance of the returned match, as different 205 // callers want different behavior. Callers must set this manually. 206 // This function should only be called on the UI thread. 207 AutocompleteMatch SuggestExactInput(const base::string16& text, 208 const GURL& destination_url, 209 bool trim_http); 210 211 // Runs the history query on the history thread, called by the history 212 // system. The history database MAY BE NULL in which case it is not 213 // available and we should return no data. Also schedules returning the 214 // results to the main thread 215 void ExecuteWithDB(HistoryURLProviderParams* params, 216 history::HistoryBackend* backend, 217 history::URLDatabase* db); 218 219 private: 220 FRIEND_TEST_ALL_PREFIXES(HistoryURLProviderTest, HUPScoringExperiment); 221 222 enum MatchType { 223 NORMAL, 224 WHAT_YOU_TYPED, 225 INLINE_AUTOCOMPLETE, 226 UNVISITED_INTRANET, // An intranet site that has never been visited. 227 }; 228 class VisitClassifier; 229 230 ~HistoryURLProvider(); 231 232 // Determines the relevance for a match, given its type. If |match_type| is 233 // NORMAL, |match_number| is a number indicating the relevance of the match 234 // (higher == more relevant). For other values of |match_type|, 235 // |match_number| is ignored. Only called some of the time; for some matches, 236 // relevancy scores are assigned consecutively decreasing (1416, 1415, ...). 237 static int CalculateRelevance(MatchType match_type, int match_number); 238 239 // Returns a set of classifications that highlight all the occurrences of 240 // |input_text| at word breaks in |description|. 241 static ACMatchClassifications ClassifyDescription( 242 const base::string16& input_text, 243 const base::string16& description); 244 245 // Actually runs the autocomplete job on the given database, which is 246 // guaranteed not to be NULL. Used by both autocomplete passes, and therefore 247 // called on multiple different threads (though not simultaneously). 248 void DoAutocomplete(history::HistoryBackend* backend, 249 history::URLDatabase* db, 250 HistoryURLProviderParams* params); 251 252 // May promote the what you typed match, the first history match in 253 // parmas->matches, or both to the front of |matches_|, depending on the 254 // values of params->promote_type and params->have_what_you_typed_match. 255 void PromoteMatchesIfNecessary(const HistoryURLProviderParams& params); 256 257 // Dispatches the results to the autocomplete controller. Called on the 258 // main thread by ExecuteWithDB when the results are available. 259 // Frees params_gets_deleted on exit. 260 void QueryComplete(HistoryURLProviderParams* params_gets_deleted); 261 262 // Looks up the info for params->what_you_typed_match in the DB. If found, 263 // fills in the title, promotes the match's priority to that of an inline 264 // autocomplete match (maybe it should be slightly better?), and places it on 265 // the front of params->matches (so we pick the right matches to throw away 266 // when culling redirects to/from it). Returns whether a match was promoted. 267 bool FixupExactSuggestion(history::URLDatabase* db, 268 const VisitClassifier& classifier, 269 HistoryURLProviderParams* params) const; 270 271 // Helper function for FixupExactSuggestion, this returns true if the input 272 // corresponds to some intranet URL where the user has previously visited the 273 // host in question. In this case the input should be treated as a URL. 274 bool CanFindIntranetURL(history::URLDatabase* db, 275 const AutocompleteInput& input) const; 276 277 // Sees if a shorter version of the best match should be created, and if so 278 // places it at the front of params->matches. This can suggest history URLs 279 // that are prefixes of the best match (if they've been visited enough, 280 // compared to the best match), or create host-only suggestions even when they 281 // haven't been visited before: if the user visited http://example.com/asdf 282 // once, we'll suggest http://example.com/ even if they've never been to it. 283 // Returns true if a match was successfully created/promoted that we're 284 // willing to inline autocomplete. 285 bool PromoteOrCreateShorterSuggestion( 286 history::URLDatabase* db, 287 bool have_what_you_typed_match, 288 HistoryURLProviderParams* params); 289 290 // Removes results that have been rarely typed or visited, and not any time 291 // recently. The exact parameters for this heuristic can be found in the 292 // function body. Also culls results corresponding to queries from the default 293 // search engine. These are low-quality, difficult-to-understand matches for 294 // users, and the SearchProvider should surface past queries in a better way 295 // anyway. 296 void CullPoorMatches(HistoryURLProviderParams* params) const; 297 298 // Removes results that redirect to each other, leaving at most |max_results| 299 // results. 300 void CullRedirects(history::HistoryBackend* backend, 301 history::HistoryMatches* matches, 302 size_t max_results) const; 303 304 // Helper function for CullRedirects, this removes all but the first 305 // occurance of [any of the set of strings in |remove|] from the |matches| 306 // list. 307 // 308 // The return value is the index of the item that is after the item in the 309 // input identified by |source_index|. If |source_index| or an item before 310 // is removed, the next item will be shifted, and this allows the caller to 311 // pick up on the next one when this happens. 312 size_t RemoveSubsequentMatchesOf(history::HistoryMatches* matches, 313 size_t source_index, 314 const std::vector<GURL>& remove) const; 315 316 // Converts a specified |match_number| from params.matches into an 317 // autocomplete match for display. If experimental scoring is enabled, the 318 // final relevance score might be different from the given |relevance|. 319 // NOTE: This function should only be called on the UI thread. 320 AutocompleteMatch HistoryMatchToACMatch( 321 const HistoryURLProviderParams& params, 322 size_t match_number, 323 MatchType match_type, 324 int relevance); 325 326 AutocompleteProviderListener* listener_; 327 328 // Params for the current query. The provider should not free this directly; 329 // instead, it is passed as a parameter through the history backend, and the 330 // parameter itself is freed once it's no longer needed. The only reason we 331 // keep this member is so we can set the cancel bit on it. 332 HistoryURLProviderParams* params_; 333 334 // Params controlling experimental behavior of this provider. 335 HUPScoringParams scoring_params_; 336 337 DISALLOW_COPY_AND_ASSIGN(HistoryURLProvider); 338 }; 339 340 #endif // CHROME_BROWSER_AUTOCOMPLETE_HISTORY_URL_PROVIDER_H_ 341