summaryrefslogtreecommitdiff
path: root/absl/strings/internal/str_format/parser.h
blob: 32b91d034d0ce0d32f84f8aefce01c9b8464b121 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
// 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_PARSER_H_
#define ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_

#include <limits.h>
#include <stddef.h>
#include <stdlib.h>

#include <cassert>
#include <cstdint>
#include <initializer_list>
#include <iosfwd>
#include <iterator>
#include <memory>
#include <string>
#include <vector>

#include "absl/strings/internal/str_format/checker.h"
#include "absl/strings/internal/str_format/extension.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace str_format_internal {

enum class LengthMod : std::uint8_t { h, hh, l, ll, L, j, z, t, q, none };

std::string LengthModToString(LengthMod v);

// The analyzed properties of a single specified conversion.
struct UnboundConversion {
  UnboundConversion() {}

  class InputValue {
   public:
    void set_value(int value) {
      assert(value >= 0);
      value_ = value;
    }
    int value() const { return value_; }

    // Marks the value as "from arg". aka the '*' format.
    // Requires `value >= 1`.
    // When set, is_from_arg() return true and get_from_arg() returns the
    // original value.
    // `value()`'s return value is unspecfied in this state.
    void set_from_arg(int value) {
      assert(value > 0);
      value_ = -value - 1;
    }
    bool is_from_arg() const { return value_ < -1; }
    int get_from_arg() const {
      assert(is_from_arg());
      return -value_ - 1;
    }

   private:
    int value_ = -1;
  };

  // No need to initialize. It will always be set in the parser.
  int arg_position;

  InputValue width;
  InputValue precision;

  Flags flags = Flags::kBasic;
  LengthMod length_mod = LengthMod::none;
  FormatConversionChar conv = FormatConversionCharInternal::kNone;
};

// Consume conversion spec prefix (not including '%') of [p, end) if valid.
// Examples of valid specs would be e.g.: "s", "d", "-12.6f".
// If valid, it returns the first character following the conversion spec,
// and the spec part is broken down and returned in 'conv'.
// If invalid, returns nullptr.
const char* ConsumeUnboundConversion(const char* p, const char* end,
                                     UnboundConversion* conv, int* next_arg);

// Helper tag class for the table below.
// It allows fast `char -> ConversionChar/LengthMod/Flags` checking and
// conversions.
class ConvTag {
 public:
  constexpr ConvTag(FormatConversionChar conversion_char)  // NOLINT
      : tag_(static_cast<uint8_t>(conversion_char)) {}
  constexpr ConvTag(LengthMod length_mod)  // NOLINT
      : tag_(0x80 | static_cast<uint8_t>(length_mod)) {}
  constexpr ConvTag(Flags flags)  // NOLINT
      : tag_(0xc0 | static_cast<uint8_t>(flags)) {}
  constexpr ConvTag() : tag_(0xFF) {}

  bool is_conv() const { return (tag_ & 0x80) == 0; }
  bool is_length() const { return (tag_ & 0xC0) == 0x80; }
  bool is_flags() const { return (tag_ & 0xE0) == 0xC0; }

  FormatConversionChar as_conv() const {
    assert(is_conv());
    assert(!is_length());
    assert(!is_flags());
    return static_cast<FormatConversionChar>(tag_);
  }
  LengthMod as_length() const {
    assert(!is_conv());
    assert(is_length());
    assert(!is_flags());
    return static_cast<LengthMod>(tag_ & 0x3F);
  }
  Flags as_flags() const {
    assert(!is_conv());
    assert(!is_length());
    assert(is_flags());
    return static_cast<Flags>(tag_ & 0x1F);
  }

 private:
  uint8_t tag_;
};

extern const ConvTag kTags[256];
// Keep a single table for all the conversion chars and length modifiers.
inline ConvTag GetTagForChar(char c) {
  return kTags[static_cast<unsigned char>(c)];
}

