137 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file implements the functionality of matching a file path name to11/// 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, and23// 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 last31 // 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 format136} // namespace clang137