bookmark_provider_unittest.cc revision c2db58bd994c04d98e4ee2cd7565b71548655fe3 
1// Copyright (c) 2012 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/bookmark_provider.h"
6
7#include <algorithm>
8#include <string>
9#include <vector>
10
11#include "base/memory/ref_counted.h"
12#include "base/memory/scoped_ptr.h"
13#include "base/strings/string16.h"
14#include "base/strings/string_number_conversions.h"
15#include "base/strings/utf_string_conversions.h"
16#include "chrome/browser/autocomplete/autocomplete_provider.h"
17#include "chrome/browser/autocomplete/autocomplete_provider_listener.h"
18#include "chrome/browser/bookmarks/bookmark_model.h"
19#include "chrome/browser/bookmarks/bookmark_model_factory.h"
20#include "chrome/test/base/testing_profile.h"
21#include "testing/gtest/include/gtest/gtest.h"
22
23// The bookmark corpus against which we will simulate searches.
24struct BookmarksTestInfo {
25  std::string title;
26  std::string url;
27} bookmark_provider_test_data[] = {
28  { "abc def", "http://www.catsanddogs.com/a" },
29  { "abcde", "http://www.catsanddogs.com/b" },
30  { "abcdef", "http://www.catsanddogs.com/c" },
31  { "a definition", "http://www.catsanddogs.com/d" },
32  { "carry carbon carefully", "http://www.catsanddogs.com/e" },
33  { "ghi jkl", "http://www.catsanddogs.com/f" },
34  { "jkl ghi", "http://www.catsanddogs.com/g" },
35  { "frankly frankly frank", "http://www.catsanddogs.com/h" },
36  { "foobar foobar", "http://www.foobar.com/" },
37  // For testing ranking with different URLs.
38  {"achlorhydric featherheads resuscitates mockingbirds",
39   "http://www.featherheads.com/a" },
40  {"achlorhydric mockingbirds resuscitates featherhead",
41   "http://www.featherheads.com/b" },
42  {"featherhead resuscitates achlorhydric mockingbirds",
43   "http://www.featherheads.com/c" },
44  {"mockingbirds resuscitates featherheads achlorhydric",
45   "http://www.featherheads.com/d" },
46  // For testing URL boosting.
47  {"burning worms #1", "http://www.burned.com/" },
48  {"burning worms #2", "http://www.worms.com/" },
49  {"worming burns #10", "http://www.burned.com/" },
50  {"worming burns #20", "http://www.worms.com/" },
51  {"jive music", "http://www.worms.com/" },
52};
53
54class BookmarkProviderTest : public testing::Test,
55                             public AutocompleteProviderListener {
56 public:
57  BookmarkProviderTest() : model_(new BookmarkModel(NULL)) {}
58
59  // AutocompleteProviderListener: Not called.
60  virtual void OnProviderUpdate(bool updated_matches) OVERRIDE {}
61
62 protected:
63  virtual void SetUp() OVERRIDE;
64
65  scoped_ptr<TestingProfile> profile_;
66  scoped_ptr<BookmarkModel> model_;
67  scoped_refptr<BookmarkProvider> provider_;
68
69 private:
70  DISALLOW_COPY_AND_ASSIGN(BookmarkProviderTest);
71};
72
73void BookmarkProviderTest::SetUp() {
74  profile_.reset(new TestingProfile());
75  DCHECK(profile_.get());
76  provider_ = new BookmarkProvider(this, profile_.get());
77  DCHECK(provider_.get());
78  provider_->set_bookmark_model_for_testing(model_.get());
79
80  const BookmarkNode* other_node = model_->other_node();
81  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(bookmark_provider_test_data); ++i) {
82    const BookmarksTestInfo& cur(bookmark_provider_test_data[i]);
83    const GURL url(cur.url);
84    model_->AddURL(other_node, other_node->child_count(),
85                   ASCIIToUTF16(cur.title), url);
86  }
87}
88
89// Structures and functions supporting the BookmarkProviderTest.Positions
90// unit test.
91
92struct TestBookmarkPosition {
93  TestBookmarkPosition(size_t begin, size_t end)
94      : begin(begin), end(end) {}
95
96  size_t begin;
97  size_t end;
98};
99typedef std::vector<TestBookmarkPosition> TestBookmarkPositions;
100
101// Return |positions| as a formatted string for unit test diagnostic output.
102std::string TestBookmarkPositionsAsString(
103    const TestBookmarkPositions& positions) {
104  std::string position_string("{");
105  for (TestBookmarkPositions::const_iterator i = positions.begin();
106       i != positions.end(); ++i) {
107    if (i != positions.begin())
108      position_string += ", ";
109    position_string += "{" + base::IntToString(i->begin) + ", " +
110        base::IntToString(i->end) + "}";
111  }
112  position_string += "}\n";
113  return position_string;
114}
115
116// Return the positions in |matches| as a formatted string for unit test
117// diagnostic output.
118string16 MatchesAsString16(const ACMatches& matches) {
119  string16 matches_string;
120  for (ACMatches::const_iterator i = matches.begin(); i != matches.end(); ++i) {
121    matches_string.append(ASCIIToUTF16("    '"));
122    matches_string.append(i->description);
123    matches_string.append(ASCIIToUTF16("'\n"));
124  }
125  return matches_string;
126}
127
128// Comparison function for sorting search terms by descending length.
129bool TestBookmarkPositionsEqual(const TestBookmarkPosition& pos_a,
130                                const TestBookmarkPosition& pos_b) {
131  return pos_a.begin == pos_b.begin && pos_a.end == pos_b.end;
132}
133
134// Convience function to make comparing ACMatchClassifications against the
135// test expectations structure easier.
136TestBookmarkPositions PositionsFromAutocompleteMatch(
137    const AutocompleteMatch& match) {
138  TestBookmarkPositions positions;
139  bool started = false;
140  size_t start = 0;
141  for (AutocompleteMatch::ACMatchClassifications::const_iterator
142       i = match.description_class.begin();
143       i != match.description_class.end(); ++i) {
144    if (i->style & AutocompleteMatch::ACMatchClassification::MATCH) {
145      // We have found the start of a match.
146      EXPECT_FALSE(started);
147      started = true;
148      start = i->offset;
149    } else if (started) {
150      // We have found the end of a match.
151      started = false;
152      positions.push_back(TestBookmarkPosition(start, i->offset));
153      start = 0;
154    }
155  }
156  // Record the final position if the last match goes to the end of the
157  // candidate string.
158  if (started)
159    positions.push_back(TestBookmarkPosition(start, match.description.size()));
160  return positions;
161}
162
163// Convience function to make comparing test expectations structure against the
164// actual ACMatchClassifications easier.
165TestBookmarkPositions PositionsFromExpectations(
166    const size_t expectations[9][2]) {
167  TestBookmarkPositions positions;
168  size_t i = 0;
169  // The array is zero-terminated in the [1]th element.
170  while (expectations[i][1]) {
171    positions.push_back(
172        TestBookmarkPosition(expectations[i][0], expectations[i][1]));
173    ++i;
174  }
175  return positions;
176}
177
178TEST_F(BookmarkProviderTest, Positions) {
179  // Simulate searches.
180  // Description of |positions|:
181  //   The first index represents the collection of positions for each expected
182  //   match. The count of the actual subarrays in each instance of |query_data|
183  //   must equal |match_count|. The second index represents each expected
184  //   match position. The third index represents the |start| and |end| of the
185  //   expected match's position within the |test_data|. This array must be
186  //   terminated by an entry with a value of '0' for |end|.
187  // Example:
188  //   Consider the line for 'def' below:
189  //     {"def", 2, {{{4, 7}, {XXX, 0}}, {{2, 5}, {11, 14}, {XXX, 0}}}},
190  //   There are two expected matches:
191  //     0. {{4, 7}, {XXX, 0}}
192  //     1. {{2, 5}, {11 ,14}, {XXX, 0}}
193  //   For the first match, [0], there is one match within the bookmark's title
194  //   expected, {4, 7}, which maps to the 'def' within "abc def". The 'XXX'
195  //   value is ignored. The second match, [1], indicates that two matches are
196  //   expected within the bookmark title "a definite definition". In each case,
197  //   the {XXX, 0} indicates the end of the subarray. Or:
198  //                 Match #1            Match #2
199  //                 ------------------  ----------------------------
200  //                  Pos1    Term        Pos1    Pos2      Term
201  //                  ------  --------    ------  --------  --------
202  //     {"def", 2, {{{4, 7}, {999, 0}}, {{2, 5}, {11, 14}, {999, 0}}}},
203  //
204  struct QueryData {
205    const std::string query;
206    const size_t match_count;  // This count must match the number of major
207                               // elements in the following |positions| array.
208    const size_t positions[99][9][2];
209  } query_data[] = {
210    // This first set is primarily for position detection validation.
211    {"abc",                   3, {{{0, 3}, {0, 0}},
212                                  {{0, 3}, {0, 0}},
213                                  {{0, 3}, {0, 0}}}},
214    {"abcde",                 2, {{{0, 5}, {0, 0}},
215                                  {{0, 5}, {0, 0}}}},
216    {"foo bar",               0, {{{0, 0}}}},
217    {"fooey bark",            0, {{{0, 0}}}},
218    {"def",                   2, {{{2, 5}, {0, 0}},
219                                  {{4, 7}, {0, 0}}}},
220    {"ghi jkl",               2, {{{0, 3}, {4, 7}, {0, 0}},
221                                  {{0, 3}, {4, 7}, {0, 0}}}},
222    // NB: GetBookmarksWithTitlesMatching(...) uses exact match for "a".
223    {"a",                     1, {{{0, 1}, {0, 0}}}},
224    {"a d",                   0, {{{0, 0}}}},
225    {"carry carbon",          1, {{{0, 5}, {6, 12}, {0, 0}}}},
226    // NB: GetBookmarksWithTitlesMatching(...) sorts the match positions.
227    {"carbon carry",          1, {{{0, 5}, {6, 12}, {0, 0}}}},
228    {"arbon",                 0, {{{0, 0}}}},
229    {"ar",                    0, {{{0, 0}}}},
230    {"arry",                  0, {{{0, 0}}}},
231    // Quoted terms are single terms.
232    {"\"carry carbon\"",      1, {{{0, 12}, {0, 0}}}},
233    {"\"carry carbon\" care", 1, {{{0, 12}, {13, 17}, {0, 0}}}},
234    // Quoted terms require complete word matches.
235    {"\"carry carbo\"",       0, {{{0, 0}}}},
236    // This set uses duplicated and/or overlaps search terms in the title.
237    {"frank",                 1, {{{0, 5}, {8, 13}, {16, 21}, {0, 0}}}},
238    {"frankly",               1, {{{0, 7}, {8, 15}, {0, 0}}}},
239    {"frankly frankly",       1, {{{0, 7}, {8, 15}, {0, 0}}}},
240    {"foobar foo",            1, {{{0, 6}, {7, 13}, {0, 0}}}},
241    {"foo foobar",            1, {{{0, 6}, {7, 13}, {0, 0}}}},
242  };
243
244  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(query_data); ++i) {
245    AutocompleteInput input(ASCIIToUTF16(query_data[i].query),
246                            string16::npos, string16(), GURL(),
247                            AutocompleteInput::INVALID_SPEC, false, false,
248                            false, AutocompleteInput::ALL_MATCHES);
249    provider_->Start(input, false);
250    const ACMatches& matches(provider_->matches());
251    // Validate number of results is as expected.
252    EXPECT_LE(matches.size(), query_data[i].match_count)
253        << "One or more of the following matches were unexpected:\n"
254        << MatchesAsString16(matches)
255        << "For query '" << query_data[i].query << "'.";
256    EXPECT_GE(matches.size(), query_data[i].match_count)
257        << "One or more expected matches are missing. Matches found:\n"
258        << MatchesAsString16(matches)
259        << "for query '" << query_data[i].query << "'.";
260    // Validate positions within each match is as expected.
261    for (size_t j = 0; j < matches.size(); ++j) {
262      // Collect the expected positions as a vector, collect the match's
263      // classifications for match positions as a vector, then compare.
264      TestBookmarkPositions expected_positions(
265          PositionsFromExpectations(query_data[i].positions[j]));
266      TestBookmarkPositions actual_positions(
267          PositionsFromAutocompleteMatch(matches[j]));
268      EXPECT_TRUE(std::equal(expected_positions.begin(),
269                             expected_positions.end(),
270                             actual_positions.begin(),
271                             TestBookmarkPositionsEqual))
272          << "EXPECTED: " << TestBookmarkPositionsAsString(expected_positions)
273          << "ACTUAL:   " << TestBookmarkPositionsAsString(actual_positions)
274          << "    for query: '" << query_data[i].query << "'.";
275    }
276  }
277}
278
279TEST_F(BookmarkProviderTest, Rankings) {
280  // Simulate searches.
281  struct QueryData {
282    const std::string query;
283    // |match_count| must match the number of elements in the following
284    // |matches| array.
285    const size_t match_count;
286    // |matches| specifies the titles for all bookmarks expected to be matched
287    // by the |query|
288    const std::string matches[99];
289  } query_data[] = {
290    // Basic ranking test.
291    {"abc",       3, {"abcde",      // Most complete match.
292                      "abcdef",
293                      "abc def"}},  // Least complete match.
294    {"ghi",       2, {"ghi jkl",    // Matched earlier.
295                      "jkl ghi"}},  // Matched later.
296    // Rankings of exact-word matches with different URLs.
297    {"achlorhydric",
298                  3, {"achlorhydric mockingbirds resuscitates featherhead",
299                      "achlorhydric featherheads resuscitates mockingbirds",
300                      "featherhead resuscitates achlorhydric mockingbirds"}},
301    {"achlorhydric featherheads",
302                  2, {"achlorhydric featherheads resuscitates mockingbirds",
303                      "mockingbirds resuscitates featherheads achlorhydric"}},
304    {"mockingbirds resuscitates",
305                  3, {"mockingbirds resuscitates featherheads achlorhydric",
306                      "achlorhydric mockingbirds resuscitates featherhead",
307                      "featherhead resuscitates achlorhydric mockingbirds"}},
308    // Ranking of exact-word matches with URL boost.
309    {"worms",     2, {"burning worms #2",    // boosted
310                      "burning worms #1"}},  // not boosted
311    // Ranking of prefix matches with URL boost. Note that a query of
312    // "worm burn" will have the same results.
313    {"burn worm", 3, {"burning worms #2",    // boosted
314                      "worming burns #20",   // boosted
315                      "burning worms #1"}},  // not boosted but shorter
316  };
317
318  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(query_data); ++i) {
319    AutocompleteInput input(ASCIIToUTF16(query_data[i].query),
320                            string16::npos, string16(), GURL(),
321                            AutocompleteInput::INVALID_SPEC, false, false,
322                            false, AutocompleteInput::ALL_MATCHES);
323    provider_->Start(input, false);
324    const ACMatches& matches(provider_->matches());
325    // Validate number and content of results is as expected.
326    for (size_t j = 0; j < std::max(query_data[i].match_count, matches.size());
327         ++j) {
328      EXPECT_LT(j, query_data[i].match_count) << "    Unexpected match '"
329          << UTF16ToUTF8(matches[j].description) << "' for query: '"
330          <<  query_data[i].query << "'.";
331      if (j >= query_data[i].match_count)
332        continue;
333      EXPECT_LT(j, matches.size()) << "    Missing match '"
334          << query_data[i].matches[j] << "' for query: '"
335          << query_data[i].query << "'.";
336      if (j >= matches.size())
337        continue;
338      EXPECT_EQ(query_data[i].matches[j], UTF16ToUTF8(matches[j].description))
339          << "    Mismatch at [" << base::IntToString(j) << "] for query '"
340          << query_data[i].query << "'.";
341      EXPECT_FALSE(matches[j].allowed_to_be_default_match);
342    }
343  }
344}
345