313 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a glob pattern matcher.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Support/GlobPattern.h"14#include "llvm/ADT/StringRef.h"15#include "llvm/Support/Errc.h"16 17using namespace llvm;18 19// Expands character ranges and returns a bitmap.20// For example, "a-cf-hz" is expanded to "abcfghz".21static Expected<BitVector> expand(StringRef S, StringRef Original) {22 BitVector BV(256, false);23 24 // Expand X-Y.25 for (;;) {26 if (S.size() < 3)27 break;28 29 uint8_t Start = S[0];30 uint8_t End = S[2];31 32 // If it doesn't start with something like X-Y,33 // consume the first character and proceed.34 if (S[1] != '-') {35 BV[Start] = true;36 S = S.substr(1);37 continue;38 }39 40 // It must be in the form of X-Y.41 // Validate it and then interpret the range.42 if (Start > End)43 return make_error<StringError>("invalid glob pattern: " + Original,44 errc::invalid_argument);45 46 for (int C = Start; C <= End; ++C)47 BV[(uint8_t)C] = true;48 S = S.substr(3);49 }50 51 for (char C : S)52 BV[(uint8_t)C] = true;53 return BV;54}55 56// Identify brace expansions in S and return the list of patterns they expand57// into.58static Expected<SmallVector<std::string, 1>>59parseBraceExpansions(StringRef S, std::optional<size_t> MaxSubPatterns) {60 SmallVector<std::string> SubPatterns = {S.str()};61 if (!MaxSubPatterns || !S.contains('{'))62 return std::move(SubPatterns);63 64 struct BraceExpansion {65 size_t Start;66 size_t Length;67 SmallVector<StringRef, 2> Terms;68 };69 SmallVector<BraceExpansion, 0> BraceExpansions;70 71 BraceExpansion *CurrentBE = nullptr;72 size_t TermBegin;73 for (size_t I = 0, E = S.size(); I != E; ++I) {74 if (S[I] == '[') {75 I = S.find(']', I + 2);76 if (I == std::string::npos)77 return make_error<StringError>("invalid glob pattern, unmatched '['",78 errc::invalid_argument);79 } else if (S[I] == '{') {80 if (CurrentBE)81 return make_error<StringError>(82 "nested brace expansions are not supported",83 errc::invalid_argument);84 CurrentBE = &BraceExpansions.emplace_back();85 CurrentBE->Start = I;86 TermBegin = I + 1;87 } else if (S[I] == ',') {88 if (!CurrentBE)89 continue;90 CurrentBE->Terms.push_back(S.substr(TermBegin, I - TermBegin));91 TermBegin = I + 1;92 } else if (S[I] == '}') {93 if (!CurrentBE)94 continue;95 if (CurrentBE->Terms.empty())96 return make_error<StringError>(97 "empty or singleton brace expansions are not supported",98 errc::invalid_argument);99 CurrentBE->Terms.push_back(S.substr(TermBegin, I - TermBegin));100 CurrentBE->Length = I - CurrentBE->Start + 1;101 CurrentBE = nullptr;102 } else if (S[I] == '\\') {103 if (++I == E)104 return make_error<StringError>("invalid glob pattern, stray '\\'",105 errc::invalid_argument);106 }107 }108 if (CurrentBE)109 return make_error<StringError>("incomplete brace expansion",110 errc::invalid_argument);111 112 size_t NumSubPatterns = 1;113 for (auto &BE : BraceExpansions) {114 if (NumSubPatterns > std::numeric_limits<size_t>::max() / BE.Terms.size()) {115 NumSubPatterns = std::numeric_limits<size_t>::max();116 break;117 }118 NumSubPatterns *= BE.Terms.size();119 }120 if (NumSubPatterns > *MaxSubPatterns)121 return make_error<StringError>("too many brace expansions",122 errc::invalid_argument);123 // Replace brace expansions in reverse order so that we don't invalidate124 // earlier start indices125 for (auto &BE : reverse(BraceExpansions)) {126 SmallVector<std::string> OrigSubPatterns;127 std::swap(SubPatterns, OrigSubPatterns);128 for (StringRef Term : BE.Terms)129 for (StringRef Orig : OrigSubPatterns)130 SubPatterns.emplace_back(Orig).replace(BE.Start, BE.Length, Term);131 }132 return std::move(SubPatterns);133}134 135static StringRef maxPlainSubstring(StringRef S) {136 StringRef Best;137 while (!S.empty()) {138 size_t PrefixSize = S.find_first_of("?*[{\\");139 if (PrefixSize == std::string::npos)140 PrefixSize = S.size();141 142 if (Best.size() < PrefixSize)143 Best = S.take_front(PrefixSize);144 145 S = S.drop_front(PrefixSize);146 147 // It's impossible, as the first and last characters of the input string148 // must be Glob special characters, otherwise they would be parts of149 // the prefix or the suffix.150 assert(!S.empty());151 152 switch (S.front()) {153 case '\\':154 S = S.drop_front(2);155 break;156 case '[': {157 // Drop '[' and the first character which can be ']'.158 S = S.drop_front(2);159 size_t EndBracket = S.find_first_of("]");160 // Should not be possible, SubGlobPattern::create should fail on invalid161 // pattern before we get here.162 assert(EndBracket != std::string::npos);163 S = S.drop_front(EndBracket + 1);164 break;165 }166 case '{':167 // TODO: implement.168 // Fallback to whatever is best for now.169 return Best;170 default:171 S = S.drop_front(1);172 }173 }174 175 return Best;176}177 178Expected<GlobPattern>179GlobPattern::create(StringRef S, std::optional<size_t> MaxSubPatterns) {180 GlobPattern Pat;181 Pat.Pattern = S;182 183 // Store the prefix that does not contain any metacharacter.184 Pat.PrefixSize = S.find_first_of("?*[{\\");185 if (Pat.PrefixSize == std::string::npos) {186 Pat.PrefixSize = S.size();187 return Pat;188 }189 S = S.substr(Pat.PrefixSize);190 191 // Just in case we stop on unmatched opening brackets.192 size_t SuffixStart = S.find_last_of("?*[]{}\\");193 assert(SuffixStart != std::string::npos);194 if (S[SuffixStart] == '\\')195 ++SuffixStart;196 if (SuffixStart < S.size())197 ++SuffixStart;198 Pat.SuffixSize = S.size() - SuffixStart;199 S = S.substr(0, SuffixStart);200 201 SmallVector<std::string, 1> SubPats;202 if (auto Err = parseBraceExpansions(S, MaxSubPatterns).moveInto(SubPats))203 return std::move(Err);204 for (StringRef SubPat : SubPats) {205 auto SubGlobOrErr = SubGlobPattern::create(SubPat);206 if (!SubGlobOrErr)207 return SubGlobOrErr.takeError();208 Pat.SubGlobs.push_back(*SubGlobOrErr);209 }210 211 return Pat;212}213 214Expected<GlobPattern::SubGlobPattern>215GlobPattern::SubGlobPattern::create(StringRef S) {216 SubGlobPattern Pat;217 218 // Parse brackets.219 Pat.Pat.assign(S.begin(), S.end());220 for (size_t I = 0, E = S.size(); I != E; ++I) {221 if (S[I] == '[') {222 // ']' is allowed as the first character of a character class. '[]' is223 // invalid. So, just skip the first character.224 ++I;225 size_t J = S.find(']', I + 1);226 if (J == StringRef::npos)227 return make_error<StringError>("invalid glob pattern, unmatched '['",228 errc::invalid_argument);229 StringRef Chars = S.substr(I, J - I);230 bool Invert = S[I] == '^' || S[I] == '!';231 Expected<BitVector> BV =232 Invert ? expand(Chars.substr(1), S) : expand(Chars, S);233 if (!BV)234 return BV.takeError();235 if (Invert)236 BV->flip();237 Pat.Brackets.push_back(Bracket{J + 1, std::move(*BV)});238 I = J;239 } else if (S[I] == '\\') {240 if (++I == E)241 return make_error<StringError>("invalid glob pattern, stray '\\'",242 errc::invalid_argument);243 }244 }245 return Pat;246}247 248StringRef GlobPattern::longest_substr() const {249 return maxPlainSubstring(250 Pattern.drop_front(PrefixSize).drop_back(SuffixSize));251}252 253bool GlobPattern::match(StringRef S) const {254 if (!S.consume_front(prefix()))255 return false;256 if (!S.consume_back(suffix()))257 return false;258 if (SubGlobs.empty() && S.empty())259 return true;260 for (auto &Glob : SubGlobs)261 if (Glob.match(S))262 return true;263 return false;264}265 266// Factor the pattern into segments split by '*'. The segment is matched267// sequentianlly by finding the first occurrence past the end of the previous268// match.269bool GlobPattern::SubGlobPattern::match(StringRef Str) const {270 const char *P = Pat.data(), *SegmentBegin = nullptr, *S = Str.data(),271 *SavedS = S;272 const char *const PEnd = P + Pat.size(), *const End = S + Str.size();273 size_t B = 0, SavedB = 0;274 while (S != End) {275 if (P == PEnd)276 ;277 else if (*P == '*') {278 // The non-* substring on the left of '*' matches the tail of S. Save the279 // positions to be used by backtracking if we see a mismatch later.280 SegmentBegin = ++P;281 SavedS = S;282 SavedB = B;283 continue;284 } else if (*P == '[') {285 if (Brackets[B].Bytes[uint8_t(*S)]) {286 P = Pat.data() + Brackets[B++].NextOffset;287 ++S;288 continue;289 }290 } else if (*P == '\\') {291 if (*++P == *S) {292 ++P;293 ++S;294 continue;295 }296 } else if (*P == *S || *P == '?') {297 ++P;298 ++S;299 continue;300 }301 if (!SegmentBegin)302 return false;303 // We have seen a '*'. Backtrack to the saved positions. Shift the S304 // position to probe the next starting position in the segment.305 P = SegmentBegin;306 S = ++SavedS;307 B = SavedB;308 }309 // All bytes in Str have been matched. Return true if the rest part of Pat is310 // empty or contains only '*'.311 return getPat().find_first_not_of('*', P - Pat.data()) == std::string::npos;312}313