blob: 4495f7713a9dd73043692bc595e8cd535acd6cfd [file] [log] [blame]
// Copyright (c) 2012 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/predictors/autocomplete_action_predictor.h"
#include <stddef.h>
#include <string>
#include <vector>
#include "base/auto_reset.h"
#include "base/command_line.h"
#include "base/guid.h"
#include "base/macros.h"
#include "base/memory/ref_counted.h"
#include "base/run_loop.h"
#include "base/stl_util.h"
#include "base/strings/string_util.h"
#include "base/strings/utf_string_conversions.h"
#include "base/time/time.h"
#include "chrome/browser/history/history_service_factory.h"
#include "chrome/browser/prerender/prerender_field_trial.h"
#include "chrome/browser/prerender/prerender_manager.h"
#include "chrome/browser/prerender/prerender_test_utils.h"
#include "chrome/common/chrome_switches.h"
#include "chrome/test/base/testing_profile.h"
#include "components/history/core/browser/history_service.h"
#include "components/history/core/browser/in_memory_database.h"
#include "components/history/core/browser/url_database.h"
#include "components/omnibox/browser/autocomplete_match.h"
#include "components/omnibox/browser/autocomplete_result.h"
#include "content/public/test/test_browser_thread_bundle.h"
#include "content/public/test/test_utils.h"
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/gtest/include/gtest/gtest.h"
using base::ASCIIToUTF16;
using predictors::AutocompleteActionPredictor;
namespace {
struct TestUrlInfo {
GURL url;
base::string16 title;
int days_from_now;
base::string16 user_text;
int number_of_hits;
int number_of_misses;
AutocompleteActionPredictor::Action expected_action;
} test_url_db[] = {
{ GURL("http://www.testsite.com/a.html"),
ASCIIToUTF16("Test - site - just a test"), 1,
ASCIIToUTF16("j"), 5, 0,
AutocompleteActionPredictor::ACTION_PRERENDER },
{ GURL("http://www.testsite.com/b.html"),
ASCIIToUTF16("Test - site - just a test"), 1,
ASCIIToUTF16("ju"), 3, 0,
AutocompleteActionPredictor::ACTION_PRERENDER },
{ GURL("http://www.testsite.com/c.html"),
ASCIIToUTF16("Test - site - just a test"), 5,
ASCIIToUTF16("just"), 3, 1,
AutocompleteActionPredictor::ACTION_PRECONNECT },
{ GURL("http://www.testsite.com/d.html"),
ASCIIToUTF16("Test - site - just a test"), 5,
ASCIIToUTF16("just"), 3, 0,
AutocompleteActionPredictor::ACTION_PRERENDER },
{ GURL("http://www.testsite.com/e.html"),
ASCIIToUTF16("Test - site - just a test"), 8,
ASCIIToUTF16("just"), 3, 1,
AutocompleteActionPredictor::ACTION_PRECONNECT },
{ GURL("http://www.testsite.com/f.html"),
ASCIIToUTF16("Test - site - just a test"), 8,
ASCIIToUTF16("just"), 3, 0,
AutocompleteActionPredictor::ACTION_PRERENDER },
{ GURL("http://www.testsite.com/g.html"),
ASCIIToUTF16("Test - site - just a test"), 12,
base::string16(), 5, 0,
AutocompleteActionPredictor::ACTION_NONE },
{ GURL("http://www.testsite.com/h.html"),
ASCIIToUTF16("Test - site - just a test"), 21,
ASCIIToUTF16("just a test"), 2, 0,
AutocompleteActionPredictor::ACTION_NONE },
{ GURL("http://www.testsite.com/i.html"),
ASCIIToUTF16("Test - site - just a test"), 28,
ASCIIToUTF16("just a test"), 2, 0,
AutocompleteActionPredictor::ACTION_NONE }
};
// List of urls sorted by the confidence score in ascending order.
TestUrlInfo test_url_confidence_db[] = {
{GURL("http://www.testsite.com/g.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 0, 2, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/f.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 1, 2, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/e.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 2, 2, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/d.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 3, 3, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/c.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 3, 2, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/b.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 3, 0, AutocompleteActionPredictor::ACTION_NONE},
{GURL("http://www.testsite.com/a.html"), ASCIIToUTF16("Test"), 1,
ASCIIToUTF16("test"), 5, 0, AutocompleteActionPredictor::ACTION_NONE},
};
GURL GenerateTestURL(size_t size) {
std::string prefix = "http://b/";
// Cannot generate an URL shorter than |prefix|.
DCHECK_GE(size, prefix.size());
size_t suffix_len = size - prefix.size();
std::string suffix(suffix_len, 'c');
GURL url(prefix + suffix);
DCHECK_EQ(url.spec().size(), size);
return url;
}
} // end namespace
namespace predictors {
class AutocompleteActionPredictorTest : public testing::Test {
public:
AutocompleteActionPredictorTest()
: profile_(std::make_unique<TestingProfile>()), predictor_(nullptr) {
CHECK(profile_->CreateHistoryService(true, false));
predictor_ = std::make_unique<AutocompleteActionPredictor>(profile_.get());
predictor_->CreateLocalCachesFromDatabase();
profile_->BlockUntilHistoryProcessesPendingRequests();
content::RunAllTasksUntilIdle();
CHECK(predictor_->initialized_);
CHECK(db_cache()->empty());
CHECK(db_id_cache()->empty());
}
~AutocompleteActionPredictorTest() override {
// Wait for all pending tasks on the DB sequence.
content::RunAllTasksUntilIdle();
// Since we instantiated the predictor instead of going through a factory
// and dependencies, no one else is going to call Shutdown(), which is
// supposed to be called as part of being a KeyedService. The behavior of
// this method is not explicitly verified.
predictor_->Shutdown();
}
protected:
typedef AutocompleteActionPredictor::DBCacheKey DBCacheKey;
typedef AutocompleteActionPredictor::DBCacheValue DBCacheValue;
typedef AutocompleteActionPredictor::DBCacheMap DBCacheMap;
typedef AutocompleteActionPredictor::DBIdCacheMap DBIdCacheMap;
history::URLID AddRowToHistory(const TestUrlInfo& test_row) {
history::HistoryService* history = HistoryServiceFactory::GetForProfile(
profile_.get(), ServiceAccessType::EXPLICIT_ACCESS);
CHECK(history);
history::URLDatabase* url_db = history->InMemoryDatabase();
CHECK(url_db);
const base::Time visit_time =
base::Time::Now() - base::TimeDelta::FromDays(
test_row.days_from_now);
history::URLRow row(test_row.url);
row.set_title(test_row.title);
row.set_last_visit(visit_time);
return url_db->AddURL(row);
}
AutocompleteActionPredictorTable::Row CreateRowFromTestUrlInfo(
const TestUrlInfo& test_row) const {
AutocompleteActionPredictorTable::Row row;
row.id = base::GenerateGUID();
row.user_text = test_row.user_text;
row.url = test_row.url;
row.number_of_hits = test_row.number_of_hits;
row.number_of_misses = test_row.number_of_misses;
return row;
}
void AddAllRows() {
for (size_t i = 0; i < base::size(test_url_db); ++i)
AddRow(test_url_db[i]);
}
std::string AddRow(const TestUrlInfo& test_row) {
AutocompleteActionPredictorTable::Row row =
CreateRowFromTestUrlInfo(test_row);
predictor_->AddAndUpdateRows(
AutocompleteActionPredictorTable::Rows(1, row),
AutocompleteActionPredictorTable::Rows());
return row.id;
}
void UpdateRow(const AutocompleteActionPredictorTable::Row& row) {
AutocompleteActionPredictor::DBCacheKey key = { row.user_text, row.url };
ASSERT_TRUE(db_cache()->find(key) != db_cache()->end());
predictor_->AddAndUpdateRows(
AutocompleteActionPredictorTable::Rows(),
AutocompleteActionPredictorTable::Rows(1, row));
}
void OnURLsDeletedTest(bool expired) {
ASSERT_NO_FATAL_FAILURE(AddAllRows());
EXPECT_EQ(base::size(test_url_db), db_cache()->size());
EXPECT_EQ(base::size(test_url_db), db_id_cache()->size());
std::vector<size_t> expected;
history::URLRows rows;
for (size_t i = 0; i < base::size(test_url_db); ++i) {
bool expect_deleted = false;
if (i < 2) {
rows.push_back(history::URLRow(test_url_db[i].url));
expect_deleted = true;
}
if (!expired &&
test_url_db[i].days_from_now > maximum_days_to_keep_entry()) {
expect_deleted = true;
}
if (i != 3 && i != 4)
ASSERT_TRUE(AddRowToHistory(test_url_db[i]));
else if (!expired)
expect_deleted = true;
if (!expect_deleted)
expected.push_back(i);
}
history::HistoryService* history_service =
HistoryServiceFactory::GetForProfile(
profile_.get(), ServiceAccessType::EXPLICIT_ACCESS);
ASSERT_TRUE(history_service);
predictor_->OnURLsDeleted(
history_service,
history::DeletionInfo(history::DeletionTimeRange::Invalid(), expired,
rows, std::set<GURL>(), base::nullopt));
EXPECT_EQ(expected.size(), db_cache()->size());
EXPECT_EQ(expected.size(), db_id_cache()->size());
for (size_t i = 0; i < base::size(test_url_db); ++i) {
DBCacheKey key = {test_url_db[i].user_text, test_url_db[i].url};
bool deleted = !base::ContainsValue(expected, i);
EXPECT_EQ(deleted, db_cache()->find(key) == db_cache()->end());
EXPECT_EQ(deleted, db_id_cache()->find(key) == db_id_cache()->end());
}
}
void DeleteAllRows() {
predictor_->DeleteAllRows();
}
void DeleteRowsFromCaches(
const history::URLRows& rows,
std::vector<AutocompleteActionPredictorTable::Row::Id>* id_list) {
predictor_->DeleteRowsFromCaches(rows, id_list);
}
void DeleteOldIdsFromCaches(
std::vector<AutocompleteActionPredictorTable::Row::Id>* id_list) {
history::HistoryService* history_service =
HistoryServiceFactory::GetForProfile(
profile_.get(), ServiceAccessType::EXPLICIT_ACCESS);
ASSERT_TRUE(history_service);
history::URLDatabase* url_db = history_service->InMemoryDatabase();
ASSERT_TRUE(url_db);
predictor_->DeleteOldIdsFromCaches(url_db, id_list);
}
void DeleteLowestConfidenceRowsFromCaches(
size_t count,
std::vector<AutocompleteActionPredictorTable::Row::Id>* id_list) {
predictor_->DeleteLowestConfidenceRowsFromCaches(count, id_list);
}
AutocompleteActionPredictor* predictor() { return predictor_.get(); }
DBCacheMap* db_cache() { return &predictor_->db_cache_; }
DBIdCacheMap* db_id_cache() { return &predictor_->db_id_cache_; }
std::vector<AutocompleteActionPredictor::TransitionalMatch>*
transitional_matches() {
return &predictor_->transitional_matches_;
}
static int maximum_days_to_keep_entry() {
return AutocompleteActionPredictor::kMaximumDaysToKeepEntry;
}
static size_t minimum_user_text_length() {
return AutocompleteActionPredictor::kMinimumUserTextLength;
}
static size_t maximum_string_length() {
return AutocompleteActionPredictor::kMaximumStringLength;
}
private:
content::TestBrowserThreadBundle test_browser_thread_bundle_;
std::unique_ptr<TestingProfile> profile_;
std::unique_ptr<AutocompleteActionPredictor> predictor_;
};
TEST_F(AutocompleteActionPredictorTest, AddRow) {
// Add a test entry to the predictor.
std::string guid = AddRow(test_url_db[0]);
// Get the data back out of the cache.
const DBCacheKey key = { test_url_db[0].user_text, test_url_db[0].url };
DBCacheMap::const_iterator it = db_cache()->find(key);
EXPECT_TRUE(it != db_cache()->end());
const DBCacheValue value = { test_url_db[0].number_of_hits,
test_url_db[0].number_of_misses };
EXPECT_EQ(value.number_of_hits, it->second.number_of_hits);
EXPECT_EQ(value.number_of_misses, it->second.number_of_misses);
DBIdCacheMap::const_iterator id_it = db_id_cache()->find(key);
EXPECT_TRUE(id_it != db_id_cache()->end());
EXPECT_EQ(guid, id_it->second);
}
TEST_F(AutocompleteActionPredictorTest, UpdateRow) {
ASSERT_NO_FATAL_FAILURE(AddAllRows());
EXPECT_EQ(base::size(test_url_db), db_cache()->size());
EXPECT_EQ(base::size(test_url_db), db_id_cache()->size());
// Get the data back out of the cache.
const DBCacheKey key = { test_url_db[0].user_text, test_url_db[0].url };
DBCacheMap::const_iterator it = db_cache()->find(key);
EXPECT_TRUE(it != db_cache()->end());
DBIdCacheMap::const_iterator id_it = db_id_cache()->find(key);
EXPECT_TRUE(id_it != db_id_cache()->end());
AutocompleteActionPredictorTable::Row update_row;
update_row.id = id_it->second;
update_row.user_text = key.user_text;
update_row.url = key.url;
update_row.number_of_hits = it->second.number_of_hits + 1;
update_row.number_of_misses = it->second.number_of_misses + 2;
UpdateRow(update_row);
// Get the updated version.
DBCacheMap::const_iterator update_it = db_cache()->find(key);
EXPECT_TRUE(update_it != db_cache()->end());
EXPECT_EQ(update_row.number_of_hits, update_it->second.number_of_hits);
EXPECT_EQ(update_row.number_of_misses, update_it->second.number_of_misses);
DBIdCacheMap::const_iterator update_id_it = db_id_cache()->find(key);
EXPECT_TRUE(update_id_it != db_id_cache()->end());
EXPECT_EQ(id_it->second, update_id_it->second);
}
TEST_F(AutocompleteActionPredictorTest, DeleteAllRows) {
ASSERT_NO_FATAL_FAILURE(AddAllRows());
EXPECT_EQ(base::size(test_url_db), db_cache()->size());
EXPECT_EQ(base::size(test_url_db), db_id_cache()->size());
DeleteAllRows();
EXPECT_TRUE(db_cache()->empty());
EXPECT_TRUE(db_id_cache()->empty());
}
TEST_F(AutocompleteActionPredictorTest, DeleteRowsFromCaches) {
std::vector<AutocompleteActionPredictorTable::Row::Id> all_ids;
history::URLRows rows;
for (size_t i = 0; i < base::size(test_url_db); ++i) {
std::string row_id = AddRow(test_url_db[i]);
all_ids.push_back(row_id);
if (i < 2)
rows.push_back(history::URLRow(test_url_db[i].url));
}
EXPECT_EQ(base::size(test_url_db), all_ids.size());
EXPECT_EQ(base::size(test_url_db), db_cache()->size());
EXPECT_EQ(base::size(test_url_db), db_id_cache()->size());
std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
DeleteRowsFromCaches(rows, &id_list);
EXPECT_EQ(base::size(test_url_db) - 2, db_cache()->size());
EXPECT_EQ(base::size(test_url_db) - 2, db_id_cache()->size());
for (size_t i = 0; i < base::size(test_url_db); ++i) {
DBCacheKey key = { test_url_db[i].user_text, test_url_db[i].url };
bool deleted = (i < 2);
EXPECT_EQ(deleted, db_cache()->find(key) == db_cache()->end());
EXPECT_EQ(deleted, db_id_cache()->find(key) == db_id_cache()->end());
EXPECT_EQ(deleted, base::ContainsValue(id_list, all_ids[i]));
}
}
TEST_F(AutocompleteActionPredictorTest, DeleteOldIdsFromCaches) {
std::vector<AutocompleteActionPredictorTable::Row::Id> expected;
std::vector<AutocompleteActionPredictorTable::Row::Id> all_ids;
for (size_t i = 0; i < base::size(test_url_db); ++i) {
std::string row_id = AddRow(test_url_db[i]);
all_ids.push_back(row_id);
bool exclude_url =
base::StartsWith(test_url_db[i].url.path(), "/d",
base::CompareCase::SENSITIVE) ||
(test_url_db[i].days_from_now > maximum_days_to_keep_entry());
if (exclude_url)
expected.push_back(row_id);
else
ASSERT_TRUE(AddRowToHistory(test_url_db[i]));
}
std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
DeleteOldIdsFromCaches(&id_list);
EXPECT_EQ(expected.size(), id_list.size());
EXPECT_EQ(all_ids.size() - expected.size(), db_cache()->size());
EXPECT_EQ(all_ids.size() - expected.size(), db_id_cache()->size());
for (auto it = all_ids.begin(); it != all_ids.end(); ++it) {
bool in_expected = base::ContainsValue(expected, *it);
bool in_list = base::ContainsValue(id_list, *it);
EXPECT_EQ(in_expected, in_list);
}
}
TEST_F(AutocompleteActionPredictorTest,
DeleteLowestConfidenceRowsFromCaches_OneByOne) {
std::vector<AutocompleteActionPredictorTable::Row::Id> test_url_ids;
for (const auto& info : test_url_confidence_db)
test_url_ids.push_back(AddRow(info));
std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
std::vector<AutocompleteActionPredictorTable::Row::Id> expected;
for (size_t i = 0; i < base::size(test_url_confidence_db); ++i) {
DeleteLowestConfidenceRowsFromCaches(1, &id_list);
expected.push_back(test_url_ids[i]);
EXPECT_THAT(id_list, ::testing::UnorderedElementsAreArray(expected));
DBCacheKey deleted_key = {test_url_confidence_db[i].user_text,
test_url_confidence_db[i].url};
EXPECT_FALSE(base::ContainsKey(*db_cache(), deleted_key));
EXPECT_FALSE(base::ContainsKey(*db_id_cache(), deleted_key));
}
}
TEST_F(AutocompleteActionPredictorTest,
DeleteLowestConfidenceRowsFromCaches_Bulk) {
std::vector<AutocompleteActionPredictorTable::Row::Id> test_url_ids;
for (const auto& info : test_url_confidence_db)
test_url_ids.push_back(AddRow(info));
std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
std::vector<AutocompleteActionPredictorTable::Row::Id> expected;
const size_t count_to_remove = 4;
CHECK_LT(count_to_remove, base::size(test_url_confidence_db));
for (size_t i = 0; i < count_to_remove; ++i)
expected.push_back(test_url_ids[i]);
DeleteLowestConfidenceRowsFromCaches(count_to_remove, &id_list);
ASSERT_THAT(id_list, ::testing::UnorderedElementsAreArray(expected));
for (size_t i = 0; i < count_to_remove; ++i) {
DBCacheKey deleted_key = {test_url_confidence_db[i].user_text,
test_url_confidence_db[i].url};
EXPECT_FALSE(base::ContainsKey(*db_cache(), deleted_key));
EXPECT_FALSE(base::ContainsKey(*db_id_cache(), deleted_key));
}
}
TEST_F(AutocompleteActionPredictorTest, OnURLsDeletedExpired) {
OnURLsDeletedTest(true);
}
TEST_F(AutocompleteActionPredictorTest, OnURLsDeletedNonExpired) {
OnURLsDeletedTest(false);
}
TEST_F(AutocompleteActionPredictorTest, RecommendActionURL) {
ASSERT_NO_FATAL_FAILURE(AddAllRows());
AutocompleteMatch match;
match.type = AutocompleteMatchType::HISTORY_URL;
prerender::test_utils::RestorePrerenderMode restore_prerender_mode;
prerender::PrerenderManager::SetMode(
prerender::PrerenderManager::PRERENDER_MODE_NOSTATE_PREFETCH);
for (size_t i = 0; i < base::size(test_url_db); ++i) {
match.destination_url = GURL(test_url_db[i].url);
EXPECT_EQ(test_url_db[i].expected_action,
predictor()->RecommendAction(test_url_db[i].user_text, match))
<< "Unexpected action for " << match.destination_url;
}
}
TEST_F(AutocompleteActionPredictorTest, RecommendActionSearch) {
ASSERT_NO_FATAL_FAILURE(AddAllRows());
AutocompleteMatch match;
match.type = AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED;
prerender::test_utils::RestorePrerenderMode restore_prerender_mode;
prerender::PrerenderManager::SetMode(
prerender::PrerenderManager::PRERENDER_MODE_NOSTATE_PREFETCH);
for (size_t i = 0; i < base::size(test_url_db); ++i) {
match.destination_url = GURL(test_url_db[i].url);
AutocompleteActionPredictor::Action expected_action =
(test_url_db[i].expected_action ==
AutocompleteActionPredictor::ACTION_PRERENDER) ?
AutocompleteActionPredictor::ACTION_PRECONNECT :
test_url_db[i].expected_action;
EXPECT_EQ(expected_action,
predictor()->RecommendAction(test_url_db[i].user_text, match))
<< "Unexpected action for " << match.destination_url;
}
}
TEST_F(AutocompleteActionPredictorTest,
RegisterTransitionalMatchesUserTextSizeLimits) {
auto test = [this](const base::string16& user_text,
bool should_be_registered) {
predictor()->RegisterTransitionalMatches(user_text, AutocompleteResult());
bool registered = base::ContainsValue(*transitional_matches(), user_text);
EXPECT_EQ(registered, should_be_registered);
};
base::string16 short_text =
ASCIIToUTF16(std::string(minimum_user_text_length(), 'g'));
test(short_text, true);
base::string16 too_short_text =
ASCIIToUTF16(std::string(minimum_user_text_length() - 1, 'g'));
test(too_short_text, false);
base::string16 long_text =
ASCIIToUTF16(std::string(maximum_string_length(), 'g'));
test(long_text, true);
base::string16 too_long_text =
ASCIIToUTF16(std::string(maximum_string_length() + 1, 'g'));
test(too_long_text, false);
}
TEST_F(AutocompleteActionPredictorTest,
RegisterTransitionalMatchesURLSizeLimits) {
GURL urls[] = {GenerateTestURL(10), GenerateTestURL(maximum_string_length()),
GenerateTestURL(maximum_string_length() + 1),
GenerateTestURL(maximum_string_length() * 10)};
ACMatches matches;
for (const auto& url : urls) {
AutocompleteMatch match;
match.destination_url = url;
matches.push_back(match);
}
AutocompleteResult result;
result.AppendMatches(AutocompleteInput(), matches);
base::string16 user_text = ASCIIToUTF16("google");
predictor()->RegisterTransitionalMatches(user_text, result);
auto it = std::find(transitional_matches()->begin(),
transitional_matches()->end(), user_text);
ASSERT_NE(it, transitional_matches()->end());
EXPECT_THAT(it->urls, ::testing::ElementsAre(urls[0], urls[1]));
}
} // namespace predictors