Cleanup:

chrome/browser/autocomplete/history_url_provider.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/autocomplete/history_url_provider.h"
 
 #include <algorithm>
 
 #include "base/basictypes.h"
 #include "base/message_loop.h"
 #include "base/metrics/histogram.h"
 #include "base/string_util.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
 #include "chrome/browser/history/history.h"
 #include "chrome/browser/history/history_backend.h"
 #include "chrome/browser/history/history_database.h"
 #include "chrome/browser/history/history_types.h"
 #include "chrome/browser/net/url_fixer_upper.h"
 #include "chrome/browser/prefs/pref_service.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/common/pref_names.h"
 #include "chrome/common/url_constants.h"
 #include "googleurl/src/gurl.h"
 #include "googleurl/src/url_parse.h"
 #include "googleurl/src/url_util.h"
 #include "net/base/net_util.h"
 
-using base::Time;
-using base::TimeDelta;
-using base::TimeTicks;
-using history::Prefix;
-using history::Prefixes;
-using history::HistoryMatch;
-using history::HistoryMatches;
+namespace {
 
-namespace history {
+// Ensures that |matches| contains an entry for |info|, which may mean adding a
+// new such entry (using |input_location| and |match_in_scheme|).
+//
+// If |promote| is true, this also ensures the entry is the first element in
+// |matches|, moving or adding it to the front as appropriate.  When |promote|
+// is false, existing matches are left in place, and newly added matches are
+// placed at the back.
+void EnsureMatchPresent(const history::URLRow& info,
+                        size_t input_location,
+                        bool match_in_scheme,
+                        history::HistoryMatches* matches,
+                        bool promote) {
+  // |matches| may already have an entry for this.
+  for (history::HistoryMatches::iterator i(matches->begin());
+       i != matches->end(); ++i) {
+    if (i->url_info.url() == info.url()) {
+      // Rotate it to the front if the caller wishes.
+      if (promote)
+        std::rotate(matches->begin(), i, i + 1);
+      return;
+    }
+  }
 
-// Returns true if |url| is just a host (e.g. "http://www.google.com/") and
-// not some other subpage (e.g. "http://www.google.com/foo.html").
+  // No entry, so create one.
+  history::HistoryMatch match(info, input_location, match_in_scheme, true);
+  if (promote)
+    matches->push_front(match);
+  else
+    matches->push_back(match);
+}
+
+// Given the user's |input| and a |match| created from it, reduce the match's
+// URL to just a host.  If this host still matches the user input, return it.
+// Returns the empty string on failure.
+GURL ConvertToHostOnly(const history::HistoryMatch& match,
+                       const string16& input) {
+  // See if we should try to do host-only suggestions for this URL. Nonstandard
+  // schemes means there's no authority section, so suggesting the host name
+  // is useless. File URLs are standard, but host suggestion is not useful for
+  // them either.
+  const GURL& url = match.url_info.url();
+  if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile())
+    return GURL();
+
+  // Transform to a host-only match.  Bail if the host no longer matches the
+  // user input (e.g. because the user typed more than just a host).
+  GURL host = url.GetWithEmptyPath();
+  if ((host.spec().length() < (match.input_location + input.length())))
+    return GURL();  // User typing is longer than this host suggestion.
+
+  const string16 spec = UTF8ToUTF16(host.spec());
+  if (spec.compare(match.input_location, input.length(), input))
+    return GURL();  // User typing is no longer a prefix.
+
+  return host;
+}
+
+// See if a shorter version of the best match should be created, and if so place
+// it at the front of |matches|.  This can suggest history URLs that are
+// prefixes of the best match (if they've been visited enough, compared to the
+// best match), or create host-only suggestions even when they haven't been
+// visited before: if the user visited http://example.com/asdf once, we'll
+// suggest http://example.com/ even if they've never been to it.
+void PromoteOrCreateShorterSuggestion(
+    history::URLDatabase* db,
+    const HistoryURLProviderParams& params,
+    bool have_what_you_typed_match,
+    const AutocompleteMatch& what_you_typed_match,
+    history::HistoryMatches* matches) {
+  if (matches->empty())
+    return;  // No matches, nothing to do.
+
+  // Determine the base URL from which to search, and whether that URL could
+  // itself be added as a match.  We can add the base iff it's not "effectively
+  // the same" as any "what you typed" match.
+  const history::HistoryMatch& match = matches->front();
+  GURL search_base = ConvertToHostOnly(match, params.input.text());
+  bool can_add_search_base_to_matches = !have_what_you_typed_match;
+  if (search_base.is_empty()) {
+    // Search from what the user typed when we couldn't reduce the best match
+    // to a host.  Careful: use a substring of |match| here, rather than the
+    // first match in |params|, because they might have different prefixes.  If
+    // the user typed "google.com", |what_you_typed_match| will hold
+    // "http://google.com/", but |match| might begin with
+    // "http://www.google.com/".
+    // TODO: this should be cleaned up, and is probably incorrect for IDN.
+    std::string new_match = match.url_info.url().possibly_invalid_spec().
+        substr(0, match.input_location + params.input.text().length());
+    search_base = GURL(new_match);
+    // TODO(mrossetti): There is a degenerate case where the following may
+    // cause a failure: http://www/~someword/fubar.html. Diagnose.
+    // See: http://crbug.com/50101
+    if (search_base.is_empty())
+      return;  // Can't construct a valid URL from which to start a search.
+  } else if (!can_add_search_base_to_matches) {
+    can_add_search_base_to_matches =
+        (search_base != what_you_typed_match.destination_url);
+  }
+  if (search_base == match.url_info.url())
+    return;  // Couldn't shorten |match|, so no range of URLs to search over.
+
+  // Search the DB for short URLs between our base and |match|.
+  history::URLRow info(search_base);
+  bool promote = true;
+  // A short URL is only worth suggesting if it's been visited at least a third
+  // as often as the longer URL.
+  const int min_visit_count = ((match.url_info.visit_count() - 1) / 3) + 1;
+  // For stability between the in-memory and on-disk autocomplete passes, when
+  // the long URL has been typed before, only suggest shorter URLs that have
+  // also been typed.  Otherwise, the on-disk pass could suggest a shorter URL
+  // (which hasn't been typed) that the in-memory pass doesn't know about,
+  // thereby making the top match, and thus the behavior of inline
+  // autocomplete, unstable.
+  const int min_typed_count = match.url_info.typed_count() ? 1 : 0;
+  if (!db->FindShortestURLFromBase(search_base.possibly_invalid_spec(),
+          match.url_info.url().possibly_invalid_spec(), min_visit_count,
+          min_typed_count, can_add_search_base_to_matches, &info)) {
+    if (!can_add_search_base_to_matches)
+      return;  // Couldn't find anything and can't add the search base, bail.
+
+    // Try to get info on the search base itself.  Promote it to the top if the
+    // original best match isn't good enough to autocomplete.
+    db->GetRowForURL(search_base, &info);
+    promote = match.url_info.typed_count() <= 1;
+  }
+
+  // Promote or add the desired URL to the list of matches.
+  EnsureMatchPresent(info, match.input_location, match.match_in_scheme,
+                     matches, promote);
+}
+
+// Returns true if |url| is just a host (e.g. "http://www.google.com/") and not
+// some other subpage (e.g. "http://www.google.com/foo.html").
 bool IsHostOnly(const GURL& url) {
   DCHECK(url.is_valid());
   return (!url.has_path() || (url.path() == "/")) && !url.has_query() &&
       !url.has_ref();
 }
 
 // Acts like the > operator for URLInfo classes.
-bool CompareHistoryMatch(const HistoryMatch& a, const HistoryMatch& b) {
+bool CompareHistoryMatch(const history::HistoryMatch& a,
+                         const history::HistoryMatch& b) {
   // A URL that has been typed at all is better than one that has never been
   // typed.  (Note "!"s on each side)
   if (!a.url_info.typed_count() != !b.url_info.typed_count())
     return a.url_info.typed_count() > b.url_info.typed_count();
 
   // Innermost matches (matches after any scheme or "www.") are better than
   // non-innermost matches.
   if (a.innermost_match != b.innermost_match)
     return a.innermost_match;
 
   // URLs that have been typed more often are better.
   if (a.url_info.typed_count() != b.url_info.typed_count())
     return a.url_info.typed_count() > b.url_info.typed_count();
 
   // For URLs that have each been typed once, a host (alone) is better than a
   // page inside.
   if (a.url_info.typed_count() == 1) {
-    const bool a_is_host_only = history::IsHostOnly(a.url_info.url());
-    if (a_is_host_only != history::IsHostOnly(b.url_info.url()))
+    const bool a_is_host_only = IsHostOnly(a.url_info.url());
+    if (a_is_host_only != IsHostOnly(b.url_info.url()))
       return a_is_host_only;
   }
 
   // URLs that have been visited more often are better.
   if (a.url_info.visit_count() != b.url_info.visit_count())
     return a.url_info.visit_count() > b.url_info.visit_count();
 
   // URLs that have been visited more recently are better.
   return a.url_info.last_visit() > b.url_info.last_visit();
 }
 
-// Given the user's |input| and a |match| created from it, reduce the
-// match's URL to just a host.  If this host still matches the user input,
-// return it.  Returns the empty string on failure.
-GURL ConvertToHostOnly(const HistoryMatch& match, const string16& input) {
-  // See if we should try to do host-only suggestions for this URL. Nonstandard
-  // schemes means there's no authority section, so suggesting the host name
-  // is useless. File URLs are standard, but host suggestion is not useful for
-  // them either.
-  const GURL& url = match.url_info.url();
-  if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile())
-    return GURL();
-
-  // Transform to a host-only match.  Bail if the host no longer matches the
-  // user input (e.g. because the user typed more than just a host).
-  GURL host = url.GetWithEmptyPath();
-  if ((host.spec().length() < (match.input_location + input.length())))
-    return GURL();  // User typing is longer than this host suggestion.
-
-  const string16 spec = UTF8ToUTF16(host.spec());
-  if (spec.compare(match.input_location, input.length(), input))
-    return GURL();  // User typing is no longer a prefix.
-
-  return host;
+// Determines the confidence for a |match| when compared to all the |matches|.
+// Returns a number in the range [0, 1].
+float CalculateConfidence(const history::HistoryMatch& match,
+                          const history::HistoryMatches& matches) {
+  // TODO(dominich): Take into account bookmarked page?
+  // TODO(dominich): See CompareHistoryMatch for more measures to include.
+  // Using typed count in place of visit count as:
+  // - It's a better indicator of what the user wants to open given that they
+  //   are typing in the address bar (users tend to open certain URLs by typing
+  //   and others by e.g. bookmarks, so visit_count is a good indicator of
+  //   overall interest but a bad one for specifically omnibox interest).
+  // - Since the DB query is sorted by typed_count, the results may be
+  //   effectively a random selection as far as visit_counts are concerned
+  //   (meaning many high-visit_count-URLs may be present in one query and
+  //   absent in a similar one), leading to wild swings in confidence for the
+  //   same result across distinct queries.
+  float numerator = match.url_info.typed_count();
+  float denominator = 0.0f;
+  for (history::HistoryMatches::const_iterator it = matches.begin();
+       it != matches.end(); ++it) {
+    denominator += it->url_info.typed_count();
+  }
+  if (denominator < 1) {
+    numerator = match.url_info.visit_count();
+    for (history::HistoryMatches::const_iterator it = matches.begin();
+         it != matches.end(); ++it) {
+      denominator += it->url_info.visit_count();
+    }
+  }
+  return (denominator > 0.0f ? numerator / denominator : 0);
 }
 
 }  // namespace history
 
 HistoryURLProviderParams::HistoryURLProviderParams(
     const AutocompleteInput& input,
     bool trim_http,
     const std::string& languages)
     : message_loop(MessageLoop::current()),
       input(input),
       prevent_inline_autocomplete(input.prevent_inline_autocomplete()),
       trim_http(trim_http),
       failed(false),
       languages(languages),
       dont_suggest_exact_input(false) {
 }
 
-HistoryURLProviderParams::~HistoryURLProviderParams() {}
+HistoryURLProviderParams::~HistoryURLProviderParams() {
+}
 
 HistoryURLProvider::HistoryURLProvider(ACProviderListener* listener,
                                        Profile* profile)
     : HistoryProvider(listener, profile, "HistoryURL"),
       prefixes_(GetPrefixes()),
       params_(NULL) {
 }
 
 void HistoryURLProvider::Start(const AutocompleteInput& input,
                                bool minimal_changes) {
@@ skipping 21 matching lines @@
 
 // Called on the history thread.
 void HistoryURLProvider::ExecuteWithDB(history::HistoryBackend* backend,
                                        history::URLDatabase* db,
                                        HistoryURLProviderParams* params) {
   // We may get called with a NULL database if it couldn't be properly
   // initialized.
   if (!db) {
     params->failed = true;
   } else if (!params->cancel_flag.IsSet()) {
-    TimeTicks beginning_time = TimeTicks::Now();
+    base::TimeTicks beginning_time = base::TimeTicks::Now();
 
     DoAutocomplete(backend, db, params);
 
     UMA_HISTOGRAM_TIMES("Autocomplete.HistoryAsyncQueryTime",
-                        TimeTicks::Now() - beginning_time);
+                        base::TimeTicks::Now() - beginning_time);
   }
 
   // Return the results (if any) to the main thread.
   params->message_loop->PostTask(FROM_HERE, NewRunnableMethod(
       this, &HistoryURLProvider::QueryComplete, params));
 }
 
 // Used by both autocomplete passes, and therefore called on multiple different
 // threads (though not simultaneously).
 void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend,
@@ skipping 14 matching lines @@
       ((params->input.type() != AutocompleteInput::UNKNOWN) ||
           !params->trim_http ||
           url_util::FindAndCompareScheme(UTF16ToUTF8(params->input.text()),
                                          chrome::kHttpsScheme, NULL));
   AutocompleteMatch what_you_typed_match(SuggestExactInput(params->input,
                                                            params->trim_http));
 
   // Get the matching URLs from the DB
   typedef std::vector<history::URLRow> URLRowVector;
   URLRowVector url_matches;
-  HistoryMatches history_matches;
+  history::HistoryMatches history_matches;
 
-  for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end();
-       ++i) {
+  for (history::Prefixes::const_iterator i(prefixes_.begin());
+       i != prefixes_.end(); ++i) {
     if (params->cancel_flag.IsSet())
       return;  // Canceled in the middle of a query, give up.
     // We only need kMaxMatches results in the end, but before we get there we
     // need to promote lower-quality matches that are prefixes of
     // higher-quality matches, and remove lower-quality redirects.  So we ask
     // for more results than we need, of every prefix type, in hopes this will
     // give us far more than enough to work with.  CullRedirects() will then
     // reduce the list to the best kMaxMatches results.
     db->AutocompleteForPrefix(i->prefix + params->input.text(),
                               kMaxMatches * 2, (backend == NULL), &url_matches);
     for (URLRowVector::const_iterator j(url_matches.begin());
          j != url_matches.end(); ++j) {
-      const Prefix* best_prefix = BestPrefix(j->url(), string16());
+      const history::Prefix* best_prefix = BestPrefix(j->url(), string16());
       DCHECK(best_prefix != NULL);
-      history_matches.push_back(HistoryMatch(*j, i->prefix.length(),
+      history_matches.push_back(history::HistoryMatch(*j, i->prefix.length(),
           !i->num_components,
           i->num_components >= best_prefix->num_components));
     }
   }
 
   // Create sorted list of suggestions.
   CullPoorMatches(&history_matches);
   SortMatches(&history_matches);
   PromoteOrCreateShorterSuggestion(db, *params, have_what_you_typed_match,
                                    what_you_typed_match, &history_matches);
@@ skipping 28 matching lines @@
   if (!backend)
     return;
 
   // Remove redirects and trim list to size.  We want to provide up to
   // kMaxMatches results plus the What You Typed result, if it was added to
   // |history_matches| above.
   CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion);
 
   // Convert the history matches to autocomplete matches.
   for (size_t i = first_match; i < history_matches.size(); ++i) {
-    const HistoryMatch& match = history_matches[i];
+    const history::HistoryMatch& match = history_matches[i];
     DCHECK(!have_what_you_typed_match ||
            (match.url_info.url() !=
             GURL(params->matches.front().destination_url)));
     AutocompleteMatch ac_match =
         HistoryMatchToACMatch(params, match, history_matches, NORMAL,
                               history_matches.size() - 1 - i);
     UMA_HISTOGRAM_COUNTS_100("Autocomplete.Confidence_HistoryUrl",
                              ac_match.confidence * 100);
     params->matches.push_back(ac_match);
   }
@@ skipping 18 matching lines @@
   // match in it, whereas |params->matches| will be empty.
   if (!params->failed) {
     matches_.swap(params->matches);
     UpdateStarredStateOfMatches();
   }
 
   done_ = true;
   listener_->OnProviderUpdate(true);
 }
 
+HistoryURLProvider::~HistoryURLProvider() {
+  // Note: This object can get leaked on shutdown if there are pending
+  // requests on the database (which hold a reference to us). Normally, these
+  // messages get flushed for each thread. We do a round trip from main, to
+  // history, back to main while holding a reference. If the main thread
+  // completes before the history thread, the message to delegate back to the
+  // main thread will not run and the reference will leak. Therefore, don't do
+  // anything on destruction.
+}
+
+// static
+history::Prefixes HistoryURLProvider::GetPrefixes() {
+  // We'll complete text following these prefixes.
+  // NOTE: There's no requirement that these be in any particular order.
+  history::Prefixes prefixes;
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("https://www."), 2));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("http://www."), 2));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("ftp://ftp."), 2));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("ftp://www."), 2));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("https://"), 1));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("http://"), 1));
+  prefixes.push_back(history::Prefix(ASCIIToUTF16("ftp://"), 1));
+  // Empty string catches within-scheme matches as well.
+  prefixes.push_back(history::Prefix(string16(), 0));
+  return prefixes;
+}
+
+// static
+int HistoryURLProvider::CalculateRelevance(AutocompleteInput::Type input_type,
+                                           MatchType match_type,
+                                           size_t match_number) {
+  switch (match_type) {
+    case INLINE_AUTOCOMPLETE:
+      return 1400;
+
+    case WHAT_YOU_TYPED:
+      return 1200;
+
+    default:
+      return 900 + static_cast<int>(match_number);
+  }
+}
+
+void HistoryURLProvider::RunAutocompletePasses(
+    const AutocompleteInput& input,
+    bool fixup_input_and_run_pass_1) {
+  matches_.clear();
+
+  if ((input.type() == AutocompleteInput::INVALID) ||
+      (input.type() == AutocompleteInput::FORCED_QUERY))
+    return;
+
+  // Create a match for exactly what the user typed.  This will only be used as
+  // a fallback in case we can't get the history service or URL DB; otherwise,
+  // we'll run this again in DoAutocomplete() and use that result instead.
+  const bool trim_http = !HasHTTPScheme(input.text());
+  // Don't do this for queries -- while we can sometimes mark up a match for
+  // this, it's not what the user wants, and just adds noise.
+  if ((input.type() != AutocompleteInput::QUERY) &&
+      input.canonicalized_url().is_valid())
+    matches_.push_back(SuggestExactInput(input, trim_http));
+
+  // We'll need the history service to run both passes, so try to obtain it.
+  if (!profile_)
+    return;
+  HistoryService* const history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (!history_service)
+    return;
+
+  // Create the data structure for the autocomplete passes.  We'll save this off
+  // onto the |params_| member for later deletion below if we need to run pass
+  // 2.
+  std::string languages(languages_);
+  if (languages.empty()) {
+    languages =
+        profile_->GetPrefs()->GetString(prefs::kAcceptLanguages);
+  }
+  scoped_ptr<HistoryURLProviderParams> params(
+      new HistoryURLProviderParams(input, trim_http, languages));
+
+  params->prevent_inline_autocomplete =
+      PreventInlineAutocomplete(input);
+
+  if (fixup_input_and_run_pass_1) {
+    // Do some fixup on the user input before matching against it, so we provide
+    // good results for local file paths, input with spaces, etc.
+    // NOTE: This purposefully doesn't take input.desired_tld() into account; if
+    // it did, then holding "ctrl" would change all the results from the
+    // HistoryURLProvider provider, not just the What You Typed Result.
+    const string16 fixed_text(FixupUserInput(input));
+    if (fixed_text.empty()) {
+      // Conceivably fixup could result in an empty string (although I don't
+      // have cases where this happens offhand).  We can't do anything with
+      // empty input, so just bail; otherwise we'd crash later.
+      return;
+    }
+    params->input.set_text(fixed_text);
+
+    // Pass 1: Get the in-memory URL database, and use it to find and promote
+    // the inline autocomplete match, if any.
+    history::URLDatabase* url_db = history_service->InMemoryDatabase();
+    // url_db can be NULL if it hasn't finished initializing (or failed to
+    // initialize).  In this case all we can do is fall back on the second
+    // pass.
+    //
+    // TODO(pkasting): We should just block here until this loads.  Any time
+    // someone unloads the history backend, we'll get inconsistent inline
+    // autocomplete behavior here.
+    if (url_db) {
+      DoAutocomplete(NULL, url_db, params.get());
+      // params->matches now has the matches we should expose to the provider.
+      // Pass 2 expects a "clean slate" set of matches.
+      matches_.clear();
+      matches_.swap(params->matches);
+      UpdateStarredStateOfMatches();
+    }
+  }
+
+  // Pass 2: Ask the history service to call us back on the history thread,
+  // where we can read the full on-disk DB.
+  if (input.matches_requested() == AutocompleteInput::ALL_MATCHES) {
+    done_ = false;
+    params_ = params.release();  // This object will be destroyed in
+                                 // QueryComplete() once we're done with it.
+    history_service->ScheduleAutocomplete(this, params_);
+  }
+}
+
+const history::Prefix* HistoryURLProvider::BestPrefix(
+    const GURL& url,
+    const string16& prefix_suffix) const {
+  const history::Prefix* best_prefix = NULL;
+  const string16 text(UTF8ToUTF16(url.spec()));
+  for (history::Prefixes::const_iterator i(prefixes_.begin());
+       i != prefixes_.end(); ++i) {
+    if ((best_prefix == NULL) ||
+        (i->num_components > best_prefix->num_components)) {
+      string16 prefix_with_suffix(i->prefix + prefix_suffix);
+      if ((text.length() >= prefix_with_suffix.length()) &&
+          !text.compare(0, prefix_with_suffix.length(), prefix_with_suffix))
+        best_prefix = &(*i);
+    }
+  }
+  return best_prefix;
+}
+
 AutocompleteMatch HistoryURLProvider::SuggestExactInput(
     const AutocompleteInput& input,
     bool trim_http) {
   // TODO(dominich): Find a confidence measure for this.
   AutocompleteMatch match(this,
       CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), 0.0f, false,
       AutocompleteMatch::URL_WHAT_YOU_TYPED);
   UMA_HISTOGRAM_COUNTS_100("Autocomplete.Confidence_HistoryUrl",
                            match.confidence * 100);
 
