// Copyright 2020 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_
#define ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_

#include "absl/base/attributes.h"
#include "absl/strings/internal/str_format/arg.h"
#include "absl/strings/internal/str_format/extension.h"

// Compile time check support for entry points.

#ifndef ABSL_INTERNAL_ENABLE_FORMAT_CHECKER
#if ABSL_HAVE_ATTRIBUTE(enable_if) && !defined(__native_client__)
#define ABSL_INTERNAL_ENABLE_FORMAT_CHECKER 1
#endif  // ABSL_HAVE_ATTRIBUTE(enable_if) && !defined(__native_client__)
#endif  // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace str_format_internal {

constexpr bool AllOf() { return true; }

template <typename... T>
constexpr bool AllOf(bool b, T... t) {
  return b && AllOf(t...);
}

#ifdef ABSL_INTERNAL_ENABLE_FORMAT_CHECKER

constexpr bool ContainsChar(const char* chars, char c) {
  return *chars == c || (*chars && ContainsChar(chars + 1, c));
}

// A constexpr compatible list of Convs.
struct ConvList {
  const FormatConversionCharSet* array;
  int count;

  // We do the bound check here to avoid having to do it on the callers.
  // Returning an empty FormatConversionCharSet has the same effect as
  // short circuiting because it will never match any conversion.
  constexpr FormatConversionCharSet operator[](int i) const {
    return i < count ? array[i] : FormatConversionCharSet{};
  }

  constexpr ConvList without_front() const {
    return count != 0 ? ConvList{array + 1, count - 1} : *this;
  }
};

template <size_t count>
struct ConvListT {
  // Make sure the array has size > 0.
  FormatConversionCharSet list[count ? count : 1];
};

constexpr char GetChar(string_view str, size_t index) {
  return index < str.size() ? str[index] : char{};
}

constexpr string_view ConsumeFront(string_view str, size_t len = 1) {
  return len <= str.size() ? string_view(str.data() + len, str.size() - len)
                           : string_view();
}

constexpr string_view ConsumeAnyOf(string_view format, const char* chars) {
  return ContainsChar(chars, GetChar(format, 0))
             ? ConsumeAnyOf(ConsumeFront(format), chars)
             : format;
}

constexpr bool IsDigit(char c) { return c >= '0' && c <= '9'; }

// Helper class for the ParseDigits function.
// It encapsulates the two return values we need there.
struct Integer {
  string_view format;
  int value;

  // If the next character is a '$', consume it.
  // Otherwise, make `this` an invalid positional argument.
  constexpr Integer ConsumePositionalDollar() const {
    return GetChar(format, 0) == '$' ? Integer{ConsumeFront(format), value}
                                     : Integer{format, 0};
  }
};

constexpr Integer ParseDigits(string_view format, int value = 0) {
  return IsDigit(GetChar(format, 0))
             ? ParseDigits(ConsumeFront(format),
                           10 * value + GetChar(format, 0) - '0')
             : Integer{format, value};
}

// Parse digits for a positional argument.
// The parsing also consumes the '$'.
constexpr Integer ParsePositional(string_view format) {
  return ParseDigits(format).ConsumePositionalDollar();
}

// Parses a single conversion specifier.
// See ConvParser::Run() for post conditions.
class ConvParser {
  constexpr ConvParser SetFormat(string_view format) const {
    return ConvParser(format, args_, error_, arg_position_, is_positional_);
  }

  constexpr ConvParser SetArgs(ConvList args) const {
    return ConvParser(format_, args, error_, arg_position_, is_positional_);
  }

  constexpr ConvParser SetError(bool error) const {
    return ConvParser(format_, args_, error_ || error, arg_position_,
                      is_positional_);
  }

  constexpr ConvParser SetArgPosition(int arg_position) const {
    return ConvParser(format_, args_, error_, arg_position, is_positional_);
  }

  // Consumes the next arg and verifies that it matches `conv`.
  // `error_` is set if there is no next arg or if it doesn't match `conv`.
  constexpr ConvParser ConsumeNextArg(char conv) const {
    return SetArgs(args_.without_front()).SetError(!Contains(args_[0], conv));
  }

  // Verify that positional argument `i.value` matches `conv`.
  // `error_` is set if `i.value` is not a valid argument or if it doesn't
  // match.
  constexpr ConvParser VerifyPositional(Integer i, char conv) const {
    return SetFormat(i.format).SetError(!Contains(args_[i.value - 1], conv));
  }

  // Parse the position of the arg and store it in `arg_position_`.
  constexpr ConvParser ParseArgPosition(Integer arg) const {
    return SetFormat(arg.format).SetArgPosition(arg.value);
  }

  // Consume the flags.
  constexpr ConvParser ParseFlags() const {
    return SetFormat(ConsumeAnyOf(format_, "-+ #0"));
  }

  // Consume the width.
  // If it is '*', we verify that it matches `args_`. `error_` is set if it
  // doesn't match.
  constexpr ConvParser ParseWidth() const {
    return IsDigit(GetChar(format_, 0))
               ? SetFormat(ParseDigits(format_).format)
               : GetChar(format_, 0) == '*'
                     ? is_positional_
                           ? VerifyPositional(
                                 ParsePositional(ConsumeFront(format_)), '*')
                           : SetFormat(ConsumeFront(format_))
                                 .ConsumeNextArg('*')
                     : *this;
  }

