src/chrome/browser/autocomplete/history_quick_provider.cc

   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 #include "chrome/browser/autocomplete/history_quick_provider.h"
   6
   7 #include <vector>
   8
   9 #include "base/basictypes.h"
  10 #include "base/command_line.h"
  11 #include "base/i18n/break_iterator.h"
  12 #include "base/logging.h"
  13 #include "base/metrics/field_trial.h"
  14 #include "base/metrics/histogram.h"
  15 #include "base/prefs/pref_service.h"
  16 #include "base/strings/string_number_conversions.h"
  17 #include "base/strings/string_util.h"
  18 #include "base/strings/utf_string_conversions.h"
  19 #include "base/time/time.h"
  20 #include "chrome/browser/autocomplete/autocomplete_result.h"
  21 #include "chrome/browser/autocomplete/history_url_provider.h"
  22 #include "chrome/browser/history/history_database.h"
  23 #include "chrome/browser/history/history_service.h"
  24 #include "chrome/browser/history/history_service_factory.h"
  25 #include "chrome/browser/history/in_memory_url_index.h"
  26 #include "chrome/browser/history/in_memory_url_index_types.h"
  27 #include "chrome/browser/history/scored_history_match.h"
  28 #include "chrome/browser/omnibox/omnibox_field_trial.h"
  29 #include "chrome/browser/profiles/profile.h"
  30 #include "chrome/browser/search/search.h"
  31 #include "chrome/browser/search_engines/template_url.h"
  32 #include "chrome/browser/search_engines/template_url_service.h"
  33 #include "chrome/browser/search_engines/template_url_service_factory.h"
  34 #include "chrome/common/autocomplete_match_type.h"
  35 #include "chrome/common/chrome_switches.h"
  36 #include "chrome/common/net/url_fixer_upper.h"
  37 #include "chrome/common/pref_names.h"
  38 #include "chrome/common/url_constants.h"
  39 #include "content/public/browser/browser_thread.h"
  40 #include "content/public/browser/notification_source.h"
  41 #include "content/public/browser/notification_types.h"
  42 #include "net/base/escape.h"
  43 #include "net/base/net_util.h"
  44 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
  45 #include "url/url_parse.h"
  46 #include "url/url_util.h"
  47
  48 using history::InMemoryURLIndex;
  49 using history::ScoredHistoryMatch;
  50 using history::ScoredHistoryMatches;
  51
  52 bool HistoryQuickProvider::disabled_ = false;
  53
  54 HistoryQuickProvider::HistoryQuickProvider(
  55     AutocompleteProviderListener* listener,
  56     Profile* profile)
  57     : HistoryProvider(listener, profile,
  58           AutocompleteProvider::TYPE_HISTORY_QUICK),
  59       languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)) {
  60 }
  61
  62 void HistoryQuickProvider::Start(const AutocompleteInput& input,
  63                                  bool minimal_changes) {
  64   matches_.clear();
  65   if (disabled_)
  66     return;
  67
  68   // Don't bother with INVALID and FORCED_QUERY.  Also pass when looking for
  69   // BEST_MATCH and there is no inline autocompletion because none of the HQP
  70   // matches can score highly enough to qualify.
  71   if ((input.type() == AutocompleteInput::INVALID) ||
  72       (input.type() == AutocompleteInput::FORCED_QUERY) ||
  73       (input.matches_requested() == AutocompleteInput::BEST_MATCH &&
  74        input.prevent_inline_autocomplete()))
  75     return;
  76
  77   autocomplete_input_ = input;
  78
  79   // TODO(pkasting): We should just block here until this loads.  Any time
  80   // someone unloads the history backend, we'll get inconsistent inline
  81   // autocomplete behavior here.
  82   if (GetIndex()) {
  83     base::TimeTicks start_time = base::TimeTicks::Now();
  84     DoAutocomplete();
  85     if (input.text().length() < 6) {
  86       base::TimeTicks end_time = base::TimeTicks::Now();
  87       std::string name = "HistoryQuickProvider.QueryIndexTime." +
  88           base::IntToString(input.text().length());
  89       base::HistogramBase* counter = base::Histogram::FactoryGet(
  90           name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
  91       counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
  92     }
  93     UpdateStarredStateOfMatches();
  94   }
  95 }
  96
  97 void HistoryQuickProvider::DeleteMatch(const AutocompleteMatch& match) {
  98   DCHECK(match.deletable);
  99   DCHECK(match.destination_url.is_valid());
 100   // Delete the match from the InMemoryURLIndex.
 101   GetIndex()->DeleteURL(match.destination_url);
 102   DeleteMatchFromMatches(match);
 103 }
 104
 105 HistoryQuickProvider::~HistoryQuickProvider() {}
 106
 107 void HistoryQuickProvider::DoAutocomplete() {
 108   // Get the matching URLs from the DB.
 109   ScoredHistoryMatches matches = GetIndex()->HistoryItemsForTerms(
 110       autocomplete_input_.text(),
 111       autocomplete_input_.cursor_position());
 112   if (matches.empty())
 113     return;
 114
 115   // Figure out if HistoryURL provider has a URL-what-you-typed match
 116   // that ought to go first and what its score will be.
 117   bool will_have_url_what_you_typed_match_first = false;
 118   int url_what_you_typed_match_score = -1;  // undefined
 119   // These are necessary (but not sufficient) conditions for the omnibox
 120   // input to be a URL-what-you-typed match.  The username test checks that
 121   // either the username does not exist (a regular URL such as http://site/)
 122   // or, if the username exists (http://user@site/), there must be either
 123   // a password or a port.  Together these exclude pure username@site
 124   // inputs because these are likely to be an e-mail address.  HistoryURL
 125   // provider won't promote the URL-what-you-typed match to first
 126   // for these inputs.
 127   const bool can_have_url_what_you_typed_match_first =
 128       autocomplete_input_.canonicalized_url().is_valid() &&
 129       (autocomplete_input_.type() != AutocompleteInput::QUERY) &&
 130       (autocomplete_input_.type() != AutocompleteInput::FORCED_QUERY) &&
 131       (!autocomplete_input_.parts().username.is_nonempty() ||
 132        autocomplete_input_.parts().password.is_nonempty() ||
 133        autocomplete_input_.parts().path.is_nonempty());
 134   if (can_have_url_what_you_typed_match_first) {
 135     HistoryService* const history_service =
 136         HistoryServiceFactory::GetForProfile(profile_,
 137                                              Profile::EXPLICIT_ACCESS);
 138     // We expect HistoryService to be available.  In case it's not,
 139     // (e.g., due to Profile corruption) we let HistoryQuick provider
 140     // completions (which may be available because it's a different
 141     // data structure) compete with the URL-what-you-typed match as
 142     // normal.
 143     if (history_service) {
 144       history::URLDatabase* url_db = history_service->InMemoryDatabase();
 145       // url_db can be NULL if it hasn't finished initializing (or
 146       // failed to to initialize).  In this case, we let HistoryQuick
 147       // provider completions compete with the URL-what-you-typed
 148       // match as normal.
 149       if (url_db) {
 150         const std::string host(UTF16ToUTF8(autocomplete_input_.text().substr(
 151             autocomplete_input_.parts().host.begin,
 152             autocomplete_input_.parts().host.len)));
 153         // We want to put the URL-what-you-typed match first if either
 154         // * the user visited the URL before (intranet or internet).
 155         // * it's a URL on a host that user visited before and this
 156         //   is the root path of the host.  (If the user types some
 157         //   of a path--more than a simple "/"--we let autocomplete compete
 158         //   normally with the URL-what-you-typed match.)
 159         // TODO(mpearson): Remove this hacky code and simply score URL-what-
 160         // you-typed in some sane way relative to possible completions:
 161         // URL-what-you-typed should get some sort of a boost relative
 162         // to completions, but completions should naturally win if
 163         // they're a lot more popular.  In this process, if the input
 164         // is a bare intranet hostname that has been visited before, we
 165         // may want to enforce that the only completions that can outscore
 166         // the URL-what-you-typed match are on the same host (i.e., aren't
 167         // from a longer internet hostname for which the omnibox input is
 168         // a prefix).
 169         if (url_db->GetRowForURL(
 170             autocomplete_input_.canonicalized_url(), NULL) != 0) {
 171           // We visited this URL before.
 172           will_have_url_what_you_typed_match_first = true;
 173           // HistoryURLProvider gives visited what-you-typed URLs a high score.
 174           url_what_you_typed_match_score =
 175               HistoryURLProvider::kScoreForBestInlineableResult;
 176         } else if (url_db->IsTypedHost(host) &&
 177              (!autocomplete_input_.parts().path.is_nonempty() ||
 178               ((autocomplete_input_.parts().path.len == 1) &&
 179                (autocomplete_input_.text()[
 180                    autocomplete_input_.parts().path.begin] == '/'))) &&
 181              !autocomplete_input_.parts().query.is_nonempty() &&
 182              !autocomplete_input_.parts().ref.is_nonempty()) {
 183           // Not visited, but we've seen the host before.
 184           will_have_url_what_you_typed_match_first = true;
 185           const size_t registry_length =
 186               net::registry_controlled_domains::GetRegistryLength(
 187                   host,
 188                   net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
 189                   net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
 190           if (registry_length == 0) {
 191             // Known intranet hosts get one score.
 192             url_what_you_typed_match_score =
 193                 HistoryURLProvider::kScoreForUnvisitedIntranetResult;
 194           } else {
 195             // Known internet hosts get another.
 196             url_what_you_typed_match_score =
 197                 HistoryURLProvider::kScoreForWhatYouTypedResult;
 198           }
 199         }
 200       }
 201     }
 202   }
 203
 204   // Loop over every result and add it to matches_.  In the process,
 205   // guarantee that scores are decreasing.  |max_match_score| keeps
 206   // track of the highest score we can assign to any later results we
 207   // see.  Also, if we're not allowing inline autocompletions in
 208   // general or the current best suggestion isn't inlineable,
 209   // artificially reduce the starting |max_match_score| (which
 210   // therefore applies to all results) to something low enough that
 211   // guarantees no result will be offered as an inline autocomplete
 212   // suggestion.  Also do a similar reduction if we think there will be
 213   // a URL-what-you-typed match.  (We want URL-what-you-typed matches for
 214   // visited URLs to beat out any longer URLs, no matter how frequently
 215   // they're visited.)  The strength of this last reduction depends on the
 216   // likely score for the URL-what-you-typed result.
 217
 218   // |template_url_service| or |template_url| can be NULL in unit tests.
 219   TemplateURLService* template_url_service =
 220       TemplateURLServiceFactory::GetForProfile(profile_);
 221   TemplateURL* template_url = template_url_service ?
 222       template_url_service->GetDefaultSearchProvider() : NULL;
 223   int max_match_score =
 224       (OmniboxFieldTrial::ReorderForLegalDefaultMatch(
 225          autocomplete_input_.current_page_classification()) ||
 226        (!PreventInlineAutocomplete(autocomplete_input_) &&
 227         matches.begin()->can_inline)) ?
 228       matches.begin()->raw_score :
 229       (AutocompleteResult::kLowestDefaultScore - 1);
 230   if (will_have_url_what_you_typed_match_first) {
 231     max_match_score = std::min(max_match_score,
 232         url_what_you_typed_match_score - 1);
 233   }
 234   for (ScoredHistoryMatches::const_iterator match_iter = matches.begin();
 235        match_iter != matches.end(); ++match_iter) {
 236     const ScoredHistoryMatch& history_match(*match_iter);
 237     // Culls results corresponding to queries from the default search engine.
 238     // These are low-quality, difficult-to-understand matches for users, and the
 239     // SearchProvider should surface past queries in a better way anyway.
 240     if (!template_url ||
 241         !template_url->IsSearchURL(history_match.url_info.url())) {
 242       // Set max_match_score to the score we'll assign this result:
 243       max_match_score = std::min(max_match_score, history_match.raw_score);
 244       matches_.push_back(QuickMatchToACMatch(history_match, max_match_score));
 245       // Mark this max_match_score as being used:
 246       max_match_score--;
 247     }
 248   }
 249 }
 250
 251 AutocompleteMatch HistoryQuickProvider::QuickMatchToACMatch(
 252     const ScoredHistoryMatch& history_match,
 253     int score) {
 254   const history::URLRow& info = history_match.url_info;
 255   AutocompleteMatch match(this, score, !!info.visit_count(),
 256       history_match.url_matches.empty() ? AutocompleteMatchType::HISTORY_TITLE :
 257           AutocompleteMatchType::HISTORY_URL);
 258   match.typed_count = info.typed_count();
 259   match.destination_url = info.url();
 260   DCHECK(match.destination_url.is_valid());
 261
 262   // Format the URL autocomplete presentation.
 263   std::vector<size_t> offsets =
 264       OffsetsFromTermMatches(history_match.url_matches);
 265   const net::FormatUrlTypes format_types = net::kFormatUrlOmitAll &
 266       ~(!history_match.match_in_scheme ? 0 : net::kFormatUrlOmitHTTP);
 267   match.fill_into_edit =
 268       AutocompleteInput::FormattedStringWithEquivalentMeaning(info.url(),
 269           net::FormatUrlWithOffsets(info.url(), languages_, format_types,
 270               net::UnescapeRule::SPACES, NULL, NULL, &offsets));
 271   history::TermMatches new_matches =
 272       ReplaceOffsetsInTermMatches(history_match.url_matches, offsets);
 273   match.contents = net::FormatUrl(info.url(), languages_, format_types,
 274               net::UnescapeRule::SPACES, NULL, NULL, NULL);
 275   match.contents_class =
 276       SpansFromTermMatch(new_matches, match.contents.length(), true);
 277
 278   match.allowed_to_be_default_match = history_match.can_inline &&
 279       !PreventInlineAutocomplete(autocomplete_input_);
 280   if (match.allowed_to_be_default_match) {
 281     DCHECK(!new_matches.empty());
 282     size_t inline_autocomplete_offset = new_matches[0].offset +
 283         new_matches[0].length;
 284     // |inline_autocomplete_offset| may be beyond the end of the
 285     // |fill_into_edit| if the user has typed an URL with a scheme and the
 286     // last character typed is a slash.  That slash is removed by the
 287     // FormatURLWithOffsets call above.
 288     if (inline_autocomplete_offset < match.fill_into_edit.length()) {
 289       match.inline_autocompletion =
 290           match.fill_into_edit.substr(inline_autocomplete_offset);
 291     }
 292   }
 293
 294   // Format the description autocomplete presentation.
 295   match.description = info.title();
 296   match.description_class = SpansFromTermMatch(
 297       history_match.title_matches, match.description.length(), false);
 298
 299   match.RecordAdditionalInfo("typed count", info.typed_count());
 300   match.RecordAdditionalInfo("visit count", info.visit_count());
 301   match.RecordAdditionalInfo("last visit", info.last_visit());
 302
 303   return match;
 304 }
 305
 306 history::InMemoryURLIndex* HistoryQuickProvider::GetIndex() {
 307   if (index_for_testing_.get())
 308     return index_for_testing_.get();
 309
 310   HistoryService* const history_service =
 311       HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
 312   if (!history_service)
 313     return NULL;
 314
 315   return history_service->InMemoryIndex();
 316 }
 317
 318 // static
 319 ACMatchClassifications HistoryQuickProvider::SpansFromTermMatch(
 320     const history::TermMatches& matches,
 321     size_t text_length,
 322     bool is_url) {
 323   ACMatchClassification::Style url_style =
 324       is_url ? ACMatchClassification::URL : ACMatchClassification::NONE;
 325   ACMatchClassifications spans;
 326   if (matches.empty()) {
 327     if (text_length)
 328       spans.push_back(ACMatchClassification(0, url_style));
 329     return spans;
 330   }
 331   if (matches[0].offset)
 332     spans.push_back(ACMatchClassification(0, url_style));
 333   size_t match_count = matches.size();
 334   for (size_t i = 0; i < match_count;) {
 335     size_t offset = matches[i].offset;
 336     spans.push_back(ACMatchClassification(offset,
 337         ACMatchClassification::MATCH | url_style));
 338     // Skip all adjacent matches.
 339     do {
 340       offset += matches[i].length;
 341       ++i;
 342     } while ((i < match_count) && (offset == matches[i].offset));
 343     if (offset < text_length)
 344       spans.push_back(ACMatchClassification(offset, url_style));
 345   }
 346
 347   return spans;
 348 }