1 //===-- GlobPattern.cpp - Glob pattern matcher implementation -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a glob pattern matcher.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/GlobPattern.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/Optional.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/Errc.h"
22 static bool hasWildcard(StringRef S) {
23 return S.find_first_of("?*[") != StringRef::npos;
26 // Expands character ranges and returns a bitmap.
27 // For example, "a-cf-hz" is expanded to "abcfghz".
28 static Expected<BitVector> expand(StringRef S, StringRef Original) {
29 BitVector BV(256, false);
36 // If it doesn't start with something like X-Y,
37 // consume the first character and proceed.
44 // It must be in the form of X-Y.
45 // Validate it and then interpret the range.
47 return make_error<StringError>("invalid glob pattern: " + Original,
48 errc::invalid_argument);
50 for (int C = S[0]; C <= S[2]; ++C)
60 // This is a scanner for the glob pattern.
61 // A glob pattern token is one of "*", "?", "[<chars>]", "[^<chars>]"
62 // (which is a negative form of "[<chars>]"), or a non-meta character.
63 // This function returns the first token in S.
64 static Expected<BitVector> scan(StringRef &S, StringRef Original) {
68 // '*' is represented by an empty bitvector.
69 // All other bitvectors are 256-bit long.
73 return BitVector(256, true);
75 size_t End = S.find(']', 1);
76 if (End == StringRef::npos)
77 return make_error<StringError>("invalid glob pattern: " + Original,
78 errc::invalid_argument);
80 StringRef Chars = S.substr(1, End - 1);
81 S = S.substr(End + 1);
82 if (Chars.startswith("^")) {
83 Expected<BitVector> BV = expand(Chars.substr(1), Original);
85 return BV.takeError();
88 return expand(Chars, Original);
91 BitVector BV(256, false);
98 Expected<GlobPattern> GlobPattern::create(StringRef S) {
101 // S doesn't contain any metacharacter,
102 // so the regular string comparison should work.
103 if (!hasWildcard(S)) {
108 // S is something like "foo*". We can use startswith().
109 if (S.endswith("*") && !hasWildcard(S.drop_back())) {
110 Pat.Prefix = S.drop_back();
114 // S is something like "*foo". We can use endswith().
115 if (S.startswith("*") && !hasWildcard(S.drop_front())) {
116 Pat.Suffix = S.drop_front();
120 // Otherwise, we need to do real glob pattern matching.
121 // Parse the pattern now.
122 StringRef Original = S;
124 Expected<BitVector> BV = scan(S, Original);
126 return BV.takeError();
127 Pat.Tokens.push_back(*BV);
132 bool GlobPattern::match(StringRef S) const {
136 return S.startswith(*Prefix);
138 return S.endswith(*Suffix);
139 return matchOne(Tokens, S);
142 // Runs glob pattern Pats against string S.
143 bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
148 // If Pats[0] is '*', try to match Pats[1..] against all possible
149 // tail strings of S to see at least one pattern succeeds.
150 if (Pats[0].size() == 0) {
151 Pats = Pats.slice(1);
153 // Fast path. If a pattern is '*', it matches anything.
155 for (size_t I = 0, E = S.size(); I < E; ++I)
156 if (matchOne(Pats, S.substr(I)))
161 // If Pats[0] is not '*', it must consume one character.
162 if (S.empty() || !Pats[0][S[0]])
164 Pats = Pats.slice(1);