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
12using namespace llvm;
13namespace {
14
15class GlobPatternTest : public ::testing::Test {};
16
17TEST_F(GlobPatternTest, Empty) {
18 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "");
19 EXPECT_TRUE((bool)Pat1);
20 EXPECT_TRUE(Pat1->match(""));
21 EXPECT_FALSE(Pat1->match("a"));
22}
23
24TEST_F(GlobPatternTest, Glob) {
25 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "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
34TEST_F(GlobPatternTest, Wildcard) {
35 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "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
42TEST_F(GlobPatternTest, Escape) {
43 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "\\*");
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(Pat: "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(Pat: "\\{");
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(Pat: "\\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(Pat: S);
69 if (I % 2) {
70 EXPECT_FALSE((bool)Pat);
71 handleAllErrors(E: Pat.takeError(), Handlers: [&](ErrorInfoBase &) {});
72 } else {
73 EXPECT_TRUE((bool)Pat);
74 }
75 }
76}
77
78TEST_F(GlobPatternTest, BasicCharacterClass) {
79 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "[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(Pat: "[ab]*[cd]?**[ef]");
93 ASSERT_TRUE((bool)Pat2);
94 EXPECT_TRUE(Pat2->match("aecde"));
95 EXPECT_FALSE(Pat2->match("aecdg"));
96}
97
98TEST_F(GlobPatternTest, NegatedCharacterClass) {
99 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "[^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(Pat: "[!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
126TEST_F(GlobPatternTest, BracketFrontOfCharacterClass) {
127 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "[]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
135TEST_F(GlobPatternTest, SpecialCharsInCharacterClass) {
136 auto Pat1 = GlobPattern::create(Pat: "[*?^{},]");
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(Pat: "[*]");
148 ASSERT_TRUE((bool)Pat2);
149 EXPECT_TRUE(Pat2->match("*"));
150 EXPECT_FALSE(Pat2->match("]"));
151}
152
153TEST_F(GlobPatternTest, Invalid) {
154 for (const auto &InvalidPattern : {"[", "[]"}) {
155 auto Pat1 = GlobPattern::create(Pat: InvalidPattern);
156 EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
157 handleAllErrors(E: Pat1.takeError(), Handlers: [&](ErrorInfoBase &EIB) {});
158 }
159}
160
161TEST_F(GlobPatternTest, InvalidBraceExpansion) {
162 for (const auto &InvalidPattern :
163 {"{", "{{", "{\\", "{\\}", "{}", "{a}", "[{}"}) {
164 auto Pat1 = GlobPattern::create(Pat: InvalidPattern, /*MaxSubPatterns=*/1024);
165 EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
166 handleAllErrors(E: Pat1.takeError(), Handlers: [&](ErrorInfoBase &EIB) {});
167 }
168 auto Pat1 = GlobPattern::create(Pat: "{a,b}{c,d}{e,f}", /*MaxSubPatterns=*/7);
169 EXPECT_FALSE((bool)Pat1);
170 handleAllErrors(E: Pat1.takeError(), Handlers: [&](ErrorInfoBase &EIB) {});
171}
172
173TEST_F(GlobPatternTest, BraceExpansion) {
174 auto Pat1 = GlobPattern::create(Pat: "{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(Pat: ",}{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(Pat: "{a,ab}b", /*MaxSubPatterns=*/1024);
195 ASSERT_TRUE((bool)Pat3);
196 EXPECT_TRUE(Pat3->match("ab"));
197 EXPECT_TRUE(Pat3->match("abb"));
198}
199
200TEST_F(GlobPatternTest, NoBraceExpansion) {
201 auto Pat1 = GlobPattern::create(Pat: "{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(Pat: "{{");
207 ASSERT_TRUE((bool)Pat2);
208 EXPECT_TRUE(Pat2->match("{{"));
209}
210
211TEST_F(GlobPatternTest, BraceExpansionCharacterClass) {
212 // Matches mangled names of C++ standard library functions
213 auto Pat =
214 GlobPattern::create(Pat: "_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
223TEST_F(GlobPatternTest, ExtSym) {
224 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "a*\xFF");
225 EXPECT_TRUE((bool)Pat1);
226 EXPECT_TRUE(Pat1->match("axxx\xFF"));
227 Expected<GlobPattern> Pat2 = GlobPattern::create(Pat: "[\xFF-\xFF]");
228 EXPECT_TRUE((bool)Pat2);
229 EXPECT_TRUE(Pat2->match("\xFF"));
230}
231
232TEST_F(GlobPatternTest, IsTrivialMatchAll) {
233 Expected<GlobPattern> Pat1 = GlobPattern::create(Pat: "*");
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(Pat: P);
240 EXPECT_TRUE((bool)Pat2);
241 EXPECT_FALSE(Pat2->isTrivialMatchAll());
242 }
243}
244
245TEST_F(GlobPatternTest, NUL) {
246 for (char C : "?*") {
247 std::string S(1, C);
248 Expected<GlobPattern> Pat = GlobPattern::create(Pat: 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(E: Pat.takeError(), Handlers: [&](ErrorInfoBase &) {});
256 }
257 }
258}
259
260TEST_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(Pat: P, /*MaxSubPatterns=*/1024);
266 ASSERT_TRUE((bool)Pat);
267 EXPECT_TRUE(Pat->match(S));
268 P += 'b';
269 Pat = GlobPattern::create(Pat: P, /*MaxSubPatterns=*/1024);
270 ASSERT_TRUE((bool)Pat);
271 EXPECT_FALSE(Pat->match(S));
272 EXPECT_TRUE(Pat->match(S + 'b'));
273}
274}
275

source code of llvm/unittests/Support/GlobPatternTest.cpp