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