xref: /llvm-project/llvm/lib/Support/GlobPattern.cpp (revision ebb0a210995dcf69d9696f8e14629e1378e63a21)
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