1//===--- MatchFilePath.cpp - Match file path with pattern -------*- C++ -*-===//
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/// \file
10/// This file implements the functionality of matching a file path name to
11/// a pattern, similar to the POSIX fnmatch() function.
12///
13//===----------------------------------------------------------------------===//
14
15#include "MatchFilePath.h"
16
17using namespace llvm;
18
19namespace clang {
20namespace format {
21
22// Check whether `FilePath` matches `Pattern` based on POSIX 2.13.1, 2.13.2, and
23// Rule 1 of 2.13.3.
24bool matchFilePath(StringRef Pattern, StringRef FilePath) {
25 assert(!Pattern.empty());
26 assert(!FilePath.empty());
27
28 const auto FilePathBack = FilePath.back();
29
30 // No match if `Pattern` ends with a non-meta character not equal to the last
31 // character of `FilePath`.
32 if (const auto C = Pattern.back(); !strchr(s: "?*]", c: C) && C != FilePathBack)
33 return false;
34
35 constexpr auto Separator = '/';
36 const auto EOP = Pattern.size(); // End of `Pattern`.
37 const auto End = FilePath.size(); // End of `FilePath`.
38 unsigned I = 0; // Index to `Pattern`.
39
40 for (unsigned J = 0; J < End; ++J) {
41 if (I == EOP)
42 return false;
43
44 switch (const auto F = FilePath[J]; Pattern[I]) {
45 case '\\':
46 if (++I == EOP || F != Pattern[I])
47 return false;
48 break;
49 case '?':
50 if (F == Separator)
51 return false;
52 break;
53 case '*': {
54 bool Globstar = I == 0 || Pattern[I - 1] == Separator;
55 int StarCount = 1;
56 for (; ++I < EOP && Pattern[I] == '*'; ++StarCount) {
57 // Skip consecutive stars.
58 }
59 if (StarCount != 2)
60 Globstar = false;
61 const auto K = FilePath.find(C: Separator, From: J); // Index of next `Separator`.
62 const bool NoMoreSeparatorsInFilePath = K == StringRef::npos;
63 if (I == EOP) // `Pattern` ends with a star.
64 return Globstar || NoMoreSeparatorsInFilePath;
65 if (Pattern[I] != Separator) {
66 // `Pattern` ends with a lone backslash.
67 if (Pattern[I] == '\\' && ++I == EOP)
68 return false;
69 Globstar = false;
70 }
71 // The star is followed by a (possibly escaped) `Separator`.
72 if (Pattern[I] == Separator) {
73 if (!Globstar) {
74 if (NoMoreSeparatorsInFilePath)
75 return false;
76 J = K; // Skip to next `Separator` in `FilePath`.
77 break;
78 }
79 if (++I == EOP)
80 return FilePathBack == Separator;
81 }
82 // Recurse.
83 for (auto Pat = Pattern.substr(Start: I);
84 J < End && (Globstar || FilePath[J] != Separator); ++J) {
85 if (matchFilePath(Pattern: Pat, FilePath: FilePath.substr(Start: J)))
86 return true;
87 }
88 return false;
89 }
90 case '[':
91 // Skip e.g. `[!]`.
92 if (I + 3 < EOP || (I + 3 == EOP && Pattern[I + 1] != '!')) {
93 // Skip unpaired `[`, brackets containing slashes, and `[]`.
94 if (const auto K = Pattern.find_first_of(Chars: "]/", From: I + 1);
95 K != StringRef::npos && Pattern[K] == ']' && K > I + 1) {
96 if (F == Separator)
97 return false;
98 ++I; // After the `[`.
99 bool Negated = false;
100 if (Pattern[I] == '!') {
101 Negated = true;
102 ++I; // After the `!`.
103 }
104 bool Match = false;
105 do {
106 if (I + 2 < K && Pattern[I + 1] == '-') {
107 Match = Pattern[I] <= F && F <= Pattern[I + 2];
108 I += 3; // After the range, e.g. `A-Z`.
109 } else {
110 Match = F == Pattern[I++];
111 }
112 } while (!Match && I < K);
113 if (Negated ? Match : !Match)
114 return false;
115 I = K + 1; // After the `]`.
116 continue;
117 }
118 }
119 [[fallthrough]]; // Match `[` literally.
120 default:
121 if (F != Pattern[I])
122 return false;
123 }
124
125 ++I;
126 }
127
128 // Match trailing stars with null strings.
129 while (I < EOP && Pattern[I] == '*')
130 ++I;
131
132 return I == EOP;
133}
134
135} // namespace format
136} // namespace clang
137