lib/Support/GlobPattern.cpp

   1 //===-- GlobPattern.cpp - Glob pattern matcher implementation -------------===//
   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 // This file implements a glob pattern matcher.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/GlobPattern.h"
  14 #include "llvm/ADT/ArrayRef.h"
  15 #include "llvm/ADT/Optional.h"
  16 #include "llvm/ADT/StringRef.h"
  17 #include "llvm/Support/Errc.h"
  18
  19 using namespace llvm;
  20
  21 static bool hasWildcard(StringRef S) {
  22   return S.find_first_of("?*[\\") != StringRef::npos;
  23 }
  24
  25 // Expands character ranges and returns a bitmap.
  26 // For example, "a-cf-hz" is expanded to "abcfghz".
  27 static Expected<BitVector> expand(StringRef S, StringRef Original) {
  28   BitVector BV(256, false);
  29
  30   // Expand X-Y.
  31   for (;;) {
  32     if (S.size() < 3)
  33       break;
  34
  35     uint8_t Start = S[0];
  36     uint8_t End = S[2];
  37
  38     // If it doesn't start with something like X-Y,
  39     // consume the first character and proceed.
  40     if (S[1] != '-') {
  41       BV[Start] = true;
  42       S = S.substr(1);
  43       continue;
  44     }
  45
  46     // It must be in the form of X-Y.
  47     // Validate it and then interpret the range.
  48     if (Start > End)
  49       return make_error<StringError>("invalid glob pattern: " + Original,
  50                                      errc::invalid_argument);
  51
  52     for (int C = Start; C <= End; ++C)
  53       BV[(uint8_t)C] = true;
  54     S = S.substr(3);
  55   }
  56
  57   for (char C : S)
  58     BV[(uint8_t)C] = true;
  59   return BV;
  60 }
  61
  62 // This is a scanner for the glob pattern.
  63 // A glob pattern token is one of "*", "?", "\", "[<chars>]", "[^<chars>]"
  64 // (which is a negative form of "[<chars>]"), "[!<chars>]" (which is
  65 // equivalent to "[^<chars>]"), or a non-meta character.
  66 // This function returns the first token in S.
  67 static Expected<BitVector> scan(StringRef &S, StringRef Original) {
  68   switch (S[0]) {
  69   case '*':
  70     S = S.substr(1);
  71     // '*' is represented by an empty bitvector.
  72     // All other bitvectors are 256-bit long.
  73     return BitVector();
  74   case '?':
  75     S = S.substr(1);
  76     return BitVector(256, true);
  77   case '[': {
  78     // ']' is allowed as the first character of a character class. '[]' is
  79     // invalid. So, just skip the first character.
  80     size_t End = S.find(']', 2);
  81     if (End == StringRef::npos)
  82       return make_error<StringError>("invalid glob pattern: " + Original,
  83                                      errc::invalid_argument);
  84
  85     StringRef Chars = S.substr(1, End - 1);
  86     S = S.substr(End + 1);
  87     if (Chars.startswith("^") || Chars.startswith("!")) {
  88       Expected<BitVector> BV = expand(Chars.substr(1), Original);
  89       if (!BV)
  90         return BV.takeError();
  91       return BV->flip();
  92     }
  93     return expand(Chars, Original);
  94   }
  95   case '\\':
  96     // Eat this character and fall through below to treat it like a non-meta
  97     // character.
  98     S = S.substr(1);
  99     LLVM_FALLTHROUGH;
 100   default:
 101     BitVector BV(256, false);
 102     BV[(uint8_t)S[0]] = true;
 103     S = S.substr(1);
 104     return BV;
 105   }
 106 }
 107
 108 Expected<GlobPattern> GlobPattern::create(StringRef S) {
 109   GlobPattern Pat;
 110
 111   // S doesn't contain any metacharacter,
 112   // so the regular string comparison should work.
 113   if (!hasWildcard(S)) {
 114     Pat.Exact = S;
 115     return Pat;
 116   }
 117
 118   // S is something like "foo*", and the "* is not escaped. We can use
 119   // startswith().
 120   if (S.endswith("*") && !S.endswith("\\*") && !hasWildcard(S.drop_back())) {
 121     Pat.Prefix = S.drop_back();
 122     return Pat;
 123   }
 124
 125   // S is something like "*foo". We can use endswith().
 126   if (S.startswith("*") && !hasWildcard(S.drop_front())) {
 127     Pat.Suffix = S.drop_front();
 128     return Pat;
 129   }
 130
 131   // Otherwise, we need to do real glob pattern matching.
 132   // Parse the pattern now.
 133   StringRef Original = S;
 134   while (!S.empty()) {
 135     Expected<BitVector> BV = scan(S, Original);
 136     if (!BV)
 137       return BV.takeError();
 138     Pat.Tokens.push_back(*BV);
 139   }
 140   return Pat;
 141 }
 142
 143 bool GlobPattern::match(StringRef S) const {
 144   if (Exact)
 145     return S == *Exact;
 146   if (Prefix)
 147     return S.startswith(*Prefix);
 148   if (Suffix)
 149     return S.endswith(*Suffix);
 150   return matchOne(Tokens, S);
 151 }
 152
 153 // Runs glob pattern Pats against string S.
 154 bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
 155   for (;;) {
 156     if (Pats.empty())
 157       return S.empty();
 158
 159     // If Pats[0] is '*', try to match Pats[1..] against all possible
 160     // tail strings of S to see at least one pattern succeeds.
 161     if (Pats[0].size() == 0) {
 162       Pats = Pats.slice(1);
 163       if (Pats.empty())
 164         // Fast path. If a pattern is '*', it matches anything.
 165         return true;
 166       for (size_t I = 0, E = S.size(); I < E; ++I)
 167         if (matchOne(Pats, S.substr(I)))
 168           return true;
 169       return false;
 170     }
 171
 172     // If Pats[0] is not '*', it must consume one character.
 173     if (S.empty() || !Pats[0][(uint8_t)S[0]])
 174       return false;
 175     Pats = Pats.slice(1);
 176     S = S.substr(1);
 177   }
 178 }