// Parse the format string provided in 'src' and pass the identified items into
// 'consumer'.
// Text runs will be passed by calling
//   Consumer::Append(string_view);
// ConversionItems will be passed by calling
//   Consumer::ConvertOne(UnboundConversion, string_view);
// In the case of ConvertOne, the string_view that is passed is the
// portion of the format string corresponding to the conversion, not including
// the leading %. On success, it returns true. On failure, it stops and returns
// false.
template <typename Consumer>
bool ParseFormatString(string_view src, Consumer consumer) {
  int next_arg = 0;
  const char* p = src.data();
  const char* const end = p + src.size();
  while (p != end) {
    const char* percent =
        static_cast<const char*>(memchr(p, '%', static_cast<size_t>(end - p)));
    if (!percent) {
      // We found the last substring.
      return consumer.Append(string_view(p, end - p));
    }
    // We found a percent, so push the text run then process the percent.
    if (ABSL_PREDICT_FALSE(!consumer.Append(string_view(p, percent - p)))) {
      return false;
    }
    if (ABSL_PREDICT_FALSE(percent + 1 >= end)) return false;

    auto tag = GetTagForChar(percent[1]);
    if (tag.is_conv()) {
      if (ABSL_PREDICT_FALSE(next_arg < 0)) {
        // This indicates an error in the format string.
        // The only way to get `next_arg < 0` here is to have a positional
        // argument first which sets next_arg to -1 and then a non-positional
        // argument.
        return false;
      }
      p = percent + 2;

      // Keep this case separate from the one below.
      // ConvertOne is more efficient when the compiler can see that the `basic`
      // flag is set.
      UnboundConversion conv;
      conv.conv = tag.as_conv();
      conv.arg_position = ++next_arg;
      if (ABSL_PREDICT_FALSE(
              !consumer.ConvertOne(conv, string_view(percent + 1, 1)))) {
        return false;
      }
    } else if (percent[1] != '%') {
      UnboundConversion conv;
      p = ConsumeUnboundConversion(percent + 1, end, &conv, &next_arg);
      if (ABSL_PREDICT_FALSE(p == nullptr)) return false;
      if (ABSL_PREDICT_FALSE(!consumer.ConvertOne(
          conv, string_view(percent + 1, p - (percent + 1))))) {
        return false;
      }
    } else {
      if (ABSL_PREDICT_FALSE(!consumer.Append("%"))) return false;
      p = percent + 2;
      continue;
    }
  }
  return true;
}

// Always returns true, or fails to compile in a constexpr context if s does not
// point to a constexpr char array.
constexpr bool EnsureConstexpr(string_view s) {
  return s.empty() || s[0] == s[0];
}

class ParsedFormatBase {
 public:
  explicit ParsedFormatBase(
      string_view format, bool allow_ignored,
      std::initializer_list<FormatConversionCharSet> convs);

  ParsedFormatBase(const ParsedFormatBase& other) { *this = other; }

  ParsedFormatBase(ParsedFormatBase&& other) { *this = std::move(other); }

  ParsedFormatBase& operator=(const ParsedFormatBase& other) {
    if (this == &other) return *this;
    has_error_ = other.has_error_;
    items_ = other.items_;
    size_t text_size = items_.empty() ? 0 : items_.back().text_end;
    data_.reset(new char[text_size]);
    memcpy(data_.get(), other.data_.get(), text_size);
    return *this;
  }

  ParsedFormatBase& operator=(ParsedFormatBase&& other) {
    if (this == &other) return *this;
    has_error_ = other.has_error_;
    data_ = std::move(other.data_);
    items_ = std::move(other.items_);
    // Reset the vector to make sure the invariants hold.
    other.items_.clear();
    return *this;
  }

  template <typename Consumer>
  bool ProcessFormat(Consumer consumer) const {
    const char* const base = data_.get();
    string_view text(base, 0);
    for (const auto& item : items_) {
      const char* const end = text.data() + text.size();
      text =
          string_view(end, static_cast<size_t>((base + item.text_end) - end));
      if (item.is_conversion) {
        if (!consumer.ConvertOne(item.conv, text)) return false;
      } else {
        if (!consumer.Append(text)) return false;
      }
    }
    return !has_error_;
  }

