Home | History | Annotate | Download | only in browser 
      1 // Copyright 2014 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 "components/bookmarks/browser/bookmark_index.h"
      6 
      7 #include <string>
      8 #include <vector>
      9 
     10 #include "base/macros.h"
     11 #include "base/strings/string_number_conversions.h"
     12 #include "base/strings/string_split.h"
     13 #include "base/strings/string_util.h"
     14 #include "base/strings/utf_string_conversions.h"
     15 #include "components/bookmarks/browser/bookmark_match.h"
     16 #include "components/bookmarks/browser/bookmark_model.h"
     17 #include "components/bookmarks/test/bookmark_test_helpers.h"
     18 #include "components/bookmarks/test/test_bookmark_client.h"
     19 #include "testing/gtest/include/gtest/gtest.h"
     20 
     21 using base::ASCIIToUTF16;
     22 using base::UTF8ToUTF16;
     23 
     24 namespace bookmarks {
     25 namespace {
     26 
     27 const char kAboutBlankURL[] = "about:blank";
     28 
     29 class BookmarkClientMock : public TestBookmarkClient {
     30  public:
     31   BookmarkClientMock(const std::map<GURL, int>& typed_count_map)
     32       : typed_count_map_(typed_count_map) {}
     33 
     34   virtual bool SupportsTypedCountForNodes() OVERRIDE { return true; }
     35 
     36   virtual void GetTypedCountForNodes(
     37       const NodeSet& nodes,
     38       NodeTypedCountPairs* node_typed_count_pairs) OVERRIDE {
     39     for (NodeSet::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
     40       const BookmarkNode* node = *it;
     41       std::map<GURL, int>::const_iterator found =
     42           typed_count_map_.find(node->url());
     43       if (found == typed_count_map_.end())
     44         continue;
     45 
     46       node_typed_count_pairs->push_back(std::make_pair(node, found->second));
     47     }
     48   }
     49 
     50  private:
     51   const std::map<GURL, int> typed_count_map_;
     52 
     53   DISALLOW_COPY_AND_ASSIGN(BookmarkClientMock);
     54 };
     55 
     56 class BookmarkIndexTest : public testing::Test {
     57  public:
     58   BookmarkIndexTest() : model_(client_.CreateModel()) {}
     59 
     60   typedef std::pair<std::string, std::string> TitleAndURL;
     61 
     62   void AddBookmarks(const char** titles, const char** urls, size_t count) {
     63     // The pair is (title, url).
     64     std::vector<TitleAndURL> bookmarks;
     65     for (size_t i = 0; i < count; ++i) {
     66       TitleAndURL bookmark(titles[i], urls[i]);
     67       bookmarks.push_back(bookmark);
     68     }
     69     AddBookmarks(bookmarks);
     70   }
     71 
     72   void AddBookmarks(const std::vector<TitleAndURL>& bookmarks) {
     73     for (size_t i = 0; i < bookmarks.size(); ++i) {
     74       model_->AddURL(model_->other_node(), static_cast<int>(i),
     75                      ASCIIToUTF16(bookmarks[i].first),
     76                      GURL(bookmarks[i].second));
     77     }
     78   }
     79 
     80   void ExpectMatches(const std::string& query,
     81                      const char** expected_titles,
     82                      size_t expected_count) {
     83     std::vector<std::string> title_vector;
     84     for (size_t i = 0; i < expected_count; ++i)
     85       title_vector.push_back(expected_titles[i]);
     86     ExpectMatches(query, title_vector);
     87   }
     88 
     89   void ExpectMatches(const std::string& query,
     90                      const std::vector<std::string>& expected_titles) {
     91     std::vector<BookmarkMatch> matches;
     92     model_->GetBookmarksMatching(ASCIIToUTF16(query), 1000, &matches);
     93     ASSERT_EQ(expected_titles.size(), matches.size());
     94     for (size_t i = 0; i < expected_titles.size(); ++i) {
     95       bool found = false;
     96       for (size_t j = 0; j < matches.size(); ++j) {
     97         if (ASCIIToUTF16(expected_titles[i]) == matches[j].node->GetTitle()) {
     98           matches.erase(matches.begin() + j);
     99           found = true;
    100           break;
    101         }
    102       }
    103       ASSERT_TRUE(found);
    104     }
    105   }
    106 
    107   void ExtractMatchPositions(const std::string& string,
    108                              BookmarkMatch::MatchPositions* matches) {
    109     std::vector<std::string> match_strings;
    110     base::SplitString(string, ':', &match_strings);
    111     for (size_t i = 0; i < match_strings.size(); ++i) {
    112       std::vector<std::string> chunks;
    113       base::SplitString(match_strings[i], ',', &chunks);
    114       ASSERT_EQ(2U, chunks.size());
    115       matches->push_back(BookmarkMatch::MatchPosition());
    116       int chunks0, chunks1;
    117       EXPECT_TRUE(base::StringToInt(chunks[0], &chunks0));
    118       EXPECT_TRUE(base::StringToInt(chunks[1], &chunks1));
    119       matches->back().first = chunks0;
    120       matches->back().second = chunks1;
    121     }
    122   }
    123 
    124   void ExpectMatchPositions(
    125       const BookmarkMatch::MatchPositions& actual_positions,
    126       const BookmarkMatch::MatchPositions& expected_positions) {
    127     ASSERT_EQ(expected_positions.size(), actual_positions.size());
    128     for (size_t i = 0; i < expected_positions.size(); ++i) {
    129       EXPECT_EQ(expected_positions[i].first, actual_positions[i].first);
    130       EXPECT_EQ(expected_positions[i].second, actual_positions[i].second);
    131     }
    132   }
    133 
    134  protected:
    135   TestBookmarkClient client_;
    136   scoped_ptr<BookmarkModel> model_;
    137 
    138  private:
    139   DISALLOW_COPY_AND_ASSIGN(BookmarkIndexTest);
    140 };
    141 
    142 // Various permutations with differing input, queries and output that exercises
    143 // all query paths.
    144 TEST_F(BookmarkIndexTest, GetBookmarksMatching) {
    145   struct TestData {
    146     const std::string titles;
    147     const std::string query;
    148     const std::string expected;
    149   } data[] = {
    150     // Trivial test case of only one term, exact match.
    151     { "a;b",                        "A",        "a" },
    152 
    153     // Prefix match, one term.
    154     { "abcd;abc;b",                 "abc",      "abcd;abc" },
    155 
    156     // Prefix match, multiple terms.
    157     { "abcd cdef;abcd;abcd cdefg",  "abc cde",  "abcd cdef;abcd cdefg"},
    158 
    159     // Exact and prefix match.
    160     { "ab cdef;abcd;abcd cdefg",    "ab cdef",  "ab cdef"},
    161 
    162     // Exact and prefix match.
    163     { "ab cdef ghij;ab;cde;cdef;ghi;cdef ab;ghij ab",
    164       "ab cde ghi",
    165       "ab cdef ghij"},
    166 
    167     // Title with term multiple times.
    168     { "ab ab",                      "ab",       "ab ab"},
    169 
    170     // Make sure quotes don't do a prefix match.
    171     { "think",                      "\"thi\"",  ""},
    172 
    173     // Prefix matches against multiple candidates.
    174     { "abc1 abc2 abc3 abc4", "abc", "abc1 abc2 abc3 abc4"},
    175   };
    176   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
    177     std::vector<std::string> titles;
    178     base::SplitString(data[i].titles, ';', &titles);
    179     std::vector<TitleAndURL> bookmarks;
    180     for (size_t j = 0; j < titles.size(); ++j) {
    181       TitleAndURL bookmark(titles[j], kAboutBlankURL);
    182       bookmarks.push_back(bookmark);
    183     }
    184     AddBookmarks(bookmarks);
    185 
    186     std::vector<std::string> expected;
    187     if (!data[i].expected.empty())
    188       base::SplitString(data[i].expected, ';', &expected);
    189 
    190     ExpectMatches(data[i].query, expected);
    191 
    192     model_ = client_.CreateModel();
    193   }
    194 }
    195 
    196 // Analogous to GetBookmarksMatching, this test tests various permutations
    197 // of title, URL, and input to see if the title/URL matches the input as
    198 // expected.
    199 TEST_F(BookmarkIndexTest, GetBookmarksMatchingWithURLs) {
    200   struct TestData {
    201     const std::string query;
    202     const std::string title;
    203     const std::string url;
    204     const bool should_be_retrieved;
    205   } data[] = {
    206     // Test single-word inputs.  Include both exact matches and prefix matches.
    207     { "foo", "Foo",    "http://www.bar.com/",    true  },
    208     { "foo", "Foodie", "http://www.bar.com/",    true  },
    209     { "foo", "Bar",    "http://www.foo.com/",    true  },
    210     { "foo", "Bar",    "http://www.foodie.com/", true  },
    211     { "foo", "Foo",    "http://www.foo.com/",    true  },
    212     { "foo", "Bar",    "http://www.bar.com/",    false },
    213     { "foo", "Bar",    "http://www.bar.com/blah/foo/blah-again/ ",    true  },
    214     { "foo", "Bar",    "http://www.bar.com/blah/foodie/blah-again/ ", true  },
    215     { "foo", "Bar",    "http://www.bar.com/blah-foo/blah-again/ ",    true  },
    216     { "foo", "Bar",    "http://www.bar.com/blah-foodie/blah-again/ ", true  },
    217     { "foo", "Bar",    "http://www.bar.com/blahafoo/blah-again/ ",    false },
    218 
    219     // Test multi-word inputs.
    220     { "foo bar", "Foo Bar",      "http://baz.com/",   true  },
    221     { "foo bar", "Foodie Bar",   "http://baz.com/",   true  },
    222     { "bar foo", "Foo Bar",      "http://baz.com/",   true  },
    223     { "bar foo", "Foodie Barly", "http://baz.com/",   true  },
    224     { "foo bar", "Foo Baz",      "http://baz.com/",   false },
    225     { "foo bar", "Foo Baz",      "http://bar.com/",   true  },
    226     { "foo bar", "Foo Baz",      "http://barly.com/", true  },
    227     { "foo bar", "Foodie Baz",   "http://barly.com/", true  },
    228     { "bar foo", "Foo Baz",      "http://bar.com/",   true  },
    229     { "bar foo", "Foo Baz",      "http://barly.com/", true  },
    230     { "foo bar", "Baz Bar",      "http://blah.com/foo",         true  },
    231     { "foo bar", "Baz Barly",    "http://blah.com/foodie",      true  },
    232     { "foo bar", "Baz Bur",      "http://blah.com/foo/bar",     true  },
    233     { "foo bar", "Baz Bur",      "http://blah.com/food/barly",  true  },
    234     { "foo bar", "Baz Bur",      "http://bar.com/blah/foo",     true  },
    235     { "foo bar", "Baz Bur",      "http://barly.com/blah/food",  true  },
    236     { "foo bar", "Baz Bur",      "http://bar.com/blah/flub",    false },
    237     { "foo bar", "Baz Bur",      "http://foo.com/blah/flub",    false }
    238   };
    239 
    240   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
    241     model_ = client_.CreateModel();
    242     std::vector<TitleAndURL> bookmarks;
    243     bookmarks.push_back(TitleAndURL(data[i].title, data[i].url));
    244     AddBookmarks(bookmarks);
    245 
    246     std::vector<std::string> expected;
    247     if (data[i].should_be_retrieved)
    248       expected.push_back(data[i].title);
    249 
    250     ExpectMatches(data[i].query, expected);
    251   }
    252 }
    253 
    254 TEST_F(BookmarkIndexTest, Normalization) {
    255   struct TestData {
    256     const char* const title;
    257     const char* const query;
    258   } data[] = {
    259     { "fooa\xcc\x88-test", "foo\xc3\xa4-test" },
    260     { "fooa\xcc\x88-test", "fooa\xcc\x88-test" },
    261     { "fooa\xcc\x88-test", "foo\xc3\xa4" },
    262     { "fooa\xcc\x88-test", "fooa\xcc\x88" },
    263     { "fooa\xcc\x88-test", "foo" },
    264     { "foo\xc3\xa4-test", "foo\xc3\xa4-test" },
    265     { "foo\xc3\xa4-test", "fooa\xcc\x88-test" },
    266     { "foo\xc3\xa4-test", "foo\xc3\xa4" },
    267     { "foo\xc3\xa4-test", "fooa\xcc\x88" },
    268     { "foo\xc3\xa4-test", "foo" },
    269     { "foo", "foo" }
    270   };
    271 
    272   GURL url(kAboutBlankURL);
    273   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
    274     model_->AddURL(model_->other_node(), 0, UTF8ToUTF16(data[i].title), url);
    275     std::vector<BookmarkMatch> matches;
    276     model_->GetBookmarksMatching(UTF8ToUTF16(data[i].query), 10, &matches);
    277     EXPECT_EQ(1u, matches.size());
    278     model_ = client_.CreateModel();
    279   }
    280 }
    281 
    282 // Makes sure match positions are updated appropriately for title matches.
    283 TEST_F(BookmarkIndexTest, MatchPositionsTitles) {
    284   struct TestData {
    285     const std::string title;
    286     const std::string query;
    287     const std::string expected_title_match_positions;
    288   } data[] = {
    289     // Trivial test case of only one term, exact match.
    290     { "a",                        "A",        "0,1" },
    291     { "foo bar",                  "bar",      "4,7" },
    292     { "fooey bark",               "bar foo",  "0,3:6,9" },
    293     // Non-trivial tests.
    294     { "foobar foo",               "foobar foo",   "0,6:7,10" },
    295     { "foobar foo",               "foo foobar",   "0,6:7,10" },
    296     { "foobar foobar",            "foobar foo",   "0,6:7,13" },
    297     { "foobar foobar",            "foo foobar",   "0,6:7,13" },
    298   };
    299   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
    300     std::vector<TitleAndURL> bookmarks;
    301     TitleAndURL bookmark(data[i].title, kAboutBlankURL);
    302     bookmarks.push_back(bookmark);
    303     AddBookmarks(bookmarks);
    304 
    305     std::vector<BookmarkMatch> matches;
    306     model_->GetBookmarksMatching(ASCIIToUTF16(data[i].query), 1000, &matches);
    307     ASSERT_EQ(1U, matches.size());
    308 
    309     BookmarkMatch::MatchPositions expected_title_matches;
    310     ExtractMatchPositions(data[i].expected_title_match_positions,
    311                           &expected_title_matches);
    312     ExpectMatchPositions(matches[0].title_match_positions,
    313                          expected_title_matches);
    314 
    315     model_ = client_.CreateModel();
    316   }
    317 }
    318 
    319 // Makes sure match positions are updated appropriately for URL matches.
    320 TEST_F(BookmarkIndexTest, MatchPositionsURLs) {
    321   // The encoded stuff between /wiki/ and the # is 
    322   const std::string ja_wiki_url = "http://ja.wikipedia.org/wiki/%E7%AC%AC%E4"
    323       "%BA%8C%E6%AC%A1%E4%B8%96%E7%95%8C%E5%A4%A7%E6%88%A6#.E3.83.B4.E3.82.A7"
    324       ".E3.83.AB.E3.82.B5.E3.82.A4.E3.83.A6.E4.BD.93.E5.88.B6";
    325   struct TestData {
    326     const std::string query;
    327     const std::string url;
    328     const std::string expected_url_match_positions;
    329   } data[] = {
    330     { "foo",        "http://www.foo.com/",    "11,14" },
    331     { "foo",        "http://www.foodie.com/", "11,14" },
    332     { "foo",        "http://www.foofoo.com/", "11,14" },
    333     { "www",        "http://www.foo.com/",    "7,10"  },
    334     { "foo",        "http://www.foodie.com/blah/foo/fi", "11,14:27,30"      },
    335     { "foo",        "http://www.blah.com/blah/foo/fi",   "25,28"            },
    336     { "foo www",    "http://www.foodie.com/blah/foo/fi", "7,10:11,14:27,30" },
    337     { "www foo",    "http://www.foodie.com/blah/foo/fi", "7,10:11,14:27,30" },
    338     { "www bla",    "http://www.foodie.com/blah/foo/fi", "7,10:22,25"       },
    339     { "http",       "http://www.foo.com/",               "0,4"              },
    340     { "http www",   "http://www.foo.com/",               "0,4:7,10"         },
    341     { "http foo",   "http://www.foo.com/",               "0,4:11,14"        },
    342     { "http foo",   "http://www.bar.com/baz/foodie/hi",  "0,4:23,26"        },
    343     { "",      ja_wiki_url,                         "29,56"            },
    344     { "ja ",   ja_wiki_url,                         "7,9:29,56"        },
    345     { " E3.8", ja_wiki_url,                         "29,56:94,98:103,107:"
    346                                                          "112,116:121,125:"
    347                                                          "130,134:139,143"  }
    348   };
    349 
    350   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
    351     model_ = client_.CreateModel();
    352     std::vector<TitleAndURL> bookmarks;
    353     TitleAndURL bookmark("123456", data[i].url);
    354     bookmarks.push_back(bookmark);
    355     AddBookmarks(bookmarks);
    356 
    357     std::vector<BookmarkMatch> matches;
    358     model_->GetBookmarksMatching(UTF8ToUTF16(data[i].query), 1000, &matches);
    359     ASSERT_EQ(1U, matches.size()) << data[i].url << data[i].query;
    360 
    361     BookmarkMatch::MatchPositions expected_url_matches;
    362     ExtractMatchPositions(data[i].expected_url_match_positions,
    363                           &expected_url_matches);
    364     ExpectMatchPositions(matches[0].url_match_positions, expected_url_matches);
    365   }
    366 }
    367 
    368 // Makes sure index is updated when a node is removed.
    369 TEST_F(BookmarkIndexTest, Remove) {
    370   const char* titles[] = { "a", "b" };
    371   const char* urls[] = {kAboutBlankURL, kAboutBlankURL};
    372   AddBookmarks(titles, urls, ARRAYSIZE_UNSAFE(titles));
    373 
    374   // Remove the node and make sure we don't get back any results.
    375   model_->Remove(model_->other_node(), 0);
    376   ExpectMatches("A", NULL, 0U);
    377 }
    378 
    379 // Makes sure index is updated when a node's title is changed.
    380 TEST_F(BookmarkIndexTest, ChangeTitle) {
    381   const char* titles[] = { "a", "b" };
    382   const char* urls[] = {kAboutBlankURL, kAboutBlankURL};
    383   AddBookmarks(titles, urls, ARRAYSIZE_UNSAFE(titles));
    384 
    385   // Remove the node and make sure we don't get back any results.
    386   const char* expected[] = { "blah" };
    387   model_->SetTitle(model_->other_node()->GetChild(0), ASCIIToUTF16("blah"));
    388   ExpectMatches("BlAh", expected, ARRAYSIZE_UNSAFE(expected));
    389 }
    390 
    391 // Makes sure no more than max queries is returned.
    392 TEST_F(BookmarkIndexTest, HonorMax) {
    393   const char* titles[] = { "abcd", "abcde" };
    394   const char* urls[] = {kAboutBlankURL, kAboutBlankURL};
    395   AddBookmarks(titles, urls, ARRAYSIZE_UNSAFE(titles));
    396 
    397   std::vector<BookmarkMatch> matches;
    398   model_->GetBookmarksMatching(ASCIIToUTF16("ABc"), 1, &matches);
    399   EXPECT_EQ(1U, matches.size());
    400 }
    401 
    402 // Makes sure if the lower case string of a bookmark title is more characters
    403 // than the upper case string no match positions are returned.
    404 TEST_F(BookmarkIndexTest, EmptyMatchOnMultiwideLowercaseString) {
    405   const BookmarkNode* n1 = model_->AddURL(model_->other_node(), 0,
    406                                           base::WideToUTF16(L"\u0130 i"),
    407                                           GURL("http://www.google.com"));
    408 
    409   std::vector<BookmarkMatch> matches;
    410   model_->GetBookmarksMatching(ASCIIToUTF16("i"), 100, &matches);
    411   ASSERT_EQ(1U, matches.size());
    412   EXPECT_EQ(n1, matches[0].node);
    413   EXPECT_TRUE(matches[0].title_match_positions.empty());
    414 }
    415 
    416 TEST_F(BookmarkIndexTest, GetResultsSortedByTypedCount) {
    417   struct TestData {
    418     const GURL url;
    419     const char* title;
    420     const int typed_count;
    421   } data[] = {
    422     { GURL("http://www.google.com/"),      "Google",           100 },
    423     { GURL("http://maps.google.com/"),     "Google Maps",       40 },
    424     { GURL("http://docs.google.com/"),     "Google Docs",       50 },
    425     { GURL("http://reader.google.com/"),   "Google Reader",     80 },
    426   };
    427 
    428   std::map<GURL, int> typed_count_map;
    429   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i)
    430     typed_count_map.insert(std::make_pair(data[i].url, data[i].typed_count));
    431 
    432   BookmarkClientMock client(typed_count_map);
    433   scoped_ptr<BookmarkModel> model = client.CreateModel();
    434 
    435   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i)
    436     // Populate the BookmarkIndex.
    437     model->AddURL(
    438         model->other_node(), i, UTF8ToUTF16(data[i].title), data[i].url);
    439 
    440   // Populate match nodes.
    441   std::vector<BookmarkMatch> matches;
    442   model->GetBookmarksMatching(ASCIIToUTF16("google"), 4, &matches);
    443 
    444   // The resulting order should be:
    445   // 1. Google (google.com) 100
    446   // 2. Google Reader (google.com/reader) 80
    447   // 3. Google Docs (docs.google.com) 50
    448   // 4. Google Maps (maps.google.com) 40
    449   ASSERT_EQ(4, static_cast<int>(matches.size()));
    450   EXPECT_EQ(data[0].url, matches[0].node->url());
    451   EXPECT_EQ(data[3].url, matches[1].node->url());
    452   EXPECT_EQ(data[2].url, matches[2].node->url());
    453   EXPECT_EQ(data[1].url, matches[3].node->url());
    454 
    455   matches.clear();
    456   // Select top two matches.
    457   model->GetBookmarksMatching(ASCIIToUTF16("google"), 2, &matches);
    458 
    459   ASSERT_EQ(2, static_cast<int>(matches.size()));
    460   EXPECT_EQ(data[0].url, matches[0].node->url());
    461   EXPECT_EQ(data[3].url, matches[1].node->url());
    462 }
    463 
    464 }  // namespace
    465 }  // namespace bookmarks
    466