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