//===--- MatchFilePath.cpp - Match file path with pattern -------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements the functionality of matching a file path name to
/// a pattern, similar to the POSIX fnmatch() function.
///
//===----------------------------------------------------------------------===//

#include "MatchFilePath.h"

using namespace llvm;

namespace clang {
namespace format {

// Check whether `FilePath` matches `Pattern` based on POSIX 2.13.1, 2.13.2, and
// Rule 1 of 2.13.3.
bool matchFilePath(StringRef Pattern, StringRef FilePath) {
  assert(!Pattern.empty());
  assert(!FilePath.empty());

  const auto FilePathBack = FilePath.back();

  // No match if `Pattern` ends with a non-meta character not equal to the last
  // character of `FilePath`.
  if (const auto C = Pattern.back(); !strchr("?*]", C) && C != FilePathBack)
    return false;

  constexpr auto Separator = '/';
  const auto EOP = Pattern.size();  // End of `Pattern`.
  const auto End = FilePath.size(); // End of `FilePath`.
  unsigned I = 0;                   // Index to `Pattern`.

  for (unsigned J = 0; J < End; ++J) {
    if (I == EOP)
      return false;

    switch (const auto F = FilePath[J]; Pattern[I]) {
    case '\\':
      if (++I == EOP || F != Pattern[I])
        return false;
      break;
    case '?':
      if (F == Separator)
        return false;
      break;
    case '*': {
      bool Globstar = I == 0 || Pattern[I - 1] == Separator;
      int StarCount = 1;
      for (; ++I < EOP && Pattern[I] == '*'; ++StarCount) {
        // Skip consecutive stars.
      }
      if (StarCount != 2)
        Globstar = false;
      const auto K = FilePath.find(Separator, J); // Index of next `Separator`.
      const bool NoMoreSeparatorsInFilePath = K == StringRef::npos;
      if (I == EOP) // `Pattern` ends with a star.
        return Globstar || NoMoreSeparatorsInFilePath;
      if (Pattern[I] != Separator) {
        // `Pattern` ends with a lone backslash.
        if (Pattern[I] == '\\' && ++I == EOP)
          return false;
        Globstar = false;
      }
      // The star is followed by a (possibly escaped) `Separator`.
      if (Pattern[I] == Separator) {
        if (!Globstar) {
          if (NoMoreSeparatorsInFilePath)
            return false;
          J = K; // Skip to next `Separator` in `FilePath`.
          break;
        }
        if (++I == EOP)
          return FilePathBack == Separator;
      }
      // Recurse.
      for (auto Pat = Pattern.substr(I);
           J < End && (Globstar || FilePath[J] != Separator); ++J) {
        if (matchFilePath(Pat, FilePath.substr(J)))
          return true;
      }
      return false;
    }
    case '[':
      // Skip e.g. `[!]`.
      if (I + 3 < EOP || (I + 3 == EOP && Pattern[I + 1] != '!')) {
        // Skip unpaired `[`, brackets containing slashes, and `[]`.
        if (const auto K = Pattern.find_first_of("]/", I + 1);
            K != StringRef::npos && Pattern[K] == ']' && K > I + 1) {
          if (F == Separator)
            return false;
          ++I; // After the `[`.
          bool Negated = false;
          if (Pattern[I] == '!') {
            Negated = true;
            ++I; // After the `!`.
          }
          bool Match = false;
          do {
            if (I + 2 < K && Pattern[I + 1] == '-') {
              Match = Pattern[I] <= F && F <= Pattern[I + 2];
              I += 3; // After the range, e.g. `A-Z`.
            } else {
              Match = F == Pattern[I++];
            }
          } while (!Match && I < K);
          if (Negated ? Match : !Match)
            return false;
          I = K + 1; // After the `]`.
          continue;
        }
      }
      [[fallthrough]]; // Match `[` literally.
    default:
      if (F != Pattern[I])
        return false;
    }

    ++I;
  }

  // Match trailing stars with null strings.
  while (I < EOP && Pattern[I] == '*')
    ++I;

  return I == EOP;
}

} // namespace format
} // namespace clang