413 lines · cpp
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-exception6//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("");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("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("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("\\*");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 78TEST_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 98TEST_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 126TEST_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 135TEST_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 153TEST_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 161TEST_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 173TEST_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 one193 // by one instead of using subglobs194 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 200TEST_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 211TEST_F(GlobPatternTest, BraceExpansionCharacterClass) {212 // Matches mangled names of C++ standard library functions213 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 223TEST_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 232TEST_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 245TEST_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 260TEST_F(GlobPatternTest, PrefixSuffix) {261 auto Pat = GlobPattern::create("");262 ASSERT_TRUE((bool)Pat);263 EXPECT_EQ("", Pat->prefix());264 EXPECT_EQ("", Pat->suffix());265 266 Pat = GlobPattern::create("abcd");267 ASSERT_TRUE((bool)Pat);268 EXPECT_EQ("abcd", Pat->prefix());269 EXPECT_EQ("", Pat->suffix());270 271 Pat = GlobPattern::create("*abcd");272 ASSERT_TRUE((bool)Pat);273 EXPECT_EQ("", Pat->prefix());274 EXPECT_EQ("abcd", Pat->suffix());275 276 Pat = GlobPattern::create("abcd*");277 ASSERT_TRUE((bool)Pat);278 EXPECT_EQ("abcd", Pat->prefix());279 EXPECT_EQ("", Pat->suffix());280 281 Pat = GlobPattern::create("ab*cd");282 ASSERT_TRUE((bool)Pat);283 EXPECT_EQ("ab", Pat->prefix());284 EXPECT_EQ("cd", Pat->suffix());285 286 Pat = GlobPattern::create("ab?cd");287 ASSERT_TRUE((bool)Pat);288 EXPECT_EQ("ab", Pat->prefix());289 EXPECT_EQ("cd", Pat->suffix());290 291 Pat = GlobPattern::create("ab[n]cd");292 ASSERT_TRUE((bool)Pat);293 EXPECT_EQ("ab", Pat->prefix());294 EXPECT_EQ("cd", Pat->suffix());295 296 Pat = GlobPattern::create("ab{}cd");297 ASSERT_TRUE((bool)Pat);298 EXPECT_EQ("ab", Pat->prefix());299 EXPECT_EQ("cd", Pat->suffix());300 301 Pat = GlobPattern::create("ab{cd");302 ASSERT_TRUE((bool)Pat);303 EXPECT_EQ("ab", Pat->prefix());304 EXPECT_EQ("cd", Pat->suffix());305 306 Pat = GlobPattern::create("ab]cd");307 ASSERT_TRUE((bool)Pat);308 EXPECT_EQ("ab]cd", Pat->prefix());309 EXPECT_EQ("", Pat->suffix());310 311 Pat = GlobPattern::create("ab\\cd");312 ASSERT_TRUE((bool)Pat);313 EXPECT_EQ("ab", Pat->prefix());314 EXPECT_EQ("d", Pat->suffix());315 316 Pat = GlobPattern::create("ab\\\\cd");317 ASSERT_TRUE((bool)Pat);318 EXPECT_EQ("ab", Pat->prefix());319 EXPECT_EQ("d", Pat->suffix());320 321 Pat = GlobPattern::create("ab?cd?");322 ASSERT_TRUE((bool)Pat);323 EXPECT_EQ("ab", Pat->prefix());324 EXPECT_EQ("", Pat->suffix());325 326 Pat = GlobPattern::create("?ab?cd");327 ASSERT_TRUE((bool)Pat);328 EXPECT_EQ("", Pat->prefix());329 EXPECT_EQ("cd", Pat->suffix());330}331 332TEST_F(GlobPatternTest, Substr) {333 auto Pat = GlobPattern::create("");334 ASSERT_TRUE((bool)Pat);335 EXPECT_EQ("", Pat->longest_substr());336 337 Pat = GlobPattern::create("abcd");338 ASSERT_TRUE((bool)Pat);339 EXPECT_EQ("", Pat->longest_substr());340 341 Pat = GlobPattern::create("a*bcd");342 ASSERT_TRUE((bool)Pat);343 EXPECT_EQ("", Pat->longest_substr());344 345 Pat = GlobPattern::create("*abcd");346 ASSERT_TRUE((bool)Pat);347 EXPECT_EQ("", Pat->longest_substr());348 349 Pat = GlobPattern::create("abcd*");350 ASSERT_TRUE((bool)Pat);351 EXPECT_EQ("", Pat->longest_substr());352 353 Pat = GlobPattern::create("a*bc*d");354 ASSERT_TRUE((bool)Pat);355 EXPECT_EQ("bc", Pat->longest_substr());356 357 Pat = GlobPattern::create("a*bc*def*g");358 ASSERT_TRUE((bool)Pat);359 EXPECT_EQ("def", Pat->longest_substr());360 361 Pat = GlobPattern::create("a*bcd*ef*g");362 ASSERT_TRUE((bool)Pat);363 EXPECT_EQ("bcd", Pat->longest_substr());364 365 Pat = GlobPattern::create("a*bcd*efg*h");366 ASSERT_TRUE((bool)Pat);367 EXPECT_EQ("bcd", Pat->longest_substr());368 369 Pat = GlobPattern::create("a*bcd[ef]g*h");370 ASSERT_TRUE((bool)Pat);371 EXPECT_EQ("bcd", Pat->longest_substr());372 373 Pat = GlobPattern::create("a*bc[d]efg*h");374 ASSERT_TRUE((bool)Pat);375 EXPECT_EQ("efg", Pat->longest_substr());376 377 Pat = GlobPattern::create("a*bc[]]efg*h");378 ASSERT_TRUE((bool)Pat);379 EXPECT_EQ("efg", Pat->longest_substr());380 381 Pat = GlobPattern::create("a*bcde\\fg*h");382 ASSERT_TRUE((bool)Pat);383 EXPECT_EQ("bcde", Pat->longest_substr());384 385 Pat = GlobPattern::create("a*bcde\\[fg*h");386 ASSERT_TRUE((bool)Pat);387 EXPECT_EQ("bcde", Pat->longest_substr());388 389 Pat = GlobPattern::create("a*bcde?fg*h");390 ASSERT_TRUE((bool)Pat);391 EXPECT_EQ("bcde", Pat->longest_substr());392 393 Pat = GlobPattern::create("a*bcdef{g}*h");394 ASSERT_TRUE((bool)Pat);395 EXPECT_EQ("bcdef", Pat->longest_substr());396}397 398TEST_F(GlobPatternTest, Pathological) {399 std::string P, S(40, 'a');400 StringRef Pieces[] = {"a*", "[ba]*", "{b*,a*}*"};401 for (int I = 0; I != 30; ++I)402 P += Pieces[I % 3];403 Expected<GlobPattern> Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);404 ASSERT_TRUE((bool)Pat);405 EXPECT_TRUE(Pat->match(S));406 P += 'b';407 Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);408 ASSERT_TRUE((bool)Pat);409 EXPECT_FALSE(Pat->match(S));410 EXPECT_TRUE(Pat->match(S + 'b'));411}412}413