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>]"), or a non-meta character.
  65 // This function returns the first token in S.
  66 static Expected<BitVector> scan(StringRef &S, StringRef Original) {
  67   switch (S[0]) {
  68   case '*':
  69     S = S.substr(1);
  70     // '*' is represented by an empty bitvector.
  71     // All other bitvectors are 256-bit long.
  72     return BitVector();
  73   case '?':
  74     S = S.substr(1);
  75     return BitVector(256, true);
  76   case '[': {
  77     size_t End = S.find(']', 1);
  78     if (End == StringRef::npos)
  79       return make_error<StringError>("invalid glob pattern: " + Original,
  80                                      errc::invalid_argument);
  81
  82     StringRef Chars = S.substr(1, End - 1);
  83     S = S.substr(End + 1);
  84     if (Chars.startswith("^")) {
  85       Expected<BitVector> BV = expand(Chars.substr(1), Original);
  86       if (!BV)
  87         return BV.takeError();
  88       return BV->flip();
  89     }
  90     return expand(Chars, Original);
  91   }
  92   default:
  93     BitVector BV(256, false);
  94     BV[(uint8_t)S[0]] = true;
  95     S = S.substr(1);
  96     return BV;
  97   }
  98 }
  99
 100 Expected<GlobPattern> GlobPattern::create(StringRef S) {
 101   GlobPattern Pat;
 102
 103   // S doesn't contain any metacharacter,
 104   // so the regular string comparison should work.
 105   if (!hasWildcard(S)) {
 106     Pat.Exact = S;
 107     return Pat;
 108   }
 109
 110   // S is something like "foo*". We can use startswith().
 111   if (S.endswith("*") && !hasWildcard(S.drop_back())) {
 112     Pat.Prefix = S.drop_back();
 113     return Pat;
 114   }
 115
 116   // S is something like "*foo". We can use endswith().
 117   if (S.startswith("*") && !hasWildcard(S.drop_front())) {
 118     Pat.Suffix = S.drop_front();
 119     return Pat;
 120   }
 121
 122   // Otherwise, we need to do real glob pattern matching.
 123   // Parse the pattern now.
 124   StringRef Original = S;
 125   while (!S.empty()) {
 126     Expected<BitVector> BV = scan(S, Original);
 127     if (!BV)
 128       return BV.takeError();
 129     Pat.Tokens.push_back(*BV);
 130   }
 131   return Pat;
 132 }
 133
 134 bool GlobPattern::match(StringRef S) const {
 135   if (Exact)
 136     return S == *Exact;
 137   if (Prefix)
 138     return S.startswith(*Prefix);
 139   if (Suffix)
 140     return S.endswith(*Suffix);
 141   return matchOne(Tokens, S);
 142 }
 143
 144 // Runs glob pattern Pats against string S.
 145 bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
 146   for (;;) {
 147     if (Pats.empty())
 148       return S.empty();
 149
 150     // If Pats[0] is '*', try to match Pats[1..] against all possible
 151     // tail strings of S to see at least one pattern succeeds.
 152     if (Pats[0].size() == 0) {
 153       Pats = Pats.slice(1);
 154       if (Pats.empty())
 155         // Fast path. If a pattern is '*', it matches anything.
 156         return true;
 157       for (size_t I = 0, E = S.size(); I < E; ++I)
 158         if (matchOne(Pats, S.substr(I)))
 159           return true;
 160       return false;
 161     }
 162
 163     // If Pats[0] is not '*', it must consume one character.
 164     if (S.empty() || !Pats[0][(uint8_t)S[0]])
 165       return false;
 166     Pats = Pats.slice(1);
 167     S = S.substr(1);
 168   }
 169 }