src/chrome/browser/autocomplete/bookmark_provider_unittest.cc

   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.
  24 struct 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
  54 class 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
  73 void 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
  92 struct TestBookmarkPosition {
  93   TestBookmarkPosition(size_t begin, size_t end)
  94       : begin(begin), end(end) {}
  95
  96   size_t begin;
  97   size_t end;
  98 };
  99 typedef std::vector<TestBookmarkPosition> TestBookmarkPositions;
 100
 101 // Return |positions| as a formatted string for unit test diagnostic output.
 102 std::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.
 118 string16 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.
 129 bool 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.
 136 TestBookmarkPositions 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.
 165 TestBookmarkPositions 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
 178 TEST_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
 279 TEST_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 }