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