internal/str_format/parser.h

0001 // Copyright 2020 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_PARSER_H_
0016 #define ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_
0017
0018 #include <stddef.h>
0019 #include <stdlib.h>
0020
0021 #include <cassert>
0022 #include <cstring>
0023 #include <initializer_list>
0024 #include <memory>
0025 #include <string>
0026 #include <utility>
0027 #include <vector>
0028
0029 #include "absl/base/config.h"
0030 #include "absl/base/optimization.h"
0031 #include "absl/strings/internal/str_format/checker.h"
0032 #include "absl/strings/internal/str_format/constexpr_parser.h"
0033 #include "absl/strings/internal/str_format/extension.h"
0034 #include "absl/strings/string_view.h"
0035
0036 namespace absl {
0037 ABSL_NAMESPACE_BEGIN
0038 namespace str_format_internal {
0039
0040 std::string LengthModToString(LengthMod v);
0041
0042 const char* ConsumeUnboundConversionNoInline(const char* p, const char* end,
0043                                              UnboundConversion* conv,
0044                                              int* next_arg);
0045
0046 // Parse the format string provided in 'src' and pass the identified items into
0047 // 'consumer'.
0048 // Text runs will be passed by calling
0049 //   Consumer::Append(string_view);
0050 // ConversionItems will be passed by calling
0051 //   Consumer::ConvertOne(UnboundConversion, string_view);
0052 // In the case of ConvertOne, the string_view that is passed is the
0053 // portion of the format string corresponding to the conversion, not including
0054 // the leading %. On success, it returns true. On failure, it stops and returns
0055 // false.
0056 template <typename Consumer>
0057 bool ParseFormatString(string_view src, Consumer consumer) {
0058   int next_arg = 0;
0059   const char* p = src.data();
0060   const char* const end = p + src.size();
0061   while (p != end) {
0062     const char* percent =
0063         static_cast<const char*>(memchr(p, '%', static_cast<size_t>(end - p)));
0064     if (!percent) {
0065       // We found the last substring.
0066       return consumer.Append(string_view(p, static_cast<size_t>(end - p)));
0067     }
0068     // We found a percent, so push the text run then process the percent.
0069     if (ABSL_PREDICT_FALSE(!consumer.Append(
0070             string_view(p, static_cast<size_t>(percent - p))))) {
0071       return false;
0072     }
0073     if (ABSL_PREDICT_FALSE(percent + 1 >= end)) return false;
0074
0075     auto tag = GetTagForChar(percent[1]);
0076     if (tag.is_conv()) {
0077       if (ABSL_PREDICT_FALSE(next_arg < 0)) {
0078         // This indicates an error in the format string.
0079         // The only way to get `next_arg < 0` here is to have a positional
0080         // argument first which sets next_arg to -1 and then a non-positional
0081         // argument.
0082         return false;
0083       }
0084       p = percent + 2;
0085
0086       // Keep this case separate from the one below.
0087       // ConvertOne is more efficient when the compiler can see that the `basic`
0088       // flag is set.
0089       UnboundConversion conv;
0090       conv.conv = tag.as_conv();
0091       conv.arg_position = ++next_arg;
0092       if (ABSL_PREDICT_FALSE(
0093               !consumer.ConvertOne(conv, string_view(percent + 1, 1)))) {
0094         return false;
0095       }
0096     } else if (percent[1] != '%') {
0097       UnboundConversion conv;
0098       p = ConsumeUnboundConversionNoInline(percent + 1, end, &conv, &next_arg);
0099       if (ABSL_PREDICT_FALSE(p == nullptr)) return false;
0100       if (ABSL_PREDICT_FALSE(!consumer.ConvertOne(
0101               conv, string_view(percent + 1,
0102                                 static_cast<size_t>(p - (percent + 1)))))) {
0103         return false;
0104       }
0105     } else {
0106       if (ABSL_PREDICT_FALSE(!consumer.Append("%"))) return false;
0107       p = percent + 2;
0108       continue;
0109     }
0110   }
0111   return true;
0112 }
0113
0114 // Always returns true, or fails to compile in a constexpr context if s does not
0115 // point to a constexpr char array.
0116 constexpr bool EnsureConstexpr(string_view s) {
0117   return s.empty() || s[0] == s[0];
0118 }
0119
0120 class ParsedFormatBase {
0121  public:
0122   explicit ParsedFormatBase(
0123       string_view format, bool allow_ignored,
0124       std::initializer_list<FormatConversionCharSet> convs);
0125
0126   ParsedFormatBase(const ParsedFormatBase& other) { *this = other; }
0127
0128   ParsedFormatBase(ParsedFormatBase&& other) { *this = std::move(other); }
0129
0130   ParsedFormatBase& operator=(const ParsedFormatBase& other) {
0131     if (this == &other) return *this;
0132     has_error_ = other.has_error_;
0133     items_ = other.items_;
0134     size_t text_size = items_.empty() ? 0 : items_.back().text_end;
0135     data_.reset(new char[text_size]);
0136     memcpy(data_.get(), other.data_.get(), text_size);
0137     return *this;
0138   }
0139
0140   ParsedFormatBase& operator=(ParsedFormatBase&& other) {
0141     if (this == &other) return *this;
0142     has_error_ = other.has_error_;
0143     data_ = std::move(other.data_);
0144     items_ = std::move(other.items_);
0145     // Reset the vector to make sure the invariants hold.
0146     other.items_.clear();
0147     return *this;
0148   }
0149
0150   template <typename Consumer>
0151   bool ProcessFormat(Consumer consumer) const {
0152     const char* const base = data_.get();
0153     string_view text(base, 0);
0154     for (const auto& item : items_) {
0155       const char* const end = text.data() + text.size();
0156       text =
0157           string_view(end, static_cast<size_t>((base + item.text_end) - end));
0158       if (item.is_conversion) {
0159         if (!consumer.ConvertOne(item.conv, text)) return false;
0160       } else {
0161         if (!consumer.Append(text)) return false;
0162       }
0163     }
0164     return !has_error_;
0165   }
0166
0167   bool has_error() const { return has_error_; }
0168
0169  private:
0170   // Returns whether the conversions match and if !allow_ignored it verifies
0171   // that all conversions are used by the format.
0172   bool MatchesConversions(
0173       bool allow_ignored,
0174       std::initializer_list<FormatConversionCharSet> convs) const;
0175
0176   struct ParsedFormatConsumer;
0177
0178   struct ConversionItem {
0179     bool is_conversion;
0180     // Points to the past-the-end location of this element in the data_ array.
0181     size_t text_end;
0182     UnboundConversion conv;
0183   };
0184
0185   bool has_error_;
0186   std::unique_ptr<char[]> data_;
0187   std::vector<ConversionItem> items_;
0188 };
0189
0190
0191 // A value type representing a preparsed format.  These can be created, copied
0192 // around, and reused to speed up formatting loops.
0193 // The user must specify through the template arguments the conversion
0194 // characters used in the format. This will be checked at compile time.
0195 //
0196 // This class uses Conv enum values to specify each argument.
0197 // This allows for more flexibility as you can specify multiple possible
0198 // conversion characters for each argument.
0199 // ParsedFormat<char...> is a simplified alias for when the user only
0200 // needs to specify a single conversion character for each argument.
0201 //
0202 // Example:
0203 //   // Extended format supports multiple characters per argument:
0204 //   using MyFormat = ExtendedParsedFormat<Conv::d | Conv::x>;
0205 //   MyFormat GetFormat(bool use_hex) {
0206 //     if (use_hex) return MyFormat("foo %x bar");
0207 //     return MyFormat("foo %d bar");
0208 //   }
0209 //   // 'format' can be used with any value that supports 'd' and 'x',
0210 //   // like `int`.
0211 //   auto format = GetFormat(use_hex);
0212 //   value = StringF(format, i);
0213 //
0214 // This class also supports runtime format checking with the ::New() and
0215 // ::NewAllowIgnored() factory functions.
0216 // This is the only API that allows the user to pass a runtime specified format
0217 // string. These factory functions will return NULL if the format does not match
0218 // the conversions requested by the user.
0219 template <FormatConversionCharSet... C>
0220 class ExtendedParsedFormat : public str_format_internal::ParsedFormatBase {
0221  public:
0222   explicit ExtendedParsedFormat(string_view format)
0223 #ifdef ABSL_INTERNAL_ENABLE_FORMAT_CHECKER
0224       __attribute__((
0225           enable_if(str_format_internal::EnsureConstexpr(format),
0226                     "Format string is not constexpr."),
0227           enable_if(str_format_internal::ValidFormatImpl<C...>(format),
0228                     "Format specified does not match the template arguments.")))
0229 #endif  // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER
0230       : ExtendedParsedFormat(format, false) {
0231   }
0232
0233   // ExtendedParsedFormat factory function.
0234   // The user still has to specify the conversion characters, but they will not
0235   // be checked at compile time. Instead, it will be checked at runtime.
0236   // This delays the checking to runtime, but allows the user to pass
0237   // dynamically sourced formats.
0238   // It returns NULL if the format does not match the conversion characters.
0239   // The user is responsible for checking the return value before using it.
0240   //
0241   // The 'New' variant will check that all the specified arguments are being
0242   // consumed by the format and return NULL if any argument is being ignored.
0243   // The 'NewAllowIgnored' variant will not verify this and will allow formats
0244   // that ignore arguments.
0245   static std::unique_ptr<ExtendedParsedFormat> New(string_view format) {
0246     return New(format, false);
0247   }
0248   static std::unique_ptr<ExtendedParsedFormat> NewAllowIgnored(
0249       string_view format) {
0250     return New(format, true);
0251   }
0252
0253  private:
0254   static std::unique_ptr<ExtendedParsedFormat> New(string_view format,
0255                                                    bool allow_ignored) {
0256     std::unique_ptr<ExtendedParsedFormat> conv(
0257         new ExtendedParsedFormat(format, allow_ignored));
0258     if (conv->has_error()) return nullptr;
0259     return conv;
0260   }
0261
0262   ExtendedParsedFormat(string_view s, bool allow_ignored)
0263       : ParsedFormatBase(s, allow_ignored, {C...}) {}
0264 };
0265 }  // namespace str_format_internal
0266 ABSL_NAMESPACE_END
0267 }  // namespace absl
0268
0269 #endif  // ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_