15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "components/url_matcher/substring_set_matcher.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace url_matcher { 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestOnePattern(const std::string& test_string, 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& pattern, 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool is_match) { 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string test = 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "TestOnePattern(" + test_string + ", " + pattern + ", " + 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (is_match ? "1" : "0") + ")"; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<const StringPattern*> patterns; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern substring_pattern(pattern, 1); 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&substring_pattern); 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubstringSetMatcher matcher; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.RegisterPatterns(patterns); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<int> matches; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.Match(test_string, &matches); 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t expected_matches = (is_match ? 1 : 0); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(expected_matches, matches.size()) << test; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(is_match, matches.find(1) != matches.end()) << test; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestTwoPatterns(const std::string& test_string, 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& pattern_1, 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& pattern_2, 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool is_match_1, 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool is_match_2) { 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string test = 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "TestTwoPatterns(" + test_string + ", " + pattern_1 + ", " + pattern_2 + 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ", " + (is_match_1 ? "1" : "0") + ", " + (is_match_2 ? "1" : "0") + ")"; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern substring_pattern_1(pattern_1, 1); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern substring_pattern_2(pattern_2, 2); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In order to make sure that the order in which patterns are registered 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // does not make any difference we try both permutations. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int permutation = 0; permutation < 2; ++permutation) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<const StringPattern*> patterns; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (permutation == 0) { 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&substring_pattern_1); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&substring_pattern_2); 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&substring_pattern_2); 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&substring_pattern_1); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubstringSetMatcher matcher; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.RegisterPatterns(patterns); 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<int> matches; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.Match(test_string, &matches); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t expected_matches = (is_match_1 ? 1 : 0) + (is_match_2 ? 1 : 0); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(expected_matches, matches.size()) << test; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(is_match_1, matches.find(1) != matches.end()) << test; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(is_match_2, matches.find(2) != matches.end()) << test; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SubstringSetMatcherTest, TestMatcher) { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test overlapping patterns 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 bc 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 cd 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestTwoPatterns("abcde", "bc", "cd", true, true); 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test subpatterns - part 1 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 bc 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 b 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestTwoPatterns("abcde", "bc", "b", true, true); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test subpatterns - part 2 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 bc 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 c 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestTwoPatterns("abcde", "bc", "c", true, true); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test identical matches 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 abcde 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestOnePattern("abcde", "abcde", true); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test multiple matches 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String aaaaa 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 a 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestOnePattern("abcde", "a", true); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test matches at beginning and end 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 ab 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 de 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestTwoPatterns("abcde", "ab", "de", true, true); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test duplicate patterns with different IDs 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 bc 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 bc 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestTwoPatterns("abcde", "bc", "bc", true, true); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test non-match 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 fg 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestOnePattern("abcde", "fg", false); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test empty pattern and too long pattern 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // String abcde 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 1 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pattern 2 abcdef 121c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) TestTwoPatterns("abcde", std::string(), "abcdef", true, false); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SubstringSetMatcherTest, RegisterAndRemove) { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubstringSetMatcher matcher; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern pattern_1("a", 1); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern pattern_2("b", 2); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPattern pattern_3("c", 3); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<const StringPattern*> patterns; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_1); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.RegisterPatterns(patterns); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.clear(); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_2); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_3); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.RegisterPatterns(patterns); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<int> matches; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.Match("abd", &matches); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(2u, matches.size()); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matches.end() != matches.find(1)); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matches.end() != matches.find(2)); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.clear(); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_2); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.UnregisterPatterns(patterns); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches.clear(); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.Match("abd", &matches); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(1u, matches.size()); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matches.end() != matches.find(1)); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matches.end() == matches.find(2)); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.clear(); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_1); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) patterns.push_back(&pattern_3); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.UnregisterPatterns(patterns); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matcher.IsEmpty()); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(SubstringSetMatcherTest, TestEmptyMatcher) { 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubstringSetMatcher matcher; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<int> matches; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matcher.Match("abd", &matches); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(matches.empty()); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace url_matcher 171