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
29using base::Time;
30using base::TimeDelta;
31
32struct 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
75class 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
124void HistoryQuickProviderTest::OnProviderUpdate(bool updated_matches) {
125  MessageLoop::current()->Quit();
126}
127
128void 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
158class 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
177void 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
212TEST_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
220TEST_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
232TEST_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
241TEST_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
250TEST_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
259TEST_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
268TEST_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
289TEST_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