Do at least some rudimentary sorting of bookmarked URLs in the omnibox dropdown (existing sort was effectively random). Patch by Pierre-Antoine LaFayette (see http://codereview.chromium.org/165455 ), r=sky,me, tweaked.

BUG=16230
TEST=In the omnibox dropdown, bookmarked URLs that have been typed more often should be ranked above those that have been typed less often.

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

7 files changed, 212 insertions, 47 deletions

diff --git a/chrome/browser/autocomplete/history_contents_provider.cc b/chrome/browser/autocomplete/history_contents_provider.cc
index c81ccd8..558911c 100644
--- a/chrome/browser/autocomplete/history_contents_provider.cc
+++ b/chrome/browser/autocomplete/history_contents_provider.cc
@@ -71,12 +71,10 @@ void HistoryContentsProvider::Start(const AutocompleteInput& input,
     return;
   }
 
-  // Change input type and reset relevance counters, so matches will be marked
-  // up properly.
+  // Change input type so matches will be marked up properly.
   input_type_ = input.type();
   trim_http_ = !url_util::FindAndCompareScheme(WideToUTF8(input.text()),
                                                chrome::kHttpScheme, NULL);
-  star_title_count_ = star_contents_count_ = title_count_ = contents_count_ = 0;
 
   // Decide what to do about any previous query/results.
   if (!minimal_changes) {
@@ -150,11 +148,20 @@ void HistoryContentsProvider::QueryComplete(HistoryService::Handle handle,
 }
 
 void HistoryContentsProvider::ConvertResults() {
+  // Reset the relevance counters so that result relevance won't vary on
+  // subsequent passes of ConvertResults.
+  star_title_count_ = star_contents_count_ = title_count_ = contents_count_ = 0;
+
   // Make the result references and score the results.
   std::vector<MatchReference> result_refs;
   result_refs.reserve(results_.size());
-  for (size_t i = 0; i < results_.size(); i++) {
-    MatchReference ref(&results_[i], CalculateRelevance(results_[i]));
+
+  // Results are sorted in decreasing order so we run the loop backwards so that
+  // the relevance increment favors the higher ranked results.
+  for (std::vector<history::URLResult*>::const_reverse_iterator i =
+       results_.rbegin(); i != results_.rend(); ++i) {
+    history::URLResult* result = *i;
+    MatchReference ref(result, CalculateRelevance(*result));
     result_refs.push_back(ref);
   }
 
@@ -275,8 +282,7 @@ void HistoryContentsProvider::QueryBookmarks(const AutocompleteInput& input) {
   if (!bookmark_model)
     return;
 
-  DCHECK(results_.size() == 0);  // When we get here the results should be
-                                 // empty.
+  DCHECK(results_.empty());
 
   TimeTicks start_time = TimeTicks::Now();
   std::vector<bookmark_utils::TitleMatch> matches;
diff --git a/chrome/browser/autocomplete/history_contents_provider_unittest.cc b/chrome/browser/autocomplete/history_contents_provider_unittest.cc
index 8930353..84dde8f 100644
--- a/chrome/browser/autocomplete/history_contents_provider_unittest.cc
+++ b/chrome/browser/autocomplete/history_contents_provider_unittest.cc
@@ -101,10 +101,10 @@ TEST_F(HistoryContentsProviderTest, Body) {
   // The results should be the first two pages, in decreasing order.
   const ACMatches& m = matches();
   ASSERT_EQ(2U, m.size());
-  EXPECT_EQ(test_entries[1].url, m[0].destination_url.spec());
-  EXPECT_STREQ(test_entries[1].title, m[0].description.c_str());
-  EXPECT_EQ(test_entries[0].url, m[1].destination_url.spec());
-  EXPECT_STREQ(test_entries[0].title, m[1].description.c_str());
+  EXPECT_EQ(test_entries[0].url, m[0].destination_url.spec());
+  EXPECT_STREQ(test_entries[0].title, m[0].description.c_str());
+  EXPECT_EQ(test_entries[1].url, m[1].destination_url.spec());
+  EXPECT_STREQ(test_entries[1].title, m[1].description.c_str());
 }
 
 TEST_F(HistoryContentsProviderTest, Title) {
@@ -114,10 +114,10 @@ TEST_F(HistoryContentsProviderTest, Title) {
   // The results should be the first two pages.
   const ACMatches& m = matches();
   ASSERT_EQ(2U, m.size());
-  EXPECT_EQ(test_entries[1].url, m[0].destination_url.spec());
-  EXPECT_STREQ(test_entries[1].title, m[0].description.c_str());
-  EXPECT_EQ(test_entries[0].url, m[1].destination_url.spec());
-  EXPECT_STREQ(test_entries[0].title, m[1].description.c_str());
+  EXPECT_EQ(test_entries[0].url, m[0].destination_url.spec());
+  EXPECT_STREQ(test_entries[0].title, m[0].description.c_str());
+  EXPECT_EQ(test_entries[1].url, m[1].destination_url.spec());
+  EXPECT_STREQ(test_entries[1].title, m[1].description.c_str());
 }
 
 // The "minimal changes" flag should mean that we don't re-query the DB.
diff --git a/chrome/browser/bookmarks/bookmark_index.cc b/chrome/browser/bookmarks/bookmark_index.cc
index fa512c2..8245ac1 100644
--- a/chrome/browser/bookmarks/bookmark_index.cc
+++ b/chrome/browser/bookmarks/bookmark_index.cc
@@ -10,7 +10,9 @@
 #include "app/l10n_util.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
 #include "chrome/browser/bookmarks/bookmark_utils.h"
+#include "chrome/browser/history/history_database.h"
 #include "chrome/browser/history/query_parser.h"
+#include "chrome/browser/profile.h"
 
 BookmarkIndex::NodeSet::const_iterator
     BookmarkIndex::Match::nodes_begin() const {
@@ -52,37 +54,71 @@ void BookmarkIndex::GetBookmarksWithTitlesMatching(
       return;
   }
 
+  NodeTypedCountPairs node_typed_counts;
+  SortMatches(matches, &node_typed_counts);
+
   // We use a QueryParser to fill in match positions for us. It's not the most
   // efficient way to go about this, but by the time we get here we know what
   // matches and so this shouldn't be performance critical.
   QueryParser parser;
   ScopedVector<QueryNode> query_nodes;
   parser.ParseQuery(query, &query_nodes.get());
-  for (size_t i = 0; i < matches.size() && results->size() < max_count; ++i) {
-    AddMatchToResults(matches[i], max_count, &parser, query_nodes.get(),
-                      results);
+
+  // The highest typed counts should be at the beginning of the results vector
+  // so that the best matches will always be included in the results. The loop
+  // that calculates result relevance in HistoryContentsProvider::ConvertResults
+  // will run backwards to assure higher relevance will be attributed to the
+  // best matches.
+  for (NodeTypedCountPairs::const_iterator i = node_typed_counts.begin();
+       i != node_typed_counts.end() && results->size() < max_count; ++i)
+    AddMatchToResults(i->first, &parser, query_nodes.get(), results);
+}
+
+void BookmarkIndex::SortMatches(const Matches& matches,
+                                NodeTypedCountPairs* node_typed_counts) const {
+  HistoryService* const history_service = profile_ ?
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS) : NULL;
+
+  history::URLDatabase* url_db = history_service ?
+      history_service->in_memory_database() : NULL;
+
+  for (Matches::const_iterator i = matches.begin(); i != matches.end(); ++i)
+    ExtractBookmarkNodePairs(url_db, *i, node_typed_counts);
+
+  std::sort(node_typed_counts->begin(), node_typed_counts->end(),
+            &NodeTypedCountPairSortFunc);
+}
+
+void BookmarkIndex::ExtractBookmarkNodePairs(
+    history::URLDatabase* url_db,
+    const Match& match,
+    NodeTypedCountPairs* node_typed_counts) const {
+
+  for (NodeSet::const_iterator i = match.nodes_begin();
+       i != match.nodes_end(); ++i) {
+    history::URLRow url;
+    if (url_db)
+      url_db->GetRowForURL((*i)->GetURL(), &url);
+    NodeTypedCountPair pair(*i, url.typed_count());
+    node_typed_counts->push_back(pair);
   }
 }
 
 void BookmarkIndex::AddMatchToResults(
-    const Match& match,
-    size_t max_count,
+    const BookmarkNode* node,
     QueryParser* parser,
     const std::vector<QueryNode*>& query_nodes,
     std::vector<bookmark_utils::TitleMatch>* results) {
-  for (NodeSet::const_iterator i = match.nodes_begin();
-       i != match.nodes_end() && results->size() < max_count; ++i) {
-    bookmark_utils::TitleMatch title_match;
-    // Check that the result matches the query.  The previous search
-    // was a simple per-word search, while the more complex matching
-    // of QueryParser may filter it out.  For example, the query
-    // ["thi"] will match the bookmark titled [Thinking], but since
-    // ["thi"] is quoted we don't want to do a prefix match.
-    if (parser->DoesQueryMatch((*i)->GetTitle(), query_nodes,
-                               &(title_match.match_positions))) {
-      title_match.node = *i;
-      results->push_back(title_match);
-    }
+  bookmark_utils::TitleMatch title_match;
+  // Check that the result matches the query.  The previous search
+  // was a simple per-word search, while the more complex matching
+  // of QueryParser may filter it out.  For example, the query
+  // ["thi"] will match the bookmark titled [Thinking], but since
+  // ["thi"] is quoted we don't want to do a prefix match.
+  if (parser->DoesQueryMatch(node->GetTitle(), query_nodes,
+                             &(title_match.match_positions))) {
+    title_match.node = node;
+    results->push_back(title_match);
   }
 }
 
diff --git a/chrome/browser/bookmarks/bookmark_index.h b/chrome/browser/bookmarks/bookmark_index.h
index f3da604..0fa1a58 100644
--- a/chrome/browser/bookmarks/bookmark_index.h
+++ b/chrome/browser/bookmarks/bookmark_index.h
@@ -14,6 +14,7 @@
 #include "base/basictypes.h"
 
 class BookmarkNode;
+class Profile;
 class QueryNode;
 class QueryParser;
 
@@ -21,6 +22,10 @@ namespace bookmark_utils {
 struct TitleMatch;
 }
 
+namespace history {
+class URLDatabase;
+}
+
 // BookmarkIndex maintains an index of the titles of bookmarks for quick
 // look up. BookmarkIndex is owned and maintained by BookmarkModel, you
 // shouldn't need to interact directly with BookmarkIndex.
@@ -31,7 +36,7 @@ struct TitleMatch;
 
 class BookmarkIndex {
  public:
-  BookmarkIndex() {}
+  explicit BookmarkIndex(Profile* profile) : profile_(profile) {}
 
   // Invoked when a bookmark has been added to the model.
   void Add(const BookmarkNode* node);
@@ -70,16 +75,39 @@ class BookmarkIndex {
     NodeSet::const_iterator nodes_begin() const;
 
     // Returns an iterator to the beginning of the matching nodes. See
-    // description of nodes for why this should be used over nodes.begin().
+    // description of nodes for why this should be used over nodes.end().
     NodeSet::const_iterator nodes_end() const;
   };
 
   typedef std::vector<Match> Matches;
 
-  // Add all the matching nodes in |match.nodes| to |results| until there are
-  // at most |max_count| matches in |results|.
-  void AddMatchToResults(const Match& match,
-                         size_t max_count,
+  // Pairs BookmarkNodes and the number of times the nodes' URLs were typed.
+  // Used to sort Matches in decreasing order of typed count.
+  typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair;
+  typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs;
+
+  // Extracts |matches.nodes| into NodeTypedCountPairs and sorts the pairs in
+  // decreasing order of typed count.
+  void SortMatches(const Matches& matches,
+                   NodeTypedCountPairs* node_typed_counts) const;
+
+  // Extracts BookmarkNodes from |match| and retrieves typed counts for each
+  // node from the in-memory database. Inserts pairs containing the node and
+  // typed count into the vector |node_typed_counts|. |node_typed_counts| is
+  // sorted in decreasing order of typed count.
+  void ExtractBookmarkNodePairs(history::URLDatabase* url_db,
+                                const Match& match,
+                                NodeTypedCountPairs* node_typed_counts) const;
+
+  // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed
+  // count so that the best matches will always be added to the results.
+  static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a,
+                                         const NodeTypedCountPair& b) {
+      return a.second > b.second;
+  }
+
+  // Add |node| to |results| if the node matches the query.
+  void AddMatchToResults(const BookmarkNode* node,
                          QueryParser* parser,
                          const std::vector<QueryNode*>& query_nodes,
                          std::vector<bookmark_utils::TitleMatch>* results);
@@ -123,6 +151,8 @@ class BookmarkIndex {
 
   Index index_;
 
+  Profile* profile_;
+
   DISALLOW_COPY_AND_ASSIGN(BookmarkIndex);
 };
 
diff --git a/chrome/browser/bookmarks/bookmark_index_unittest.cc b/chrome/browser/bookmarks/bookmark_index_unittest.cc
index 621869e..edac8b0 100644
--- a/chrome/browser/bookmarks/bookmark_index_unittest.cc
+++ b/chrome/browser/bookmarks/bookmark_index_unittest.cc
@@ -5,10 +5,14 @@
 #include <string>
 #include <vector>
 
+#include "base/message_loop.h"
 #include "base/string_util.h"
 #include "chrome/browser/bookmarks/bookmark_index.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
+#include "chrome/browser/history/history_database.h"
+#include "chrome/browser/history/in_memory_database.h"
 #include "chrome/browser/history/query_parser.h"
+#include "chrome/test/testing_profile.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 class BookmarkIndexTest : public testing::Test {
@@ -82,7 +86,6 @@ class BookmarkIndexTest : public testing::Test {
     }
   }
 
-
  protected:
   scoped_ptr<BookmarkModel> model_;
 
@@ -120,7 +123,6 @@ TEST_F(BookmarkIndexTest, Tests) {
 
     // Make sure quotes don't do a prefix match.
     { L"think",                     L"\"thi\"", L""},
-
   };
   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
     std::vector<std::wstring> titles;
@@ -205,3 +207,84 @@ TEST_F(BookmarkIndexTest, EmptyMatchOnMultiwideLowercaseString) {
   EXPECT_TRUE(matches[0].node == n1);
   EXPECT_TRUE(matches[0].match_positions.empty());
 }
+
+TEST_F(BookmarkIndexTest, GetResultsSortedByTypedCount) {
+  // This ensures MessageLoop::current() will exist, which is needed by
+  // TestingProfile::BlockUntilHistoryProcessesPendingRequests().
+  MessageLoop loop(MessageLoop::TYPE_DEFAULT);
+
+  TestingProfile profile;
+  profile.CreateHistoryService(true);
+  profile.BlockUntilHistoryProcessesPendingRequests();
+  profile.CreateBookmarkModel(true);
+  profile.BlockUntilBookmarkModelLoaded();
+
+  BookmarkModel* model = profile.GetBookmarkModel();
+
+  HistoryService* const history_service =
+      profile.GetHistoryService(Profile::EXPLICIT_ACCESS);
+
+  history::URLDatabase* url_db = history_service->in_memory_database();
+
+  struct TestData {
+    const GURL url;
+    const std::wstring title;
+    const int typed_count;
+  } data[] = {
+    { GURL("http://www.google.com/"),      L"Google",           100 },
+    { GURL("http://maps.google.com/"),     L"Google Maps",       40 },
+    { GURL("http://docs.google.com/"),     L"Google Docs",       50 },
+    { GURL("http://reader.google.com/"),   L"Google Reader",     80 },
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
+    history::URLRow info(data[i].url);
+    info.set_title(data[i].title);
+    info.set_typed_count(data[i].typed_count);
+    // Populate the InMemoryDatabase....
+    url_db->AddURL(info);
+    // Populate the BookmarkIndex.
+    model->AddURL(model->other_node(), i, data[i].title, data[i].url);
+  }
+
+  // Check that the InMemoryDatabase stored the URLs properly.
+  history::URLRow result1;
+  url_db->GetRowForURL(data[0].url, &result1);
+  EXPECT_EQ(data[0].title, result1.title());
+
+  history::URLRow result2;
+  url_db->GetRowForURL(data[1].url, &result2);
+  EXPECT_EQ(data[1].title, result2.title());
+
+  history::URLRow result3;
+  url_db->GetRowForURL(data[2].url, &result3);
+  EXPECT_EQ(data[2].title, result3.title());
+
+  history::URLRow result4;
+  url_db->GetRowForURL(data[3].url, &result4);
+  EXPECT_EQ(data[3].title, result4.title());
+
+  // Populate match nodes.
+  std::vector<bookmark_utils::TitleMatch> matches;
+  model->GetBookmarksWithTitlesMatching(L"google", 4, &matches);
+
+  // The resulting order should be:
+  // 1. Google (google.com) 100
+  // 2. Google Reader (google.com/reader) 80
+  // 3. Google Docs (docs.google.com) 50
+  // 4. Google Maps (maps.google.com) 40
+  EXPECT_EQ(4, static_cast<int>(matches.size()));
+  EXPECT_EQ(data[0].url, matches[0].node->GetURL());
+  EXPECT_EQ(data[3].url, matches[1].node->GetURL());
+  EXPECT_EQ(data[2].url, matches[2].node->GetURL());
+  EXPECT_EQ(data[1].url, matches[3].node->GetURL());
+
+  matches.clear();
+  // Select top two matches.
+  model->GetBookmarksWithTitlesMatching(L"google", 2, &matches);
+
+  EXPECT_EQ(2, static_cast<int>(matches.size()));
+  EXPECT_EQ(data[0].url, matches[0].node->GetURL());
+  EXPECT_EQ(data[3].url, matches[1].node->GetURL());
+}
+
diff --git a/chrome/browser/bookmarks/bookmark_model.cc b/chrome/browser/bookmarks/bookmark_model.cc
index 2eeeff1..5bb5bb9 100644
--- a/chrome/browser/bookmarks/bookmark_model.cc
+++ b/chrome/browser/bookmarks/bookmark_model.cc
@@ -36,7 +36,7 @@ BookmarkNode::BookmarkNode(const GURL& url)
 }
 
 BookmarkNode::BookmarkNode(int64 id, const GURL& url)
-    : url_(url){
+    : url_(url) {
   Initialize(id);
 }
 
@@ -78,7 +78,7 @@ void BookmarkNode::Reset(const history::StarredEntry& entry) {
 namespace {
 
 // Comparator used when sorting bookmarks. Folders are sorted first, then
-  // bookmarks.
+// bookmarks.
 class SortComparator : public std::binary_function<const BookmarkNode*,
                                                    const BookmarkNode*,
                                                    bool> {
@@ -510,7 +510,7 @@ void BookmarkModel::RemoveAndDeleteNode(BookmarkNode* delete_me) {
     // RemoveNode adds an entry to changed_urls for each node of type URL. As we
     // allow duplicates we need to remove any entries that are still bookmarked.
     for (std::set<GURL>::iterator i = details.changed_urls.begin();
-         i != details.changed_urls.end(); ){
+         i != details.changed_urls.end(); ) {
       if (IsBookmarkedNoLock(*i)) {
         // When we erase the iterator pointing at the erasee is
         // invalidated, so using i++ here within the "erase" call is
@@ -727,5 +727,5 @@ BookmarkStorage::LoadDetails* BookmarkModel::CreateLoadDetails() {
   BookmarkNode* bb_node = CreateBookmarkNode();
   BookmarkNode* other_folder_node = CreateOtherBookmarksNode();
   return new BookmarkStorage::LoadDetails(
-      bb_node, other_folder_node, new BookmarkIndex(), next_node_id_);
+      bb_node, other_folder_node, new BookmarkIndex(profile()), next_node_id_);
 }
diff --git a/chrome/browser/history/history_types.h b/chrome/browser/history/history_types.h
index f23af42..c967374 100644
--- a/chrome/browser/history/history_types.h
+++ b/chrome/browser/history/history_types.h
@@ -365,6 +365,8 @@ class URLResult : public URLRow {
 // a given URL appears in those results.
 class QueryResults {
  public:
+  typedef std::vector<URLResult*> URLResultVector;
+
   QueryResults();
   ~QueryResults();
 
@@ -388,10 +390,20 @@ class QueryResults {
   bool reached_beginning() { return reached_beginning_; }
 
   size_t size() const { return results_.size(); }
+  bool empty() const { return results_.empty(); }
 
   URLResult& operator[](size_t i) { return *results_[i]; }
   const URLResult& operator[](size_t i) const { return *results_[i]; }
 
+  URLResultVector::const_iterator begin() const { return results_.begin(); }
+  URLResultVector::const_iterator end() const { return results_.end(); }
+  URLResultVector::const_reverse_iterator rbegin() const {
+    return results_.rbegin();
+  }
+  URLResultVector::const_reverse_iterator rend() const {
+    return results_.rend();
+  }
+
   // Returns a pointer to the beginning of an array of all matching indices
   // for entries with the given URL. The array will be |*num_matches| long.
   // |num_matches| can be NULL if the caller is not interested in the number of
@@ -423,8 +435,6 @@ class QueryResults {
   void DeleteRange(size_t begin, size_t end);
 
  private:
-  typedef std::vector<URLResult*> URLResultVector;
-
   // Maps the given URL to a list of indices into results_ which identify each
   // time an entry with that URL appears. Normally, each URL will have one or
   // very few indices after it, so we optimize this to use statically allocated