@@ skipping 13 matching lines @@
         AutocompleteInput::FormattedStringWithEquivalentMeaning(url,
                                                                 display_string);
     // NOTE: Don't set match.input_location (to allow inline autocompletion)
     // here, it's surprising and annoying.
 
     // Try to highlight "innermost" match location.  If we fix up "w" into
     // "www.w.com", we want to highlight the fifth character, not the first.
     // This relies on match.destination_url being the non-prefix-trimmed version
     // of match.contents.
     match.contents = display_string;
-    const Prefix* best_prefix = BestPrefix(match.destination_url, input.text());
+    const history::Prefix* best_prefix =
+        BestPrefix(match.destination_url, input.text());
     // Because of the vagaries of GURL, it's possible for match.destination_url
     // to not contain the user's input at all.  In this case don't mark anything
     // as a match.
     const size_t match_location = (best_prefix == NULL) ?
         string16::npos : best_prefix->prefix.length() - offset;
     AutocompleteMatch::ClassifyLocationInString(match_location,
                                                 input.text().length(),
                                                 match.contents.length(),
                                                 ACMatchClassification::URL,
                                                 &match.contents_class);
 
     match.is_history_what_you_typed_match = true;
   }
 
   return match;
 }
 
-bool HistoryURLProvider::FixupExactSuggestion(history::URLDatabase* db,
-                                              const AutocompleteInput& input,
-                                              AutocompleteMatch* match,
-                                              HistoryMatches* matches) const {
+bool HistoryURLProvider::FixupExactSuggestion(
+    history::URLDatabase* db,
+    const AutocompleteInput& input,
+    AutocompleteMatch* match,
+    history::HistoryMatches* matches) const {
   DCHECK(match != NULL);
   DCHECK(matches != NULL);
 
   // Tricky corner case: The user has visited intranet site "foo", but not
   // internet site "www.foo.com".  He types in foo (getting an exact match),
   // then tries to hit ctrl-enter.  When pressing ctrl, the what-you-typed
   // match ("www.foo.com") doesn't show up in history, and thus doesn't get a
   // promoted relevance, but a different match from the input ("foo") does, and
   // gets promoted for inline autocomplete.  Thus instead of getting
   // "www.foo.com", the user still gets "foo" (and, before hitting enter,
@@ skipping 40 matching lines @@
   // Promote as an exact match.
   match->relevance = CalculateRelevance(input.type(), type, 0);
 
   // Put it on the front of the HistoryMatches for redirect culling.
   EnsureMatchPresent(info, string16::npos, false, matches, true);
   return true;
 }
 
 bool HistoryURLProvider::PromoteMatchForInlineAutocomplete(
     HistoryURLProviderParams* params,
-    const HistoryMatch& match,
-    const HistoryMatches& matches) {
+    const history::HistoryMatch& match,
+    const history::HistoryMatches& matches) {
   // Promote the first match if it's been typed at least n times, where n == 1
   // for "simple" (host-only) URLs and n == 2 for others.  We set a higher bar
   // for these long URLs because it's less likely that users will want to visit
   // them again.  Even though we don't increment the typed_count for pasted-in
   // URLs, if the user manually edits the URL or types some long thing in by
   // hand, we wouldn't want to immediately start autocompleting it.
   if (!match.url_info.typed_count() ||
       ((match.url_info.typed_count() == 1) &&
-       !history::IsHostOnly(match.url_info.url())))
+       !IsHostOnly(match.url_info.url())))
     return false;
 
   // In the case where the user has typed "foo.com" and visited (but not typed)
   // "foo/", and the input is "foo", we can reach here for "foo.com" during the
   // first pass but have the second pass suggest the exact input as a better
   // URL.  Since we need both passes to agree, and since during the first pass
   // there's no way to know about "foo/", make reaching this point prevent any
   // future pass from suggesting the exact input as a better match.
   params->dont_suggest_exact_input = true;
   params->matches.push_back(HistoryMatchToACMatch(params, match, matches,
                                                   INLINE_AUTOCOMPLETE, 0));
   return true;
 }
 
