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 17 using namespace llvm; 18 19 namespace clang { 20 namespace 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. 24 bool 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("?*]", 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(Separator, 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(I); 84 J < End && (Globstar || FilePath[J] != Separator); ++J) { 85 if (matchFilePath(Pat, FilePath.substr(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("]/", 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