1//===-- SpecialCaseList.cpp - special case list for sanitizers ------------===//
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 is a utility class for instrumentation passes (like AddressSanitizer
10// or ThreadSanitizer) to avoid instrumenting some functions or global
11// variables, or to instrument some functions or global variables in a specific
12// way, based on a user-supplied list.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Support/SpecialCaseList.h"
17#include "llvm/ADT/RadixTree.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StringMap.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Support/Compiler.h"
24#include "llvm/Support/GlobPattern.h"
25#include "llvm/Support/LineIterator.h"
26#include "llvm/Support/MemoryBuffer.h"
27#include "llvm/Support/Path.h"
28#include "llvm/Support/Regex.h"
29#include "llvm/Support/VirtualFileSystem.h"
30#include "llvm/Support/WithColor.h"
31#include <assert.h>
32#include <memory>
33#include <mutex>
34#include <stdio.h>
35#include <string>
36#include <system_error>
37#include <utility>
38#include <variant>
39#include <vector>
40
41namespace llvm {
42
43namespace {
44
45// Lagacy v1 matcher.
46class RegexMatcher {
47public:
48 Error insert(StringRef Pattern, unsigned LineNumber, bool SlashAgnostic);
49 unsigned match(StringRef Query) const;
50 StringRef findRule(unsigned LineNo) const;
51
52private:
53 struct Reg {
54 Reg(StringRef Name, unsigned LineNo, Regex &&Rg)
55 : Name(Name), LineNo(LineNo), Rg(std::move(Rg)) {}
56 StringRef Name;
57 unsigned LineNo;
58 Regex Rg;
59 };
60
61 std::vector<Reg> RegExes;
62};
63
64class GlobMatcher {
65public:
66 Error insert(StringRef Pattern, unsigned LineNumber, bool SlashAgnostic);
67 unsigned match(StringRef Query) const;
68 StringRef findRule(unsigned LineNo) const;
69
70private:
71 struct Glob {
72 Glob(StringRef Name, unsigned LineNo, GlobPattern &&Pattern)
73 : Name(Name), LineNo(LineNo), Pattern(std::move(Pattern)) {}
74 StringRef Name;
75 unsigned LineNo;
76 GlobPattern Pattern;
77 };
78
79 void LazyInit() const;
80
81 std::vector<GlobMatcher::Glob> Globs;
82
83 mutable RadixTree<iterator_range<StringRef::const_iterator>,
84 RadixTree<iterator_range<StringRef::const_reverse_iterator>,
85 SmallVector<int, 1>>>
86 PrefixSuffixToGlob;
87
88 mutable RadixTree<iterator_range<StringRef::const_iterator>,
89 SmallVector<int, 1>>
90 SubstrToGlob;
91
92 mutable bool Initialized = false;
93};
94
95struct QueryOptions {
96 bool UseGlobs = true;
97 bool RemoveDotSlash = false;
98 bool WarnDotSlashMatch = false;
99 bool SlashAgnostic = false;
100};
101
102/// Represents a set of patterns and their line numbers
103class Matcher {
104public:
105 explicit Matcher(QueryOptions QOpts);
106
107 Error insert(StringRef Pattern, unsigned LineNumber);
108 unsigned match(StringRef Query) const;
109
110 bool matchAny(StringRef Query) const { return match(Query); }
111
112private:
113 unsigned matchInternal(StringRef Query) const;
114 StringRef findRule(unsigned LineNo) const;
115
116 std::variant<RegexMatcher, GlobMatcher> M;
117 QueryOptions Options;
118 mutable std::once_flag Warned;
119};
120
121Error RegexMatcher::insert(StringRef Pattern, unsigned LineNumber,
122 bool SlashAgnostic) {
123 if (Pattern.empty())
124 return createStringError(EC: errc::invalid_argument,
125 S: "Supplied regex was blank");
126
127 // Replace * with .*
128 auto Regexp = Pattern.str();
129 for (size_t pos = 0; (pos = Regexp.find(c: '*', pos: pos)) != std::string::npos;
130 pos += strlen(s: ".*")) {
131 Regexp.replace(pos: pos, n1: strlen(s: "*"), s: ".*");
132 }
133
134 Regexp = (Twine("^(") + StringRef(Regexp) + ")$").str();
135
136 // Check that the regexp is valid.
137 Regex CheckRE(Regexp);
138 std::string REError;
139 if (!CheckRE.isValid(Error&: REError))
140 return createStringError(EC: errc::invalid_argument, S: REError);
141
142 RegExes.emplace_back(args&: Pattern, args&: LineNumber, args: std::move(CheckRE));
143 return Error::success();
144}
145
146unsigned RegexMatcher::match(StringRef Query) const {
147 for (const auto &R : reverse(C: RegExes))
148 if (R.Rg.match(String: Query))
149 return R.LineNo;
150 return 0;
151}
152
153StringRef RegexMatcher::findRule(unsigned LineNo) const {
154 for (const auto &R : RegExes)
155 if (R.LineNo == LineNo)
156 return R.Name;
157 llvm_unreachable("`findRule` should be called only with correct `LineNo`");
158 return {};
159}
160
161Error GlobMatcher::insert(StringRef Pattern, unsigned LineNumber,
162 bool SlashAgnostic) {
163 if (Pattern.empty())
164 return createStringError(EC: errc::invalid_argument, S: "Supplied glob was blank");
165
166 auto Res =
167 GlobPattern::create(Pat: Pattern, /*MaxSubPatterns=*/1024, SlashAgnostic);
168 if (auto Err = Res.takeError())
169 return Err;
170 Globs.emplace_back(args&: Pattern, args&: LineNumber, args: std::move(Res.get()));
171 return Error::success();
172}
173
174void GlobMatcher::LazyInit() const {
175 if (LLVM_LIKELY(Initialized))
176 return;
177 Initialized = true;
178 for (const auto &[Idx, G] : enumerate(First: Globs)) {
179 StringRef Prefix = G.Pattern.prefix();
180 StringRef Suffix = G.Pattern.suffix();
181
182 if (Suffix.empty() && Prefix.empty()) {
183 // If both prefix and suffix are empty put into special tree to search by
184 // substring in a middle.
185 StringRef Substr = G.Pattern.longest_substr();
186 if (!Substr.empty()) {
187 // But only if substring is not empty. Searching this tree is more
188 // expensive.
189 auto &V = SubstrToGlob.emplace(Key: Substr).first->second;
190 V.emplace_back(Args&: Idx);
191 continue;
192 }
193 }
194
195 auto &SToGlob = PrefixSuffixToGlob.emplace(Key: Prefix).first->second;
196 auto &V = SToGlob.emplace(Key: reverse(C&: Suffix)).first->second;
197 V.emplace_back(Args&: Idx);
198 }
199}
200
201unsigned GlobMatcher::match(StringRef Query) const {
202 LazyInit();
203
204 int Best = -1;
205 if (!PrefixSuffixToGlob.empty()) {
206 for (const auto &[_, SToGlob] : PrefixSuffixToGlob.find_prefixes(Key: Query)) {
207 for (const auto &[_, V] : SToGlob.find_prefixes(Key: reverse(C&: Query))) {
208 for (int Idx : reverse(C: V)) {
209 if (Best > Idx)
210 break;
211 const GlobMatcher::Glob &G = Globs[Idx];
212 if (G.Pattern.match(S: Query)) {
213 Best = Idx;
214 // As soon as we find a match in the vector, we can break for this
215 // vector, since the globs are already sorted by priority within the
216 // prefix group. However, we continue searching other prefix groups
217 // in the map, as they may contain a better match overall.
218 break;
219 }
220 }
221 }
222 }
223 }
224
225 if (!SubstrToGlob.empty()) {
226 // As we don't know when substring exactly starts, we will try all
227 // possibilities. In most cases search will fail on first characters.
228 for (StringRef Q = Query; !Q.empty(); Q = Q.drop_front()) {
229 for (const auto &[_, V] : SubstrToGlob.find_prefixes(Key: Q)) {
230 for (int Idx : reverse(C: V)) {
231 if (Best > Idx)
232 break;
233 const GlobMatcher::Glob &G = Globs[Idx];
234 if (G.Pattern.match(S: Query)) {
235 Best = Idx;
236 // As soon as we find a match in the vector, we can break for this
237 // vector, since the globs are already sorted by priority within the
238 // prefix group. However, we continue searching other prefix groups
239 // in the map, as they may contain a better match overall.
240 break;
241 }
242 }
243 }
244 }
245 }
246 return Best < 0 ? 0 : Globs[Best].LineNo;
247}
248
249StringRef GlobMatcher::findRule(unsigned LineNo) const {
250 for (const auto &G : Globs)
251 if (G.LineNo == LineNo)
252 return G.Name;
253 llvm_unreachable("`findRule` should be called only with correct `LineNo`");
254 return {};
255}
256
257Matcher::Matcher(QueryOptions QOpts) : Options(QOpts) {
258 if (Options.UseGlobs)
259 M.emplace<GlobMatcher>();
260 else
261 M.emplace<RegexMatcher>();
262}
263
264Error Matcher::insert(StringRef Pattern, unsigned LineNumber) {
265 return std::visit(
266 visitor: [&](auto &V) {
267 return V.insert(Pattern, LineNumber, Options.SlashAgnostic);
268 },
269 variants&: M);
270}
271
272/// Matches Query against the patterns. The behavior is controlled by
273/// `#!special-case-list` version.
274//
275// - Version 1 and 2: Path is matched as-is, regardless of presence of "./".
276// - Version 3, 5 and higher: Paths with leading dot-slash are canonicalized
277// to paths without dot-slash before matching. This means that a rule
278// like `src=./foo` will never match, and `src=foo` will match both
279// `foo` and `./foo`. (Version 3 never became default but has this behavior).
280// - Version 4: Transitionary version. Paths are matched both ways
281// (canonicalized and non-canonicalized) to maintain backward compatibility.
282// If a match only works with the old behavior (non-canonicalized), a warning
283// is emitted.
284unsigned Matcher::match(StringRef Query) const {
285 if (!Options.RemoveDotSlash)
286 return matchInternal(Query);
287
288 if (!Options.WarnDotSlashMatch)
289 return matchInternal(Query: llvm::sys::path::remove_leading_dotslash(path: Query));
290
291 StringRef FixedQuery = llvm::sys::path::remove_leading_dotslash(path: Query);
292 unsigned FixedMatched = matchInternal(Query: FixedQuery);
293 if (FixedQuery == Query)
294 return FixedMatched;
295
296 unsigned OriginalMatch = matchInternal(Query);
297 if (OriginalMatch > FixedMatched) {
298 std::call_once(once&: Warned, f: [&]() {
299 WithColor::warning() << "Deprecated behaviour: pattern '"
300 << findRule(LineNo: OriginalMatch) << "' matches '" << Query
301 << "', update it to match '" << FixedQuery
302 << "' instead (further warnings suppressed).\n";
303 });
304 }
305 return std::max(a: OriginalMatch, b: FixedMatched);
306}
307
308unsigned Matcher::matchInternal(StringRef Query) const {
309 return std::visit(visitor: [&](auto &V) -> unsigned { return V.match(Query); }, variants: M);
310}
311
312StringRef Matcher::findRule(unsigned LineNo) const {
313 return std::visit(visitor: [&](auto &V) -> StringRef { return V.findRule(LineNo); },
314 variants: M);
315}
316} // namespace
317
318class SpecialCaseList::Section::SectionImpl {
319public:
320 const Matcher *findMatcher(StringRef Prefix, StringRef Category) const;
321
322 using SectionEntries = StringMap<StringMap<Matcher>>;
323
324 explicit SectionImpl(QueryOptions QOpts) : SectionMatcher(QOpts) {}
325
326 Matcher SectionMatcher;
327 SectionEntries Entries;
328};
329
330// TODO: Refactor this to return Expected<...>
331std::unique_ptr<SpecialCaseList>
332SpecialCaseList::create(const std::vector<std::string> &Paths,
333 llvm::vfs::FileSystem &FS, std::string &Error) {
334 std::unique_ptr<SpecialCaseList> SCL(new SpecialCaseList());
335 if (SCL->createInternal(Paths, VFS&: FS, Error))
336 return SCL;
337 return nullptr;
338}
339
340std::unique_ptr<SpecialCaseList> SpecialCaseList::create(const MemoryBuffer *MB,
341 std::string &Error) {
342 std::unique_ptr<SpecialCaseList> SCL(new SpecialCaseList());
343 if (SCL->createInternal(MB, Error))
344 return SCL;
345 return nullptr;
346}
347
348std::unique_ptr<SpecialCaseList>
349SpecialCaseList::createOrDie(const std::vector<std::string> &Paths,
350 llvm::vfs::FileSystem &FS) {
351 std::string Error;
352 if (auto SCL = create(Paths, FS, Error))
353 return SCL;
354 report_fatal_error(reason: Twine(Error));
355}
356
357bool SpecialCaseList::createInternal(const std::vector<std::string> &Paths,
358 vfs::FileSystem &VFS, std::string &Error) {
359 for (size_t i = 0; i < Paths.size(); ++i) {
360 const auto &Path = Paths[i];
361 ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
362 VFS.getBufferForFile(Name: Path);
363 if (std::error_code EC = FileOrErr.getError()) {
364 Error = (Twine("can't open file '") + Path + "': " + EC.message()).str();
365 return false;
366 }
367 std::string ParseError;
368 if (!parse(FileIdx: i, MB: FileOrErr.get().get(), Error&: ParseError)) {
369 Error = (Twine("error parsing file '") + Path + "': " + ParseError).str();
370 return false;
371 }
372 }
373 return true;
374}
375
376bool SpecialCaseList::createInternal(const MemoryBuffer *MB,
377 std::string &Error) {
378 if (!parse(FileIdx: 0, MB, Error))
379 return false;
380 return true;
381}
382
383Expected<SpecialCaseList::Section *>
384SpecialCaseList::addSection(StringRef SectionStr, unsigned FileNo,
385 unsigned LineNo, bool UseGlobs) {
386 SectionStr = SectionStr.copy(A&: StrAlloc);
387 Sections.emplace_back(args&: SectionStr, args&: FileNo, args&: UseGlobs);
388 auto &Section = Sections.back();
389
390 if (auto Err = Section.Impl->SectionMatcher.insert(Pattern: SectionStr, LineNumber: LineNo)) {
391 return createStringError(EC: errc::invalid_argument,
392 S: "malformed section at line " + Twine(LineNo) +
393 ": '" + SectionStr +
394 "': " + toString(E: std::move(Err)));
395 }
396
397 return &Section;
398}
399
400bool SpecialCaseList::parse(unsigned FileIdx, const MemoryBuffer *MB,
401 std::string &Error) {
402 unsigned long long Version = 2;
403
404 StringRef Header = MB->getBuffer();
405 if (Header.consume_front(Prefix: "#!special-case-list-v"))
406 consumeUnsignedInteger(Str&: Header, Radix: 10, Result&: Version);
407
408 auto MinVersion = [&](unsigned V) { return Version >= V; };
409
410 // In https://reviews.llvm.org/D154014 we added glob support and planned
411 // to remove regex support in patterns. We temporarily support the
412 // original behavior using regexes if "#!special-case-list-v1" is the
413 // first line of the file. For more details, see
414 // https://discourse.llvm.org/t/use-glob-instead-of-regex-for-specialcaselists/71666
415 bool UseGlobs = MinVersion(2);
416 bool RemoveDotSlash = MinVersion(3);
417 bool WarnDotSlash = MinVersion(4) && !MinVersion(5);
418 // TODO: Improve efficiency on Windows.
419 // `SlashAgnostic` makes `GlobMatcher` lookup inefficient by reducing the part
420 // of the pattern handled by the RadixTree. This was already the case even
421 // before `SlashAgnostic` because `GlobMatcher` pessimizes on escape sequences
422 // needed to represent Windows backslashes. A possible, but not unique,
423 // solution is to assume (or convert Windows query) backslashes, and
424 // preprocess the Glob pattern to use different escape sequences.
425 bool SlashAgnostic = MinVersion(4) && llvm::sys::path::is_style_windows(
426 S: llvm::sys::path::Style::native);
427
428 auto ErrOrSection = addSection(SectionStr: "*", FileNo: FileIdx, LineNo: 1, UseGlobs: true);
429 if (auto Err = ErrOrSection.takeError()) {
430 Error = toString(E: std::move(Err));
431 return false;
432 }
433 Section::SectionImpl *CurrentImpl = ErrOrSection.get()->Impl.get();
434
435 // This is the current list of prefixes for all existing users matching file
436 // path. We may need parametrization in constructor in future.
437 constexpr StringRef PathPrefixes[] = {"src", "!src", "mainfile", "source"};
438
439 for (line_iterator LineIt(*MB, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
440 !LineIt.is_at_eof(); LineIt++) {
441 unsigned LineNo = LineIt.line_number();
442 StringRef Line = LineIt->trim();
443 if (Line.empty())
444 continue;
445
446 // Save section names
447 if (Line.starts_with(Prefix: "[")) {
448 if (!Line.ends_with(Suffix: "]")) {
449 Error =
450 ("malformed section header on line " + Twine(LineNo) + ": " + Line)
451 .str();
452 return false;
453 }
454
455 auto ErrOrSection =
456 addSection(SectionStr: Line.drop_front().drop_back(), FileNo: FileIdx, LineNo, UseGlobs);
457 if (auto Err = ErrOrSection.takeError()) {
458 Error = toString(E: std::move(Err));
459 return false;
460 }
461 CurrentImpl = ErrOrSection.get()->Impl.get();
462 continue;
463 }
464
465 // Get our prefix and unparsed glob.
466 auto [Prefix, Postfix] = Line.split(Separator: ":");
467 if (Postfix.empty()) {
468 // Missing ':' in the line.
469 Error = ("malformed line " + Twine(LineNo) + ": '" + Line + "'").str();
470 return false;
471 }
472
473 QueryOptions QOpts;
474 QOpts.UseGlobs = UseGlobs;
475 if (llvm::is_contained(Range: PathPrefixes, Element: Prefix)) {
476 QOpts.RemoveDotSlash = RemoveDotSlash;
477 QOpts.WarnDotSlashMatch = WarnDotSlash;
478 QOpts.SlashAgnostic = SlashAgnostic;
479 }
480
481 auto [Pattern, Category] = Postfix.split(Separator: "=");
482 auto [It, _] = CurrentImpl->Entries[Prefix].try_emplace(Key: Category, Args&: QOpts);
483 Pattern = Pattern.copy(A&: StrAlloc);
484 if (auto Err = It->second.insert(Pattern, LineNumber: LineNo)) {
485 Error =
486 (Twine("malformed ") + (UseGlobs ? "glob" : "regex") + " in line " +
487 Twine(LineNo) + ": '" + Pattern + "': " + toString(E: std::move(Err)))
488 .str();
489 return false;
490 }
491 }
492
493 return true;
494}
495
496SpecialCaseList::~SpecialCaseList() = default;
497
498bool SpecialCaseList::inSection(StringRef Section, StringRef Prefix,
499 StringRef Query, StringRef Category) const {
500 auto [FileIdx, LineNo] = inSectionBlame(Section, Prefix, Query, Category);
501 return LineNo;
502}
503
504std::pair<unsigned, unsigned>
505SpecialCaseList::inSectionBlame(StringRef Section, StringRef Prefix,
506 StringRef Query, StringRef Category) const {
507 for (const auto &S : reverse(C: Sections)) {
508 if (S.Impl->SectionMatcher.matchAny(Query: Section)) {
509 unsigned Blame = S.getLastMatch(Prefix, Query, Category);
510 if (Blame)
511 return {S.FileIdx, Blame};
512 }
513 }
514 return NotFound;
515}
516
517SpecialCaseList::Section::Section(StringRef Str, unsigned FileIdx,
518 bool UseGlobs)
519 : Name(Str), FileIdx(FileIdx),
520 Impl(std::make_unique<SectionImpl>(
521 args: QueryOptions{.UseGlobs: UseGlobs, /*RemoveDotSlash=*/false})) {}
522
523SpecialCaseList::Section::Section(Section &&) = default;
524
525SpecialCaseList::Section::~Section() = default;
526
527bool SpecialCaseList::Section::matchName(StringRef Name) const {
528 return Impl->SectionMatcher.matchAny(Query: Name);
529}
530
531const Matcher *
532SpecialCaseList::Section::SectionImpl::findMatcher(StringRef Prefix,
533 StringRef Category) const {
534 SectionEntries::const_iterator I = Entries.find(Key: Prefix);
535 if (I == Entries.end())
536 return nullptr;
537 StringMap<Matcher>::const_iterator II = I->second.find(Key: Category);
538 if (II == I->second.end())
539 return nullptr;
540
541 return &II->second;
542}
543
544unsigned SpecialCaseList::Section::getLastMatch(StringRef Prefix,
545 StringRef Query,
546 StringRef Category) const {
547 if (const Matcher *M = Impl->findMatcher(Prefix, Category))
548 return M->match(Query);
549 return 0;
550}
551
552bool SpecialCaseList::Section::hasPrefix(StringRef Prefix) const {
553 return Impl->Entries.contains(Key: Prefix);
554}
555
556} // namespace llvm
557