internal/str_format/constexpr_parser.h

0001 // Copyright 2022 The Abseil Authors
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //     https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_CONSTEXPR_PARSER_H_
0016 #define ABSL_STRINGS_INTERNAL_STR_FORMAT_CONSTEXPR_PARSER_H_
0017
0018 #include <cassert>
0019 #include <cstdint>
0020 #include <cstdio>
0021 #include <limits>
0022
0023 #include "absl/base/config.h"
0024 #include "absl/base/const_init.h"
0025 #include "absl/base/optimization.h"
0026 #include "absl/strings/internal/str_format/extension.h"
0027
0028 namespace absl {
0029 ABSL_NAMESPACE_BEGIN
0030 namespace str_format_internal {
0031
0032 // The analyzed properties of a single specified conversion.
0033 struct UnboundConversion {
0034   // This is a user defined default constructor on purpose to skip the
0035   // initialization of parts of the object that are not necessary.
0036   UnboundConversion() {}  // NOLINT
0037
0038   // This constructor is provided for the static checker. We don't want to do
0039   // the unnecessary initialization in the normal case.
0040   explicit constexpr UnboundConversion(absl::ConstInitType)
0041       : arg_position{}, width{}, precision{} {}
0042
0043   class InputValue {
0044    public:
0045     constexpr void set_value(int value) {
0046       assert(value >= 0);
0047       value_ = value;
0048     }
0049     constexpr int value() const { return value_; }
0050
0051     // Marks the value as "from arg". aka the '*' format.
0052     // Requires `value >= 1`.
0053     // When set, is_from_arg() return true and get_from_arg() returns the
0054     // original value.
0055     // `value()`'s return value is unspecified in this state.
0056     constexpr void set_from_arg(int value) {
0057       assert(value > 0);
0058       value_ = -value - 1;
0059     }
0060     constexpr bool is_from_arg() const { return value_ < -1; }
0061     constexpr int get_from_arg() const {
0062       assert(is_from_arg());
0063       return -value_ - 1;
0064     }
0065
0066    private:
0067     int value_ = -1;
0068   };
0069
0070   // No need to initialize. It will always be set in the parser.
0071   int arg_position;
0072
0073   InputValue width;
0074   InputValue precision;
0075
0076   Flags flags = Flags::kBasic;
0077   LengthMod length_mod = LengthMod::none;
0078   FormatConversionChar conv = FormatConversionCharInternal::kNone;
0079 };
0080
0081 // Helper tag class for the table below.
0082 // It allows fast `char -> ConversionChar/LengthMod/Flags` checking and
0083 // conversions.
0084 class ConvTag {
0085  public:
0086   constexpr ConvTag(FormatConversionChar conversion_char)  // NOLINT
0087       : tag_(static_cast<uint8_t>(conversion_char)) {}
0088   constexpr ConvTag(LengthMod length_mod)  // NOLINT
0089       : tag_(0x80 | static_cast<uint8_t>(length_mod)) {}
0090   constexpr ConvTag(Flags flags)  // NOLINT
0091       : tag_(0xc0 | static_cast<uint8_t>(flags)) {}
0092   constexpr ConvTag() : tag_(0xFF) {}
0093
0094   constexpr bool is_conv() const { return (tag_ & 0x80) == 0; }
0095   constexpr bool is_length() const { return (tag_ & 0xC0) == 0x80; }
0096   constexpr bool is_flags() const { return (tag_ & 0xE0) == 0xC0; }
0097
0098   constexpr FormatConversionChar as_conv() const {
0099     assert(is_conv());
0100     assert(!is_length());
0101     assert(!is_flags());
0102     return static_cast<FormatConversionChar>(tag_);
0103   }
0104   constexpr LengthMod as_length() const {
0105     assert(!is_conv());
0106     assert(is_length());
0107     assert(!is_flags());
0108     return static_cast<LengthMod>(tag_ & 0x3F);
0109   }
0110   constexpr Flags as_flags() const {
0111     assert(!is_conv());
0112     assert(!is_length());
0113     assert(is_flags());
0114     return static_cast<Flags>(tag_ & 0x1F);
0115   }
0116
0117  private:
0118   uint8_t tag_;
0119 };
0120
0121 struct ConvTagHolder {
0122   using CC = FormatConversionCharInternal;
0123   using LM = LengthMod;
0124
0125   // Abbreviations to fit in the table below.
0126   static constexpr auto kFSign = Flags::kSignCol;
0127   static constexpr auto kFAlt = Flags::kAlt;
0128   static constexpr auto kFPos = Flags::kShowPos;
0129   static constexpr auto kFLeft = Flags::kLeft;
0130   static constexpr auto kFZero = Flags::kZero;
0131
0132   static constexpr ConvTag value[256] = {
0133       {},     {},    {},    {},    {},    {},     {},    {},     // 00-07
0134       {},     {},    {},    {},    {},    {},     {},    {},     // 08-0f
0135       {},     {},    {},    {},    {},    {},     {},    {},     // 10-17
0136       {},     {},    {},    {},    {},    {},     {},    {},     // 18-1f
0137       kFSign, {},    {},    kFAlt, {},    {},     {},    {},     //  !"#$%&'
0138       {},     {},    {},    kFPos, {},    kFLeft, {},    {},     // ()*+,-./
0139       kFZero, {},    {},    {},    {},    {},     {},    {},     // 01234567
0140       {},     {},    {},    {},    {},    {},     {},    {},     // 89:;<=>?
0141       {},     CC::A, {},    {},    {},    CC::E,  CC::F, CC::G,  // @ABCDEFG
0142       {},     {},    {},    {},    LM::L, {},     {},    {},     // HIJKLMNO
0143       {},     {},    {},    {},    {},    {},     {},    {},     // PQRSTUVW
0144       CC::X,  {},    {},    {},    {},    {},     {},    {},     // XYZ[\]^_
0145       {},     CC::a, {},    CC::c, CC::d, CC::e,  CC::f, CC::g,  // `abcdefg
0146       LM::h,  CC::i, LM::j, {},    LM::l, {},     CC::n, CC::o,  // hijklmno
0147       CC::p,  LM::q, {},    CC::s, LM::t, CC::u,  CC::v, {},     // pqrstuvw
0148       CC::x,  {},    LM::z, {},    {},    {},     {},    {},     // xyz{|}!
0149       {},     {},    {},    {},    {},    {},     {},    {},     // 80-87
0150       {},     {},    {},    {},    {},    {},     {},    {},     // 88-8f
0151       {},     {},    {},    {},    {},    {},     {},    {},     // 90-97
0152       {},     {},    {},    {},    {},    {},     {},    {},     // 98-9f
0153       {},     {},    {},    {},    {},    {},     {},    {},     // a0-a7
0154       {},     {},    {},    {},    {},    {},     {},    {},     // a8-af
0155       {},     {},    {},    {},    {},    {},     {},    {},     // b0-b7
0156       {},     {},    {},    {},    {},    {},     {},    {},     // b8-bf
0157       {},     {},    {},    {},    {},    {},     {},    {},     // c0-c7
0158       {},     {},    {},    {},    {},    {},     {},    {},     // c8-cf
0159       {},     {},    {},    {},    {},    {},     {},    {},     // d0-d7
0160       {},     {},    {},    {},    {},    {},     {},    {},     // d8-df
0161       {},     {},    {},    {},    {},    {},     {},    {},     // e0-e7
0162       {},     {},    {},    {},    {},    {},     {},    {},     // e8-ef
0163       {},     {},    {},    {},    {},    {},     {},    {},     // f0-f7
0164       {},     {},    {},    {},    {},    {},     {},    {},     // f8-ff
0165   };
0166 };
0167
0168 // Keep a single table for all the conversion chars and length modifiers.
0169 constexpr ConvTag GetTagForChar(char c) {
0170   return ConvTagHolder::value[static_cast<unsigned char>(c)];
0171 }
0172
0173 constexpr bool CheckFastPathSetting(const UnboundConversion& conv) {
0174   bool width_precision_needed =
0175       conv.width.value() >= 0 || conv.precision.value() >= 0;
0176   if (width_precision_needed && conv.flags == Flags::kBasic) {
0177 #if defined(__clang__)
0178     // Some compilers complain about this in constexpr even when not executed,
0179     // so only enable the error dump in clang.
0180     fprintf(stderr,
0181             "basic=%d left=%d show_pos=%d sign_col=%d alt=%d zero=%d "
0182             "width=%d precision=%d\n",
0183             conv.flags == Flags::kBasic ? 1 : 0,
0184             FlagsContains(conv.flags, Flags::kLeft) ? 1 : 0,
0185             FlagsContains(conv.flags, Flags::kShowPos) ? 1 : 0,
0186             FlagsContains(conv.flags, Flags::kSignCol) ? 1 : 0,
0187             FlagsContains(conv.flags, Flags::kAlt) ? 1 : 0,
0188             FlagsContains(conv.flags, Flags::kZero) ? 1 : 0, conv.width.value(),
0189             conv.precision.value());
0190 #endif  // defined(__clang__)
0191     return false;
0192   }
0193   return true;
0194 }
0195
0196 constexpr int ParseDigits(char& c, const char*& pos, const char* const end) {
0197   int digits = c - '0';
0198   // We do not want to overflow `digits` so we consume at most digits10
0199   // digits. If there are more digits the parsing will fail later on when the
0200   // digit doesn't match the expected characters.
0201   int num_digits = std::numeric_limits<int>::digits10;
0202   for (;;) {
0203     if (ABSL_PREDICT_FALSE(pos == end)) break;
0204     c = *pos++;
0205     if ('0' > c || c > '9') break;
0206     --num_digits;
0207     if (ABSL_PREDICT_FALSE(!num_digits)) break;
0208     digits = 10 * digits + c - '0';
0209   }
0210   return digits;
0211 }
0212
0213 template <bool is_positional>
0214 constexpr const char* ConsumeConversion(const char* pos, const char* const end,
0215                                         UnboundConversion* conv,
0216                                         int* next_arg) {
0217   const char* const original_pos = pos;
0218   char c = 0;
0219   // Read the next char into `c` and update `pos`. Returns false if there are
0220   // no more chars to read.
0221 #define ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR()          \
0222   do {                                                  \
0223     if (ABSL_PREDICT_FALSE(pos == end)) return nullptr; \
0224     c = *pos++;                                         \
0225   } while (0)
0226
0227   if (is_positional) {
0228     ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0229     if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return nullptr;
0230     conv->arg_position = ParseDigits(c, pos, end);
0231     assert(conv->arg_position > 0);
0232     if (ABSL_PREDICT_FALSE(c != '$')) return nullptr;
0233   }
0234
0235   ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0236
0237   // We should start with the basic flag on.
0238   assert(conv->flags == Flags::kBasic);
0239
0240   // Any non alpha character makes this conversion not basic.
0241   // This includes flags (-+ #0), width (1-9, *) or precision (.).
0242   // All conversion characters and length modifiers are alpha characters.
0243   if (c < 'A') {
0244     while (c <= '0') {
0245       auto tag = GetTagForChar(c);
0246       if (tag.is_flags()) {
0247         conv->flags = conv->flags | tag.as_flags();
0248         ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0249       } else {
0250         break;
0251       }
0252     }
0253
0254     if (c <= '9') {
0255       if (c >= '0') {
0256         int maybe_width = ParseDigits(c, pos, end);
0257         if (!is_positional && c == '$') {
0258           if (ABSL_PREDICT_FALSE(*next_arg != 0)) return nullptr;
0259           // Positional conversion.
0260           *next_arg = -1;
0261           return ConsumeConversion<true>(original_pos, end, conv, next_arg);
0262         }
0263         conv->flags = conv->flags | Flags::kNonBasic;
0264         conv->width.set_value(maybe_width);
0265       } else if (c == '*') {
0266         conv->flags = conv->flags | Flags::kNonBasic;
0267         ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0268         if (is_positional) {
0269           if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return nullptr;
0270           conv->width.set_from_arg(ParseDigits(c, pos, end));
0271           if (ABSL_PREDICT_FALSE(c != '$')) return nullptr;
0272           ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0273         } else {
0274           conv->width.set_from_arg(++*next_arg);
0275         }
0276       }
0277     }
0278
0279     if (c == '.') {
0280       conv->flags = conv->flags | Flags::kNonBasic;
0281       ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0282       if ('0' <= c && c <= '9') {
0283         conv->precision.set_value(ParseDigits(c, pos, end));
0284       } else if (c == '*') {
0285         ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0286         if (is_positional) {
0287           if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return nullptr;
0288           conv->precision.set_from_arg(ParseDigits(c, pos, end));
0289           if (c != '$') return nullptr;
0290           ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0291         } else {
0292           conv->precision.set_from_arg(++*next_arg);
0293         }
0294       } else {
0295         conv->precision.set_value(0);
0296       }
0297     }
0298   }
0299
0300   auto tag = GetTagForChar(c);
0301
0302   if (ABSL_PREDICT_FALSE(c == 'v' && conv->flags != Flags::kBasic)) {
0303     return nullptr;
0304   }
0305
0306   if (ABSL_PREDICT_FALSE(!tag.is_conv())) {
0307     if (ABSL_PREDICT_FALSE(!tag.is_length())) return nullptr;
0308
0309     // It is a length modifier.
0310     LengthMod length_mod = tag.as_length();
0311     ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0312     if (c == 'h' && length_mod == LengthMod::h) {
0313       conv->length_mod = LengthMod::hh;
0314       ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0315     } else if (c == 'l' && length_mod == LengthMod::l) {
0316       conv->length_mod = LengthMod::ll;
0317       ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR();
0318     } else {
0319       conv->length_mod = length_mod;
0320     }
0321     tag = GetTagForChar(c);
0322
0323     if (ABSL_PREDICT_FALSE(c == 'v')) return nullptr;
0324     if (ABSL_PREDICT_FALSE(!tag.is_conv())) return nullptr;
0325
0326     // `wchar_t` args are marked non-basic so `Bind()` will copy the length mod.
0327     if (conv->length_mod == LengthMod::l && c == 'c') {
0328       conv->flags = conv->flags | Flags::kNonBasic;
0329     }
0330   }
0331 #undef ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR
0332
0333   assert(CheckFastPathSetting(*conv));
0334   (void)(&CheckFastPathSetting);
0335
0336   conv->conv = tag.as_conv();
0337   if (!is_positional) conv->arg_position = ++*next_arg;
0338   return pos;
0339 }
0340
0341 // Consume conversion spec prefix (not including '%') of [p, end) if valid.
0342 // Examples of valid specs would be e.g.: "s", "d", "-12.6f".
0343 // If valid, it returns the first character following the conversion spec,
0344 // and the spec part is broken down and returned in 'conv'.
0345 // If invalid, returns nullptr.
0346 constexpr const char* ConsumeUnboundConversion(const char* p, const char* end,
0347                                                UnboundConversion* conv,
0348                                                int* next_arg) {
0349   if (*next_arg < 0) return ConsumeConversion<true>(p, end, conv, next_arg);
0350   return ConsumeConversion<false>(p, end, conv, next_arg);
0351 }
0352
0353 }  // namespace str_format_internal
0354 ABSL_NAMESPACE_END
0355 }  // namespace absl
0356
0357 #endif  // ABSL_STRINGS_INTERNAL_STR_FORMAT_CONSTEXPR_PARSER_H_