  // Consume the precision.
  // If it is '*', we verify that it matches `args_`. `error_` is set if it
  // doesn't match.
  constexpr ConvParser ParsePrecision() const {
    return GetChar(format_, 0) != '.'
               ? *this
               : GetChar(format_, 1) == '*'
                     ? is_positional_
                           ? VerifyPositional(
                                 ParsePositional(ConsumeFront(format_, 2)), '*')
                           : SetFormat(ConsumeFront(format_, 2))
                                 .ConsumeNextArg('*')
                     : SetFormat(ParseDigits(ConsumeFront(format_)).format);
  }

  // Consume the length characters.
  constexpr ConvParser ParseLength() const {
    return SetFormat(ConsumeAnyOf(format_, "lLhjztq"));
  }

  // Consume the conversion character and verify that it matches `args_`.
  // `error_` is set if it doesn't match.
  constexpr ConvParser ParseConversion() const {
    return is_positional_
               ? VerifyPositional({ConsumeFront(format_), arg_position_},
                                  GetChar(format_, 0))
               : ConsumeNextArg(GetChar(format_, 0))
                     .SetFormat(ConsumeFront(format_));
  }

  constexpr ConvParser(string_view format, ConvList args, bool error,
                       int arg_position, bool is_positional)
      : format_(format),
        args_(args),
        error_(error),
        arg_position_(arg_position),
        is_positional_(is_positional) {}

 public:
  constexpr ConvParser(string_view format, ConvList args, bool is_positional)
      : format_(format),
        args_(args),
        error_(false),
        arg_position_(0),
        is_positional_(is_positional) {}

  // Consume the whole conversion specifier.
  // `format()` will be set to the character after the conversion character.
  // `error()` will be set if any of the arguments do not match.
  constexpr ConvParser Run() const {
    return (is_positional_ ? ParseArgPosition(ParsePositional(format_)) : *this)
        .ParseFlags()
        .ParseWidth()
        .ParsePrecision()
        .ParseLength()
        .ParseConversion();
  }

  constexpr string_view format() const { return format_; }
  constexpr ConvList args() const { return args_; }
  constexpr bool error() const { return error_; }
  constexpr bool is_positional() const { return is_positional_; }

 private:
  string_view format_;
  // Current list of arguments. If we are not in positional mode we will consume
  // from the front.
  ConvList args_;
  bool error_;
  // Holds the argument position of the conversion character, if we are in
  // positional mode. Otherwise, it is unspecified.
  int arg_position_;
  // Whether we are in positional mode.
  // It changes the behavior of '*' and where to find the converted argument.
  bool is_positional_;
};

// Parses a whole format expression.
// See FormatParser::Run().
class FormatParser {
  static constexpr bool FoundPercent(string_view format) {
    return format.empty() ||
           (GetChar(format, 0) == '%' && GetChar(format, 1) != '%');
  }

  // We use an inner function to increase the recursion limit.
  // The inner function consumes up to `limit` characters on every run.
  // This increases the limit from 512 to ~512*limit.
  static constexpr string_view ConsumeNonPercentInner(string_view format,
                                                      int limit = 20) {
    return FoundPercent(format) || !limit
               ? format
               : ConsumeNonPercentInner(
                     ConsumeFront(format, GetChar(format, 0) == '%' &&
                                                  GetChar(format, 1) == '%'
                                              ? 2
                                              : 1),
                     limit - 1);
  }

  // Consume characters until the next conversion spec %.
  // It skips %%.
  static constexpr string_view ConsumeNonPercent(string_view format) {
    return FoundPercent(format)
               ? format
               : ConsumeNonPercent(ConsumeNonPercentInner(format));
  }

  static constexpr bool IsPositional(string_view format) {
    return IsDigit(GetChar(format, 0)) ? IsPositional(ConsumeFront(format))
                                       : GetChar(format, 0) == '$';
  }

  constexpr bool RunImpl(bool is_positional) const {
    // In non-positional mode we require all arguments to be consumed.
    // In positional mode just reaching the end of the format without errors is
    // enough.
    return (format_.empty() && (is_positional || args_.count == 0)) ||
           (!format_.empty() &&
            ValidateArg(
                ConvParser(ConsumeFront(format_), args_, is_positional).Run()));
  }

  constexpr bool ValidateArg(ConvParser conv) const {
    return !conv.error() && FormatParser(conv.format(), conv.args())
                                .RunImpl(conv.is_positional());
  }

 public:
  constexpr FormatParser(string_view format, ConvList args)
      : format_(ConsumeNonPercent(format)), args_(args) {}

  // Runs the parser for `format` and `args`.
  // It verifies that the format is valid and that all conversion specifiers
  // match the arguments passed.
  // In non-positional mode it also verfies that all arguments are consumed.
  constexpr bool Run() const {
    return RunImpl(!format_.empty() && IsPositional(ConsumeFront(format_)));
  }

 private:
  string_view format_;
  // Current list of arguments.
  // If we are not in positional mode we will consume from the front and will
  // have to be empty in the end.
  ConvList args_;
};

template <FormatConversionCharSet... C>
constexpr bool ValidFormatImpl(string_view format) {
  return FormatParser(format,
                      {ConvListT<sizeof...(C)>{{C...}}.list, sizeof...(C)})
      .Run();
}

#endif  // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER

}  // namespace str_format_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_