[AiS] Better prefetch cache.

Step 1 - factor out current cache and increase its size.

BUG=401758
R=pkasting@chromium.org

Review URL: https://codereview.chromium.org/455563002

Cr-Commit-Position: refs/heads/master@{#291307}
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@291307 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 223 insertions, 34 deletions

diff --git a/chrome/browser/autocomplete/answers_cache.cc b/chrome/browser/autocomplete/answers_cache.cc
new file mode 100644
index 0000000..35a07da
--- /dev/null
+++ b/chrome/browser/autocomplete/answers_cache.cc
@@ -0,0 +1,51 @@
+// Copyright 2014 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/answers_cache.h"
+
+#include "base/strings/string_util.h"
+
+AnswersQueryData::AnswersQueryData() {
+}
+AnswersQueryData::AnswersQueryData(const base::string16& text,
+                                   const base::string16& type)
+    : full_query_text(text), query_type(type) {
+}
+
+AnswersCache::AnswersCache(size_t max_entries) : max_entries_(max_entries) {
+}
+
+AnswersCache::~AnswersCache() {
+}
+
+AnswersQueryData AnswersCache::GetTopAnswerEntry(const base::string16& query) {
+  base::string16 collapsed_query = base::CollapseWhitespace(query, false);
+  for (Cache::iterator it = cache_.begin(); it != cache_.end(); ++it) {
+    // If the query text starts with trimmed input, this is valid prefetch data.
+    if (StartsWith(it->full_query_text, collapsed_query, false)) {
+      // Move the touched item to the front of the list.
+      cache_.splice(cache_.begin(), cache_, it);
+      return cache_.front();
+    }
+  }
+  return AnswersQueryData();
+}
+
+void AnswersCache::UpdateRecentAnswers(const base::string16& full_query_text,
+                                       const base::string16& query_type) {
+  // If this entry is already part of the cache, just update recency.
+  for (Cache::iterator it = cache_.begin(); it != cache_.end(); ++it) {
+    if (full_query_text == it->full_query_text &&
+        query_type == it->query_type) {
+      cache_.splice(cache_.begin(), cache_, it);
+      return;
+    }
+  }
+
+  // Evict if cache size is exceeded.
+  if (cache_.size() >= max_entries_)
+    cache_.pop_back();
+
+  cache_.push_front(AnswersQueryData(full_query_text, query_type));
+}
diff --git a/chrome/browser/autocomplete/answers_cache.h b/chrome/browser/autocomplete/answers_cache.h
new file mode 100644
index 0000000..3182b2a
--- /dev/null
+++ b/chrome/browser/autocomplete/answers_cache.h
@@ -0,0 +1,46 @@
+// Copyright 2014 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_ANSWERS_CACHE_H_
+#define CHROME_BROWSER_AUTOCOMPLETE_ANSWERS_CACHE_H_
+
+#include <list>
+
+#include "base/basictypes.h"
+#include "base/strings/string16.h"
+
+struct AnswersQueryData {
+  AnswersQueryData();
+  AnswersQueryData(const base::string16& full_query_text,
+                   const base::string16& query_type);
+  base::string16 full_query_text;
+  base::string16 query_type;
+};
+
+// Cache for the most-recently seen answer for Answers in Suggest.
+class AnswersCache {
+ public:
+  explicit AnswersCache(size_t max_entries);
+  ~AnswersCache();
+
+  // Gets the top answer query completion for the query term. The query data
+  // will contain empty query text and type if no matching data was found.
+  AnswersQueryData GetTopAnswerEntry(const base::string16& query);
+
+  // Registers a query that received an answer suggestion.
+  void UpdateRecentAnswers(const base::string16& full_query_text,
+                           const base::string16& query_type);
+
+  // Signals if cache is empty.
+  bool empty() const { return cache_.empty(); }
+
+ private:
+  size_t max_entries_;
+  typedef std::list<AnswersQueryData> Cache;
+  Cache cache_;
+
+  DISALLOW_COPY_AND_ASSIGN(AnswersCache);
+};
+
+#endif  // CHROME_BROWSER_AUTOCOMPLETE_ANSWERS_CACHE_H_
diff --git a/chrome/browser/autocomplete/answers_cache_unittest.cc b/chrome/browser/autocomplete/answers_cache_unittest.cc
new file mode 100644
index 0000000..0ee7ef5
--- /dev/null
+++ b/chrome/browser/autocomplete/answers_cache_unittest.cc
@@ -0,0 +1,113 @@
+// Copyright 2014 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/answers_cache.h"
+
+#include "base/strings/utf_string_conversions.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+TEST(AnswersCacheTest, CacheStartsEmpty) {
+  AnswersCache cache(1);
+  EXPECT_TRUE(cache.empty());
+}
+
+TEST(AnswersCacheTest, UpdatePopulatesCache) {
+  AnswersCache cache(1);
+  cache.UpdateRecentAnswers(base::ASCIIToUTF16("weather los angeles"),
+                            base::ASCIIToUTF16("2334"));
+  EXPECT_FALSE(cache.empty());
+}
+
+TEST(AnswersCacheTest, GetWillRetrieveMatchingInfo) {
+  AnswersCache cache(1);
+
+  base::string16 full_query_text = base::ASCIIToUTF16("weather los angeles");
+  base::string16 query_type = base::ASCIIToUTF16("2334");
+  cache.UpdateRecentAnswers(full_query_text, query_type);
+
+  // Partial prefixes retrieve info.
+  AnswersQueryData data = cache.GetTopAnswerEntry(full_query_text.substr(0, 8));
+  EXPECT_EQ(full_query_text, data.full_query_text);
+  EXPECT_EQ(query_type, data.query_type);
+
+  // Mismatched prefix retrieves empty data.
+  data = cache.GetTopAnswerEntry(full_query_text.substr(1, 8));
+  EXPECT_TRUE(data.full_query_text.empty() && data.query_type.empty());
+
+  // Full match retrieves info.
+  data = cache.GetTopAnswerEntry(full_query_text);
+  EXPECT_EQ(full_query_text, data.full_query_text);
+  EXPECT_EQ(query_type, data.query_type);
+}
+
+TEST(AnswersCacheTest, MatchMostRecent) {
+  AnswersCache cache(2);
+
+  base::string16 query_weather_la = base::ASCIIToUTF16("weather los angeles");
+  base::string16 query_weather_lv = base::ASCIIToUTF16("weather las vegas");
+  base::string16 query_type = base::ASCIIToUTF16("2334");
+
+  cache.UpdateRecentAnswers(query_weather_lv, query_type);
+  cache.UpdateRecentAnswers(query_weather_la, query_type);
+
+  // "weather los angeles" is most recent match to "weather l".
+  AnswersQueryData data =
+      cache.GetTopAnswerEntry(base::ASCIIToUTF16("weather l"));
+  EXPECT_EQ(query_weather_la, data.full_query_text);
+
+  // Update recency for "weather las vegas".
+  cache.GetTopAnswerEntry(query_weather_lv);
+
+  // "weather las vegas" should now be the most recent match to "weather l".
+  data = cache.GetTopAnswerEntry(base::ASCIIToUTF16("weather l"));
+  EXPECT_EQ(query_weather_lv, data.full_query_text);
+}
+
+TEST(AnswersCacheTest, LeastRecentItemIsEvicted) {
+  AnswersCache cache(2);
+
+  base::string16 query_weather_la = base::ASCIIToUTF16("weather los angeles");
+  base::string16 query_weather_lv = base::ASCIIToUTF16("weather las vegas");
+  base::string16 query_weather_lb = base::ASCIIToUTF16("weather long beach");
+  base::string16 query_type = base::ASCIIToUTF16("2334");
+
+  cache.UpdateRecentAnswers(query_weather_lb, query_type);
+  cache.UpdateRecentAnswers(query_weather_lv, query_type);
+  EXPECT_FALSE(
+      cache.GetTopAnswerEntry(query_weather_lb).full_query_text.empty());
+  EXPECT_FALSE(
+      cache.GetTopAnswerEntry(query_weather_lv).full_query_text.empty());
+  EXPECT_TRUE(
+      cache.GetTopAnswerEntry(query_weather_la).full_query_text.empty());
+
+  cache.UpdateRecentAnswers(query_weather_la, query_type);
+  EXPECT_TRUE(
+      cache.GetTopAnswerEntry(query_weather_lb).full_query_text.empty());
+  EXPECT_FALSE(
+      cache.GetTopAnswerEntry(query_weather_lv).full_query_text.empty());
+  EXPECT_FALSE(
+      cache.GetTopAnswerEntry(query_weather_la).full_query_text.empty());
+}
+
+TEST(AnswersCacheTest, DuplicateEntries) {
+  AnswersCache cache(2);
+
+  base::string16 query_weather_lv = base::ASCIIToUTF16("weather las vegas");
+  base::string16 query_weather_lb = base::ASCIIToUTF16("weather long beach");
+  base::string16 query_weather_l = base::ASCIIToUTF16("weather l");
+  base::string16 query_type = base::ASCIIToUTF16("2334");
+
+  cache.UpdateRecentAnswers(query_weather_lb, query_type);
+  cache.UpdateRecentAnswers(query_weather_lv, query_type);
+
+  // Test that duplicate entries update recency.
+  cache.UpdateRecentAnswers(query_weather_lb, query_type);
+  EXPECT_EQ(query_weather_lb,
+            cache.GetTopAnswerEntry(query_weather_l).full_query_text);
+
+  // Test duplicate do not evict other entries. LV should still be in cache.
+  cache.UpdateRecentAnswers(query_weather_lb, query_type);
+  EXPECT_FALSE(
+      cache.GetTopAnswerEntry(query_weather_lv).full_query_text.empty());
+}
diff --git a/chrome/browser/autocomplete/search_provider.cc b/chrome/browser/autocomplete/search_provider.cc
index c059c6e..4dca4d4 100644
--- a/chrome/browser/autocomplete/search_provider.cc
+++ b/chrome/browser/autocomplete/search_provider.cc
@@ -136,7 +136,8 @@ SearchProvider::SearchProvider(AutocompleteProviderListener* listener,
                          AutocompleteProvider::TYPE_SEARCH),
       listener_(listener),
       suggest_results_pending_(0),
