1 //===- llvm/unittest/Support/GlobPatternTest.cpp --------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/Support/GlobPattern.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13 namespace {
14
15 class GlobPatternTest : public ::testing::Test {};
16
TEST_F(GlobPatternTest,Empty)17 TEST_F(GlobPatternTest, Empty) {
18 Expected<GlobPattern> Pat1 = GlobPattern::create("");
19 EXPECT_TRUE((bool)Pat1);
20 EXPECT_TRUE(Pat1->match(""));
21 EXPECT_FALSE(Pat1->match("a"));
22 }
23
TEST_F(GlobPatternTest,Glob)24 TEST_F(GlobPatternTest, Glob) {
25 Expected<GlobPattern> Pat1 = GlobPattern::create("ab*c*def");
26 EXPECT_TRUE((bool)Pat1);
27 EXPECT_TRUE(Pat1->match("abcdef"));
28 EXPECT_TRUE(Pat1->match("abxcxdef"));
29 EXPECT_FALSE(Pat1->match(""));
30 EXPECT_FALSE(Pat1->match("xabcdef"));
31 EXPECT_FALSE(Pat1->match("abcdefx"));
32 }
33
TEST_F(GlobPatternTest,Wildcard)34 TEST_F(GlobPatternTest, Wildcard) {
35 Expected<GlobPattern> Pat1 = GlobPattern::create("a??c");
36 EXPECT_TRUE((bool)Pat1);
37 EXPECT_TRUE(Pat1->match("axxc"));
38 EXPECT_FALSE(Pat1->match("axxx"));
39 EXPECT_FALSE(Pat1->match(""));
40 }
41
TEST_F(GlobPatternTest,Escape)42 TEST_F(GlobPatternTest, Escape) {
43 Expected<GlobPattern> Pat1 = GlobPattern::create("\\*");
44 EXPECT_TRUE((bool)Pat1);
45 EXPECT_TRUE(Pat1->match("*"));
46 EXPECT_FALSE(Pat1->match("\\*"));
47 EXPECT_FALSE(Pat1->match("a"));
48
49 Expected<GlobPattern> Pat2 = GlobPattern::create("a?\\?c");
50 EXPECT_TRUE((bool)Pat2);
51 EXPECT_TRUE(Pat2->match("ax?c"));
52 EXPECT_FALSE(Pat2->match("axxc"));
53 EXPECT_FALSE(Pat2->match(""));
54
55 auto Pat3 = GlobPattern::create("\\{");
56 ASSERT_TRUE((bool)Pat3);
57 EXPECT_TRUE(Pat3->match("{"));
58 EXPECT_FALSE(Pat3->match("\\{"));
59 EXPECT_FALSE(Pat3->match(""));
60
61 auto Pat4 = GlobPattern::create("\\a");
62 ASSERT_TRUE((bool)Pat4);
63 EXPECT_TRUE(Pat4->match("a"));
64 EXPECT_FALSE(Pat4->match("\\a"));
65
66 for (size_t I = 0; I != 4; ++I) {
67 std::string S(I, '\\');
68 Expected<GlobPattern> Pat = GlobPattern::create(S);
69 if (I % 2) {
70 EXPECT_FALSE((bool)Pat);
71 handleAllErrors(Pat.takeError(), [&](ErrorInfoBase &) {});
72 } else {
73 EXPECT_TRUE((bool)Pat);
74 }
75 }
76 }
77
TEST_F(GlobPatternTest,BasicCharacterClass)78 TEST_F(GlobPatternTest, BasicCharacterClass) {
79 Expected<GlobPattern> Pat1 = GlobPattern::create("[abc-fy-z]");
80 EXPECT_TRUE((bool)Pat1);
81 EXPECT_TRUE(Pat1->match("a"));
82 EXPECT_TRUE(Pat1->match("b"));
83 EXPECT_TRUE(Pat1->match("c"));
84 EXPECT_TRUE(Pat1->match("d"));
85 EXPECT_TRUE(Pat1->match("e"));
86 EXPECT_TRUE(Pat1->match("f"));
87 EXPECT_TRUE(Pat1->match("y"));
88 EXPECT_TRUE(Pat1->match("z"));
89 EXPECT_FALSE(Pat1->match("g"));
90 EXPECT_FALSE(Pat1->match(""));
91
92 Expected<GlobPattern> Pat2 = GlobPattern::create("[ab]*[cd]?**[ef]");
93 ASSERT_TRUE((bool)Pat2);
94 EXPECT_TRUE(Pat2->match("aecde"));
95 EXPECT_FALSE(Pat2->match("aecdg"));
96 }
97
TEST_F(GlobPatternTest,NegatedCharacterClass)98 TEST_F(GlobPatternTest, NegatedCharacterClass) {
99 Expected<GlobPattern> Pat1 = GlobPattern::create("[^abc-fy-z]");
100 EXPECT_TRUE((bool)Pat1);
101 EXPECT_TRUE(Pat1->match("g"));
102 EXPECT_FALSE(Pat1->match("a"));
103 EXPECT_FALSE(Pat1->match("b"));
104 EXPECT_FALSE(Pat1->match("c"));
105 EXPECT_FALSE(Pat1->match("d"));
106 EXPECT_FALSE(Pat1->match("e"));
107 EXPECT_FALSE(Pat1->match("f"));
108 EXPECT_FALSE(Pat1->match("y"));
109 EXPECT_FALSE(Pat1->match("z"));
110 EXPECT_FALSE(Pat1->match(""));
111
112 Expected<GlobPattern> Pat2 = GlobPattern::create("[!abc-fy-z]");
113 EXPECT_TRUE((bool)Pat2);
114 EXPECT_TRUE(Pat2->match("g"));
115 EXPECT_FALSE(Pat2->match("a"));
116 EXPECT_FALSE(Pat2->match("b"));
117 EXPECT_FALSE(Pat2->match("c"));
118 EXPECT_FALSE(Pat2->match("d"));
119 EXPECT_FALSE(Pat2->match("e"));
120 EXPECT_FALSE(Pat2->match("f"));
121 EXPECT_FALSE(Pat2->match("y"));
122 EXPECT_FALSE(Pat2->match("z"));
123 EXPECT_FALSE(Pat2->match(""));
124 }
125
TEST_F(GlobPatternTest,BracketFrontOfCharacterClass)126 TEST_F(GlobPatternTest, BracketFrontOfCharacterClass) {
127 Expected<GlobPattern> Pat1 = GlobPattern::create("[]a]x");
128 EXPECT_TRUE((bool)Pat1);
129 EXPECT_TRUE(Pat1->match("]x"));
130 EXPECT_TRUE(Pat1->match("ax"));
131 EXPECT_FALSE(Pat1->match("a]x"));
132 EXPECT_FALSE(Pat1->match(""));
133 }
134
TEST_F(GlobPatternTest,SpecialCharsInCharacterClass)135 TEST_F(GlobPatternTest, SpecialCharsInCharacterClass) {
136 auto Pat1 = GlobPattern::create("[*?^{},]");
137 ASSERT_TRUE((bool)Pat1);
138 EXPECT_TRUE(Pat1->match("*"));
139 EXPECT_TRUE(Pat1->match("?"));
140 EXPECT_TRUE(Pat1->match("^"));
141 EXPECT_TRUE(Pat1->match("{"));
142 EXPECT_TRUE(Pat1->match("}"));
143 EXPECT_TRUE(Pat1->match(","));
144 EXPECT_FALSE(Pat1->match("*?^{},"));
145 EXPECT_FALSE(Pat1->match(""));
146
147 Expected<GlobPattern> Pat2 = GlobPattern::create("[*]");
148 ASSERT_TRUE((bool)Pat2);
149 EXPECT_TRUE(Pat2->match("*"));
150 EXPECT_FALSE(Pat2->match("]"));
151 }
152
TEST_F(GlobPatternTest,Invalid)153 TEST_F(GlobPatternTest, Invalid) {
154 for (const auto &InvalidPattern : {"[", "[]"}) {
155 auto Pat1 = GlobPattern::create(InvalidPattern);
156 EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
157 handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
158 }
159 }
160
TEST_F(GlobPatternTest,InvalidBraceExpansion)161 TEST_F(GlobPatternTest, InvalidBraceExpansion) {
162 for (const auto &InvalidPattern :
163 {"{", "{{", "{\\", "{\\}", "{}", "{a}", "[{}"}) {
164 auto Pat1 = GlobPattern::create(InvalidPattern, /*MaxSubPatterns=*/1024);
165 EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
166 handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
167 }
168 auto Pat1 = GlobPattern::create("{a,b}{c,d}{e,f}", /*MaxSubPatterns=*/7);
169 EXPECT_FALSE((bool)Pat1);
170 handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
171 }
172
TEST_F(GlobPatternTest,BraceExpansion)173 TEST_F(GlobPatternTest, BraceExpansion) {
174 auto Pat1 = GlobPattern::create("{a,b}{1,2}", /*MaxSubPatterns=*/1024);
175 ASSERT_TRUE((bool)Pat1);
176 EXPECT_TRUE(Pat1->match("a1"));
177 EXPECT_TRUE(Pat1->match("a2"));
178 EXPECT_TRUE(Pat1->match("b1"));
179 EXPECT_TRUE(Pat1->match("b2"));
180 EXPECT_FALSE(Pat1->match("ab"));
181
182 auto Pat2 = GlobPattern::create(",}{foo,\\,\\},z*}", /*MaxSubPatterns=*/1024);
183 ASSERT_TRUE((bool)Pat2);
184 EXPECT_TRUE(Pat2->match(",}foo"));
185 EXPECT_TRUE(Pat2->match(",},}"));
186 EXPECT_TRUE(Pat2->match(",}z"));
187 EXPECT_TRUE(Pat2->match(",}zoo"));
188 EXPECT_FALSE(Pat2->match(",}fooz"));
189 EXPECT_FALSE(Pat2->match("foo"));
190 EXPECT_FALSE(Pat2->match(""));
191
192 // This test breaks if we store terms separately and attempt to match them one
193 // by one instead of using subglobs
194 auto Pat3 = GlobPattern::create("{a,ab}b", /*MaxSubPatterns=*/1024);
195 ASSERT_TRUE((bool)Pat3);
196 EXPECT_TRUE(Pat3->match("ab"));
197 EXPECT_TRUE(Pat3->match("abb"));
198 }
199
TEST_F(GlobPatternTest,NoBraceExpansion)200 TEST_F(GlobPatternTest, NoBraceExpansion) {
201 auto Pat1 = GlobPattern::create("{a,b}{1,2}");
202 ASSERT_TRUE((bool)Pat1);
203 EXPECT_TRUE(Pat1->match("{a,b}{1,2}"));
204 EXPECT_FALSE(Pat1->match("a1"));
205
206 auto Pat2 = GlobPattern::create("{{");
207 ASSERT_TRUE((bool)Pat2);
208 EXPECT_TRUE(Pat2->match("{{"));
209 }
210
TEST_F(GlobPatternTest,BraceExpansionCharacterClass)211 TEST_F(GlobPatternTest, BraceExpansionCharacterClass) {
212 // Matches mangled names of C++ standard library functions
213 auto Pat =
214 GlobPattern::create("_Z{N,NK,}S[tabsiod]*", /*MaxSubPatterns=*/1024);
215 ASSERT_TRUE((bool)Pat);
216 EXPECT_TRUE(Pat->match("_ZNSt6vectorIiSaIiEE9push_backEOi"));
217 EXPECT_TRUE(Pat->match("_ZNKStfoo"));
218 EXPECT_TRUE(Pat->match("_ZNSafoo"));
219 EXPECT_TRUE(Pat->match("_ZStfoo"));
220 EXPECT_FALSE(Pat->match("_Zfoo"));
221 }
222
TEST_F(GlobPatternTest,ExtSym)223 TEST_F(GlobPatternTest, ExtSym) {
224 Expected<GlobPattern> Pat1 = GlobPattern::create("a*\xFF");
225 EXPECT_TRUE((bool)Pat1);
226 EXPECT_TRUE(Pat1->match("axxx\xFF"));
227 Expected<GlobPattern> Pat2 = GlobPattern::create("[\xFF-\xFF]");
228 EXPECT_TRUE((bool)Pat2);
229 EXPECT_TRUE(Pat2->match("\xFF"));
230 }
231
TEST_F(GlobPatternTest,IsTrivialMatchAll)232 TEST_F(GlobPatternTest, IsTrivialMatchAll) {
233 Expected<GlobPattern> Pat1 = GlobPattern::create("*");
234 EXPECT_TRUE((bool)Pat1);
235 EXPECT_TRUE(Pat1->isTrivialMatchAll());
236
237 const char *NegativeCases[] = {"a*", "*a", "?*", "*?", "**", "\\*"};
238 for (auto *P : NegativeCases) {
239 Expected<GlobPattern> Pat2 = GlobPattern::create(P);
240 EXPECT_TRUE((bool)Pat2);
241 EXPECT_FALSE(Pat2->isTrivialMatchAll());
242 }
243 }
244
TEST_F(GlobPatternTest,NUL)245 TEST_F(GlobPatternTest, NUL) {
246 for (char C : "?*") {
247 std::string S(1, C);
248 Expected<GlobPattern> Pat = GlobPattern::create(S);
249 ASSERT_TRUE((bool)Pat);
250 EXPECT_TRUE(Pat->match(S));
251 if (C == '*') {
252 EXPECT_TRUE(Pat->match(S + '\0'));
253 } else {
254 EXPECT_FALSE(Pat->match(S + '\0'));
255 handleAllErrors(Pat.takeError(), [&](ErrorInfoBase &) {});
256 }
257 }
258 }
259
TEST_F(GlobPatternTest,Pathological)260 TEST_F(GlobPatternTest, Pathological) {
261 std::string P, S(40, 'a');
262 StringRef Pieces[] = {"a*", "[ba]*", "{b*,a*}*"};
263 for (int I = 0; I != 30; ++I)
264 P += Pieces[I % 3];
265 Expected<GlobPattern> Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);
266 ASSERT_TRUE((bool)Pat);
267 EXPECT_TRUE(Pat->match(S));
268 P += 'b';
269 Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);
270 ASSERT_TRUE((bool)Pat);
271 EXPECT_FALSE(Pat->match(S));
272 EXPECT_TRUE(Pat->match(S + 'b'));
273 }
274 }
275