LLVM  10.0.0svn
GlobPattern.cpp
Go to the documentation of this file.
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 
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".
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,
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.
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,
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 
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 
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 }
uint64_t CallInst * C
LLVM_NODISCARD bool endswith(StringRef Suffix) const
Check if this string ends with the given Suffix.
Definition: StringRef.h:267
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool match(StringRef S) const
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:256
Error takeError()
Take ownership of the stored error.
Definition: Error.h:552
LLVM_NODISCARD StringRef drop_front(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with the first N elements dropped.
Definition: StringRef.h:620
Tagged union holding either a T or a Error.
Definition: CachePruning.h:22
LLVM_NODISCARD StringRef substr(size_t Start, size_t N=npos) const
Return a reference to the substring from [Start, Start + N).
Definition: StringRef.h:578
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:126
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:130
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool hasWildcard(StringRef S)
Definition: GlobPattern.cpp:21
LLVM_NODISCARD size_t find(char C, size_t From=0) const
Search for the first character C in the string.
Definition: StringRef.h:285
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1173
static Expected< GlobPattern > create(StringRef Pat)
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:178
static const size_t npos
Definition: StringRef.h:50
LLVM_NODISCARD size_t find_first_of(char C, size_t From=0) const
Find the first character in the string that is C, or npos if not found.
Definition: StringRef.h:380
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD StringRef drop_back(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with the last N elements dropped.
Definition: StringRef.h:628
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static Expected< BitVector > scan(StringRef &S, StringRef Original)
Definition: GlobPattern.cpp:66
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143