llvm/unittests/Support/GlobPatternTest.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-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
  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
  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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 }