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/StringRef.h" 16 #include "llvm/Support/Errc.h" 17 18 using namespace llvm; 19 20 // Expands character ranges and returns a bitmap. 21 // For example, "a-cf-hz" is expanded to "abcfghz". 22 static Expected<BitVector> expand(StringRef S, StringRef Original) { 23 BitVector BV(256, false); 24 25 // Expand X-Y. 26 for (;;) { 27 if (S.size() < 3) 28 break; 29 30 uint8_t Start = S[0]; 31 uint8_t End = S[2]; 32 33 // If it doesn't start with something like X-Y, 34 // consume the first character and proceed. 35 if (S[1] != '-') { 36 BV[Start] = true; 37 S = S.substr(1); 38 continue; 39 } 40 41 // It must be in the form of X-Y. 42 // Validate it and then interpret the range. 43 if (Start > End) 44 return make_error<StringError>("invalid glob pattern: " + Original, 45 errc::invalid_argument); 46 47 for (int C = Start; C <= End; ++C) 48 BV[(uint8_t)C] = true; 49 S = S.substr(3); 50 } 51 52 for (char C : S) 53 BV[(uint8_t)C] = true; 54 return BV; 55 } 56 57 Expected<GlobPattern> GlobPattern::create(StringRef S) { 58 GlobPattern Pat; 59 60 // Store the prefix that does not contain any metacharacter. 61 size_t PrefixSize = S.find_first_of("?*[\\"); 62 Pat.Prefix = S.substr(0, PrefixSize); 63 if (PrefixSize == std::string::npos) 64 return Pat; 65 S = S.substr(PrefixSize); 66 67 // Parse brackets. 68 Pat.Pat = S; 69 for (size_t I = 0, E = S.size(); I != E; ++I) { 70 if (S[I] == '[') { 71 // ']' is allowed as the first character of a character class. '[]' is 72 // invalid. So, just skip the first character. 73 ++I; 74 size_t J = S.find(']', I + 1); 75 if (J == StringRef::npos) 76 return make_error<StringError>("invalid glob pattern, unmatched '['", 77 errc::invalid_argument); 78 StringRef Chars = S.substr(I, J - I); 79 bool Invert = S[I] == '^' || S[I] == '!'; 80 Expected<BitVector> BV = 81 Invert ? expand(Chars.substr(1), S) : expand(Chars, S); 82 if (!BV) 83 return BV.takeError(); 84 if (Invert) 85 BV->flip(); 86 Pat.Brackets.push_back(Bracket{S.data() + J + 1, std::move(*BV)}); 87 I = J; 88 } else if (S[I] == '\\') { 89 if (++I == E) 90 return make_error<StringError>("invalid glob pattern, stray '\\'", 91 errc::invalid_argument); 92 } 93 } 94 return Pat; 95 } 96 97 bool GlobPattern::match(StringRef S) const { 98 return S.consume_front(Prefix) && matchOne(S); 99 } 100 101 // Factor the pattern into segments split by '*'. The segment is matched 102 // sequentianlly by finding the first occurrence past the end of the previous 103 // match. 104 bool GlobPattern::matchOne(StringRef Str) const { 105 const char *P = Pat.data(), *SegmentBegin = nullptr, *S = Str.data(), 106 *SavedS = S; 107 const char *const PEnd = P + Pat.size(), *const End = S + Str.size(); 108 size_t B = 0, SavedB = 0; 109 while (S != End) { 110 if (P == PEnd) 111 ; 112 else if (*P == '*') { 113 // The non-* substring on the left of '*' matches the tail of S. Save the 114 // positions to be used by backtracking if we see a mismatch later. 115 SegmentBegin = ++P; 116 SavedS = S; 117 SavedB = B; 118 continue; 119 } else if (*P == '[') { 120 if (Brackets[B].Bytes[uint8_t(*S)]) { 121 P = Brackets[B++].Next; 122 ++S; 123 continue; 124 } 125 } else if (*P == '\\') { 126 if (*++P == *S) { 127 ++P; 128 ++S; 129 continue; 130 } 131 } else if (*P == *S || *P == '?') { 132 ++P; 133 ++S; 134 continue; 135 } 136 if (!SegmentBegin) 137 return false; 138 // We have seen a '*'. Backtrack to the saved positions. Shift the S 139 // position to probe the next starting position in the segment. 140 P = SegmentBegin; 141 S = ++SavedS; 142 B = SavedB; 143 } 144 // All bytes in Str have been matched. Return true if the rest part of Pat is 145 // empty or contains only '*'. 146 return Pat.find_first_not_of('*', P - Pat.data()) == std::string::npos; 147 } 148