Limit impact of large result sets in the HistoryQuickProvider by short-circuiting any scoring if a certain maximum number of results is exceeded. That limit is currently set to 500.

BUG=None
TEST=Using a large history database enter a term of 'h' in the omnibox. No HQP results should be presented since 'h' occurs in nearly all URLs. Continue typing a URL from the history and after getting to the domain portion the HQP should start returning results. Alternatively, type a word starting with 'h' and which matches a term in an historical page title. Added a unit test.
Review URL: http://codereview.chromium.org/6676051

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

3 files changed, 57 insertions, 10 deletions

diff --git a/chrome/browser/history/in_memory_url_index.cc b/chrome/browser/history/in_memory_url_index.cc
index b093188..6d9a44f 100644
--- a/chrome/browser/history/in_memory_url_index.cc
+++ b/chrome/browser/history/in_memory_url_index.cc
@@ -48,6 +48,7 @@ typedef imui::InMemoryURLIndexCacheItem_HistoryInfoMapItem_HistoryInfoMapEntry
 
 const size_t InMemoryURLIndex::kNoCachedResultForTerm = -1;
 
+// Scoring constants.
 const float kOrderMaxValue = 50.0;
 const float kStartMaxValue = 50.0;
 const size_t kMaxSignificantStart = 20;
@@ -326,11 +327,15 @@ ScoredHistoryMatches InMemoryURLIndex::HistoryItemsForTerms(
     String16Vector::value_type all_terms(JoinString(lower_terms, ' '));
     HistoryIDSet history_id_set = HistoryIDSetFromWords(all_terms);
 
-    // Pass over all of the candidates filtering out any without a proper
-    // substring match, inserting those which pass in order by score.
-    scored_items = std::for_each(history_id_set.begin(), history_id_set.end(),
-                                 AddHistoryMatch(*this,
-                                                 lower_terms)).ScoredMatches();
+    // Don't perform any scoring (and don't return any matches) if the
+    // candidate pool is large. (See comments in header.)
+    const size_t kItemsToScoreLimit = 500;
+    if (history_id_set.size() <= kItemsToScoreLimit) {
+      // Pass over all of the candidates filtering out any without a proper
+      // substring match, inserting those which pass in order by score.
+      scored_items = std::for_each(history_id_set.begin(), history_id_set.end(),
+          AddHistoryMatch(*this, lower_terms)).ScoredMatches();
+    }
   }
 
   // Remove any stale TermCharWordSet's.
diff --git a/chrome/browser/history/in_memory_url_index.h b/chrome/browser/history/in_memory_url_index.h
index b7f832f..eb964e3 100644
--- a/chrome/browser/history/in_memory_url_index.h
+++ b/chrome/browser/history/in_memory_url_index.h
@@ -126,10 +126,16 @@ class InMemoryURLIndex {
 
   // Given a vector containing one or more words as string16s, scans the
   // history index and return a vector with all scored, matching history items.
-  // Each term must occur somewhere in the history item for the item to
-  // qualify; however, the terms do not necessarily have to be adjacent.
-  // Results are sorted with higher scoring items first. Each term from |terms|
-  // may contain punctuation but should not contain spaces.
+  // Each term must occur somewhere in the history item's URL or page title for
+  // the item to qualify; however, the terms do not necessarily have to be
+  // adjacent. Results are sorted with higher scoring items first. Each term
+  // from |terms| may contain punctuation but should not contain spaces.
+  // A search request which results in more than |kItemsToScoreLimit| total
+  // candidate items returns no matches (though the results set will be
+  // retained and used for subsequent calls to this function) as the scoring
+  // of such a large number of candidates may cause perceptible typing response
+  // delays in the omnibox. This is likely to occur for short omnibox terms
+  // such as 'h' and 'w' which will be found in nearly all history candidates.
   ScoredHistoryMatches HistoryItemsForTerms(const String16Vector& terms);
 
   // Updates or adds an history item to the index if it meets the minimum
diff --git a/chrome/browser/history/in_memory_url_index_unittest.cc b/chrome/browser/history/in_memory_url_index_unittest.cc
index c29abf7..700ef21 100644
--- a/chrome/browser/history/in_memory_url_index_unittest.cc
+++ b/chrome/browser/history/in_memory_url_index_unittest.cc
@@ -15,6 +15,7 @@
 #include "base/file_util.h"
 #include "base/path_service.h"
 #include "base/scoped_ptr.h"
+#include "base/string_util.h"
 #include "base/time.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/history/in_memory_url_index.h"
@@ -140,6 +141,24 @@ class LimitedInMemoryURLIndexTest : public InMemoryURLIndexTest {
   }
 };
 
+class ExpandedInMemoryURLIndexTest : public InMemoryURLIndexTest {
+ protected:
+  virtual void SetUp() {
+    InMemoryURLIndexTest::SetUp();
+    // Add 600 more history items.
+    // NOTE: Keep the string length constant at least the length of the format
+    // string plus 5 to account for a 3 digit number and terminator.
+    char url_format[] = "http://www.google.com/%d";
+    const size_t kMaxLen = arraysize(url_format) + 5;
+    char url_string[kMaxLen + 1];
+    for (int i = 0; i < 600; ++i) {
+      base::snprintf(url_string, kMaxLen, url_format, i);
+      URLRow row(MakeURLRow(url_string, "Google Search", 20, 0, 20));
+      AddURL(row);
+    }
+  }
+};
+
 TEST_F(InMemoryURLIndexTest, Construction) {
   url_index_.reset(new InMemoryURLIndex(FilePath(FILE_PATH_LITERAL("/dummy"))));
   EXPECT_TRUE(url_index_.get());
@@ -183,7 +202,7 @@ TEST_F(InMemoryURLIndexTest, Retrieval) {
   terms.clear();
   terms.push_back(ASCIIToUTF16("drudge"));
   matches = url_index_->HistoryItemsForTerms(terms);
-  ASSERT_EQ(2U, url_index_->HistoryItemsForTerms(terms).size());
+  ASSERT_EQ(2U, matches.size());
   // The results should be in descending score order.
   EXPECT_GT(matches[0].raw_score, matches[1].raw_score);
 
@@ -217,6 +236,23 @@ TEST_F(InMemoryURLIndexTest, Retrieval) {
             matches[0].url_info.title());
 }
 
+TEST_F(ExpandedInMemoryURLIndexTest, ShortCircuit) {
+  url_index_.reset(new InMemoryURLIndex(FilePath(FILE_PATH_LITERAL("/dummy"))));
+  url_index_->Init(this, "en,ja,hi,zh");
+  InMemoryURLIndex::String16Vector terms;
+
+  // A search for 'w' should short-circuit and not return any matches.
+  terms.push_back(ASCIIToUTF16("w"));
+  ScoredHistoryMatches matches = url_index_->HistoryItemsForTerms(terms);
+  EXPECT_TRUE(matches.empty());
+
+  // A search for 'working' should not short-circuit.
+  terms.clear();
+  terms.push_back(ASCIIToUTF16("working"));
+  matches = url_index_->HistoryItemsForTerms(terms);
+  EXPECT_EQ(1U, matches.size());
+}
+
 TEST_F(InMemoryURLIndexTest, TitleSearch) {
   url_index_.reset(new InMemoryURLIndex());
   url_index_->Init(this, "en,ja,hi,zh");