1 // Copyright 2013 The Chromium Authors
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 "base/substring_set_matcher/substring_set_matcher.h"
6
7 #include <stddef.h>
8
9 #include <set>
10 #include <string>
11 #include <vector>
12
13 #include "testing/gmock/include/gmock/gmock.h"
14 #include "testing/gtest/include/gtest/gtest.h"
15
16 namespace base {
17
18 namespace {
19
TestOnePattern(const std::string & test_string,const std::string & pattern,bool is_match)20 void TestOnePattern(const std::string& test_string,
21 const std::string& pattern,
22 bool is_match) {
23 std::string test = "TestOnePattern(" + test_string + ", " + pattern + ", " +
24 (is_match ? "1" : "0") + ")";
25 std::vector<MatcherStringPattern> patterns;
26 patterns.emplace_back(pattern, 1);
27 SubstringSetMatcher matcher;
28 ASSERT_TRUE(matcher.Build(patterns));
29 std::set<MatcherStringPattern::ID> matches;
30 matcher.Match(test_string, &matches);
31
32 size_t expected_matches = (is_match ? 1 : 0);
33 EXPECT_EQ(expected_matches, matches.size()) << test;
34 EXPECT_EQ(is_match, matches.find(1) != matches.end()) << test;
35 }
36
TestTwoPatterns(const std::string & test_string,const std::string & pattern_1,const std::string & pattern_2,bool is_match_1,bool is_match_2)37 void TestTwoPatterns(const std::string& test_string,
38 const std::string& pattern_1,
39 const std::string& pattern_2,
40 bool is_match_1,
41 bool is_match_2) {
42 std::string test = "TestTwoPatterns(" + test_string + ", " + pattern_1 +
43 ", " + pattern_2 + ", " + (is_match_1 ? "1" : "0") + ", " +
44 (is_match_2 ? "1" : "0") + ")";
45 ASSERT_NE(pattern_1, pattern_2);
46 MatcherStringPattern substring_pattern_1(pattern_1, 1);
47 MatcherStringPattern substring_pattern_2(pattern_2, 2);
48 // In order to make sure that the order in which patterns are registered
49 // does not make any difference we try both permutations.
50 for (int permutation = 0; permutation < 2; ++permutation) {
51 std::vector<const MatcherStringPattern*> patterns;
52 if (permutation == 0) {
53 patterns.push_back(&substring_pattern_1);
54 patterns.push_back(&substring_pattern_2);
55 } else {
56 patterns.push_back(&substring_pattern_2);
57 patterns.push_back(&substring_pattern_1);
58 }
59 SubstringSetMatcher matcher;
60 ASSERT_TRUE(matcher.Build(patterns));
61 std::set<MatcherStringPattern::ID> matches;
62 matcher.Match(test_string, &matches);
63
64 size_t expected_matches = (is_match_1 ? 1 : 0) + (is_match_2 ? 1 : 0);
65 EXPECT_EQ(expected_matches, matches.size()) << test;
66 EXPECT_EQ(is_match_1, matches.find(1) != matches.end()) << test;
67 EXPECT_EQ(is_match_2, matches.find(2) != matches.end()) << test;
68 }
69 }
70
71 } // namespace
72
TEST(SubstringSetMatcherTest,TestMatcher)73 TEST(SubstringSetMatcherTest, TestMatcher) {
74 // Test overlapping patterns
75 // String abcde
76 // Pattern 1 bc
77 // Pattern 2 cd
78 TestTwoPatterns("abcde", "bc", "cd", true, true);
79 if (HasFatalFailure())
80 return;
81
82 // Test subpatterns - part 1
83 // String abcde
84 // Pattern 1 bc
85 // Pattern 2 b
86 TestTwoPatterns("abcde", "bc", "b", true, true);
87 if (HasFatalFailure())
88 return;
89
90 // Test subpatterns - part 2
91 // String abcde
92 // Pattern 1 bc
93 // Pattern 2 c
94 TestTwoPatterns("abcde", "bc", "c", true, true);
95 if (HasFatalFailure())
96 return;
97
98 // Test identical matches
99 // String abcde
100 // Pattern 1 abcde
101 TestOnePattern("abcde", "abcde", true);
102 if (HasFatalFailure())
103 return;
104
105 // Test multiple matches
106 // String aaaaa
107 // Pattern 1 a
108 TestOnePattern("abcde", "a", true);
109 if (HasFatalFailure())
110 return;
111
112 // Test matches at beginning and end
113 // String abcde
114 // Pattern 1 ab
115 // Pattern 2 de
116 TestTwoPatterns("abcde", "ab", "de", true, true);
117 if (HasFatalFailure())
118 return;
119
120 // Test non-match
121 // String abcde
122 // Pattern 1 fg
123 TestOnePattern("abcde", "fg", false);
124 if (HasFatalFailure())
125 return;
126
127 // Test empty pattern and too long pattern
128 // String abcde
129 // Pattern 1
130 // Pattern 2 abcdef
131 TestTwoPatterns("abcde", std::string(), "abcdef", true, false);
132 if (HasFatalFailure())
133 return;
134 }
135
TEST(SubstringSetMatcherTest,TestMatcher2)136 TEST(SubstringSetMatcherTest, TestMatcher2) {
137 MatcherStringPattern pattern_1("a", 1);
138 MatcherStringPattern pattern_2("b", 2);
139 MatcherStringPattern pattern_3("c", 3);
140
141 std::vector<const MatcherStringPattern*> patterns = {&pattern_1, &pattern_2,
142 &pattern_3};
143 auto matcher = std::make_unique<SubstringSetMatcher>();
144 ASSERT_TRUE(matcher->Build(patterns));
145
146 std::set<MatcherStringPattern::ID> matches;
147 matcher->Match("abd", &matches);
148 EXPECT_EQ(2u, matches.size());
149 EXPECT_TRUE(matches.end() != matches.find(1));
150 EXPECT_TRUE(matches.end() != matches.find(2));
151
152 patterns = {&pattern_1, &pattern_3};
153 matcher = std::make_unique<SubstringSetMatcher>();
154 ASSERT_TRUE(matcher->Build(patterns));
155
156 matches.clear();
157 matcher->Match("abd", &matches);
158 EXPECT_EQ(1u, matches.size());
159 EXPECT_TRUE(matches.end() != matches.find(1));
160 EXPECT_TRUE(matches.end() == matches.find(2));
161
162 matcher = std::make_unique<SubstringSetMatcher>();
163 ASSERT_TRUE(matcher->Build(std::vector<const MatcherStringPattern*>()));
164 EXPECT_TRUE(matcher->IsEmpty());
165 }
166
TEST(SubstringSetMatcherTest,TestMatcher3)167 TEST(SubstringSetMatcherTest, TestMatcher3) {
168 std::string text = "abcde";
169
170 std::vector<MatcherStringPattern> patterns;
171 int id = 0;
172 // Add all substrings of this string, including empty string.
173 patterns.emplace_back("", id++);
174 for (size_t i = 0; i < text.length(); i++) {
175 for (size_t j = i; j < text.length(); j++) {
176 patterns.emplace_back(text.substr(i, j - i + 1), id++);
177 }
178 }
179
180 SubstringSetMatcher matcher;
181 matcher.Build(patterns);
182 std::set<MatcherStringPattern::ID> matches;
183 matcher.Match(text, &matches);
184 EXPECT_EQ(patterns.size(), matches.size());
185 for (const MatcherStringPattern& pattern : patterns) {
186 EXPECT_TRUE(matches.find(pattern.id()) != matches.end())
187 << pattern.pattern();
188 }
189 }
190
TEST(SubstringSetMatcherTest,TestEmptyMatcher)191 TEST(SubstringSetMatcherTest, TestEmptyMatcher) {
192 std::vector<MatcherStringPattern> patterns;
193 SubstringSetMatcher matcher;
194 matcher.Build(patterns);
195 std::set<MatcherStringPattern::ID> matches;
196 matcher.Match("abd", &matches);
197 EXPECT_TRUE(matches.empty());
198 EXPECT_TRUE(matcher.IsEmpty());
199 }
200
201 // Test a case where we have more than 256 edges from one node
202 // (the “a” node gets one for each possible ASCII bytes, and then
203 // one for the output link).
TEST(SubstringSetMatcherTest,LotsOfEdges)204 TEST(SubstringSetMatcherTest, LotsOfEdges) {
205 std::vector<MatcherStringPattern> patterns;
206 for (int i = 0; i < 256; ++i) {
207 std::string str;
208 str.push_back('a');
209 str.push_back(static_cast<char>(i));
210 patterns.emplace_back(str, i);
211 }
212
213 {
214 std::string str;
215 str.push_back('a');
216 patterns.emplace_back(str, 256);
217 }
218
219 SubstringSetMatcher matcher;
220 matcher.Build(patterns);
221 }
222
223 } // namespace base
224