-HistoryURLProvider::~HistoryURLProvider() {}
-
-// static
-history::Prefixes HistoryURLProvider::GetPrefixes() {
-  // We'll complete text following these prefixes.
-  // NOTE: There's no requirement that these be in any particular order.
-  Prefixes prefixes;
-  prefixes.push_back(Prefix(ASCIIToUTF16("https://www."), 2));
-  prefixes.push_back(Prefix(ASCIIToUTF16("http://www."), 2));
-  prefixes.push_back(Prefix(ASCIIToUTF16("ftp://ftp."), 2));
-  prefixes.push_back(Prefix(ASCIIToUTF16("ftp://www."), 2));
-  prefixes.push_back(Prefix(ASCIIToUTF16("https://"), 1));
-  prefixes.push_back(Prefix(ASCIIToUTF16("http://"), 1));
-  prefixes.push_back(Prefix(ASCIIToUTF16("ftp://"), 1));
-  // Empty string catches within-scheme matches as well.
-  prefixes.push_back(Prefix(string16(), 0));
-  return prefixes;
-}
-
-// static
-int HistoryURLProvider::CalculateRelevance(AutocompleteInput::Type input_type,
-                                           MatchType match_type,
-                                           size_t match_number) {
-  switch (match_type) {
-    case INLINE_AUTOCOMPLETE:
-      return 1400;
-
-    case WHAT_YOU_TYPED:
-      return 1200;
-
-    default:
-      return 900 + static_cast<int>(match_number);
-  }
-}
-
-// static
-float HistoryURLProvider::CalculateConfidence(
-    const history::HistoryMatch& match,
-    const history::HistoryMatches& matches) {
-  // TODO(dominich): Take into account bookmarked page?
-  // TODO(dominich): See CompareHistoryMatch for more measures to include.
-  // Using typed count in place of visit count as:
-  // - It's a better indicator of what the user wants to open given that they
-  //   are typing in the address bar (users tend to open certain URLs by typing
-  //   and others by e.g. bookmarks, so visit_count is a good indicator of
-  //   overall interest but a bad one for specifically omnibox interest).
-  // - Since the DB query is sorted by typed_count, the results may be
-  //   effectively a random selection as far as visit_counts are concerned
-  //   (meaning many high-visit_count-URLs may be present in one query and
-  //   absent in a similar one), leading to wild swings in confidence for the
-  //   same result across distinct queries.
-  float numerator = match.url_info.typed_count();
-  float denominator = 0.0f;
-  for (history::HistoryMatches::const_iterator it = matches.begin();
-       it != matches.end(); ++it) {
-    denominator += it->url_info.typed_count();
-  }
-  if (denominator < 1) {
-    numerator = match.url_info.visit_count();
-    for (history::HistoryMatches::const_iterator it = matches.begin();
-         it != matches.end(); ++it) {
-      denominator += it->url_info.visit_count();
-    }
-  }
-  return (denominator > 0.0f ? numerator / denominator : 0);
-}
-
-// static
-void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
-    history::URLDatabase* db,
-    const HistoryURLProviderParams& params,
-    bool have_what_you_typed_match,
-    const AutocompleteMatch& what_you_typed_match,
-    HistoryMatches* matches) {
-  if (matches->empty())
-    return;  // No matches, nothing to do.
-
-  // Determine the base URL from which to search, and whether that URL could
-  // itself be added as a match.  We can add the base iff it's not "effectively
-  // the same" as any "what you typed" match.
-  const HistoryMatch& match = matches->front();
-  GURL search_base = history::ConvertToHostOnly(match, params.input.text());
-  bool can_add_search_base_to_matches = !have_what_you_typed_match;
-  if (search_base.is_empty()) {
-    // Search from what the user typed when we couldn't reduce the best match
-    // to a host.  Careful: use a substring of |match| here, rather than the
-    // first match in |params|, because they might have different prefixes.  If
-    // the user typed "google.com", |what_you_typed_match| will hold
-    // "http://google.com/", but |match| might begin with
-    // "http://www.google.com/".
-    // TODO: this should be cleaned up, and is probably incorrect for IDN.
-    std::string new_match = match.url_info.url().possibly_invalid_spec().
-        substr(0, match.input_location + params.input.text().length());
-    search_base = GURL(new_match);
-    // TODO(mrossetti): There is a degenerate case where the following may
-    // cause a failure: http://www/~someword/fubar.html. Diagnose.
-    // See: http://crbug.com/50101
-    if (search_base.is_empty())
-      return;  // Can't construct a valid URL from which to start a search.
-  } else if (!can_add_search_base_to_matches) {
-    can_add_search_base_to_matches =
-        (search_base != what_you_typed_match.destination_url);
-  }
-  if (search_base == match.url_info.url())
-    return;  // Couldn't shorten |match|, so no range of URLs to search over.
-
-  // Search the DB for short URLs between our base and |match|.
-  history::URLRow info(search_base);
-  bool promote = true;
-  // A short URL is only worth suggesting if it's been visited at least a third
-  // as often as the longer URL.
-  const int min_visit_count = ((match.url_info.visit_count() - 1) / 3) + 1;
-  // For stability between the in-memory and on-disk autocomplete passes, when
-  // the long URL has been typed before, only suggest shorter URLs that have
-  // also been typed.  Otherwise, the on-disk pass could suggest a shorter URL
-  // (which hasn't been typed) that the in-memory pass doesn't know about,
-  // thereby making the top match, and thus the behavior of inline
-  // autocomplete, unstable.
-  const int min_typed_count = match.url_info.typed_count() ? 1 : 0;
-  if (!db->FindShortestURLFromBase(search_base.possibly_invalid_spec(),
-          match.url_info.url().possibly_invalid_spec(), min_visit_count,
-          min_typed_count, can_add_search_base_to_matches, &info)) {
-    if (!can_add_search_base_to_matches)
-      return;  // Couldn't find anything and can't add the search base, bail.
-
-    // Try to get info on the search base itself.  Promote it to the top if the
-    // original best match isn't good enough to autocomplete.
-    db->GetRowForURL(search_base, &info);
-    promote = match.url_info.typed_count() <= 1;
-  }
-
-  // Promote or add the desired URL to the list of matches.
-  EnsureMatchPresent(info, match.input_location, match.match_in_scheme,
-                     matches, promote);
-}
-
-// static
-void HistoryURLProvider::EnsureMatchPresent(const history::URLRow& info,
-                                            size_t input_location,
-                                            bool match_in_scheme,
-                                            HistoryMatches* matches,
-                                            bool promote) {
-  // |matches| may already have an entry for this.
-  for (HistoryMatches::iterator i(matches->begin()); i != matches->end();
-       ++i) {
-    if (i->url_info.url() == info.url()) {
-      // Rotate it to the front if the caller wishes.
-      if (promote)
-        std::rotate(matches->begin(), i, i + 1);
-      return;
-    }
-  }
-
-  // No entry, so create one.
-  HistoryMatch match(info, input_location, match_in_scheme, true);
-  if (promote)
-    matches->push_front(match);
-  else
-    matches->push_back(match);
-}
-
-void HistoryURLProvider::RunAutocompletePasses(
-    const AutocompleteInput& input,
-    bool fixup_input_and_run_pass_1) {
-  matches_.clear();
-
-  if ((input.type() == AutocompleteInput::INVALID) ||
-      (input.type() == AutocompleteInput::FORCED_QUERY))
-    return;
-
-  // Create a match for exactly what the user typed.  This will only be used as
-  // a fallback in case we can't get the history service or URL DB; otherwise,
-  // we'll run this again in DoAutocomplete() and use that result instead.
-  const bool trim_http = !HasHTTPScheme(input.text());
-  // Don't do this for queries -- while we can sometimes mark up a match for
-  // this, it's not what the user wants, and just adds noise.
-  if ((input.type() != AutocompleteInput::QUERY) &&
-      input.canonicalized_url().is_valid())
-    matches_.push_back(SuggestExactInput(input, trim_http));
-
-  // We'll need the history service to run both passes, so try to obtain it.
-  if (!profile_)
-    return;
-  HistoryService* const history_service =
-      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
-  if (!history_service)
-    return;
-
-  // Create the data structure for the autocomplete passes.  We'll save this off
-  // onto the |params_| member for later deletion below if we need to run pass
-  // 2.
-  std::string languages(languages_);
-  if (languages.empty()) {
-    languages =
-        profile_->GetPrefs()->GetString(prefs::kAcceptLanguages);
-  }
-  scoped_ptr<HistoryURLProviderParams> params(
-      new HistoryURLProviderParams(input, trim_http, languages));
-
-  params->prevent_inline_autocomplete =
-      PreventInlineAutocomplete(input);
-
-  if (fixup_input_and_run_pass_1) {
-    // Do some fixup on the user input before matching against it, so we provide
-    // good results for local file paths, input with spaces, etc.
-    // NOTE: This purposefully doesn't take input.desired_tld() into account; if
-    // it did, then holding "ctrl" would change all the results from the
-    // HistoryURLProvider provider, not just the What You Typed Result.
-    const string16 fixed_text(FixupUserInput(input));
-    if (fixed_text.empty()) {
-      // Conceivably fixup could result in an empty string (although I don't
-      // have cases where this happens offhand).  We can't do anything with
-      // empty input, so just bail; otherwise we'd crash later.
-      return;
-    }
-    params->input.set_text(fixed_text);
-
-    // Pass 1: Get the in-memory URL database, and use it to find and promote
-    // the inline autocomplete match, if any.
-    history::URLDatabase* url_db = history_service->InMemoryDatabase();
-    // url_db can be NULL if it hasn't finished initializing (or failed to
-    // initialize).  In this case all we can do is fall back on the second
-    // pass.
-    //
-    // TODO(pkasting): We should just block here until this loads.  Any time
-    // someone unloads the history backend, we'll get inconsistent inline
-    // autocomplete behavior here.
-    if (url_db) {
-      DoAutocomplete(NULL, url_db, params.get());
-      // params->matches now has the matches we should expose to the provider.
-      // Pass 2 expects a "clean slate" set of matches.
-      matches_.clear();
-      matches_.swap(params->matches);
-      UpdateStarredStateOfMatches();
-    }
-  }
-
-  // Pass 2: Ask the history service to call us back on the history thread,
-  // where we can read the full on-disk DB.
-  if (input.matches_requested() == AutocompleteInput::ALL_MATCHES) {
-    done_ = false;
-    params_ = params.release();  // This object will be destroyed in
-                                 // QueryComplete() once we're done with it.
-    history_service->ScheduleAutocomplete(this, params_);
-  }
-}
-
-const history::Prefix* HistoryURLProvider::BestPrefix(
-    const GURL& url,
-    const string16& prefix_suffix) const {
-  const Prefix* best_prefix = NULL;
-  const string16 text(UTF8ToUTF16(url.spec()));
-  for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end();
-       ++i) {
-    if ((best_prefix == NULL) ||
-        (i->num_components > best_prefix->num_components)) {
-      string16 prefix_with_suffix(i->prefix + prefix_suffix);
-      if ((text.length() >= prefix_with_suffix.length()) &&
-          !text.compare(0, prefix_with_suffix.length(), prefix_with_suffix))
-        best_prefix = &(*i);
-    }
-  }
-  return best_prefix;
-}
-
-void HistoryURLProvider::SortMatches(HistoryMatches* matches) const {
+void HistoryURLProvider::SortMatches(history::HistoryMatches* matches) const {
   // Sort by quality, best first.
-  std::sort(matches->begin(), matches->end(), &history::CompareHistoryMatch);
+  std::sort(matches->begin(), matches->end(), &CompareHistoryMatch);
 
   // Remove duplicate matches (caused by the search string appearing in one of
   // the prefixes as well as after it).  Consider the following scenario:
   //
   // User has visited "http://http.com" once and "http://htaccess.com" twice.
   // User types "http".  The autocomplete search with prefix "http://" returns
   // the first host, while the search with prefix "" returns both hosts.  Now
   // we sort them into rank order:
   //   http://http.com     (innermost_match)
   //   http://htaccess.com (!innermost_match, url_info.visit_count == 2)
   //   http://http.com     (!innermost_match, url_info.visit_count == 1)
   //
   // The above scenario tells us we can't use std::unique(), since our
   // duplicates are not always sequential.  It also tells us we should remove
   // the lower-quality duplicate(s), since otherwise the returned results won't
   // be ordered correctly.  This is easy to do: we just always remove the later
   // element of a duplicate pair.
   // Be careful!  Because the vector contents may change as we remove elements,
   // we use an index instead of an iterator in the outer loop, and don't
   // precalculate the ending position.
   for (size_t i = 0; i < matches->size(); ++i) {
-    HistoryMatches::iterator j(matches->begin() + i + 1);
-    while (j != matches->end()) {
+    for (history::HistoryMatches::iterator j(matches->begin() + i + 1);
+         j != matches->end(); ) {
       if ((*matches)[i].url_info.url() == j->url_info.url())
         j = matches->erase(j);
       else
         ++j;
     }
   }
 }
 
-void HistoryURLProvider::CullPoorMatches(HistoryMatches* matches) const {
+void HistoryURLProvider::CullPoorMatches(
+    history::HistoryMatches* matches) const {
   const base::Time& threshold(history::AutocompleteAgeThreshold());
-  for (HistoryMatches::iterator i(matches->begin()); i != matches->end();) {
+  for (history::HistoryMatches::iterator i(matches->begin());
+       i != matches->end();) {
     if (RowQualifiesAsSignificant(i->url_info, threshold))
       ++i;
     else
       i = matches->erase(i);
   }
 }
 
 void HistoryURLProvider::CullRedirects(history::HistoryBackend* backend,
-                                       HistoryMatches* matches,
+                                       history::HistoryMatches* matches,
                                        size_t max_results) const {
   for (size_t source = 0;
        (source < matches->size()) && (source < max_results); ) {
     const GURL& url = (*matches)[source].url_info.url();
     // TODO(brettw) this should go away when everything uses GURL.
     history::RedirectList redirects;
     backend->GetMostRecentRedirectsFrom(url, &redirects);
     if (!redirects.empty()) {
       // Remove all but the first occurrence of any of these redirects in the
       // search results. We also must add the URL we queried for, since it may
       // not be the first match and we'd want to remove it.
       //
       // For example, when A redirects to B and our matches are [A, X, B],
       // we'll get B as the redirects from, and we want to remove the second
       // item of that pair, removing B. If A redirects to B and our matches are
       // [B, X, A], we'll want to remove A instead.
       redirects.push_back(url);
       source = RemoveSubsequentMatchesOf(matches, source, redirects);
     } else {
       // Advance to next item.
       source++;
     }
   }
 
   if (matches->size() > max_results)
     matches->resize(max_results);
 }
 
 size_t HistoryURLProvider::RemoveSubsequentMatchesOf(
-    HistoryMatches* matches,
+    history::HistoryMatches* matches,
     size_t source_index,
     const std::vector<GURL>& remove) const {
   size_t next_index = source_index + 1;  // return value = item after source
 
   // Find the first occurrence of any URL in the redirect chain. We want to
   // keep this one since it is rated the highest.
-  HistoryMatches::iterator first(std::find_first_of(
+  history::HistoryMatches::iterator first(std::find_first_of(
       matches->begin(), matches->end(), remove.begin(), remove.end()));
-  DCHECK(first != matches->end()) <<
-      "We should have always found at least the original URL.";
+  DCHECK(first != matches->end()) << "We should have always found at least the "
+      "original URL.";
 
   // Find any following occurrences of any URL in the redirect chain, these
   // should be deleted.
-  HistoryMatches::iterator next(first);
-  next++;  // Start searching immediately after the one we found already.
-  while (next != matches->end() &&
-         (next = std::find_first_of(next, matches->end(), remove.begin(),
-                                    remove.end())) != matches->end()) {
+  for (history::HistoryMatches::iterator next(std::find_first_of(first + 1,
+           matches->end(), remove.begin(), remove.end()));
+       next != matches->end(); next = std::find_first_of(next, matches->end(),
+           remove.begin(), remove.end())) {
     // Remove this item. When we remove an item before the source index, we
     // need to shift it to the right and remember that so we can return it.
     next = matches->erase(next);
     if (static_cast<size_t>(next - matches->begin()) < next_index)
-      next_index--;
+      --next_index;
   }
   return next_index;
 }
 
 AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch(
     HistoryURLProviderParams* params,
-    const HistoryMatch& history_match,
-    const HistoryMatches& history_matches,
+    const history::HistoryMatch& history_match,
+    const history::HistoryMatches& history_matches,
     MatchType match_type,
     size_t match_number) {
   const history::URLRow& info = history_match.url_info;
   AutocompleteMatch match(this,
       CalculateRelevance(params->input.type(), match_type, match_number),
       CalculateConfidence(history_match, history_matches),
       !!info.visit_count(), AutocompleteMatch::HISTORY_URL);
   match.destination_url = info.url();
   DCHECK(match.destination_url.is_valid());
   size_t inline_autocomplete_offset =
@@ skipping 29 matching lines @@
         &match.contents_class);
   }
   match.description = info.title();
   AutocompleteMatch::ClassifyMatchInString(params->input.text(),
                                            info.title(),
                                            ACMatchClassification::NONE,
                                            &match.description_class);
 
   return match;
 }