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