-      providers_(template_url_service) {
+      providers_(template_url_service),
+      answers_cache_(1) {
 }
 
 // static
@@ -669,9 +670,9 @@ net::URLFetcher* SearchProvider::CreateSuggestFetcher(
     search_term_args.session_token = GetSessionToken();
     if (!prefetch_data_.full_query_text.empty()) {
       search_term_args.prefetch_query =
-          base::UTF16ToUTF8(last_answer_seen_.full_query_text);
+          base::UTF16ToUTF8(prefetch_data_.full_query_text);
       search_term_args.prefetch_query_type =
-          base::UTF16ToUTF8(last_answer_seen_.query_type);
+          base::UTF16ToUTF8(prefetch_data_.query_type);
     }
   }
   GURL suggest_url(template_url->suggestions_url_ref().ReplaceSearchTerms(
@@ -1256,14 +1257,9 @@ void SearchProvider::RegisterDisplayedAnswers(
     return;
 
   // Valid answer encountered, cache it for further queries.
-  last_answer_seen_.full_query_text = match->fill_into_edit;
-  last_answer_seen_.query_type = match->answer_type;
+  answers_cache_.UpdateRecentAnswers(match->fill_into_edit, match->answer_type);
 }
 
 void SearchProvider::DoAnswersQuery(const AutocompleteInput& input) {
-  // If the query text starts with trimmed input, this is valid prefetch data.
-  prefetch_data_ = StartsWith(last_answer_seen_.full_query_text,
-                              base::CollapseWhitespace(input.text(), false),
-                              false) ?
-      last_answer_seen_ : AnswersQueryData();
+  prefetch_data_ = answers_cache_.GetTopAnswerEntry(input.text());
 }
diff --git a/chrome/browser/autocomplete/search_provider.h b/chrome/browser/autocomplete/search_provider.h
index 14a4836..8ee4bd8 100644
--- a/chrome/browser/autocomplete/search_provider.h
+++ b/chrome/browser/autocomplete/search_provider.h
@@ -16,6 +16,7 @@
 #include "base/memory/scoped_ptr.h"
 #include "base/time/time.h"
 #include "base/timer/timer.h"
+#include "chrome/browser/autocomplete/answers_cache.h"
 #include "chrome/browser/autocomplete/base_search_provider.h"
 #include "components/metrics/proto/omnibox_input_type.pb.h"
 #include "components/search_engines/template_url.h"
@@ -136,11 +137,6 @@ class SearchProvider : public BaseSearchProvider,
 
   class CompareScoredResults;
 
-  struct AnswersQueryData {
-    base::string16 full_query_text;
-    base::string16 query_type;
-  };
-
   typedef std::vector<history::KeywordSearchTermVisit> HistoryResults;
 
   // Removes non-inlineable results until either the top result can inline
@@ -362,8 +358,8 @@ class SearchProvider : public BaseSearchProvider,
   base::TimeTicks token_expiration_time_;
 
   // Answers prefetch management.
-  AnswersQueryData prefetch_data_;     // Data to use for query prefetching.
-  AnswersQueryData last_answer_seen_;  // Last answer seen.
+  AnswersCache answers_cache_;  // Cache for last answers seen.
+  AnswersQueryData prefetch_data_;  // Data to use for query prefetching.
 
   DISALLOW_COPY_AND_ASSIGN(SearchProvider);
 };
diff --git a/chrome/browser/autocomplete/search_provider_unittest.cc b/chrome/browser/autocomplete/search_provider_unittest.cc
index 7f096da..3afcbac 100644
--- a/chrome/browser/autocomplete/search_provider_unittest.cc
+++ b/chrome/browser/autocomplete/search_provider_unittest.cc
@@ -3231,9 +3231,6 @@ TEST_F(SearchProviderTest, SessionToken) {
 }
 
 TEST_F(SearchProviderTest, AnswersCache) {
-  // Initial condition: empty cache.
-  ASSERT_TRUE(provider_->last_answer_seen_.full_query_text.empty());
-
   AutocompleteResult result;
   ACMatches matches;
   AutocompleteMatch match1;
@@ -3249,10 +3246,7 @@ TEST_F(SearchProviderTest, AnswersCache) {
   matches.push_back(non_answer_match1);
   result.AppendMatches(matches);
   provider_->RegisterDisplayedAnswers(result);
-  EXPECT_EQ(base::ASCIIToUTF16("weather los angeles"),
-            provider_->last_answer_seen_.full_query_text);
-  EXPECT_EQ(base::ASCIIToUTF16("2334"),
-            provider_->last_answer_seen_.query_type);
+  ASSERT_FALSE(provider_->answers_cache_.empty());
 
   // Test that DoAnswersQuery retrieves data from cache.
   AutocompleteInput input(base::ASCIIToUTF16("weather l"),
@@ -3264,14 +3258,4 @@ TEST_F(SearchProviderTest, AnswersCache) {
   EXPECT_EQ(base::ASCIIToUTF16("weather los angeles"),
             provider_->prefetch_data_.full_query_text);
   EXPECT_EQ(base::ASCIIToUTF16("2334"), provider_->prefetch_data_.query_type);
-
-  // Mismatching input will return empty prefetch data.
-  AutocompleteInput input2(base::ASCIIToUTF16("weather n"),
-                           base::string16::npos, base::string16(), GURL(),
-                           metrics::OmniboxEventProto::INVALID_SPEC, false,
-                           false, true, true,
-                           ChromeAutocompleteSchemeClassifier(&profile_));
-  provider_->DoAnswersQuery(input2);
-  EXPECT_TRUE(provider_->prefetch_data_.full_query_text.empty());
-  EXPECT_TRUE(provider_->prefetch_data_.query_type.empty());
 }
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index 3fa7498..26d0a5e 100644
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -122,6 +122,8 @@
       'browser/app_icon_win.h',
       'browser/app_mode/app_mode_utils.cc',
       'browser/app_mode/app_mode_utils.h',
+      'browser/autocomplete/answers_cache.h',
+      'browser/autocomplete/answers_cache.cc',
       'browser/autocomplete/autocomplete_classifier.cc',
       'browser/autocomplete/autocomplete_classifier.h',
       'browser/autocomplete/autocomplete_classifier_factory.cc',
diff --git a/chrome/chrome_tests_unit.gypi b/chrome/chrome_tests_unit.gypi
index 73c2368..cbdf562 100644
--- a/chrome/chrome_tests_unit.gypi
+++ b/chrome/chrome_tests_unit.gypi
@@ -574,6 +574,7 @@
         'browser/app_controller_mac_unittest.mm',
         'browser/apps/drive/drive_app_mapping_unittest.cc',
         'browser/apps/ephemeral_app_service_unittest.cc',
+        'browser/autocomplete/answers_cache_unittest.cc',
         'browser/autocomplete/autocomplete_provider_unittest.cc',
         'browser/autocomplete/bookmark_provider_unittest.cc',
         'browser/autocomplete/builtin_provider_unittest.cc',