OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "components/subresource_filter/core/common/fuzzy_pattern_matching.h" | 5 #include "components/subresource_filter/core/common/fuzzy_pattern_matching.h" |
6 | 6 |
7 #include <vector> | |
8 | |
9 #include "testing/gtest/include/gtest/gtest.h" | 7 #include "testing/gtest/include/gtest/gtest.h" |
10 | 8 |
11 namespace subresource_filter { | 9 namespace subresource_filter { |
12 | 10 |
13 TEST(FuzzyPatternMatchingTest, StartsWithFuzzy) { | 11 TEST(SubresourceFilterFuzzyPatternMatchingTest, StartsWithFuzzy) { |
14 const struct { | 12 const struct { |
15 const char* text; | 13 const char* text; |
16 const char* subpattern; | 14 const char* subpattern; |
17 bool expected_starts_with; | 15 bool expected_starts_with; |
18 } kTestCases[] = { | 16 } kTestCases[] = { |
19 {"abc", "", true}, {"abc", "a", true}, {"abc", "ab", true}, | 17 {"abc", "", true}, {"abc", "a", true}, {"abc", "ab", true}, |
20 {"abc", "abc", true}, {"abc", "abcd", false}, {"abc", "abc^^", false}, | 18 {"abc", "abc", true}, {"abc", "abcd", false}, {"abc", "abc^^", false}, |
21 {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "bc", false}, | 19 {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "bc", false}, |
22 {"abc", "bc^", false}, {"abc", "^abc", false}, | 20 {"abc", "bc^", false}, {"abc", "^abc", false}, |
23 }; | 21 }; |
24 // TODO(pkalinnikov): Make end-of-string match '^' again. | 22 // TODO(pkalinnikov): Make end-of-string match '^' again. |
25 | 23 |
26 for (const auto& test_case : kTestCases) { | 24 for (const auto& test_case : kTestCases) { |
27 SCOPED_TRACE(testing::Message() | 25 SCOPED_TRACE(testing::Message() |
28 << "Test: " << test_case.text | 26 << "Test: " << test_case.text |
29 << "; Subpattern: " << test_case.subpattern); | 27 << "; Subpattern: " << test_case.subpattern); |
30 | 28 |
31 const bool starts_with = | 29 const bool starts_with = |
32 StartsWithFuzzy(test_case.text, test_case.subpattern); | 30 StartsWithFuzzy(test_case.text, test_case.subpattern); |
33 EXPECT_EQ(test_case.expected_starts_with, starts_with); | 31 EXPECT_EQ(test_case.expected_starts_with, starts_with); |
34 } | 32 } |
35 } | 33 } |
36 | 34 |
37 TEST(FuzzyPatternMatchingTest, EndsWithFuzzy) { | 35 TEST(SubresourceFilterFuzzyPatternMatchingTest, EndsWithFuzzy) { |
38 const struct { | 36 const struct { |
39 const char* text; | 37 const char* text; |
40 const char* subpattern; | 38 const char* subpattern; |
41 bool expected_ends_with; | 39 bool expected_ends_with; |
42 } kTestCases[] = { | 40 } kTestCases[] = { |
43 {"abc", "", true}, {"abc", "c", true}, {"abc", "bc", true}, | 41 {"abc", "", true}, {"abc", "c", true}, {"abc", "bc", true}, |
44 {"abc", "abc", true}, {"abc", "0abc", false}, {"abc", "abc^^", false}, | 42 {"abc", "abc", true}, {"abc", "0abc", false}, {"abc", "abc^^", false}, |
45 {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "ab", false}, | 43 {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "ab", false}, |
46 {"abc", "^abc", false}, | 44 {"abc", "^abc", false}, |
47 }; | 45 }; |
48 // TODO(pkalinnikov): Make end-of-string match '^' again. | 46 // TODO(pkalinnikov): Make end-of-string match '^' again. |
49 | 47 |
50 for (const auto& test_case : kTestCases) { | 48 for (const auto& test_case : kTestCases) { |
51 SCOPED_TRACE(testing::Message() | 49 SCOPED_TRACE(testing::Message() |
52 << "Test: " << test_case.text | 50 << "Test: " << test_case.text |
53 << "; Subpattern: " << test_case.subpattern); | 51 << "; Subpattern: " << test_case.subpattern); |
54 | 52 |
55 const bool ends_with = EndsWithFuzzy(test_case.text, test_case.subpattern); | 53 const bool ends_with = EndsWithFuzzy(test_case.text, test_case.subpattern); |
56 EXPECT_EQ(test_case.expected_ends_with, ends_with); | 54 EXPECT_EQ(test_case.expected_ends_with, ends_with); |
57 } | 55 } |
58 } | 56 } |
59 TEST(FuzzyPatternMatchingTest, AllOccurrences) { | |
60 const struct { | |
61 const char* text; | |
62 const char* subpattern; | |
63 std::vector<size_t> expected_matches; | |
64 } kTestCases[] = { | |
65 {"abcd", "", {0, 1, 2, 3, 4}}, | |
66 {"abcd", "de", std::vector<size_t>()}, | |
67 {"abcd", "ab", {2}}, | |
68 {"abcd", "bc", {3}}, | |
69 {"abcd", "cd", {4}}, | |
70 | |
71 {"a/bc/a/b", "", {0, 1, 2, 3, 4, 5, 6, 7, 8}}, | |
72 {"a/bc/a/b", "de", std::vector<size_t>()}, | |
73 {"a/bc/a/b", "a/", {2, 7}}, | |
74 {"a/bc/a/c", "a/c", {8}}, | |
75 {"a/bc/a/c", "a^c", {8}}, | |
76 {"a/bc/a/c", "a?c", std::vector<size_t>()}, | |
77 | |
78 {"ab^cd", "ab/cd", std::vector<size_t>()}, | |
79 {"ab^cd", "b/c", std::vector<size_t>()}, | |
80 {"ab^cd", "ab^cd", {5}}, | |
81 {"ab^cd", "b^c", {4}}, | |
82 {"ab^b/b", "b/b", {6}}, | |
83 | |
84 {"a/a/a/a", "a/a", {3, 5, 7}}, | |
85 {"a/a/a/a", "^a^a^a", {7}}, | |
86 {"a/a/a/a", "^a^a?a", std::vector<size_t>()}, | |
87 {"a/a/a/a", "?a?a?a", std::vector<size_t>()}, | |
88 }; | |
89 | |
90 for (const auto& test_case : kTestCases) { | |
91 SCOPED_TRACE(testing::Message() | |
92 << "Test: " << test_case.text | |
93 << "; Subpattern: " << test_case.subpattern); | |
94 | |
95 std::vector<size_t> failure; | |
96 BuildFailureFunctionFuzzy(test_case.subpattern, &failure); | |
97 | |
98 const auto& occurrences = AllOccurrencesFuzzy<size_t>( | |
99 test_case.text, test_case.subpattern, failure.data()); | |
100 std::vector<size_t> matches(occurrences.begin(), occurrences.end()); | |
101 EXPECT_EQ(test_case.expected_matches, matches); | |
102 } | |
103 } | |
104 | 57 |
105 } // namespace subresource_filter | 58 } // namespace subresource_filter |
OLD | NEW |