  bool has_error() const { return has_error_; }

 private:
  // Returns whether the conversions match and if !allow_ignored it verifies
  // that all conversions are used by the format.
  bool MatchesConversions(
      bool allow_ignored,
      std::initializer_list<FormatConversionCharSet> convs) const;

  struct ParsedFormatConsumer;

  struct ConversionItem {
    bool is_conversion;
    // Points to the past-the-end location of this element in the data_ array.
    size_t text_end;
    UnboundConversion conv;
  };

  bool has_error_;
  std::unique_ptr<char[]> data_;
  std::vector<ConversionItem> items_;
};


// A value type representing a preparsed format.  These can be created, copied
// around, and reused to speed up formatting loops.
// The user must specify through the template arguments the conversion
// characters used in the format. This will be checked at compile time.
//
// This class uses Conv enum values to specify each argument.
// This allows for more flexibility as you can specify multiple possible
// conversion characters for each argument.
// ParsedFormat<char...> is a simplified alias for when the user only
// needs to specify a single conversion character for each argument.
//
// Example:
//   // Extended format supports multiple characters per argument:
//   using MyFormat = ExtendedParsedFormat<Conv::d | Conv::x>;
//   MyFormat GetFormat(bool use_hex) {
//     if (use_hex) return MyFormat("foo %x bar");
//     return MyFormat("foo %d bar");
//   }
//   // 'format' can be used with any value that supports 'd' and 'x',
//   // like `int`.
//   auto format = GetFormat(use_hex);
//   value = StringF(format, i);
//
// This class also supports runtime format checking with the ::New() and
// ::NewAllowIgnored() factory functions.
// This is the only API that allows the user to pass a runtime specified format
// string. These factory functions will return NULL if the format does not match
// the conversions requested by the user.
template <FormatConversionCharSet... C>
class ExtendedParsedFormat : public str_format_internal::ParsedFormatBase {
 public:
  explicit ExtendedParsedFormat(string_view format)
#ifdef ABSL_INTERNAL_ENABLE_FORMAT_CHECKER
      __attribute__((
          enable_if(str_format_internal::EnsureConstexpr(format),
                    "Format string is not constexpr."),
          enable_if(str_format_internal::ValidFormatImpl<C...>(format),
                    "Format specified does not match the template arguments.")))
#endif  // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER
      : ExtendedParsedFormat(format, false) {
  }

  // ExtendedParsedFormat factory function.
  // The user still has to specify the conversion characters, but they will not
  // be checked at compile time. Instead, it will be checked at runtime.
  // This delays the checking to runtime, but allows the user to pass
  // dynamically sourced formats.
  // It returns NULL if the format does not match the conversion characters.
  // The user is responsible for checking the return value before using it.
  //
  // The 'New' variant will check that all the specified arguments are being
  // consumed by the format and return NULL if any argument is being ignored.
  // The 'NewAllowIgnored' variant will not verify this and will allow formats
  // that ignore arguments.
  static std::unique_ptr<ExtendedParsedFormat> New(string_view format) {
    return New(format, false);
  }
  static std::unique_ptr<ExtendedParsedFormat> NewAllowIgnored(
      string_view format) {
    return New(format, true);
  }

 private:
  static std::unique_ptr<ExtendedParsedFormat> New(string_view format,
                                                   bool allow_ignored) {
    std::unique_ptr<ExtendedParsedFormat> conv(
        new ExtendedParsedFormat(format, allow_ignored));
    if (conv->has_error()) return nullptr;
    return conv;
  }

  ExtendedParsedFormat(string_view s, bool allow_ignored)
      : ParsedFormatBase(s, allow_ignored, {C...}) {}
};
}  // namespace str_format_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_