1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/autocomplete/history_quick_provider.h" 6 7 #include <algorithm> 8 #include <functional> 9 #include <set> 10 #include <string> 11 #include <vector> 12 13 #include "base/memory/scoped_ptr.h" 14 #include "base/message_loop.h" 15 #include "base/utf_string_conversions.h" 16 #include "chrome/browser/autocomplete/autocomplete.h" 17 #include "chrome/browser/autocomplete/autocomplete_match.h" 18 #include "chrome/browser/history/history.h" 19 #include "chrome/browser/history/in_memory_url_index.h" 20 #include "chrome/browser/history/url_database.h" 21 #include "chrome/browser/prefs/pref_service.h" 22 #include "chrome/common/pref_names.h" 23 #include "chrome/test/testing_browser_process.h" 24 #include "chrome/test/testing_browser_process_test.h" 25 #include "chrome/test/testing_profile.h" 26 #include "content/browser/browser_thread.h" 27 #include "testing/gtest/include/gtest/gtest.h" 28 29 using base::Time; 30 using base::TimeDelta; 31 32 struct TestURLInfo { 33 std::string url; 34 std::string title; 35 int visit_count; 36 int typed_count; 37 int days_from_now; 38 } quick_test_db[] = { 39 {"http://www.google.com/", "Google", 3, 3, 0}, 40 {"http://slashdot.org/favorite_page.html", "Favorite page", 200, 100, 0}, 41 {"http://kerneltrap.org/not_very_popular.html", "Less popular", 4, 0, 0}, 42 {"http://freshmeat.net/unpopular.html", "Unpopular", 1, 1, 0}, 43 {"http://news.google.com/?ned=us&topic=n", "Google News - U.S.", 2, 2, 0}, 44 {"http://news.google.com/", "Google News", 1, 1, 0}, 45 {"http://foo.com/", "Dir", 5, 5, 0}, 46 {"http://foo.com/dir/", "Dir", 2, 1, 10}, 47 {"http://foo.com/dir/another/", "Dir", 5, 1, 0}, 48 {"http://foo.com/dir/another/again/", "Dir", 10, 0, 0}, 49 {"http://foo.com/dir/another/again/myfile.html", "File", 10, 2, 0}, 50 {"http://visitedest.com/y/a", "VA", 5, 1, 0}, 51 {"http://visitedest.com/y/b", "VB", 4, 1, 0}, 52 {"http://visitedest.com/x/c", "VC", 3, 1, 0}, 53 {"http://visitedest.com/x/d", "VD", 2, 1, 0}, 54 {"http://visitedest.com/y/e", "VE", 1, 1, 0}, 55 {"http://typeredest.com/y/a", "TA", 3, 5, 0}, 56 {"http://typeredest.com/y/b", "TB", 3, 4, 0}, 57 {"http://typeredest.com/x/c", "TC", 3, 3, 0}, 58 {"http://typeredest.com/x/d", "TD", 3, 2, 0}, 59 {"http://typeredest.com/y/e", "TE", 3, 1, 0}, 60 {"http://daysagoest.com/y/a", "DA", 1, 1, 0}, 61 {"http://daysagoest.com/y/b", "DB", 1, 1, 1}, 62 {"http://daysagoest.com/x/c", "DC", 1, 1, 2}, 63 {"http://daysagoest.com/x/d", "DD", 1, 1, 3}, 64 {"http://daysagoest.com/y/e", "DE", 1, 1, 4}, 65 {"http://abcdefghixyzjklmnopqrstuvw.com/a", "", 3, 1, 0}, 66 {"http://spaces.com/path%20with%20spaces/foo.html", "Spaces", 2, 2, 0}, 67 {"http://abcdefghijklxyzmnopqrstuvw.com/a", "", 3, 1, 0}, 68 {"http://abcdefxyzghijklmnopqrstuvw.com/a", "", 3, 1, 0}, 69 {"http://abcxyzdefghijklmnopqrstuvw.com/a", "", 3, 1, 0}, 70 {"http://xyzabcdefghijklmnopqrstuvw.com/a", "", 3, 1, 0}, 71 {"http://cda.com/Dogs%20Cats%20Gorillas%20Sea%20Slugs%20and%20Mice", 72 "Dogs & Cats & Mice", 1, 1, 0}, 73 }; 74 75 class HistoryQuickProviderTest : public TestingBrowserProcessTest, 76 public ACProviderListener { 77 public: 78 HistoryQuickProviderTest() 79 : ui_thread_(BrowserThread::UI, &message_loop_), 80 file_thread_(BrowserThread::FILE, &message_loop_) {} 81 82 // ACProviderListener 83 virtual void OnProviderUpdate(bool updated_matches); 84 85 protected: 86 void SetUp() { 87 profile_.reset(new TestingProfile()); 88 profile_->CreateHistoryService(true, false); 89 profile_->CreateBookmarkModel(true); 90 profile_->BlockUntilBookmarkModelLoaded(); 91 history_service_ = profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); 92 EXPECT_TRUE(history_service_); 93 provider_ = new HistoryQuickProvider(this, profile_.get()); 94 FillData(); 95 } 96 97 void TearDown() { 98 provider_ = NULL; 99 } 100 101 // Fills test data into the history system. 102 void FillData(); 103 104 // Runs an autocomplete query on |text| and checks to see that the returned 105 // results' destination URLs match those provided. |expected_urls| does not 106 // need to be in sorted order. 107 void RunTest(const string16 text, 108 std::vector<std::string> expected_urls, 109 std::string expected_top_result); 110 111 MessageLoopForUI message_loop_; 112 BrowserThread ui_thread_; 113 BrowserThread file_thread_; 114 115 scoped_ptr<TestingProfile> profile_; 116 HistoryService* history_service_; 117 118 ACMatches ac_matches_; // The resulting matches after running RunTest. 119 120 private: 121 scoped_refptr<HistoryQuickProvider> provider_; 122 }; 123 124 void HistoryQuickProviderTest::OnProviderUpdate(bool updated_matches) { 125 MessageLoop::current()->Quit(); 126 } 127 128 void HistoryQuickProviderTest::FillData() { 129 history::URLDatabase* db = history_service_->InMemoryDatabase(); 130 ASSERT_TRUE(db != NULL); 131 for (size_t i = 0; i < arraysize(quick_test_db); ++i) { 132 const TestURLInfo& cur = quick_test_db[i]; 133 const GURL current_url(cur.url); 134 Time visit_time = Time::Now() - TimeDelta::FromDays(cur.days_from_now); 135 136 history::URLRow url_info(current_url); 137 url_info.set_title(UTF8ToUTF16(cur.title)); 138 url_info.set_visit_count(cur.visit_count); 139 url_info.set_typed_count(cur.typed_count); 140 url_info.set_last_visit(visit_time); 141 url_info.set_hidden(false); 142 EXPECT_TRUE(db->AddURL(url_info)); 143 144 history_service_->AddPageWithDetails(current_url, UTF8ToUTF16(cur.title), 145 cur.visit_count, cur.typed_count, 146 visit_time, false, 147 history::SOURCE_BROWSED); 148 } 149 150 history::InMemoryURLIndex* index = 151 new history::InMemoryURLIndex(FilePath(FILE_PATH_LITERAL("/dummy"))); 152 PrefService* prefs = profile_->GetPrefs(); 153 std::string languages(prefs->GetString(prefs::kAcceptLanguages)); 154 index->Init(db, languages); 155 provider_->SetIndexForTesting(index); 156 } 157 158 class SetShouldContain : public std::unary_function<const std::string&, 159 std::set<std::string> > { 160 public: 161 explicit SetShouldContain(const ACMatches& matched_urls) { 162 for (ACMatches::const_iterator iter = matched_urls.begin(); 163 iter != matched_urls.end(); ++iter) 164 matches_.insert(iter->destination_url.spec()); 165 } 166 167 void operator()(const std::string& expected) { 168 EXPECT_EQ(1U, matches_.erase(expected)); 169 } 170 171 std::set<std::string> LeftOvers() const { return matches_; } 172 173 private: 174 std::set<std::string> matches_; 175 }; 176 177 void HistoryQuickProviderTest::RunTest(const string16 text, 178 std::vector<std::string> expected_urls, 179 std::string expected_top_result) { 180 std::sort(expected_urls.begin(), expected_urls.end()); 181 182 MessageLoop::current()->RunAllPending(); 183 AutocompleteInput input(text, string16(), false, false, true, 184 AutocompleteInput::ALL_MATCHES); 185 provider_->Start(input, false); 186 EXPECT_TRUE(provider_->done()); 187 188 ac_matches_ = provider_->matches(); 189 190 // We should have gotten back at most AutocompleteProvider::kMaxMatches. 191 EXPECT_LE(ac_matches_.size(), AutocompleteProvider::kMaxMatches); 192 193 // If the number of expected and actual matches aren't equal then we need 194 // test no further, but let's do anyway so that we know which URLs failed. 195 EXPECT_EQ(expected_urls.size(), ac_matches_.size()); 196 197 // Verify that all expected URLs were found and that all found URLs 198 // were expected. 199 std::set<std::string> leftovers = 200 for_each(expected_urls.begin(), expected_urls.end(), 201 SetShouldContain(ac_matches_)).LeftOvers(); 202 EXPECT_EQ(0U, leftovers.size()); 203 204 // See if we got the expected top scorer. 205 if (!ac_matches_.empty()) { 206 std::partial_sort(ac_matches_.begin(), ac_matches_.begin() + 1, 207 ac_matches_.end(), AutocompleteMatch::MoreRelevant); 208 EXPECT_EQ(expected_top_result, ac_matches_[0].destination_url.spec()); 209 } 210 } 211 212 TEST_F(HistoryQuickProviderTest, SimpleSingleMatch) { 213 string16 text(ASCIIToUTF16("slashdot")); 214 std::string expected_url("http://slashdot.org/favorite_page.html"); 215 std::vector<std::string> expected_urls; 216 expected_urls.push_back(expected_url); 217 RunTest(text, expected_urls, expected_url); 218 } 219 220 TEST_F(HistoryQuickProviderTest, MultiMatch) { 221 string16 text(ASCIIToUTF16("foo")); 222 std::vector<std::string> expected_urls; 223 // Scores high because of typed_count. 224 expected_urls.push_back("http://foo.com/"); 225 // Scores high because of visit count. 226 expected_urls.push_back("http://foo.com/dir/another/"); 227 // Scores high because of high visit count. 228 expected_urls.push_back("http://foo.com/dir/another/again/myfile.html"); 229 RunTest(text, expected_urls, "http://foo.com/"); 230 } 231 232 TEST_F(HistoryQuickProviderTest, StartRelativeMatch) { 233 string16 text(ASCIIToUTF16("xyz")); 234 std::vector<std::string> expected_urls; 235 expected_urls.push_back("http://xyzabcdefghijklmnopqrstuvw.com/a"); 236 expected_urls.push_back("http://abcxyzdefghijklmnopqrstuvw.com/a"); 237 expected_urls.push_back("http://abcdefxyzghijklmnopqrstuvw.com/a"); 238 RunTest(text, expected_urls, "http://xyzabcdefghijklmnopqrstuvw.com/a"); 239 } 240 241 TEST_F(HistoryQuickProviderTest, VisitCountMatches) { 242 string16 text(ASCIIToUTF16("visitedest")); 243 std::vector<std::string> expected_urls; 244 expected_urls.push_back("http://visitedest.com/y/a"); 245 expected_urls.push_back("http://visitedest.com/y/b"); 246 expected_urls.push_back("http://visitedest.com/x/c"); 247 RunTest(text, expected_urls, "http://visitedest.com/y/a"); 248 } 249 250 TEST_F(HistoryQuickProviderTest, TypedCountMatches) { 251 string16 text(ASCIIToUTF16("typeredest")); 252 std::vector<std::string> expected_urls; 253 expected_urls.push_back("http://typeredest.com/y/a"); 254 expected_urls.push_back("http://typeredest.com/y/b"); 255 expected_urls.push_back("http://typeredest.com/x/c"); 256 RunTest(text, expected_urls, "http://typeredest.com/y/a"); 257 } 258 259 TEST_F(HistoryQuickProviderTest, DaysAgoMatches) { 260 string16 text(ASCIIToUTF16("daysagoest")); 261 std::vector<std::string> expected_urls; 262 expected_urls.push_back("http://daysagoest.com/y/a"); 263 expected_urls.push_back("http://daysagoest.com/y/b"); 264 expected_urls.push_back("http://daysagoest.com/x/c"); 265 RunTest(text, expected_urls, "http://daysagoest.com/y/a"); 266 } 267 268 TEST_F(HistoryQuickProviderTest, EncodingLimitMatch) { 269 string16 text(ASCIIToUTF16("ice")); 270 std::vector<std::string> expected_urls; 271 std::string url( 272 "http://cda.com/Dogs%20Cats%20Gorillas%20Sea%20Slugs%20and%20Mice"); 273 expected_urls.push_back(url); 274 RunTest(text, expected_urls, url); 275 // Verify that the matches' ACMatchClassifications offsets are in range. 276 ACMatchClassifications content(ac_matches_[0].contents_class); 277 // The max offset accounts for 6 occurrences of '%20' plus the 'http://'. 278 const size_t max_offset = url.size() - ((6 * 2) + 7); 279 for (ACMatchClassifications::const_iterator citer = content.begin(); 280 citer != content.end(); ++citer) 281 EXPECT_LT(citer->offset, max_offset); 282 ACMatchClassifications description(ac_matches_[0].description_class); 283 std::string page_title("Dogs & Cats & Mice"); 284 for (ACMatchClassifications::const_iterator diter = description.begin(); 285 diter != description.end(); ++diter) 286 EXPECT_LT(diter->offset, page_title.size()); 287 } 288 289 TEST_F(HistoryQuickProviderTest, Spans) { 290 // Test SpansFromTermMatch 291 history::TermMatches matches_a; 292 // Simulates matches: '.xx.xxx..xx...xxxxx..' which will test no match at 293 // either beginning or end as well as adjacent matches. 294 matches_a.push_back(history::TermMatch(1, 1, 2)); 295 matches_a.push_back(history::TermMatch(2, 4, 3)); 296 matches_a.push_back(history::TermMatch(3, 9, 1)); 297 matches_a.push_back(history::TermMatch(3, 10, 1)); 298 matches_a.push_back(history::TermMatch(4, 14, 5)); 299 ACMatchClassifications spans_a = 300 HistoryQuickProvider::SpansFromTermMatch(matches_a, 20); 301 // ACMatch spans should be: 'NM-NM---N-M-N--M----N-' 302 ASSERT_EQ(9U, spans_a.size()); 303 EXPECT_EQ(0U, spans_a[0].offset); 304 EXPECT_EQ(ACMatchClassification::NONE, spans_a[0].style); 305 EXPECT_EQ(1U, spans_a[1].offset); 306 EXPECT_EQ(ACMatchClassification::MATCH, spans_a[1].style); 307 EXPECT_EQ(3U, spans_a[2].offset); 308 EXPECT_EQ(ACMatchClassification::NONE, spans_a[2].style); 309 EXPECT_EQ(4U, spans_a[3].offset); 310 EXPECT_EQ(ACMatchClassification::MATCH, spans_a[3].style); 311 EXPECT_EQ(7U, spans_a[4].offset); 312 EXPECT_EQ(ACMatchClassification::NONE, spans_a[4].style); 313 EXPECT_EQ(9U, spans_a[5].offset); 314 EXPECT_EQ(ACMatchClassification::MATCH, spans_a[5].style); 315 EXPECT_EQ(11U, spans_a[6].offset); 316 EXPECT_EQ(ACMatchClassification::NONE, spans_a[6].style); 317 EXPECT_EQ(14U, spans_a[7].offset); 318 EXPECT_EQ(ACMatchClassification::MATCH, spans_a[7].style); 319 EXPECT_EQ(19U, spans_a[8].offset); 320 EXPECT_EQ(ACMatchClassification::NONE, spans_a[8].style); 321 // Simulates matches: 'xx.xx' which will test matches at both beginning an 322 // end. 323 history::TermMatches matches_b; 324 matches_b.push_back(history::TermMatch(1, 0, 2)); 325 matches_b.push_back(history::TermMatch(2, 3, 2)); 326 ACMatchClassifications spans_b = 327 HistoryQuickProvider::SpansFromTermMatch(matches_b, 5); 328 // ACMatch spans should be: 'M-NM-' 329 ASSERT_EQ(3U, spans_b.size()); 330 EXPECT_EQ(0U, spans_b[0].offset); 331 EXPECT_EQ(ACMatchClassification::MATCH, spans_b[0].style); 332 EXPECT_EQ(2U, spans_b[1].offset); 333 EXPECT_EQ(ACMatchClassification::NONE, spans_b[1].style); 334 EXPECT_EQ(3U, spans_b[2].offset); 335 EXPECT_EQ(ACMatchClassification::MATCH, spans_b[2].style); 336 } 337