1// Copyright 2013 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/url_matcher/substring_set_matcher.h"
6
7#include <set>
8#include <string>
9#include <vector>
10
11#include "testing/gtest/include/gtest/gtest.h"
12
13namespace url_matcher {
14
15namespace {
16
17void TestOnePattern(const std::string& test_string,
18                    const std::string& pattern,
19                    bool is_match) {
20  std::string test =
21      "TestOnePattern(" + test_string + ", " + pattern + ", " +
22      (is_match ? "1" : "0") + ")";
23  std::vector<const StringPattern*> patterns;
24  StringPattern substring_pattern(pattern, 1);
25  patterns.push_back(&substring_pattern);
26  SubstringSetMatcher matcher;
27  matcher.RegisterPatterns(patterns);
28  std::set<int> matches;
29  matcher.Match(test_string, &matches);
30
31  size_t expected_matches = (is_match ? 1 : 0);
32  EXPECT_EQ(expected_matches, matches.size()) << test;
33  EXPECT_EQ(is_match, matches.find(1) != matches.end()) << test;
34}
35
36void TestTwoPatterns(const std::string& test_string,
37                     const std::string& pattern_1,
38                     const std::string& pattern_2,
39                     bool is_match_1,
40                     bool is_match_2) {
41  std::string test =
42      "TestTwoPatterns(" + test_string + ", " + pattern_1 + ", " + pattern_2 +
43      ", " + (is_match_1 ? "1" : "0") + ", " + (is_match_2 ? "1" : "0") + ")";
44  StringPattern substring_pattern_1(pattern_1, 1);
45  StringPattern substring_pattern_2(pattern_2, 2);
46  // In order to make sure that the order in which patterns are registered
47  // does not make any difference we try both permutations.
48  for (int permutation = 0; permutation < 2; ++permutation) {
49    std::vector<const StringPattern*> patterns;
50    if (permutation == 0) {
51      patterns.push_back(&substring_pattern_1);
52      patterns.push_back(&substring_pattern_2);
53    } else {
54      patterns.push_back(&substring_pattern_2);
55      patterns.push_back(&substring_pattern_1);
56    }
57    SubstringSetMatcher matcher;
58    matcher.RegisterPatterns(patterns);
59    std::set<int> matches;
60    matcher.Match(test_string, &matches);
61
62    size_t expected_matches = (is_match_1 ? 1 : 0) + (is_match_2 ? 1 : 0);
63    EXPECT_EQ(expected_matches, matches.size()) << test;
64    EXPECT_EQ(is_match_1, matches.find(1) != matches.end()) << test;
65    EXPECT_EQ(is_match_2, matches.find(2) != matches.end()) << test;
66  }
67}
68
69}  // namespace
70
71TEST(SubstringSetMatcherTest, TestMatcher) {
72  // Test overlapping patterns
73  // String    abcde
74  // Pattern 1  bc
75  // Pattern 2   cd
76  TestTwoPatterns("abcde", "bc", "cd", true, true);
77
78  // Test subpatterns - part 1
79  // String    abcde
80  // Pattern 1  bc
81  // Pattern 2  b
82  TestTwoPatterns("abcde", "bc", "b", true, true);
83
84  // Test subpatterns - part 2
85  // String    abcde
86  // Pattern 1  bc
87  // Pattern 2   c
88  TestTwoPatterns("abcde", "bc", "c", true, true);
89
90  // Test identical matches
91  // String    abcde
92  // Pattern 1 abcde
93  TestOnePattern("abcde", "abcde", true);
94
95  // Test multiple matches
96  // String    aaaaa
97  // Pattern 1 a
98  TestOnePattern("abcde", "a", true);
99
100  // Test matches at beginning and end
101  // String    abcde
102  // Pattern 1 ab
103  // Pattern 2    de
104  TestTwoPatterns("abcde", "ab", "de", true, true);
105
106  // Test duplicate patterns with different IDs
107  // String    abcde
108  // Pattern 1  bc
109  // Pattern 2  bc
110  TestTwoPatterns("abcde", "bc", "bc", true, true);
111
112  // Test non-match
113  // String    abcde
114  // Pattern 1        fg
115  TestOnePattern("abcde", "fg", false);
116
117  // Test empty pattern and too long pattern
118  // String    abcde
119  // Pattern 1
120  // Pattern 2 abcdef
121  TestTwoPatterns("abcde", std::string(), "abcdef", true, false);
122}
123
124TEST(SubstringSetMatcherTest, RegisterAndRemove) {
125  SubstringSetMatcher matcher;
126
127  StringPattern pattern_1("a", 1);
128  StringPattern pattern_2("b", 2);
129  StringPattern pattern_3("c", 3);
130
131  std::vector<const StringPattern*> patterns;
132  patterns.push_back(&pattern_1);
133  matcher.RegisterPatterns(patterns);
134
135  patterns.clear();
136  patterns.push_back(&pattern_2);
137  patterns.push_back(&pattern_3);
138  matcher.RegisterPatterns(patterns);
139
140  std::set<int> matches;
141  matcher.Match("abd", &matches);
142  EXPECT_EQ(2u, matches.size());
143  EXPECT_TRUE(matches.end() != matches.find(1));
144  EXPECT_TRUE(matches.end() != matches.find(2));
145
146  patterns.clear();
147  patterns.push_back(&pattern_2);
148  matcher.UnregisterPatterns(patterns);
149
150  matches.clear();
151  matcher.Match("abd", &matches);
152  EXPECT_EQ(1u, matches.size());
153  EXPECT_TRUE(matches.end() != matches.find(1));
154  EXPECT_TRUE(matches.end() == matches.find(2));
155
156  patterns.clear();
157  patterns.push_back(&pattern_1);
158  patterns.push_back(&pattern_3);
159  matcher.UnregisterPatterns(patterns);
160  EXPECT_TRUE(matcher.IsEmpty());
161}
162
163TEST(SubstringSetMatcherTest, TestEmptyMatcher) {
164  SubstringSetMatcher matcher;
165  std::set<int> matches;
166  matcher.Match("abd", &matches);
167  EXPECT_TRUE(matches.empty());
168}
169
170}  // namespace url_matcher
171