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

9 files changed, 124 insertions, 10 deletions

diff --git a/chrome/browser/history/history.cc b/chrome/browser/history/history.cc
index aaec4207..c001298 100644
--- a/chrome/browser/history/history.cc
+++ b/chrome/browser/history/history.cc
@@ -222,6 +222,16 @@ history::URLDatabase* HistoryService::InMemoryDatabase() {
   return NULL;
 }
 
+history::InMemoryURLIndex* HistoryService::InMemoryIndex() {
+  // NOTE: See comments in BackendLoaded() as to why we call
+  // LoadBackendIfNecessary() here even though it won't affect the return value
+  // for this call.
+  LoadBackendIfNecessary();
+  if (in_memory_backend_.get())
+    return in_memory_backend_->index();
+  return NULL;
+}
+
 void HistoryService::SetSegmentPresentationIndex(int64 segment_id, int index) {
   ScheduleAndForget(PRIORITY_UI,
                     &HistoryBackend::SetSegmentPresentationIndex,
diff --git a/chrome/browser/history/history.h b/chrome/browser/history/history.h
index 8da542c..121d573 100644
--- a/chrome/browser/history/history.h
+++ b/chrome/browser/history/history.h
@@ -51,6 +51,7 @@ class TypedUrlDataTypeController;
 namespace history {
 
 class InMemoryHistoryBackend;
+class InMemoryURLIndex;
 class HistoryBackend;
 class HistoryDatabase;
 struct HistoryDetails;
@@ -151,6 +152,8 @@ class HistoryService : public CancelableRequestProvider,
   // TODO(brettw) this should return the InMemoryHistoryBackend.
   history::URLDatabase* InMemoryDatabase();
 
+  history::InMemoryURLIndex* InMemoryIndex();
+
   // Navigation ----------------------------------------------------------------
 
   // Adds the given canonical URL to history with the current time as the visit
diff --git a/chrome/browser/history/history_backend.cc b/chrome/browser/history/history_backend.cc
index 0f512db..8e1c5fb 100644
--- a/chrome/browser/history/history_backend.cc
+++ b/chrome/browser/history/history_backend.cc
@@ -548,7 +548,7 @@ void HistoryBackend::InitImpl() {
   // Fill the in-memory database and send it back to the history service on the
   // main thread.
   InMemoryHistoryBackend* mem_backend = new InMemoryHistoryBackend;
-  if (mem_backend->Init(history_name))
+  if (mem_backend->Init(history_name, db_.get()))
     delegate_->SetInMemoryBackend(mem_backend);  // Takes ownership of pointer.
   else
     delete mem_backend;  // Error case, run without the in-memory DB.
diff --git a/chrome/browser/history/history_types.cc b/chrome/browser/history/history_types.cc
index 50395aa..305fa35 100644
--- a/chrome/browser/history/history_types.cc
+++ b/chrome/browser/history/history_types.cc
@@ -10,6 +10,7 @@
 #include "base/stl_util-inl.h"
 
 using base::Time;
+using base::TimeDelta;
 
 namespace history {
 
@@ -237,4 +238,10 @@ void QueryResults::AdjustResultMap(size_t begin, size_t end, ptrdiff_t delta) {
   }
 }
 
+Time AutocompleteAgeThreshold() {
+  Time recent_threshold =
+      Time::Now() - TimeDelta::FromDays(kLowQualityMatchAgeLimitInDays);
+  return recent_threshold;
+}
+
 }  // namespace history
diff --git a/chrome/browser/history/history_types.h b/chrome/browser/history/history_types.h
index 4619792..0c283b1 100644
--- a/chrome/browser/history/history_types.h
+++ b/chrome/browser/history/history_types.h
@@ -6,6 +6,7 @@
 #define CHROME_BROWSER_HISTORY_HISTORY_TYPES_H_
 #pragma once
 
+#include <deque>
 #include <map>
 #include <set>
 #include <string>
@@ -311,7 +312,7 @@ struct StarredEntry {
 
   // If type == URL, this is the ID of the URL of the primary page that was
   // starred.
-  history::URLID url_id;
+  URLID url_id;
 
   // Time the entry was last modified. This is only used for groups and
   // indicates the last time a URL was added as a child to the group.
@@ -528,6 +529,80 @@ struct MostVisitedURL {
 
 typedef std::vector<MostVisitedURL> MostVisitedURLList;
 
-}  // history
+// 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 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;
+  }
+
+  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;
+
+struct Prefix {
+  Prefix(std::wstring const& 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;
+
+// Constants which specify, when considered altogether, 'significant'
+// history items. These are used to filter out insignificant items
+// for consideration as autocomplete candidates.
+const int kLowQualityMatchTypedLimit = 1;
+const int kLowQualityMatchVisitLimit = 3;
+const int kLowQualityMatchAgeLimitInDays = 3;
+
+// Returns the date threshold for considering an history item as significant.
+base::Time AutocompleteAgeThreshold();
+
+}  // namespace history
 
 #endif  // CHROME_BROWSER_HISTORY_HISTORY_TYPES_H_
diff --git a/chrome/browser/history/in_memory_history_backend.cc b/chrome/browser/history/in_memory_history_backend.cc
index 9f3e7be..1350667 100644
--- a/chrome/browser/history/in_memory_history_backend.cc
+++ b/chrome/browser/history/in_memory_history_backend.cc
@@ -5,10 +5,13 @@
 #include "chrome/browser/history/in_memory_history_backend.h"
 
 #include "base/command_line.h"
+#include "base/histogram.h"
+#include "base/time.h"
 #include "chrome/browser/browser_process.h"
 #include "chrome/browser/history/history_notifications.h"
 #include "chrome/browser/history/in_memory_database.h"
 #include "chrome/browser/history/in_memory_url_index.h"
+#include "chrome/browser/history/url_database.h"
 #include "chrome/browser/profile.h"
 #include "chrome/common/chrome_switches.h"
 #include "chrome/common/notification_service.h"
@@ -26,14 +29,18 @@ InMemoryHistoryBackend::InMemoryHistoryBackend()
 InMemoryHistoryBackend::~InMemoryHistoryBackend() {
 }
 
-bool InMemoryHistoryBackend::Init(const FilePath& history_filename) {
+bool InMemoryHistoryBackend::Init(const FilePath& history_filename,
+                                  URLDatabase* db) {
   db_.reset(new InMemoryDatabase);
   bool success = db_->InitFromDisk(history_filename);
 
   if (CommandLine::ForCurrentProcess()->HasSwitch(
       switches::kEnableInMemoryURLIndex)) {
     index_.reset(new InMemoryURLIndex);
-    // TODO(rohitrao): Load index.
+    base::TimeTicks beginning_time = base::TimeTicks::Now();
+    index_->Init(db);
+    UMA_HISTOGRAM_TIMES("Autocomplete.HistoryDatabaseIndexingTime",
+                        base::TimeTicks::Now() - beginning_time);
   }
 
   return success;
diff --git a/chrome/browser/history/in_memory_history_backend.h b/chrome/browser/history/in_memory_history_backend.h
index b10bb31..ac4c185 100644
--- a/chrome/browser/history/in_memory_history_backend.h
+++ b/chrome/browser/history/in_memory_history_backend.h
@@ -29,6 +29,7 @@ namespace history {
 
 class InMemoryDatabase;
 class InMemoryURLIndex;
+class URLDatabase;
 struct URLsDeletedDetails;
 struct URLsModifiedDetails;
 
@@ -38,7 +39,7 @@ class InMemoryHistoryBackend : public NotificationObserver {
   ~InMemoryHistoryBackend();
 
   // Initializes with data from the given history database.
-  bool Init(const FilePath& history_filename);
+  bool Init(const FilePath& history_filename, URLDatabase* db);
 
   // Does initialization work when this object is attached to the history
   // system on the main thread. The argument is the profile with which the
diff --git a/chrome/browser/history/in_memory_url_index.cc b/chrome/browser/history/in_memory_url_index.cc
index 83c401f..7f249df2 100644
--- a/chrome/browser/history/in_memory_url_index.cc
+++ b/chrome/browser/history/in_memory_url_index.cc
@@ -4,10 +4,16 @@
 
 #include "chrome/browser/history/in_memory_url_index.h"
 
+#include "chrome/browser/history/url_database.h"
+
 namespace history {
 
-InMemoryURLIndex::InMemoryURLIndex() {}
+// Indexing
 
-InMemoryURLIndex::~InMemoryURLIndex() {}
+bool InMemoryURLIndex::Init(history::URLDatabase* history_db) {
+  bool success = true;
+  // TODO(mrossetti): Implement.
+  return success;
+}
 
 }  // namespace history
diff --git a/chrome/browser/history/in_memory_url_index.h b/chrome/browser/history/in_memory_url_index.h
index 166c400..5b7861a 100644
--- a/chrome/browser/history/in_memory_url_index.h
+++ b/chrome/browser/history/in_memory_url_index.h
@@ -8,6 +8,8 @@
 
 namespace history {
 
+class URLDatabase;
+
 // The URL history source.
 // Holds portions of the URL database in memory in an indexed form.  Used to
 // quickly look up matching URLs for a given query string.  Used by
@@ -15,8 +17,11 @@ namespace history {
 // matches to the omnibox.
 class InMemoryURLIndex {
  public:
-  InMemoryURLIndex();
-  ~InMemoryURLIndex();
+  InMemoryURLIndex() {}
+  ~InMemoryURLIndex() {}
+
+  // Open and index the URL history database.
+  bool Init(URLDatabase* history_db);
 };
 
 }  // namespace history