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