Add Framework for History Quick Provider

Incorporate 'quick' history provider index as an autocomplete provider in preparation for the replacement of the current history_url_provider. This step refactors the history provider code a bit, introduces the replacement class (history-quick_provider), and adds a unittest template. Note that the 'quick' provider will only support the fast, synchronous autocomplete pass. Once the quick provider has been completed the current history_url_provider will be replaced. In the meantime, the latter will remain in operation in order to provide the slower history results. 

BUG=None 
TEST=None 

Review URL: http://codereview.chromium.org/3005050

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@54908 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 218 insertions, 194 deletions

diff --git a/chrome/browser/autocomplete/autocomplete.cc b/chrome/browser/autocomplete/autocomplete.cc
index 0693ca2..66d7459 100644
--- a/chrome/browser/autocomplete/autocomplete.cc
+++ b/chrome/browser/autocomplete/autocomplete.cc
@@ -8,9 +8,11 @@
 
 #include "app/l10n_util.h"
 #include "base/basictypes.h"
+#include "base/command_line.h"
 #include "base/i18n/number_formatting.h"
 #include "base/string_number_conversions.h"
 #include "base/string_util.h"
+#include "chrome/browser/autocomplete/history_quick_provider.h"
 #include "chrome/browser/autocomplete/history_url_provider.h"
 #include "chrome/browser/autocomplete/history_contents_provider.h"
 #include "chrome/browser/autocomplete/keyword_provider.h"
@@ -21,6 +23,7 @@
 #include "chrome/browser/net/url_fixer_upper.h"
 #include "chrome/browser/pref_service.h"
 #include "chrome/browser/profile.h"
+#include "chrome/common/chrome_switches.h"
 #include "chrome/common/notification_service.h"
 #include "chrome/common/pref_names.h"
 #include "chrome/common/url_constants.h"
