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.
5 #include "components/bookmarks/browser/bookmark_index.h"
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"
21 using base::ASCIIToUTF16
;
22 using base::UTF8ToUTF16
;
27 const char kAboutBlankURL
[] = "about:blank";
29 class BookmarkClientMock
: public TestBookmarkClient
{
31 BookmarkClientMock(const std::map
<GURL
, int>& typed_count_map
)
32 : typed_count_map_(typed_count_map
) {}
34 bool SupportsTypedCountForNodes() override
{ return true; }
36 void GetTypedCountForNodes(
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())
46 node_typed_count_pairs
->push_back(std::make_pair(node
, found
->second
));
51 const std::map
<GURL
, int> typed_count_map_
;
53 DISALLOW_COPY_AND_ASSIGN(BookmarkClientMock
);
56 class BookmarkIndexTest
: public testing::Test
{
58 BookmarkIndexTest() : model_(client_
.CreateModel()) {}
60 typedef std::pair
<std::string
, std::string
> TitleAndURL
;
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
);
69 AddBookmarks(bookmarks
);
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
));
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
, query_parser::MatchingAlgorithm::DEFAULT
,
90 void ExpectMatches(const std::string
& query
,
91 query_parser::MatchingAlgorithm matching_algorithm
,
92 const std::vector
<std::string
>& expected_titles
) {
93 std::vector
<BookmarkMatch
> matches
;
94 model_
->GetBookmarksMatching(ASCIIToUTF16(query
), 1000, matching_algorithm
,
96 ASSERT_EQ(expected_titles
.size(), matches
.size());
97 for (size_t i
= 0; i
< expected_titles
.size(); ++i
) {
99 for (size_t j
= 0; j
< matches
.size(); ++j
) {
100 if (ASCIIToUTF16(expected_titles
[i
]) == matches
[j
].node
->GetTitle()) {
101 matches
.erase(matches
.begin() + j
);
110 void ExtractMatchPositions(const std::string
& string
,
111 BookmarkMatch::MatchPositions
* matches
) {
112 for (const base::StringPiece
& match
:
113 base::SplitStringPiece(string
, ":",
114 base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
)) {
115 std::vector
<base::StringPiece
> chunks
= base::SplitStringPiece(
116 match
, ",", base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
);
117 ASSERT_EQ(2U, chunks
.size());
118 matches
->push_back(BookmarkMatch::MatchPosition());
119 int chunks0
, chunks1
;
120 EXPECT_TRUE(base::StringToInt(chunks
[0], &chunks0
));
121 EXPECT_TRUE(base::StringToInt(chunks
[1], &chunks1
));
122 matches
->back().first
= chunks0
;
123 matches
->back().second
= chunks1
;
127 void ExpectMatchPositions(
128 const BookmarkMatch::MatchPositions
& actual_positions
,
129 const BookmarkMatch::MatchPositions
& expected_positions
) {
130 ASSERT_EQ(expected_positions
.size(), actual_positions
.size());
131 for (size_t i
= 0; i
< expected_positions
.size(); ++i
) {
132 EXPECT_EQ(expected_positions
[i
].first
, actual_positions
[i
].first
);
133 EXPECT_EQ(expected_positions
[i
].second
, actual_positions
[i
].second
);
138 TestBookmarkClient client_
;
139 scoped_ptr
<BookmarkModel
> model_
;
142 DISALLOW_COPY_AND_ASSIGN(BookmarkIndexTest
);
145 // Various permutations with differing input, queries and output that exercises
147 TEST_F(BookmarkIndexTest
, GetBookmarksMatching
) {
149 const std::string titles
;
150 const std::string query
;
151 const std::string expected
;
153 // Trivial test case of only one term, exact match.
156 // Two terms, exact matches.
157 { "a b;b", "a b", "a b" },
159 // Prefix match, one term.
160 { "abcd;abc;b", "abc", "abcd;abc" },
162 // Prefix match, multiple terms.
163 { "abcd cdef;abcd;abcd cdefg", "abc cde", "abcd cdef;abcd cdefg"},
165 // Exact and prefix match.
166 { "ab cdef;abcd;abcd cdefg", "ab cdef", "ab cdef"},
168 // Exact and prefix match.
169 { "ab cdef ghij;ab;cde;cdef;ghi;cdef ab;ghij ab",
173 // Title with term multiple times.
174 { "ab ab", "ab", "ab ab"},
176 // Make sure quotes don't do a prefix match.
177 { "think", "\"thi\"", ""},
179 // Prefix matches against multiple candidates.
180 { "abc1 abc2 abc3 abc4", "abc", "abc1 abc2 abc3 abc4"},
182 // Multiple prefix matches (with a lot of redundancy) against multiple
184 { "abc1 abc2 abc3 abc4 def1 def2 def3 def4",
185 "abc def abc def abc def abc def abc def",
186 "abc1 abc2 abc3 abc4 def1 def2 def3 def4"},
188 // Prefix match on the first term.
191 // Prefix match on subsequent terms.
192 { "abc def", "abc d", "" },
194 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
195 std::vector
<TitleAndURL
> bookmarks
;
196 for (const std::string
& title
: base::SplitString(
198 base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
)) {
199 TitleAndURL
bookmark(title
, kAboutBlankURL
);
200 bookmarks
.push_back(bookmark
);
202 AddBookmarks(bookmarks
);
204 std::vector
<std::string
> expected
;
205 if (!data
[i
].expected
.empty()) {
206 expected
= base::SplitString(data
[i
].expected
, ";",
207 base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
);
210 ExpectMatches(data
[i
].query
, query_parser::MatchingAlgorithm::DEFAULT
,
213 model_
= client_
.CreateModel();
217 TEST_F(BookmarkIndexTest
, GetBookmarksMatchingAlwaysPrefixSearch
) {
219 const std::string titles
;
220 const std::string query
;
221 const std::string expected
;
223 // Trivial test case of only one term, exact match.
226 // Prefix match, one term.
227 { "abcd;abc;b", "abc", "abcd;abc" },
229 // Prefix match, multiple terms.
230 { "abcd cdef;abcd;abcd cdefg", "abc cde", "abcd cdef;abcd cdefg" },
232 // Exact and prefix match.
233 { "ab cdef ghij;ab;cde;cdef;ghi;cdef ab;ghij ab",
237 // Title with term multiple times.
238 { "ab ab", "ab", "ab ab" },
240 // Make sure quotes don't do a prefix match.
241 { "think", "\"thi\"", "" },
243 // Prefix matches against multiple candidates.
244 { "abc1 abc2 abc3 abc4", "abc", "abc1 abc2 abc3 abc4" },
246 // Prefix match on the first term.
247 { "abc", "a", "abc" },
249 // Prefix match on subsequent terms.
250 { "abc def", "abc d", "abc def" },
252 // Exact and prefix match.
253 { "ab cdef;abcd;abcd cdefg", "ab cdef", "ab cdef;abcd cdefg" },
255 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
256 std::vector
<TitleAndURL
> bookmarks
;
257 for (const std::string
& title
: base::SplitString(
259 base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
)) {
260 TitleAndURL
bookmark(title
, kAboutBlankURL
);
261 bookmarks
.push_back(bookmark
);
263 AddBookmarks(bookmarks
);
265 std::vector
<std::string
> expected
;
266 if (!data
[i
].expected
.empty()) {
267 expected
= base::SplitString(data
[i
].expected
, ";",
268 base::TRIM_WHITESPACE
, base::SPLIT_WANT_ALL
);
271 ExpectMatches(data
[i
].query
,
272 query_parser::MatchingAlgorithm::ALWAYS_PREFIX_SEARCH
,
275 model_
= client_
.CreateModel();
279 // Analogous to GetBookmarksMatching, this test tests various permutations
280 // of title, URL, and input to see if the title/URL matches the input as
282 TEST_F(BookmarkIndexTest
, GetBookmarksMatchingWithURLs
) {
284 const std::string query
;
285 const std::string title
;
286 const std::string url
;
287 const bool should_be_retrieved
;
289 // Test single-word inputs. Include both exact matches and prefix matches.
290 { "foo", "Foo", "http://www.bar.com/", true },
291 { "foo", "Foodie", "http://www.bar.com/", true },
292 { "foo", "Bar", "http://www.foo.com/", true },
293 { "foo", "Bar", "http://www.foodie.com/", true },
294 { "foo", "Foo", "http://www.foo.com/", true },
295 { "foo", "Bar", "http://www.bar.com/", false },
296 { "foo", "Bar", "http://www.bar.com/blah/foo/blah-again/ ", true },
297 { "foo", "Bar", "http://www.bar.com/blah/foodie/blah-again/ ", true },
298 { "foo", "Bar", "http://www.bar.com/blah-foo/blah-again/ ", true },
299 { "foo", "Bar", "http://www.bar.com/blah-foodie/blah-again/ ", true },
300 { "foo", "Bar", "http://www.bar.com/blahafoo/blah-again/ ", false },
302 // Test multi-word inputs.
303 { "foo bar", "Foo Bar", "http://baz.com/", true },
304 { "foo bar", "Foodie Bar", "http://baz.com/", true },
305 { "bar foo", "Foo Bar", "http://baz.com/", true },
306 { "bar foo", "Foodie Barly", "http://baz.com/", true },
307 { "foo bar", "Foo Baz", "http://baz.com/", false },
308 { "foo bar", "Foo Baz", "http://bar.com/", true },
309 { "foo bar", "Foo Baz", "http://barly.com/", true },
310 { "foo bar", "Foodie Baz", "http://barly.com/", true },
311 { "bar foo", "Foo Baz", "http://bar.com/", true },
312 { "bar foo", "Foo Baz", "http://barly.com/", true },
313 { "foo bar", "Baz Bar", "http://blah.com/foo", true },
314 { "foo bar", "Baz Barly", "http://blah.com/foodie", true },
315 { "foo bar", "Baz Bur", "http://blah.com/foo/bar", true },
316 { "foo bar", "Baz Bur", "http://blah.com/food/barly", true },
317 { "foo bar", "Baz Bur", "http://bar.com/blah/foo", true },
318 { "foo bar", "Baz Bur", "http://barly.com/blah/food", true },
319 { "foo bar", "Baz Bur", "http://bar.com/blah/flub", false },
320 { "foo bar", "Baz Bur", "http://foo.com/blah/flub", false }
323 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
324 model_
= client_
.CreateModel();
325 std::vector
<TitleAndURL
> bookmarks
;
326 bookmarks
.push_back(TitleAndURL(data
[i
].title
, data
[i
].url
));
327 AddBookmarks(bookmarks
);
329 std::vector
<std::string
> expected
;
330 if (data
[i
].should_be_retrieved
)
331 expected
.push_back(data
[i
].title
);
333 ExpectMatches(data
[i
].query
, query_parser::MatchingAlgorithm::DEFAULT
,
338 TEST_F(BookmarkIndexTest
, Normalization
) {
340 const char* const title
;
341 const char* const query
;
343 { "fooa\xcc\x88-test", "foo\xc3\xa4-test" },
344 { "fooa\xcc\x88-test", "fooa\xcc\x88-test" },
345 { "fooa\xcc\x88-test", "foo\xc3\xa4" },
346 { "fooa\xcc\x88-test", "fooa\xcc\x88" },
347 { "fooa\xcc\x88-test", "foo" },
348 { "foo\xc3\xa4-test", "foo\xc3\xa4-test" },
349 { "foo\xc3\xa4-test", "fooa\xcc\x88-test" },
350 { "foo\xc3\xa4-test", "foo\xc3\xa4" },
351 { "foo\xc3\xa4-test", "fooa\xcc\x88" },
352 { "foo\xc3\xa4-test", "foo" },
356 GURL
url(kAboutBlankURL
);
357 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
358 model_
->AddURL(model_
->other_node(), 0, UTF8ToUTF16(data
[i
].title
), url
);
359 std::vector
<BookmarkMatch
> matches
;
360 model_
->GetBookmarksMatching(UTF8ToUTF16(data
[i
].query
), 10, &matches
);
361 EXPECT_EQ(1u, matches
.size());
362 model_
= client_
.CreateModel();
366 // Makes sure match positions are updated appropriately for title matches.
367 TEST_F(BookmarkIndexTest
, MatchPositionsTitles
) {
369 const std::string title
;
370 const std::string query
;
371 const std::string expected_title_match_positions
;
373 // Trivial test case of only one term, exact match.
375 { "foo bar", "bar", "4,7" },
376 { "fooey bark", "bar foo", "0,3:6,9" },
377 // Non-trivial tests.
378 { "foobar foo", "foobar foo", "0,6:7,10" },
379 { "foobar foo", "foo foobar", "0,6:7,10" },
380 { "foobar foobar", "foobar foo", "0,6:7,13" },
381 { "foobar foobar", "foo foobar", "0,6:7,13" },
383 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
384 std::vector
<TitleAndURL
> bookmarks
;
385 TitleAndURL
bookmark(data
[i
].title
, kAboutBlankURL
);
386 bookmarks
.push_back(bookmark
);
387 AddBookmarks(bookmarks
);
389 std::vector
<BookmarkMatch
> matches
;
390 model_
->GetBookmarksMatching(ASCIIToUTF16(data
[i
].query
), 1000, &matches
);
391 ASSERT_EQ(1U, matches
.size());
393 BookmarkMatch::MatchPositions expected_title_matches
;
394 ExtractMatchPositions(data
[i
].expected_title_match_positions
,
395 &expected_title_matches
);
396 ExpectMatchPositions(matches
[0].title_match_positions
,
397 expected_title_matches
);
399 model_
= client_
.CreateModel();
403 // Makes sure match positions are updated appropriately for URL matches.
404 TEST_F(BookmarkIndexTest
, MatchPositionsURLs
) {
405 // The encoded stuff between /wiki/ and the # is 第二次世界大戦
406 const std::string ja_wiki_url
= "http://ja.wikipedia.org/wiki/%E7%AC%AC%E4"
407 "%BA%8C%E6%AC%A1%E4%B8%96%E7%95%8C%E5%A4%A7%E6%88%A6#.E3.83.B4.E3.82.A7"
408 ".E3.83.AB.E3.82.B5.E3.82.A4.E3.83.A6.E4.BD.93.E5.88.B6";
410 const std::string query
;
411 const std::string url
;
412 const std::string expected_url_match_positions
;
414 { "foo", "http://www.foo.com/", "11,14" },
415 { "foo", "http://www.foodie.com/", "11,14" },
416 { "foo", "http://www.foofoo.com/", "11,14" },
417 { "www", "http://www.foo.com/", "7,10" },
418 { "foo", "http://www.foodie.com/blah/foo/fi", "11,14:27,30" },
419 { "foo", "http://www.blah.com/blah/foo/fi", "25,28" },
420 { "foo www", "http://www.foodie.com/blah/foo/fi", "7,10:11,14:27,30" },
421 { "www foo", "http://www.foodie.com/blah/foo/fi", "7,10:11,14:27,30" },
422 { "www bla", "http://www.foodie.com/blah/foo/fi", "7,10:22,25" },
423 { "http", "http://www.foo.com/", "0,4" },
424 { "http www", "http://www.foo.com/", "0,4:7,10" },
425 { "http foo", "http://www.foo.com/", "0,4:11,14" },
426 { "http foo", "http://www.bar.com/baz/foodie/hi", "0,4:23,26" },
427 { "第二次", ja_wiki_url
, "29,56" },
428 { "ja 第二次", ja_wiki_url
, "7,9:29,56" },
429 { "第二次 E3.8", ja_wiki_url
, "29,56:94,98:103,107:"
434 for (size_t i
= 0; i
< arraysize(data
); ++i
) {
435 model_
= client_
.CreateModel();
436 std::vector
<TitleAndURL
> bookmarks
;
437 TitleAndURL
bookmark("123456", data
[i
].url
);
438 bookmarks
.push_back(bookmark
);
439 AddBookmarks(bookmarks
);
441 std::vector
<BookmarkMatch
> matches
;
442 model_
->GetBookmarksMatching(UTF8ToUTF16(data
[i
].query
), 1000, &matches
);
443 ASSERT_EQ(1U, matches
.size()) << data
[i
].url
<< data
[i
].query
;
445 BookmarkMatch::MatchPositions expected_url_matches
;
446 ExtractMatchPositions(data
[i
].expected_url_match_positions
,
447 &expected_url_matches
);
448 ExpectMatchPositions(matches
[0].url_match_positions
, expected_url_matches
);
452 // Makes sure index is updated when a node is removed.
453 TEST_F(BookmarkIndexTest
, Remove
) {
454 const char* titles
[] = { "a", "b" };
455 const char* urls
[] = {kAboutBlankURL
, kAboutBlankURL
};
456 AddBookmarks(titles
, urls
, arraysize(titles
));
458 // Remove the node and make sure we don't get back any results.
459 model_
->Remove(model_
->other_node()->GetChild(0));
460 ExpectMatches("A", NULL
, 0U);
463 // Makes sure index is updated when a node's title is changed.
464 TEST_F(BookmarkIndexTest
, ChangeTitle
) {
465 const char* titles
[] = { "a", "b" };
466 const char* urls
[] = {kAboutBlankURL
, kAboutBlankURL
};
467 AddBookmarks(titles
, urls
, arraysize(titles
));
469 // Remove the node and make sure we don't get back any results.
470 const char* expected
[] = { "blah" };
471 model_
->SetTitle(model_
->other_node()->GetChild(0), ASCIIToUTF16("blah"));
472 ExpectMatches("BlAh", expected
, arraysize(expected
));
475 // Makes sure index is updated when a node's URL is changed.
476 TEST_F(BookmarkIndexTest
, ChangeURL
) {
477 const char* titles
[] = { "a", "b" };
478 const char* urls
[] = {"http://fizz",
480 AddBookmarks(titles
, urls
, arraysize(titles
));
482 const char* expected
[] = { "a" };
483 model_
->SetURL(model_
->other_node()->GetChild(0), GURL("http://blah"));
484 ExpectMatches("blah", expected
, arraysize(expected
));
487 // Makes sure no more than max queries is returned.
488 TEST_F(BookmarkIndexTest
, HonorMax
) {
489 const char* titles
[] = { "abcd", "abcde" };
490 const char* urls
[] = {kAboutBlankURL
, kAboutBlankURL
};
491 AddBookmarks(titles
, urls
, arraysize(titles
));
493 std::vector
<BookmarkMatch
> matches
;
494 model_
->GetBookmarksMatching(ASCIIToUTF16("ABc"), 1, &matches
);
495 EXPECT_EQ(1U, matches
.size());
498 // Makes sure if the lower case string of a bookmark title is more characters
499 // than the upper case string no match positions are returned.
500 TEST_F(BookmarkIndexTest
, EmptyMatchOnMultiwideLowercaseString
) {
501 const BookmarkNode
* n1
= model_
->AddURL(model_
->other_node(), 0,
502 base::WideToUTF16(L
"\u0130 i"),
503 GURL("http://www.google.com"));
505 std::vector
<BookmarkMatch
> matches
;
506 model_
->GetBookmarksMatching(ASCIIToUTF16("i"), 100, &matches
);
507 ASSERT_EQ(1U, matches
.size());
508 EXPECT_EQ(n1
, matches
[0].node
);
509 EXPECT_TRUE(matches
[0].title_match_positions
.empty());
512 TEST_F(BookmarkIndexTest
, GetResultsSortedByTypedCount
) {
516 const int typed_count
;
518 { GURL("http://www.google.com/"), "Google", 100 },
519 { GURL("http://maps.google.com/"), "Google Maps", 40 },
520 { GURL("http://docs.google.com/"), "Google Docs", 50 },
521 { GURL("http://reader.google.com/"), "Google Reader", 80 },
524 std::map
<GURL
, int> typed_count_map
;
525 for (size_t i
= 0; i
< arraysize(data
); ++i
)
526 typed_count_map
.insert(std::make_pair(data
[i
].url
, data
[i
].typed_count
));
528 BookmarkClientMock
client(typed_count_map
);
529 scoped_ptr
<BookmarkModel
> model
= client
.CreateModel();
531 for (size_t i
= 0; i
< arraysize(data
); ++i
)
532 // Populate the BookmarkIndex.
534 model
->other_node(), i
, UTF8ToUTF16(data
[i
].title
), data
[i
].url
);
536 // Populate match nodes.
537 std::vector
<BookmarkMatch
> matches
;
538 model
->GetBookmarksMatching(ASCIIToUTF16("google"), 4, &matches
);
540 // The resulting order should be:
541 // 1. Google (google.com) 100
542 // 2. Google Reader (google.com/reader) 80
543 // 3. Google Docs (docs.google.com) 50
544 // 4. Google Maps (maps.google.com) 40
545 ASSERT_EQ(4U, matches
.size());
546 EXPECT_EQ(data
[0].url
, matches
[0].node
->url());
547 EXPECT_EQ(data
[3].url
, matches
[1].node
->url());
548 EXPECT_EQ(data
[2].url
, matches
[2].node
->url());
549 EXPECT_EQ(data
[1].url
, matches
[3].node
->url());
552 // Select top two matches.
553 model
->GetBookmarksMatching(ASCIIToUTF16("google"), 2, &matches
);
555 ASSERT_EQ(2U, matches
.size());
556 EXPECT_EQ(data
[0].url
, matches
[0].node
->url());
557 EXPECT_EQ(data
[3].url
, matches
[1].node
->url());
561 } // namespace bookmarks