OLD | NEW |
| (Empty) |
1 // Copyright 2016 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/subresource_filter/core/common/knuth_morris_pratt.h" | |
6 | |
7 #include <cctype> | |
8 #include <functional> | |
9 #include <string> | |
10 #include <vector> | |
11 | |
12 #include "testing/gtest/include/gtest/gtest.h" | |
13 | |
14 namespace subresource_filter { | |
15 | |
16 namespace { | |
17 | |
18 bool NumerophobicEquivalentTo(char first, char second) { | |
19 return first == second || (std::isdigit(first) && std::isdigit(second)); | |
20 } | |
21 | |
22 template <typename EquivalentTo = std::equal_to<char>> | |
23 std::vector<size_t> FindAllOccurrences( | |
24 base::StringPiece string, | |
25 base::StringPiece pattern, | |
26 const std::vector<size_t>& failure_function, | |
27 EquivalentTo equivalent_to = EquivalentTo()) { | |
28 std::vector<size_t> positions; | |
29 | |
30 size_t position = 0; | |
31 size_t relative_position = FindFirstOccurrence( | |
32 string, pattern, failure_function.data(), equivalent_to); | |
33 | |
34 while (relative_position != base::StringPiece::npos) { | |
35 position += relative_position; | |
36 positions.push_back(position); | |
37 relative_position = | |
38 FindNextOccurrence(string.substr(position), pattern, | |
39 failure_function.data(), equivalent_to); | |
40 } | |
41 | |
42 return positions; | |
43 } | |
44 | |
45 } // namespace | |
46 | |
47 TEST(KnuthMorrisPrattTest, BuildFailureFunctionRegular) { | |
48 const struct { | |
49 std::string string; | |
50 std::vector<size_t> expected_failure_function; | |
51 } kTestCases[] = { | |
52 {"", std::vector<size_t>()}, | |
53 {"a", {0}}, | |
54 {"aa", {0, 1}}, | |
55 {"aaa", {0, 1, 2}}, | |
56 {"abc", {0, 0, 0}}, | |
57 {"abca", {0, 0, 0, 1}}, | |
58 {"abacaba", {0, 0, 1, 0, 1, 2, 3}}, | |
59 {"str-sstrr", {0, 0, 0, 0, 1, 1, 2, 3, 0}}, | |
60 {"sts-ststs", {0, 0, 1, 0, 1, 2, 3, 2, 3}}, | |
61 }; | |
62 | |
63 for (const auto& test_case : kTestCases) { | |
64 SCOPED_TRACE(testing::Message() << "String: " << test_case.string); | |
65 | |
66 std::vector<size_t> failure; | |
67 BuildFailureFunction(test_case.string, &failure); | |
68 EXPECT_EQ(test_case.expected_failure_function, failure); | |
69 } | |
70 } | |
71 | |
72 TEST(KnuthMorrisPrattTest, BuildFailureFunctionWithEquivalentChars) { | |
73 const struct { | |
74 std::string string; | |
75 std::vector<size_t> expected_failure_function; | |
76 } kTestCases[] = { | |
77 {"123", {0, 1, 2}}, | |
78 {"0str1str", {0, 0, 0, 0, 1, 2, 3, 4}}, | |
79 {"7str8srr", {0, 0, 0, 0, 1, 2, 0, 0}}, | |
80 {"567str9sr", {0, 1, 2, 0, 0, 0, 1, 0, 0}}, | |
81 {"567str999sr", {0, 1, 2, 0, 0, 0, 1, 2, 3, 4, 0}}, | |
82 {"str9sr6", {0, 0, 0, 0, 1, 0, 0}}, | |
83 {"5a6a7a8a9a", {0, 0, 1, 2, 3, 4, 5, 6, 7, 8}}, | |
84 }; | |
85 | |
86 for (const auto& test_case : kTestCases) { | |
87 SCOPED_TRACE(testing::Message() << "String: " << test_case.string); | |
88 | |
89 std::vector<size_t> failure; | |
90 BuildFailureFunction(test_case.string, &failure, NumerophobicEquivalentTo); | |
91 EXPECT_EQ(test_case.expected_failure_function, failure); | |
92 } | |
93 } | |
94 | |
95 TEST(KnuthMorrisPrattTest, FindSubstringsRegular) { | |
96 const struct { | |
97 std::string string; | |
98 std::string pattern; | |
99 std::vector<size_t> expected_positions; | |
100 } kTestCases[] = { | |
101 {"", "abc", std::vector<size_t>()}, | |
102 {"abc", "", {0, 1, 2, 3}}, | |
103 {"abc", "abc", {3}}, | |
104 {"aaaabc", "abc", {6}}, | |
105 {"abcccc", "abc", {3}}, | |
106 {"aabcc", "abc", {4}}, | |
107 {"aabcabcabcc", "abc", {4, 7, 10}}, | |
108 {"abcabcabc", "abc", {3, 6, 9}}, | |
109 {"abab", "abc", std::vector<size_t>()}, | |
110 {"ababac", "abc", std::vector<size_t>()}, | |
111 {"aaaaaa", "a", {1, 2, 3, 4, 5, 6}}, | |
112 {"aaaaaa", "aaa", {3, 4, 5, 6}}, | |
113 {"abababa", "aba", {3, 5, 7}}, | |
114 {"acdacdacdac", "cdacd", {6, 9}}, | |
115 }; | |
116 | |
117 for (const auto& test_case : kTestCases) { | |
118 SCOPED_TRACE(testing::Message() << "String: " << test_case.string | |
119 << "; Pattern: " << test_case.pattern); | |
120 | |
121 std::vector<size_t> failure; | |
122 BuildFailureFunction(test_case.pattern, &failure); | |
123 | |
124 std::vector<size_t> positions = | |
125 FindAllOccurrences(test_case.string, test_case.pattern, failure); | |
126 EXPECT_EQ(test_case.expected_positions, positions); | |
127 | |
128 auto occurrences = CreateAllOccurrences(test_case.string, test_case.pattern, | |
129 failure.data()); | |
130 positions.assign(occurrences.begin(), occurrences.end()); | |
131 EXPECT_EQ(test_case.expected_positions, positions); | |
132 } | |
133 } | |
134 | |
135 TEST(KnuthMorrisPrattTest, FindSubstringsWithEquivalentChars) { | |
136 const struct { | |
137 std::string string; | |
138 std::string pattern; | |
139 std::vector<size_t> expected_positions; | |
140 } kTestCases[] = { | |
141 {"", "abc", std::vector<size_t>()}, | |
142 {"012", "1", {1, 2, 3}}, | |
143 {"012", "012", {3}}, | |
144 {"123456", "000", {3, 4, 5, 6}}, | |
145 {"0a1a2a3a", "1a2", {3, 5, 7}}, | |
146 {"0aa1a2aa3a", "1aa2", {4, 9}}, | |
147 }; | |
148 | |
149 for (const auto& test_case : kTestCases) { | |
150 SCOPED_TRACE(testing::Message() << "String: " << test_case.string | |
151 << "; Pattern: " << test_case.pattern); | |
152 | |
153 std::vector<size_t> failure; | |
154 BuildFailureFunction(test_case.pattern, &failure, NumerophobicEquivalentTo); | |
155 | |
156 std::vector<size_t> positions = FindAllOccurrences( | |
157 test_case.string, test_case.pattern, failure, NumerophobicEquivalentTo); | |
158 EXPECT_EQ(test_case.expected_positions, positions); | |
159 | |
160 auto occurrences = | |
161 CreateAllOccurrences(test_case.string, test_case.pattern, | |
162 failure.data(), NumerophobicEquivalentTo); | |
163 positions.assign(occurrences.begin(), occurrences.end()); | |
164 EXPECT_EQ(test_case.expected_positions, positions); | |
165 } | |
166 } | |
167 | |
168 TEST(KnuthMorrisPrattTest, AllOccurrencesIterator) { | |
169 const struct { | |
170 std::string string; | |
171 std::string pattern; | |
172 std::vector<size_t> expected_positions; | |
173 } kTestCases[] = { | |
174 {"", "abc", std::vector<size_t>()}, | |
175 {"abc", "", {0, 1, 2, 3}}, | |
176 {"abc", "abc", {3}}, | |
177 {"aaa", "a", {1, 2, 3}}, | |
178 {"aaaabc", "abc", {6}}, | |
179 }; | |
180 | |
181 for (const auto& test_case : kTestCases) { | |
182 SCOPED_TRACE(testing::Message() << "String: " << test_case.string | |
183 << "; Pattern: " << test_case.pattern); | |
184 | |
185 std::vector<size_t> failure; | |
186 BuildFailureFunction(test_case.pattern, &failure); | |
187 | |
188 auto occurrences = CreateAllOccurrences(test_case.string, test_case.pattern, | |
189 failure.data()); | |
190 | |
191 auto iterator = occurrences.begin(); | |
192 const size_t size = test_case.expected_positions.size(); | |
193 for (size_t i = 0; i != size; ++i, ++iterator) { | |
194 const size_t expected_position = test_case.expected_positions[i]; | |
195 EXPECT_EQ(expected_position, *iterator); | |
196 | |
197 auto iterator_copy = iterator; | |
198 EXPECT_EQ(iterator, iterator_copy); | |
199 EXPECT_EQ(expected_position, *iterator_copy); | |
200 | |
201 EXPECT_EQ(iterator_copy, iterator++); | |
202 EXPECT_NE(iterator_copy, iterator); | |
203 if (i + 1 != size) { | |
204 EXPECT_NE(occurrences.end(), iterator); | |
205 EXPECT_EQ(test_case.expected_positions[i + 1], *iterator); | |
206 } else { | |
207 EXPECT_EQ(occurrences.end(), iterator); | |
208 } | |
209 | |
210 iterator = iterator_copy; | |
211 EXPECT_EQ(expected_position, *iterator); | |
212 } | |
213 | |
214 EXPECT_EQ(occurrences.end(), iterator); | |
215 } | |
216 } | |
217 | |
218 } // namespace subresource_filter | |
OLD | NEW |