@@ -756,7 +759,11 @@ AutocompleteController::AutocompleteController(Profile* profile)
       have_committed_during_this_query_(false),
       done_(true) {
   providers_.push_back(new SearchProvider(this, profile));
-  providers_.push_back(new HistoryURLProvider(this, profile));
+  if (CommandLine::ForCurrentProcess()->HasSwitch(
+      switches::kEnableInMemoryURLIndex))
+    providers_.push_back(new HistoryQuickProvider(this, profile));
+  else
+    providers_.push_back(new HistoryURLProvider(this, profile));
   providers_.push_back(new KeywordProvider(this, profile));
   history_contents_provider_ = new HistoryContentsProvider(this, profile);
   providers_.push_back(history_contents_provider_);
diff --git a/chrome/browser/autocomplete/history_quick_provider.cc b/chrome/browser/autocomplete/history_quick_provider.cc
new file mode 100644
index 0000000..0d4fdda
--- /dev/null
+++ b/chrome/browser/autocomplete/history_quick_provider.cc
@@ -0,0 +1,10 @@
+// Copyright (c) 2010 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_quick_provider.h"
+
+void HistoryQuickProvider::Start(const AutocompleteInput& input,
+                                 bool minimal_changes) {
+  // TODO(mrossetti): Implement.
+}
diff --git a/chrome/browser/autocomplete/history_quick_provider.h b/chrome/browser/autocomplete/history_quick_provider.h
new file mode 100644
index 0000000..c0dcc15
--- /dev/null
+++ b/chrome/browser/autocomplete/history_quick_provider.h
@@ -0,0 +1,39 @@
+// Copyright (c) 2010 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.
+
+#ifndef CHROME_BROWSER_AUTOCOMPLETE_HISTORY_QUICK_PROVIDER_H_
+#define CHROME_BROWSER_AUTOCOMPLETE_HISTORY_QUICK_PROVIDER_H_
+
+#include "chrome/browser/autocomplete/autocomplete.h"
+
+// This class is an autocomplete provider (a pseudo-internal component of
+// the history system) which quickly (and synchronously) provides matching
+// results from recently or frequently visited sites in the profile's
+// history.
+//
+// TODO(mrossetti): Review to see if the following applies since we're not
+// using the database during the autocomplete pass.
+//
+// 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.
+class HistoryQuickProvider : public AutocompleteProvider {
+ public:
+  HistoryQuickProvider(ACProviderListener* listener, Profile* profile)
+      : AutocompleteProvider(listener, profile, "HistoryQuickProvider") {}
+
+  // no destructor (see note above)
+
+  // AutocompleteProvider
+  void Start(const AutocompleteInput& input, bool minimal_changes);
+
+ private:
+  ~HistoryQuickProvider() {}
+};
+
+#endif  // CHROME_BROWSER_AUTOCOMPLETE_HISTORY_QUICK_PROVIDER_H_
diff --git a/chrome/browser/autocomplete/history_quick_provider_unittest.cc b/chrome/browser/autocomplete/history_quick_provider_unittest.cc
new file mode 100644
index 0000000..24ed677
--- /dev/null
+++ b/chrome/browser/autocomplete/history_quick_provider_unittest.cc
@@ -0,0 +1,35 @@
+// Copyright (c) 2010 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_quick_provider.h"
+
+#include "base/scoped_ptr.h"
+#include "chrome/test/testing_profile.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+class HistoryQuickProviderTest : public testing::Test,
+                                 public ACProviderListener {
+ public:
+  // ACProviderListener
+  virtual void OnProviderUpdate(bool updated_matches);
+
+ protected:
+  void SetUp() {
+    profile_.reset(new TestingProfile());
+    provider_ = new HistoryQuickProvider(this, profile_.get());
+  }
+  void TearDown() {
+    provider_ = NULL;
+  }
+
+  scoped_refptr<HistoryQuickProvider> provider_;
+  scoped_ptr<TestingProfile> profile_;
+};
+
+void HistoryQuickProviderTest::OnProviderUpdate(bool updated_matches) {
+}
+
+TEST_F(HistoryQuickProviderTest, Construction) {
+  EXPECT_TRUE(provider_.get());
+}
diff --git a/chrome/browser/autocomplete/history_url_provider.cc b/chrome/browser/autocomplete/history_url_provider.cc
index bac2d1a..0f339f4 100644
--- a/chrome/browser/autocomplete/history_url_provider.cc
+++ b/chrome/browser/autocomplete/history_url_provider.cc
@@ -7,7 +7,6 @@
 #include <algorithm>
 
 #include "base/basictypes.h"
-#include "base/command_line.h"
 #include "base/histogram.h"
 #include "base/message_loop.h"
 #include "base/string_util.h"
@@ -18,7 +17,6 @@
 #include "chrome/browser/net/url_fixer_upper.h"
 #include "chrome/browser/pref_service.h"
 #include "chrome/browser/profile.h"
-#include "chrome/common/chrome_switches.h"
 #include "chrome/common/pref_names.h"
 #include "chrome/common/url_constants.h"
 #include "googleurl/src/gurl.h"
@@ -29,6 +27,80 @@
 using base::Time;
 using base::TimeDelta;
 using base::TimeTicks;
+// TODO(mrossetti): Move these to a more appropriate place.
+using history::Prefix;
+using history::Prefixes;
+using history::HistoryMatch;
+using history::HistoryMatches;
+
+namespace history {
+
+// 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) {
+  // 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()))
+      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 std::wstring& 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 std::wstring spec = UTF8ToWide(host.spec());
+  if (spec.compare(match.input_location, input.length(), input))
+    return GURL();  // User typing is no longer a prefix.
+
+  return host;
+}
+
+}  // namespace history
 
 HistoryURLProviderParams::HistoryURLProviderParams(
     const AutocompleteInput& input,
@@ -151,30 +223,25 @@ void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend,
   URLRowVector url_matches;
   HistoryMatches history_matches;
 
-  if (CommandLine::ForCurrentProcess()->HasSwitch(
-          switches::kEnableInMemoryURLIndex)) {
-    // TODO(rohitrao): Fetch results from the index.
-  } else {
-    for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end();
-         ++i) {
-      if (params->cancel)
-        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(WideToUTF16(i->prefix + params->input.text()),
-                                kMaxMatches * 2, &url_matches);
-      for (URLRowVector::const_iterator j(url_matches.begin());
-           j != url_matches.end(); ++j) {
-        const Prefix* best_prefix = BestPrefix(j->url(), std::wstring());
-        DCHECK(best_prefix != NULL);
-        history_matches.push_back(HistoryMatch(*j, i->prefix.length(),
-            !i->num_components,
-            i->num_components >= best_prefix->num_components));
-      }
+  for (Prefixes::const_iterator i(prefixes_.begin()); i != prefixes_.end();
+       ++i) {
+    if (params->cancel)
+      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(WideToUTF16(i->prefix + params->input.text()),
+                              kMaxMatches * 2, &url_matches);
+    for (URLRowVector::const_iterator j(url_matches.begin());
+         j != url_matches.end(); ++j) {
+      const Prefix* best_prefix = BestPrefix(j->url(), std::wstring());
+      DCHECK(best_prefix != NULL);
+      history_matches.push_back(HistoryMatch(*j, i->prefix.length(),
+          !i->num_components,
+          i->num_components >= best_prefix->num_components));
     }
   }
 
@@ -360,7 +427,7 @@ bool HistoryURLProvider::PromoteMatchForInlineAutocomplete(
   // hand, we wouldn't want to immediately start autocompleting it.
   if (!match.url_info.typed_count() ||
       ((match.url_info.typed_count() == 1) &&
-       !IsHostOnly(match.url_info.url())))
+       !history::IsHostOnly(match.url_info.url())))
     return false;
 
   params->matches.push_back(HistoryMatchToACMatch(params, match,
@@ -454,47 +521,7 @@ size_t HistoryURLProvider::TrimHttpPrefix(std::wstring* url) {
 }
 
 // static
-bool HistoryURLProvider::IsHostOnly(const GURL& url) {
-  DCHECK(url.is_valid());
-  return (!url.has_path() || (url.path() == "/")) && !url.has_query() &&
-      !url.has_ref();
-}
-
-// static
-bool HistoryURLProvider::CompareHistoryMatch(const HistoryMatch& a,
-                                             const 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 = 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();
-}
-
-// static
-HistoryURLProvider::Prefixes HistoryURLProvider::GetPrefixes() {
+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;
@@ -526,30 +553,6 @@ int HistoryURLProvider::CalculateRelevance(AutocompleteInput::Type input_type,
 }
 
 // static
-GURL HistoryURLProvider::ConvertToHostOnly(const HistoryMatch& match,
-                                           const std::wstring& 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 std::wstring spec = UTF8ToWide(host.spec());
-  if (spec.compare(match.input_location, input.length(), input))
-    return GURL();  // User typing is no longer a prefix.
-
-  return host;
-}
-
-// static
 void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
     history::URLDatabase* db,
     const HistoryURLProviderParams& params,
@@ -563,7 +566,7 @@ void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
   // 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 = ConvertToHostOnly(match, params.input.text());
+  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
@@ -576,6 +579,9 @@ void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
     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) {
@@ -722,7 +728,7 @@ void HistoryURLProvider::RunAutocompletePasses(
   }
 }
 
-const HistoryURLProvider::Prefix* HistoryURLProvider::BestPrefix(
+const history::Prefix* HistoryURLProvider::BestPrefix(
     const GURL& url,
     const std::wstring& prefix_suffix) const {
   const Prefix* best_prefix = NULL;
@@ -742,7 +748,7 @@ const HistoryURLProvider::Prefix* HistoryURLProvider::BestPrefix(
 
 void HistoryURLProvider::SortMatches(HistoryMatches* matches) const {
   // Sort by quality, best first.
-  std::sort(matches->begin(), matches->end(), &CompareHistoryMatch);
+  std::sort(matches->begin(), matches->end(), &history::CompareHistoryMatch);
 
   // Remove duplicate matches (caused by the search string appearing in one of
   // the prefixes as well as after it).  Consider the following scenario:
@@ -775,15 +781,13 @@ void HistoryURLProvider::SortMatches(HistoryMatches* matches) const {
 }
 
 void HistoryURLProvider::CullPoorMatches(HistoryMatches* matches) const {
-  static const int kLowQualityMatchTypedLimit = 1;
-  static const int kLowQualityMatchVisitLimit = 3;
-  static const int kLowQualityMatchAgeLimitInDays = 3;
-  Time recent_threshold =
-      Time::Now() - TimeDelta::FromDays(kLowQualityMatchAgeLimitInDays);
+  Time recent_threshold = history::AutocompleteAgeThreshold();
   for (HistoryMatches::iterator i(matches->begin()); i != matches->end();) {
-    const history::URLRow& url_info = i->url_info;
-    if ((url_info.typed_count() <= kLowQualityMatchTypedLimit) &&
-        (url_info.visit_count() <= kLowQualityMatchVisitLimit) &&
+    const history::URLRow& url_info(i->url_info);
+    if ((url_info.typed_count() <=
+             history::kLowQualityMatchTypedLimit) &&
+        (url_info.visit_count() <=
+             history::kLowQualityMatchVisitLimit) &&
         (url_info.last_visit() < recent_threshold)) {
       i = matches->erase(i);
     } else {
diff --git a/chrome/browser/autocomplete/history_url_provider.h b/chrome/browser/autocomplete/history_url_provider.h
index 56633b4..bfd13b9 100644
--- a/chrome/browser/autocomplete/history_url_provider.h
+++ b/chrome/browser/autocomplete/history_url_provider.h
@@ -17,10 +17,9 @@ class MessageLoop;
 class Profile;
 
 namespace history {
-class HistoryBackend;
+  class HistoryBackend;
 }  // namespace history
 
-
 // How history autocomplete works
 // ==============================
 //
@@ -180,69 +179,6 @@ class HistoryURLProvider : public AutocompleteProvider {
  private:
   ~HistoryURLProvider() {}
 
-  struct Prefix {
-    Prefix(std::wstring prefix, int num_components)
-        : prefix(prefix),
-          num_components(num_components) { }
-
-    std::wstring prefix;
-
-    // The number of "components" in the prefix.  The scheme is a component,
-    // and the initial "www." or "ftp." is a component.  So "http://foo.com"
-    // and "www.bar.com" each have one component, "ftp://ftp.ftp.com" has two,
-    // and "mysite.com" has none.  This is used to tell whether the user's
-    // input is an innermost match or not.  See comments in HistoryMatch.
-    int num_components;
-  };
-  typedef std::vector<Prefix> Prefixes;
-
-  // Used for intermediate history result operations.
-  struct HistoryMatch {
-    // Required for STL, we don't use this directly.
-    HistoryMatch()
-        : url_info(),
-          input_location(std::wstring::npos),
-          match_in_scheme(false),
-          innermost_match(true) {
-    }
-
-    HistoryMatch(const history::URLRow& url_info,
-                 size_t input_location,
-                 bool match_in_scheme,
-                 bool innermost_match)
-        : url_info(url_info),
-          input_location(input_location),
-          match_in_scheme(match_in_scheme),
-          innermost_match(innermost_match) {
-    }
-
-    bool operator==(const GURL& url) const {
-      return url_info.url() == url;
-    }
-
-    history::URLRow url_info;
-
-    // The offset of the user's input within the URL.
-    size_t input_location;
-
-    // Whether this is a match in the scheme.  This determines whether we'll go
-    // ahead and show a scheme on the URL even if the user didn't type one.
-    // If our best match was in the scheme, not showing the scheme is both
-    // confusing and, for inline autocomplete of the fill_into_edit, dangerous.
-    // (If the user types "h" and we match "http://foo/", we need to inline
-    // autocomplete that, not "foo/", which won't show anything at all, and
-    // will mislead the user into thinking the What You Typed match is what's
-    // selected.)
-    bool match_in_scheme;
-
-    // A match after any scheme/"www.", if the user input could match at both
-    // locations.  If the user types "w", an innermost match ("website.com") is
-    // better than a non-innermost match ("www.google.com").  If the user types
-    // "x", no scheme in our prefix list (or "www.") begins with x, so all
-    // matches are, vacuously,  "innermost matches".
-    bool innermost_match;
-  };
-  typedef std::deque<HistoryMatch> HistoryMatches;
 
   enum MatchType {
     NORMAL,
@@ -268,16 +204,8 @@ class HistoryURLProvider : public AutocompleteProvider {
   // return 0.
   static size_t TrimHttpPrefix(std::wstring* url);
 
-  // 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").
-  static bool IsHostOnly(const GURL& url);
-
-  // Acts like the > operator for URLInfo classes.
-  static bool CompareHistoryMatch(const HistoryMatch& a,
-                                  const HistoryMatch& b);
-
   // Returns the set of prefixes to use for prefixes_.
-  static Prefixes GetPrefixes();
+  static history::Prefixes GetPrefixes();
 
   // Determines the relevance for some input, given its type and which match it
   // is.  If |match_type| is NORMAL, |match_number| is a number
@@ -290,7 +218,7 @@ class HistoryURLProvider : public AutocompleteProvider {
   // 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.
-  static GURL ConvertToHostOnly(const HistoryMatch& match,
+  static GURL ConvertToHostOnly(const history::HistoryMatch& match,
                                 const std::wstring& input);
 
   // See if a shorter version of the best match should be created, and if so
@@ -305,7 +233,7 @@ class HistoryURLProvider : public AutocompleteProvider {
       const HistoryURLProviderParams& params,
       bool have_what_you_typed_match,
       const AutocompleteMatch& what_you_typed_match,
-      HistoryMatches* matches);
+      history::HistoryMatches* matches);
 
   // Ensures that |matches| contains an entry for |info|, which may mean adding
   // a new such entry (using |input_location| and |match_in_scheme|).
@@ -317,7 +245,7 @@ class HistoryURLProvider : public AutocompleteProvider {
   static void EnsureMatchPresent(const history::URLRow& info,
                                  std::wstring::size_type input_location,
                                  bool match_in_scheme,
-                                 HistoryMatches* matches,
+                                 history::HistoryMatches* matches,
                                  bool promote);
 
   // Helper function that actually launches the two autocomplete passes.
@@ -330,8 +258,8 @@ class HistoryURLProvider : public AutocompleteProvider {
   // |prefix_suffix| (which may be empty) is appended to every attempted
   // prefix.  This is useful when you need to figure out the innermost match
   // for some user input in a URL.
-  const Prefix* BestPrefix(const GURL& text,
-                           const std::wstring& prefix_suffix) const;
+  const history::Prefix* BestPrefix(const GURL& text,
+                                    const std::wstring& prefix_suffix) const;
 
   // Returns a match corresponding to exactly what the user has typed.
   AutocompleteMatch SuggestExactInput(const AutocompleteInput& input,
@@ -346,25 +274,25 @@ class HistoryURLProvider : public AutocompleteProvider {
   bool FixupExactSuggestion(history::URLDatabase* db,
                             const AutocompleteInput& input,
                             AutocompleteMatch* match,
-                            HistoryMatches* matches) const;
+                            history::HistoryMatches* matches) const;
 
   // Determines if |match| is suitable for inline autocomplete, and promotes it
   // if so.
   bool PromoteMatchForInlineAutocomplete(HistoryURLProviderParams* params,
-                                         const HistoryMatch& match);
+                                         const history::HistoryMatch& match);
 
   // Sorts the given list of matches.
-  void SortMatches(HistoryMatches* matches) const;
+  void SortMatches(history::HistoryMatches* matches) const;
 
   // Removes results that have been rarely typed or visited, and not any time
   // recently.  The exact parameters for this heuristic can be found in the
   // function body.
-  void CullPoorMatches(HistoryMatches* matches) const;
+  void CullPoorMatches(history::HistoryMatches* matches) const;
 
   // Removes results that redirect to each other, leaving at most |max_results|
   // results.
   void CullRedirects(history::HistoryBackend* backend,
-                     HistoryMatches* matches,
+                     history::HistoryMatches* matches,
                      size_t max_results) const;
 
   // Helper function for CullRedirects, this removes all but the first
@@ -376,18 +304,19 @@ class HistoryURLProvider : public AutocompleteProvider {
   // is removed, the next item will be shifted, and this allows the caller to
   // pick up on the next one when this happens.
   size_t RemoveSubsequentMatchesOf(
-      HistoryMatches* matches,
+      history::HistoryMatches* matches,
       size_t source_index,
       const std::vector<GURL>& remove) const;
 
   // Converts a line from the database into an autocomplete match for display.
-  AutocompleteMatch HistoryMatchToACMatch(HistoryURLProviderParams* params,
-                                          const HistoryMatch& history_match,
-                                          MatchType match_type,
-                                          size_t match_number);
+  AutocompleteMatch HistoryMatchToACMatch(
+      HistoryURLProviderParams* params,
+      const history::HistoryMatch& history_match,
+      MatchType match_type,
+      size_t match_number);
 
   // Prefixes to try appending to user input when looking for a match.
-  const Prefixes prefixes_;
+  const history::Prefixes prefixes_;
 
   // Params for the current query.  The provider should not free this directly;
   // instead, it is passed as a parameter through the history backend, and the