1/*
2 * Copyright 2012-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <folly/Format.h>
18
19#include <folly/ConstexprMath.h>
20#include <folly/CppAttributes.h>
21#include <folly/container/Array.h>
22
23#include <double-conversion/double-conversion.h>
24
25namespace folly {
26namespace detail {
27
28// ctor for items in the align table
29struct format_table_align_make_item {
30 static constexpr std::size_t size = 256;
31 constexpr FormatArg::Align operator()(std::size_t index) const {
32 // clang-format off
33 return
34 index == '<' ? FormatArg::Align::LEFT:
35 index == '>' ? FormatArg::Align::RIGHT :
36 index == '=' ? FormatArg::Align::PAD_AFTER_SIGN :
37 index == '^' ? FormatArg::Align::CENTER :
38 FormatArg::Align::INVALID;
39 // clang-format on
40 }
41};
42
43// ctor for items in the conv tables for representing parts of nonnegative
44// integers into ascii digits of length Size, over a given base Base
45template <std::size_t Base, std::size_t Size, bool Upper = false>
46struct format_table_conv_make_item {
47 static_assert(Base <= 36, "Base is unrepresentable");
48 struct make_item {
49 std::size_t index{};
50 constexpr explicit make_item(std::size_t index_) : index(index_) {} // gcc49
51 constexpr char alpha(std::size_t ord) const {
52 return ord < 10 ? '0' + ord : (Upper ? 'A' : 'a') + (ord - 10);
53 }
54 constexpr char operator()(std::size_t offset) const {
55 return alpha(index / constexpr_pow(Base, Size - offset - 1) % Base);
56 }
57 };
58 constexpr std::array<char, Size> operator()(std::size_t index) const {
59 return make_array_with<Size>(make_item{index});
60 }
61};
62
63// ctor for items in the sign table
64struct format_table_sign_make_item {
65 static constexpr std::size_t size = 256;
66 constexpr FormatArg::Sign operator()(std::size_t index) const {
67 // clang-format off
68 return
69 index == '+' ? FormatArg::Sign::PLUS_OR_MINUS :
70 index == '-' ? FormatArg::Sign::MINUS :
71 index == ' ' ? FormatArg::Sign::SPACE_OR_MINUS :
72 FormatArg::Sign::INVALID;
73 // clang-format on
74 }
75};
76
77// the tables
78FOLLY_STORAGE_CONSTEXPR auto formatAlignTable =
79 make_array_with<256>(format_table_align_make_item{});
80FOLLY_STORAGE_CONSTEXPR auto formatSignTable =
81 make_array_with<256>(format_table_sign_make_item{});
82FOLLY_STORAGE_CONSTEXPR decltype(formatHexLower) formatHexLower =
83 make_array_with<256>(format_table_conv_make_item<16, 2, false>{});
84FOLLY_STORAGE_CONSTEXPR decltype(formatHexUpper) formatHexUpper =
85 make_array_with<256>(format_table_conv_make_item<16, 2, true>{});
86FOLLY_STORAGE_CONSTEXPR decltype(formatOctal) formatOctal =
87 make_array_with<512>(format_table_conv_make_item<8, 3>{});
88FOLLY_STORAGE_CONSTEXPR decltype(formatBinary) formatBinary =
89 make_array_with<256>(format_table_conv_make_item<2, 8>{});
90
91} // namespace detail
92
93using namespace folly::detail;
94
95void FormatValue<double>::formatHelper(
96 fbstring& piece,
97 int& prefixLen,
98 FormatArg& arg) const {
99 using ::double_conversion::DoubleToStringConverter;
100 using ::double_conversion::StringBuilder;
101
102 arg.validate(FormatArg::Type::FLOAT);
103
104 if (arg.presentation == FormatArg::kDefaultPresentation) {
105 arg.presentation = 'g';
106 }
107
108 const char* infinitySymbol = isupper(arg.presentation) ? "INF" : "inf";
109 const char* nanSymbol = isupper(arg.presentation) ? "NAN" : "nan";
110 char exponentSymbol = isupper(arg.presentation) ? 'E' : 'e';
111
112 if (arg.precision == FormatArg::kDefaultPrecision) {
113 arg.precision = 6;
114 }
115
116 // 2+: for null terminator and optional sign shenanigans.
117 constexpr int bufLen = 2 +
118 constexpr_max(2 + DoubleToStringConverter::kMaxFixedDigitsBeforePoint +
119 DoubleToStringConverter::kMaxFixedDigitsAfterPoint,
120 constexpr_max(
121 8 + DoubleToStringConverter::kMaxExponentialDigits,
122 7 + DoubleToStringConverter::kMaxPrecisionDigits));
123 char buf[bufLen];
124 StringBuilder builder(buf + 1, bufLen - 1);
125
126 char plusSign;
127 switch (arg.sign) {
128 case FormatArg::Sign::PLUS_OR_MINUS:
129 plusSign = '+';
130 break;
131 case FormatArg::Sign::SPACE_OR_MINUS:
132 plusSign = ' ';
133 break;
134 default:
135 plusSign = '\0';
136 break;
137 };
138
139 auto flags = DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN |
140 (arg.trailingDot ? DoubleToStringConverter::EMIT_TRAILING_DECIMAL_POINT
141 : 0);
142
143 double val = val_;
144 switch (arg.presentation) {
145 case '%':
146 val *= 100;
147 FOLLY_FALLTHROUGH;
148 case 'f':
149 case 'F': {
150 if (arg.precision > DoubleToStringConverter::kMaxFixedDigitsAfterPoint) {
151 arg.precision = DoubleToStringConverter::kMaxFixedDigitsAfterPoint;
152 }
153 DoubleToStringConverter conv(
154 flags,
155 infinitySymbol,
156 nanSymbol,
157 exponentSymbol,
158 -4,
159 arg.precision,
160 0,
161 0);
162 arg.enforce(
163 conv.ToFixed(val, arg.precision, &builder),
164 "fixed double conversion failed");
165 break;
166 }
167 case 'e':
168 case 'E': {
169 if (arg.precision > DoubleToStringConverter::kMaxExponentialDigits) {
170 arg.precision = DoubleToStringConverter::kMaxExponentialDigits;
171 }
172
173 DoubleToStringConverter conv(
174 flags,
175 infinitySymbol,
176 nanSymbol,
177 exponentSymbol,
178 -4,
179 arg.precision,
180 0,
181 0);
182 arg.enforce(conv.ToExponential(val, arg.precision, &builder));
183 break;
184 }
185 case 'n': // should be locale-aware, but isn't
186 case 'g':
187 case 'G': {
188 if (arg.precision < DoubleToStringConverter::kMinPrecisionDigits) {
189 arg.precision = DoubleToStringConverter::kMinPrecisionDigits;
190 } else if (arg.precision > DoubleToStringConverter::kMaxPrecisionDigits) {
191 arg.precision = DoubleToStringConverter::kMaxPrecisionDigits;
192 }
193 DoubleToStringConverter conv(
194 flags,
195 infinitySymbol,
196 nanSymbol,
197 exponentSymbol,
198 -4,
199 arg.precision,
200 0,
201 0);
202 arg.enforce(conv.ToShortest(val, &builder));
203 break;
204 }
205 default:
206 arg.error("invalid specifier '", arg.presentation, "'");
207 }
208
209 int len = builder.position();
210 builder.Finalize();
211 DCHECK_GT(len, 0);
212
213 // Add '+' or ' ' sign if needed
214 char* p = buf + 1;
215 // anything that's neither negative nor nan
216 prefixLen = 0;
217 if (plusSign && (*p != '-' && *p != 'n' && *p != 'N')) {
218 *--p = plusSign;
219 ++len;
220 prefixLen = 1;
221 } else if (*p == '-') {
222 prefixLen = 1;
223 }
224
225 piece = fbstring(p, size_t(len));
226}
227
228void FormatArg::initSlow() {
229 auto b = fullArgString.begin();
230 auto end = fullArgString.end();
231
232 // Parse key
233 auto p = static_cast<const char*>(memchr(b, ':', size_t(end - b)));
234 if (!p) {
235 key_ = StringPiece(b, end);
236 return;
237 }
238 key_ = StringPiece(b, p);
239
240 if (*p == ':') {
241 // parse format spec
242 if (++p == end) {
243 return;
244 }
245
246 // fill/align, or just align
247 Align a;
248 if (p + 1 != end &&
249 (a = formatAlignTable[static_cast<unsigned char>(p[1])]) !=
250 Align::INVALID) {
251 fill = *p;
252 align = a;
253 p += 2;
254 if (p == end) {
255 return;
256 }
257 } else if (
258 (a = formatAlignTable[static_cast<unsigned char>(*p)]) !=
259 Align::INVALID) {
260 align = a;
261 if (++p == end) {
262 return;
263 }
264 }
265
266 Sign s;
267 unsigned char uSign = static_cast<unsigned char>(*p);
268 if ((s = formatSignTable[uSign]) != Sign::INVALID) {
269 sign = s;
270 if (++p == end) {
271 return;
272 }
273 }
274
275 if (*p == '#') {
276 basePrefix = true;
277 if (++p == end) {
278 return;
279 }
280 }
281
282 if (*p == '0') {
283 enforce(align == Align::DEFAULT, "alignment specified twice");
284 fill = '0';
285 align = Align::PAD_AFTER_SIGN;
286 if (++p == end) {
287 return;
288 }
289 }
290
291 auto readInt = [&] {
292 auto const c = p;
293 do {
294 ++p;
295 } while (p != end && *p >= '0' && *p <= '9');
296 return to<int>(StringPiece(c, p));
297 };
298
299 if (*p == '*') {
300 width = kDynamicWidth;
301 ++p;
302
303 if (p == end) {
304 return;
305 }
306
307 if (*p >= '0' && *p <= '9') {
308 widthIndex = readInt();
309 }
310
311 if (p == end) {
312 return;
313 }
314 } else if (*p >= '0' && *p <= '9') {
315 width = readInt();
316
317 if (p == end) {
318 return;
319 }
320 }
321
322 if (*p == ',') {
323 thousandsSeparator = true;
324 if (++p == end) {
325 return;
326 }
327 }
328
329 if (*p == '.') {
330 auto d = ++p;
331 while (p != end && *p >= '0' && *p <= '9') {
332 ++p;
333 }
334 if (p != d) {
335 precision = to<int>(StringPiece(d, p));
336 if (p != end && *p == '.') {
337 trailingDot = true;
338 ++p;
339 }
340 } else {
341 trailingDot = true;
342 }
343
344 if (p == end) {
345 return;
346 }
347 }
348
349 presentation = *p;
350 if (++p == end) {
351 return;
352 }
353 }
354
355 error("extra characters in format string");
356}
357
358void FormatArg::validate(Type type) const {
359 enforce(keyEmpty(), "index not allowed");
360 switch (type) {
361 case Type::INTEGER:
362 enforce(
363 precision == kDefaultPrecision, "precision not allowed on integers");
364 break;
365 case Type::FLOAT:
366 enforce(
367 !basePrefix, "base prefix ('#') specifier only allowed on integers");
368 enforce(
369 !thousandsSeparator,
370 "thousands separator (',') only allowed on integers");
371 break;
372 case Type::OTHER:
373 enforce(
374 align != Align::PAD_AFTER_SIGN,
375 "'='alignment only allowed on numbers");
376 enforce(sign == Sign::DEFAULT, "sign specifier only allowed on numbers");
377 enforce(
378 !basePrefix, "base prefix ('#') specifier only allowed on integers");
379 enforce(
380 !thousandsSeparator,
381 "thousands separator (',') only allowed on integers");
382 break;
383 }
384}
385
386namespace detail {
387void insertThousandsGroupingUnsafe(char* start_buffer, char** end_buffer) {
388 uint32_t remaining_digits = uint32_t(*end_buffer - start_buffer);
389 uint32_t separator_size = (remaining_digits - 1) / 3;
390 uint32_t result_size = remaining_digits + separator_size;
391 *end_buffer = *end_buffer + separator_size;
392
393 // get the end of the new string with the separators
394 uint32_t buffer_write_index = result_size - 1;
395 uint32_t buffer_read_index = remaining_digits - 1;
396 start_buffer[buffer_write_index + 1] = 0;
397
398 bool done = false;
399 uint32_t next_group_size = 3;
400
401 while (!done) {
402 uint32_t current_group_size = std::max<uint32_t>(
403 1, std::min<uint32_t>(remaining_digits, next_group_size));
404
405 // write out the current group's digits to the buffer index
406 for (uint32_t i = 0; i < current_group_size; i++) {
407 start_buffer[buffer_write_index--] = start_buffer[buffer_read_index--];
408 }
409
410 // if not finished, write the separator before the next group
411 if (buffer_write_index < buffer_write_index + 1) {
412 start_buffer[buffer_write_index--] = ',';
413 } else {
414 done = true;
415 }
416
417 remaining_digits -= current_group_size;
418 }
419}
420} // namespace detail
421
422FormatKeyNotFoundException::FormatKeyNotFoundException(StringPiece key)
423 : std::out_of_range(kMessagePrefix.str() + key.str()) {}
424
425constexpr StringPiece const FormatKeyNotFoundException::kMessagePrefix;
426
427} // namespace folly
428