1b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 2b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)// found in the LICENSE file. 4b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 51320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "ui/app_list/search/tokenized_string_match.h" 61320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 7b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)#include <string> 8b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 9b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)#include "base/basictypes.h" 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/utf_string_conversions.h" 11b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 12b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 13b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)namespace app_list { 14b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)namespace test { 15b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 16b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)// Returns a string of |text| marked the hits in |match| using block bracket. 17b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)// e.g. text= "Text", hits = [{0,1}], returns "[T]ext". 18a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)std::string MatchHit(const base::string16& text, 19b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const TokenizedStringMatch& match) { 20a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) base::string16 marked = text; 21b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 22b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const TokenizedStringMatch::Hits& hits = match.hits(); 23b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) for (TokenizedStringMatch::Hits::const_reverse_iterator it = hits.rbegin(); 24b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) it != hits.rend(); ++it) { 2558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const gfx::Range& hit = *it; 26b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) marked.insert(hit.end(), 1, ']'); 27b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) marked.insert(hit.start(), 1, '['); 28b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 29b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return base::UTF16ToUTF8(marked); 31b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 32b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 33b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)TEST(TokenizedStringMatchTest, NotMatch) { 34b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) struct { 35b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* text; 36b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* query; 37b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } kTestCases[] = { 38b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "", "" }, 39b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "", "query" }, 40b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "text", "" }, 41b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "!", "!@#$%^&*()<<<**>>>" }, 42b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "abd", "abcd"}, 43b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "cd", "abcd"}, 44b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) }; 45b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 46b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) TokenizedStringMatch match; 47b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) for (size_t i = 0; i < ARRAYSIZE_UNSAFE(kTestCases); ++i) { 485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const base::string16 text(base::UTF8ToUTF16(kTestCases[i].text)); 495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EXPECT_FALSE(match.Calculate(base::UTF8ToUTF16(kTestCases[i].query), text)) 50b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << "Test case " << i 51b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << " : text=" << kTestCases[i].text 52b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << ", query=" << kTestCases[i].query; 53b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 54b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 55b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 56b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)TEST(TokenizedStringMatchTest, Match) { 57b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) struct { 58b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* text; 59b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* query; 60b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* expect; 61b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } kTestCases[] = { 62b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "ScratchPad", "pad", "Scratch[Pad]" }, 63b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "ScratchPad", "sp", "[S]cratch[P]ad" }, 64b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Chess2", "che", "[Che]ss2" }, 65b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Chess2", "c2", "[C]hess[2]" }, 66b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Cut the rope", "cut ro", "[Cut] the [ro]pe" }, 67b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Cut the rope", "cr", "[C]ut the [r]ope" }, 68b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "John Doe", "jdoe", "[J]ohn [Doe]" }, 69b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "John Doe", "johnd", "[John D]oe" }, 700529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Secure Shell", "she", "Secure [She]ll" }, 710529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Simple Secure Shell", "sish", "[Si]mple Secure [Sh]ell" }, 720529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Netflix", "flix", "Net[flix]" }, 73b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) }; 74b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 75b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) TokenizedStringMatch match; 76b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) for (size_t i = 0; i < ARRAYSIZE_UNSAFE(kTestCases); ++i) { 775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const base::string16 text(base::UTF8ToUTF16(kTestCases[i].text)); 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EXPECT_TRUE(match.Calculate(base::UTF8ToUTF16(kTestCases[i].query), text)); 79b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) EXPECT_EQ(kTestCases[i].expect, MatchHit(text, match)); 80b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 81b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 82b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 83b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)TEST(TokenizedStringMatchTest, Relevance) { 84b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) struct { 85b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* text; 86b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* query_low; 87b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const char* query_high; 88b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } kTestCases[] = { 89b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // More matched chars are better. 90b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "g", "go" }, 91b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "go", "goo" }, 92b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "goo", "goog" }, 93b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "c", "ch" }, 94b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "ch", "chr" }, 95b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // Acronym match is better than something in the middle. 96b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "ch", "gc" }, 97b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // Prefix match is better than middle match and acronym match. 98b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "ch", "go" }, 99b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) { "Google Chrome", "gc", "go" }, 1000529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // Substring match has the lowest score. 1010529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Google Chrome", "oo", "gc" }, 1020529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Google Chrome", "oo", "go" }, 1030529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch { "Google Chrome", "oo", "ch" }, 104b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) }; 105b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 106b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) TokenizedStringMatch match_low; 107b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) TokenizedStringMatch match_high; 108b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) for (size_t i = 0; i < ARRAYSIZE_UNSAFE(kTestCases); ++i) { 1095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const base::string16 text(base::UTF8ToUTF16(kTestCases[i].text)); 110b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) EXPECT_TRUE( 1115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) match_low.Calculate(base::UTF8ToUTF16(kTestCases[i].query_low), text)); 1125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EXPECT_TRUE(match_high.Calculate( 1135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::UTF8ToUTF16(kTestCases[i].query_high), text)); 114b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) EXPECT_LT(match_low.relevance(), match_high.relevance()) 115b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << "Test case " << i 116b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << " : text=" << kTestCases[i].text 117b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << ", query_low=" << kTestCases[i].query_low 118b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) << ", query_high=" << kTestCases[i].query_high; 119b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 120b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 121b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 122b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} // namespace test 123b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} // namespace app_list 124