1//===-- Regex.cpp - Regular Expression 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 POSIX regular expression matcher.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Support/Regex.h"
14#include "regex_impl.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/ADT/StringRef.h"
18#include "llvm/ADT/Twine.h"
19
20#include <cassert>
21#include <string>
22
23using namespace llvm;
24
25Regex::Regex() : preg(nullptr), error(REG_BADPAT) {}
26
27Regex::Regex(StringRef regex, RegexFlags Flags) {
28 unsigned flags = 0;
29 preg = new llvm_regex();
30 preg->re_endp = regex.end();
31 if (Flags & IgnoreCase)
32 flags |= REG_ICASE;
33 if (Flags & Newline)
34 flags |= REG_NEWLINE;
35 if (!(Flags & BasicRegex))
36 flags |= REG_EXTENDED;
37 error = llvm_regcomp(preg, regex.data(), flags|REG_PEND);
38}
39
40Regex::Regex(StringRef regex, unsigned Flags)
41 : Regex(regex, static_cast<RegexFlags>(Flags)) {}
42
43Regex::Regex(Regex &&regex) {
44 preg = regex.preg;
45 error = regex.error;
46 regex.preg = nullptr;
47 regex.error = REG_BADPAT;
48}
49
50Regex::~Regex() {
51 if (preg) {
52 llvm_regfree(preg);
53 delete preg;
54 }
55}
56
57namespace {
58
59/// Utility to convert a regex error code into a human-readable string.
60void RegexErrorToString(int error, struct llvm_regex *preg,
61 std::string &Error) {
62 size_t len = llvm_regerror(error, preg, nullptr, 0);
63
64 Error.resize(n: len - 1);
65 llvm_regerror(error, preg, &Error[0], len);
66}
67
68} // namespace
69
70bool Regex::isValid(std::string &Error) const {
71 if (!error)
72 return true;
73
74 RegexErrorToString(error, preg, Error);
75 return false;
76}
77
78/// getNumMatches - In a valid regex, return the number of parenthesized
79/// matches it contains.
80unsigned Regex::getNumMatches() const {
81 return preg->re_nsub;
82}
83
84bool Regex::match(StringRef String, SmallVectorImpl<StringRef> *Matches,
85 std::string *Error) const {
86 // Reset error, if given.
87 if (Error && !Error->empty())
88 *Error = "";
89
90 // Check if the regex itself didn't successfully compile.
91 if (Error ? !isValid(Error&: *Error) : !isValid())
92 return false;
93
94 unsigned nmatch = Matches ? preg->re_nsub+1 : 0;
95
96 // Update null string to empty string.
97 if (String.data() == nullptr)
98 String = "";
99
100 // pmatch needs to have at least one element.
101 SmallVector<llvm_regmatch_t, 8> pm;
102 pm.resize(N: nmatch > 0 ? nmatch : 1);
103 pm[0].rm_so = 0;
104 pm[0].rm_eo = String.size();
105
106 int rc = llvm_regexec(preg, String.data(), nmatch, pm.data(), REG_STARTEND);
107
108 // Failure to match is not an error, it's just a normal return value.
109 // Any other error code is considered abnormal, and is logged in the Error.
110 if (rc == REG_NOMATCH)
111 return false;
112 if (rc != 0) {
113 if (Error)
114 RegexErrorToString(error, preg, Error&: *Error);
115 return false;
116 }
117
118 // There was a match.
119
120 if (Matches) { // match position requested
121 Matches->clear();
122
123 for (unsigned i = 0; i != nmatch; ++i) {
124 if (pm[i].rm_so == -1) {
125 // this group didn't match
126 Matches->push_back(Elt: StringRef());
127 continue;
128 }
129 assert(pm[i].rm_eo >= pm[i].rm_so);
130 Matches->push_back(Elt: StringRef(String.data()+pm[i].rm_so,
131 pm[i].rm_eo-pm[i].rm_so));
132 }
133 }
134
135 return true;
136}
137
138std::string Regex::sub(StringRef Repl, StringRef String,
139 std::string *Error) const {
140 SmallVector<StringRef, 8> Matches;
141
142 // Return the input if there was no match.
143 if (!match(String, Matches: &Matches, Error))
144 return std::string(String);
145
146 // Otherwise splice in the replacement string, starting with the prefix before
147 // the match.
148 std::string Res(String.begin(), Matches[0].begin());
149
150 // Then the replacement string, honoring possible substitutions.
151 while (!Repl.empty()) {
152 // Skip to the next escape.
153 std::pair<StringRef, StringRef> Split = Repl.split(Separator: '\\');
154
155 // Add the skipped substring.
156 Res += Split.first;
157
158 // Check for termination and trailing backslash.
159 if (Split.second.empty()) {
160 if (Repl.size() != Split.first.size() &&
161 Error && Error->empty())
162 *Error = "replacement string contained trailing backslash";
163 break;
164 }
165
166 // Otherwise update the replacement string and interpret escapes.
167 Repl = Split.second;
168
169 // FIXME: We should have a StringExtras function for mapping C99 escapes.
170 switch (Repl[0]) {
171
172 // Backreference with the "\g<ref>" syntax
173 case 'g':
174 if (Repl.size() >= 4 && Repl[1] == '<') {
175 size_t End = Repl.find(C: '>');
176 StringRef Ref = Repl.slice(Start: 2, End);
177 unsigned RefValue;
178 if (End != StringRef::npos && !Ref.getAsInteger(Radix: 10, Result&: RefValue)) {
179 Repl = Repl.substr(Start: End + 1);
180 if (RefValue < Matches.size())
181 Res += Matches[RefValue];
182 else if (Error && Error->empty())
183 *Error =
184 ("invalid backreference string 'g<" + Twine(Ref) + ">'").str();
185 break;
186 }
187 }
188 [[fallthrough]];
189
190 // Treat all unrecognized characters as self-quoting.
191 default:
192 Res += Repl[0];
193 Repl = Repl.substr(Start: 1);
194 break;
195
196 // Single character escapes.
197 case 't':
198 Res += '\t';
199 Repl = Repl.substr(Start: 1);
200 break;
201 case 'n':
202 Res += '\n';
203 Repl = Repl.substr(Start: 1);
204 break;
205
206 // Hex character escapes.
207 case 'x':
208 if (Repl.size() >= 3 && isHexDigit(C: Repl[1]) && isHexDigit(C: Repl[2])) {
209 Res += char(hexDigitValue(C: Repl[1]) * 16 + hexDigitValue(C: Repl[2]));
210 Repl = Repl.substr(Start: 3);
211 } else {
212 Res += Repl[0];
213 Repl = Repl.substr(Start: 1);
214 }
215 break;
216
217 // Decimal escapes are backreferences.
218 case '0': case '1': case '2': case '3': case '4':
219 case '5': case '6': case '7': case '8': case '9': {
220 // Extract the backreference number.
221 StringRef Ref = Repl.slice(Start: 0, End: Repl.find_first_not_of(Chars: "0123456789"));
222 Repl = Repl.substr(Start: Ref.size());
223
224 unsigned RefValue;
225 if (!Ref.getAsInteger(Radix: 10, Result&: RefValue) &&
226 RefValue < Matches.size())
227 Res += Matches[RefValue];
228 else if (Error && Error->empty())
229 *Error = ("invalid backreference string '" + Twine(Ref) + "'").str();
230 break;
231 }
232 }
233 }
234
235 // And finally the suffix.
236 Res += StringRef(Matches[0].end(), String.end() - Matches[0].end());
237
238 return Res;
239}
240
241// These are the special characters matched in functions like "p_ere_exp".
242static const char RegexMetachars[] = "()^$|*+?.[]\\{}";
243
244bool Regex::isLiteralERE(StringRef Str) {
245 // Check for regex metacharacters. This list was derived from our regex
246 // implementation in regcomp.c and double checked against the POSIX extended
247 // regular expression specification.
248 return Str.find_first_of(Chars: RegexMetachars) == StringRef::npos;
249}
250
251std::string Regex::escape(StringRef String) {
252 std::string RegexStr;
253 for (char C : String) {
254 if (strchr(s: RegexMetachars, c: C))
255 RegexStr += '\\';
256 RegexStr += C;
257 }
258
259 return RegexStr;
260}
261