Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(273)

Side by Side Diff: components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc

Issue 2793993002: [subresource_filter] Replace KMP by std::search. (Closed)
Patch Set: Fix tests. Created 3 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698