folly/Conv.h

   1 /*
   2  * Copyright 2016 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 /**
  18  * Converts anything to anything, with an emphasis on performance and
  19  * safety.
  20  *
  21  * @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  22  */
  23
  24 #pragma once
  25
  26 #include <folly/FBString.h>
  27 #include <folly/Likely.h>
  28 #include <folly/Preprocessor.h>
  29 #include <folly/Range.h>
  30
  31 #include <boost/implicit_cast.hpp>
  32 #include <algorithm>
  33 #include <type_traits>
  34 #include <limits>
  35 #include <string>
  36 #include <tuple>
  37 #include <stdexcept>
  38 #include <typeinfo>
  39
  40 #include <limits.h>
  41
  42 // V8 JavaScript implementation
  43 #include <double-conversion/double-conversion.h>
  44
  45 #define FOLLY_RANGE_CHECK_STRINGIZE(x) #x
  46 #define FOLLY_RANGE_CHECK_STRINGIZE2(x) FOLLY_RANGE_CHECK_STRINGIZE(x)
  47
  48 // Android doesn't support std::to_string so just use a placeholder there.
  49 #ifdef __ANDROID__
  50 #define FOLLY_RANGE_CHECK_TO_STRING(x) std::string("N/A")
  51 #else
  52 #define FOLLY_RANGE_CHECK_TO_STRING(x) std::to_string(x)
  53 #endif
  54
  55 #define FOLLY_RANGE_CHECK(condition, message, src)                          \
  56   ((condition) ? (void)0 : throw std::range_error(                          \
  57     (std::string(__FILE__ "(" FOLLY_RANGE_CHECK_STRINGIZE2(__LINE__) "): ") \
  58      + (message) + ": '" + (src) + "'").c_str()))
  59
  60 #define FOLLY_RANGE_CHECK_BEGIN_END(condition, message, b, e)    \
  61   FOLLY_RANGE_CHECK(condition, message, std::string((b), (e) - (b)))
  62
  63 #define FOLLY_RANGE_CHECK_STRINGPIECE(condition, message, sp)    \
  64   FOLLY_RANGE_CHECK(condition, message, std::string((sp).data(), (sp).size()))
  65
  66 namespace folly {
  67
  68 /**
  69  * The identity conversion function.
  70  * to<T>(T) returns itself for all types T.
  71  */
  72 template <class Tgt, class Src>
  73 typename std::enable_if<std::is_same<Tgt, Src>::value, Tgt>::type
  74 to(const Src & value) {
  75   return value;
  76 }
  77
  78 template <class Tgt, class Src>
  79 typename std::enable_if<std::is_same<Tgt, Src>::value, Tgt>::type
  80 to(Src && value) {
  81   return std::move(value);
  82 }
  83
  84 /*******************************************************************************
  85  * Integral to integral
  86  ******************************************************************************/
  87
  88 /**
  89  * Unchecked conversion from integral to boolean. This is different from the
  90  * other integral conversions because we use the C convention of treating any
  91  * non-zero value as true, instead of range checking.
  92  */
  93 template <class Tgt, class Src>
  94 typename std::enable_if<
  95   std::is_integral<Src>::value
  96   && !std::is_same<Tgt, Src>::value
  97   && std::is_same<Tgt, bool>::value,
  98   Tgt>::type
  99 to(const Src & value) {
 100   return value != 0;
 101 }
 102
 103 /**
 104  * Checked conversion from integral to integral. The checks are only
 105  * performed when meaningful, e.g. conversion from int to long goes
 106  * unchecked.
 107  */
 108 template <class Tgt, class Src>
 109 typename std::enable_if<
 110   std::is_integral<Src>::value
 111   && !std::is_same<Tgt, Src>::value
 112   && !std::is_same<Tgt, bool>::value
 113   && std::is_integral<Tgt>::value,
 114   Tgt>::type
 115 to(const Src & value) {
 116   /* static */ if (std::numeric_limits<Tgt>::max()
 117                    < std::numeric_limits<Src>::max()) {
 118     FOLLY_RANGE_CHECK(
 119       (!greater_than<Tgt, std::numeric_limits<Tgt>::max()>(value)),
 120       "Overflow",
 121       FOLLY_RANGE_CHECK_TO_STRING(value));
 122   }
 123   /* static */ if (std::is_signed<Src>::value &&
 124                    (!std::is_signed<Tgt>::value || sizeof(Src) > sizeof(Tgt))) {
 125     FOLLY_RANGE_CHECK(
 126       (!less_than<Tgt, std::numeric_limits<Tgt>::min()>(value)),
 127       "Negative overflow",
 128       FOLLY_RANGE_CHECK_TO_STRING(value));
 129   }
 130   return static_cast<Tgt>(value);
 131 }
 132
 133 /*******************************************************************************
 134  * Floating point to floating point
 135  ******************************************************************************/
 136
 137 template <class Tgt, class Src>
 138 typename std::enable_if<
 139   std::is_floating_point<Tgt>::value
 140   && std::is_floating_point<Src>::value
 141   && !std::is_same<Tgt, Src>::value,
 142   Tgt>::type
 143 to(const Src & value) {
 144   /* static */ if (std::numeric_limits<Tgt>::max() <
 145                    std::numeric_limits<Src>::max()) {
 146     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
 147                       "Overflow",
 148                       FOLLY_RANGE_CHECK_TO_STRING(value));
 149     FOLLY_RANGE_CHECK(value >= -std::numeric_limits<Tgt>::max(),
 150                       "Negative overflow",
 151                       FOLLY_RANGE_CHECK_TO_STRING(value));
 152   }
 153   return boost::implicit_cast<Tgt>(value);
 154 }
 155
 156 /*******************************************************************************
 157  * Anything to string
 158  ******************************************************************************/
 159
 160 namespace detail {
 161
 162 template <class T>
 163 const T& getLastElement(const T & v) {
 164   return v;
 165 }
 166
 167 template <class T, class... Ts>
 168 typename std::tuple_element<
 169   sizeof...(Ts),
 170   std::tuple<T, Ts...> >::type const&
 171   getLastElement(const T&, const Ts&... vs) {
 172   return getLastElement(vs...);
 173 }
 174
 175 // This class exists to specialize away std::tuple_element in the case where we
 176 // have 0 template arguments. Without this, Clang/libc++ will blow a
 177 // static_assert even if tuple_element is protected by an enable_if.
 178 template <class... Ts>
 179 struct last_element {
 180   typedef typename std::enable_if<
 181     sizeof...(Ts) >= 1,
 182     typename std::tuple_element<
 183       sizeof...(Ts) - 1, std::tuple<Ts...>
 184     >::type>::type type;
 185 };
 186
 187 template <>
 188 struct last_element<> {
 189   typedef void type;
 190 };
 191
 192 } // namespace detail
 193
 194 /*******************************************************************************
 195  * Conversions from integral types to string types.
 196  ******************************************************************************/
 197
 198 #if FOLLY_HAVE_INT128_T
 199 namespace detail {
 200
 201 template <typename IntegerType>
 202 constexpr unsigned int
 203 digitsEnough() {
 204   return (unsigned int)(ceil(sizeof(IntegerType) * CHAR_BIT * M_LN2 / M_LN10));
 205 }
 206
 207 inline size_t
 208 unsafeTelescope128(char * buffer, size_t room, unsigned __int128 x) {
 209   typedef unsigned __int128 Usrc;
 210   size_t p = room - 1;
 211
 212   while (x >= (Usrc(1) << 64)) { // Using 128-bit division while needed
 213     const auto y = x / 10;
 214     const auto digit = x % 10;
 215
 216     buffer[p--] = '0' + digit;
 217     x = y;
 218   }
 219
 220   uint64_t xx = x; // Moving to faster 64-bit division thereafter
 221
 222   while (xx >= 10) {
 223     const auto y = xx / 10ULL;
 224     const auto digit = xx % 10ULL;
 225
 226     buffer[p--] = '0' + digit;
 227     xx = y;
 228   }
 229
 230   buffer[p] = '0' + xx;
 231
 232   return p;
 233 }
 234
 235 }
 236 #endif
 237
 238 /**
 239  * Returns the number of digits in the base 10 representation of an
 240  * uint64_t. Useful for preallocating buffers and such. It's also used
 241  * internally, see below. Measurements suggest that defining a
 242  * separate overload for 32-bit integers is not worthwhile.
 243  */
 244
 245 inline uint32_t digits10(uint64_t v) {
 246 #ifdef __x86_64__
 247
 248   // For this arch we can get a little help from specialized CPU instructions
 249   // which can count leading zeroes; 64 minus that is appx. log (base 2).
 250   // Use that to approximate base-10 digits (log_10) and then adjust if needed.
 251
 252   // 10^i, defined for i 0 through 19.
 253   // This is 20 * 8 == 160 bytes, which fits neatly into 5 cache lines
 254   // (assuming a cache line size of 64).
 255   static const uint64_t powersOf10[20] FOLLY_ALIGNED(64) = {
 256     1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
 257     10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000,
 258     1000000000000000, 10000000000000000, 100000000000000000,
 259     1000000000000000000, 10000000000000000000UL
 260   };
 261
 262   // "count leading zeroes" operation not valid; for 0; special case this.
 263   if UNLIKELY (! v) {
 264     return 1;
 265   }
 266
 267   // bits is in the ballpark of log_2(v).
 268   const uint8_t leadingZeroes = __builtin_clzll(v);
 269   const auto bits = 63 - leadingZeroes;
 270
 271   // approximate log_10(v) == log_10(2) * bits.
 272   // Integer magic below: 77/256 is appx. 0.3010 (log_10(2)).
 273   // The +1 is to make this the ceiling of the log_10 estimate.
 274   const uint32_t minLength = 1 + ((bits * 77) >> 8);
 275
 276   // return that log_10 lower bound, plus adjust if input >= 10^(that bound)
 277   // in case there's a small error and we misjudged length.
 278   return minLength + (uint32_t) (UNLIKELY (v >= powersOf10[minLength]));
 279
 280 #else
 281
 282   uint32_t result = 1;
 283   for (;;) {
 284     if (LIKELY(v < 10)) return result;
 285     if (LIKELY(v < 100)) return result + 1;
 286     if (LIKELY(v < 1000)) return result + 2;
 287     if (LIKELY(v < 10000)) return result + 3;
 288     // Skip ahead by 4 orders of magnitude
 289     v /= 10000U;
 290     result += 4;
 291   }
 292
 293 #endif
 294 }
 295
 296 /**
 297  * Copies the ASCII base 10 representation of v into buffer and
 298  * returns the number of bytes written. Does NOT append a \0. Assumes
 299  * the buffer points to digits10(v) bytes of valid memory. Note that
 300  * uint64 needs at most 20 bytes, uint32_t needs at most 10 bytes,
 301  * uint16_t needs at most 5 bytes, and so on. Measurements suggest
 302  * that defining a separate overload for 32-bit integers is not
 303  * worthwhile.
 304  *
 305  * This primitive is unsafe because it makes the size assumption and
 306  * because it does not add a terminating \0.
 307  */
 308
 309 inline uint32_t uint64ToBufferUnsafe(uint64_t v, char *const buffer) {
 310   auto const result = digits10(v);
 311   // WARNING: using size_t or pointer arithmetic for pos slows down
 312   // the loop below 20x. This is because several 32-bit ops can be
 313   // done in parallel, but only fewer 64-bit ones.
 314   uint32_t pos = result - 1;
 315   while (v >= 10) {
 316     // Keep these together so a peephole optimization "sees" them and
 317     // computes them in one shot.
 318     auto const q = v / 10;
 319     auto const r = static_cast<uint32_t>(v % 10);
 320     buffer[pos--] = '0' + r;
 321     v = q;
 322   }
 323   // Last digit is trivial to handle
 324   buffer[pos] = static_cast<uint32_t>(v) + '0';
 325   return result;
 326 }
 327
 328 /**
 329  * A single char gets appended.
 330  */
 331 template <class Tgt>
 332 void toAppend(char value, Tgt * result) {
 333   *result += value;
 334 }
 335
 336 template<class T>
 337 constexpr typename std::enable_if<
 338   std::is_same<T, char>::value,
 339   size_t>::type
 340 estimateSpaceNeeded(T) {
 341   return 1;
 342 }
 343
 344 /**
 345  * Ubiquitous helper template for writing string appenders
 346  */
 347 template <class T> struct IsSomeString {
 348   enum { value = std::is_same<T, std::string>::value
 349          || std::is_same<T, fbstring>::value };
 350 };
 351
 352 /**
 353  * Everything implicitly convertible to const char* gets appended.
 354  */
 355 template <class Tgt, class Src>
 356 typename std::enable_if<
 357   std::is_convertible<Src, const char*>::value
 358   && IsSomeString<Tgt>::value>::type
 359 toAppend(Src value, Tgt * result) {
 360   // Treat null pointers like an empty string, as in:
 361   // operator<<(std::ostream&, const char*).
 362   const char* c = value;
 363   if (c) {
 364     result->append(value);
 365   }
 366 }
 367
 368 template<class Src>
 369 typename std::enable_if<
 370   std::is_convertible<Src, const char*>::value,
 371   size_t>::type
 372 estimateSpaceNeeded(Src value) {
 373   const char *c = value;
 374   if (c) {
 375     return folly::StringPiece(value).size();
 376   };
 377   return 0;
 378 }
 379
 380 template<class Src>
 381 typename std::enable_if<
 382   (std::is_convertible<Src, folly::StringPiece>::value ||
 383   IsSomeString<Src>::value) &&
 384   !std::is_convertible<Src, const char*>::value,
 385   size_t>::type
 386 estimateSpaceNeeded(Src value) {
 387   return folly::StringPiece(value).size();
 388 }
 389
 390 template <>
 391 inline size_t estimateSpaceNeeded(std::nullptr_t /* value */) {
 392   return 0;
 393 }
 394
 395 template<class Src>
 396 typename std::enable_if<
 397   std::is_pointer<Src>::value &&
 398   IsSomeString<std::remove_pointer<Src>>::value,
 399   size_t>::type
 400 estimateSpaceNeeded(Src value) {
 401   return value->size();
 402 }
 403
 404 /**
 405  * Strings get appended, too.
 406  */
 407 template <class Tgt, class Src>
 408 typename std::enable_if<
 409   IsSomeString<Src>::value && IsSomeString<Tgt>::value>::type
 410 toAppend(const Src& value, Tgt * result) {
 411   result->append(value);
 412 }
 413
 414 /**
 415  * and StringPiece objects too
 416  */
 417 template <class Tgt>
 418 typename std::enable_if<
 419    IsSomeString<Tgt>::value>::type
 420 toAppend(StringPiece value, Tgt * result) {
 421   result->append(value.data(), value.size());
 422 }
 423
 424 /**
 425  * There's no implicit conversion from fbstring to other string types,
 426  * so make a specialization.
 427  */
 428 template <class Tgt>
 429 typename std::enable_if<
 430    IsSomeString<Tgt>::value>::type
 431 toAppend(const fbstring& value, Tgt * result) {
 432   result->append(value.data(), value.size());
 433 }
 434
 435 #if FOLLY_HAVE_INT128_T
 436 /**
 437  * Special handling for 128 bit integers.
 438  */
 439
 440 template <class Tgt>
 441 void
 442 toAppend(__int128 value, Tgt * result) {
 443   typedef unsigned __int128 Usrc;
 444   char buffer[detail::digitsEnough<unsigned __int128>() + 1];
 445   size_t p;
 446
 447   if (value < 0) {
 448     p = detail::unsafeTelescope128(buffer, sizeof(buffer), Usrc(-value));
 449     buffer[--p] = '-';
 450   } else {
 451     p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
 452   }
 453
 454   result->append(buffer + p, buffer + sizeof(buffer));
 455 }
 456
 457 template <class Tgt>
 458 void
 459 toAppend(unsigned __int128 value, Tgt * result) {
 460   char buffer[detail::digitsEnough<unsigned __int128>()];
 461   size_t p;
 462
 463   p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
 464
 465   result->append(buffer + p, buffer + sizeof(buffer));
 466 }
 467
 468 template<class T>
 469 constexpr typename std::enable_if<
 470   std::is_same<T, __int128>::value,
 471   size_t>::type
 472 estimateSpaceNeeded(T) {
 473   return detail::digitsEnough<__int128>();
 474 }
 475
 476 template<class T>
 477 constexpr typename std::enable_if<
 478   std::is_same<T, unsigned __int128>::value,
 479   size_t>::type
 480 estimateSpaceNeeded(T) {
 481   return detail::digitsEnough<unsigned __int128>();
 482 }
 483
 484 #endif
 485
 486 /**
 487  * int32_t and int64_t to string (by appending) go through here. The
 488  * result is APPENDED to a preexisting string passed as the second
 489  * parameter. This should be efficient with fbstring because fbstring
 490  * incurs no dynamic allocation below 23 bytes and no number has more
 491  * than 22 bytes in its textual representation (20 for digits, one for
 492  * sign, one for the terminating 0).
 493  */
 494 template <class Tgt, class Src>
 495 typename std::enable_if<
 496   std::is_integral<Src>::value && std::is_signed<Src>::value &&
 497   IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 498 toAppend(Src value, Tgt * result) {
 499   char buffer[20];
 500   if (value < 0) {
 501     result->push_back('-');
 502     result->append(buffer, uint64ToBufferUnsafe(-uint64_t(value), buffer));
 503   } else {
 504     result->append(buffer, uint64ToBufferUnsafe(value, buffer));
 505   }
 506 }
 507
 508 template <class Src>
 509 typename std::enable_if<
 510   std::is_integral<Src>::value && std::is_signed<Src>::value
 511   && sizeof(Src) >= 4 && sizeof(Src) < 16,
 512   size_t>::type
 513 estimateSpaceNeeded(Src value) {
 514   if (value < 0) {
 515     // When "value" is the smallest negative, negating it would evoke
 516     // undefined behavior, so, instead of writing "-value" below, we write
 517     // "~static_cast<uint64_t>(value) + 1"
 518     return 1 + digits10(~static_cast<uint64_t>(value) + 1);
 519   }
 520
 521   return digits10(static_cast<uint64_t>(value));
 522 }
 523
 524 /**
 525  * As above, but for uint32_t and uint64_t.
 526  */
 527 template <class Tgt, class Src>
 528 typename std::enable_if<
 529   std::is_integral<Src>::value && !std::is_signed<Src>::value
 530   && IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 531 toAppend(Src value, Tgt * result) {
 532   char buffer[20];
 533   result->append(buffer, buffer + uint64ToBufferUnsafe(value, buffer));
 534 }
 535
 536 template <class Src>
 537 typename std::enable_if<
 538   std::is_integral<Src>::value && !std::is_signed<Src>::value
 539   && sizeof(Src) >= 4 && sizeof(Src) < 16,
 540   size_t>::type
 541 estimateSpaceNeeded(Src value) {
 542   return digits10(value);
 543 }
 544
 545 /**
 546  * All small signed and unsigned integers to string go through 32-bit
 547  * types int32_t and uint32_t, respectively.
 548  */
 549 template <class Tgt, class Src>
 550 typename std::enable_if<
 551   std::is_integral<Src>::value
 552   && IsSomeString<Tgt>::value && sizeof(Src) < 4>::type
 553 toAppend(Src value, Tgt * result) {
 554   typedef typename
 555     std::conditional<std::is_signed<Src>::value, int64_t, uint64_t>::type
 556     Intermediate;
 557   toAppend<Tgt>(static_cast<Intermediate>(value), result);
 558 }
 559
 560 template <class Src>
 561 typename std::enable_if<
 562   std::is_integral<Src>::value
 563   && sizeof(Src) < 4
 564   && !std::is_same<Src, char>::value,
 565   size_t>::type
 566 estimateSpaceNeeded(Src value) {
 567   typedef typename
 568     std::conditional<std::is_signed<Src>::value, int64_t, uint64_t>::type
 569     Intermediate;
 570   return estimateSpaceNeeded(static_cast<Intermediate>(value));
 571 }
 572
 573 /**
 574  * Enumerated values get appended as integers.
 575  */
 576 template <class Tgt, class Src>
 577 typename std::enable_if<
 578   std::is_enum<Src>::value && IsSomeString<Tgt>::value>::type
 579 toAppend(Src value, Tgt * result) {
 580   toAppend(
 581       static_cast<typename std::underlying_type<Src>::type>(value), result);
 582 }
 583
 584 template <class Src>
 585 typename std::enable_if<
 586   std::is_enum<Src>::value, size_t>::type
 587 estimateSpaceNeeded(Src value) {
 588   return estimateSpaceNeeded(
 589       static_cast<typename std::underlying_type<Src>::type>(value));
 590 }
 591
 592 /*******************************************************************************
 593  * Conversions from floating-point types to string types.
 594  ******************************************************************************/
 595
 596 namespace detail {
 597 constexpr int kConvMaxDecimalInShortestLow = -6;
 598 constexpr int kConvMaxDecimalInShortestHigh = 21;
 599 } // folly::detail
 600
 601 /** Wrapper around DoubleToStringConverter **/
 602 template <class Tgt, class Src>
 603 typename std::enable_if<
 604   std::is_floating_point<Src>::value
 605   && IsSomeString<Tgt>::value>::type
 606 toAppend(
 607   Src value,
 608   Tgt * result,
 609   double_conversion::DoubleToStringConverter::DtoaMode mode,
 610   unsigned int numDigits) {
 611   using namespace double_conversion;
 612   DoubleToStringConverter
 613     conv(DoubleToStringConverter::NO_FLAGS,
 614          "Infinity", "NaN", 'E',
 615          detail::kConvMaxDecimalInShortestLow,
 616          detail::kConvMaxDecimalInShortestHigh,
 617          6,   // max leading padding zeros
 618          1);  // max trailing padding zeros
 619   char buffer[256];
 620   StringBuilder builder(buffer, sizeof(buffer));
 621   switch (mode) {
 622     case DoubleToStringConverter::SHORTEST:
 623       conv.ToShortest(value, &builder);
 624       break;
 625     case DoubleToStringConverter::FIXED:
 626       conv.ToFixed(value, numDigits, &builder);
 627       break;
 628     default:
 629       CHECK(mode == DoubleToStringConverter::PRECISION);
 630       conv.ToPrecision(value, numDigits, &builder);
 631       break;
 632   }
 633   const size_t length = builder.position();
 634   builder.Finalize();
 635   result->append(buffer, length);
 636 }
 637
 638 /**
 639  * As above, but for floating point
 640  */
 641 template <class Tgt, class Src>
 642 typename std::enable_if<
 643   std::is_floating_point<Src>::value
 644   && IsSomeString<Tgt>::value>::type
 645 toAppend(Src value, Tgt * result) {
 646   toAppend(
 647     value, result, double_conversion::DoubleToStringConverter::SHORTEST, 0);
 648 }
 649
 650 /**
 651  * Upper bound of the length of the output from
 652  * DoubleToStringConverter::ToShortest(double, StringBuilder*),
 653  * as used in toAppend(double, string*).
 654  */
 655 template <class Src>
 656 typename std::enable_if<
 657   std::is_floating_point<Src>::value, size_t>::type
 658 estimateSpaceNeeded(Src value) {
 659   // kBase10MaximalLength is 17. We add 1 for decimal point,
 660   // e.g. 10.0/9 is 17 digits and 18 characters, including the decimal point.
 661   constexpr int kMaxMantissaSpace =
 662     double_conversion::DoubleToStringConverter::kBase10MaximalLength + 1;
 663   // strlen("E-") + digits10(numeric_limits<double>::max_exponent10)
 664   constexpr int kMaxExponentSpace = 2 + 3;
 665   static const int kMaxPositiveSpace = std::max({
 666       // E.g. 1.1111111111111111E-100.
 667       kMaxMantissaSpace + kMaxExponentSpace,
 668       // E.g. 0.000001.1111111111111111, if kConvMaxDecimalInShortestLow is -6.
 669       kMaxMantissaSpace - detail::kConvMaxDecimalInShortestLow,
 670       // If kConvMaxDecimalInShortestHigh is 21, then 1e21 is the smallest
 671       // number > 1 which ToShortest outputs in exponential notation,
 672       // so 21 is the longest non-exponential number > 1.
 673       detail::kConvMaxDecimalInShortestHigh
 674     });
 675   return kMaxPositiveSpace + (value < 0);  // +1 for minus sign, if negative
 676 }
 677
 678 /**
 679  * This can be specialized, together with adding specialization
 680  * for estimateSpaceNeed for your type, so that we allocate
 681  * as much as you need instead of the default
 682  */
 683 template<class Src>
 684 struct HasLengthEstimator : std::false_type {};
 685
 686 template <class Src>
 687 constexpr typename std::enable_if<
 688   !std::is_fundamental<Src>::value
 689 #ifdef FOLLY_HAVE_INT128_T
 690   // On OSX 10.10, is_fundamental<__int128> is false :-O
 691   && !std::is_same<__int128, Src>::value
 692   && !std::is_same<unsigned __int128, Src>::value
 693 #endif
 694   && !IsSomeString<Src>::value
 695   && !std::is_convertible<Src, const char*>::value
 696   && !std::is_convertible<Src, StringPiece>::value
 697   && !std::is_enum<Src>::value
 698   && !HasLengthEstimator<Src>::value,
 699   size_t>::type
 700 estimateSpaceNeeded(const Src&) {
 701   return sizeof(Src) + 1; // dumbest best effort ever?
 702 }
 703
 704 namespace detail {
 705
 706 inline size_t estimateSpaceToReserve(size_t sofar) {
 707   return sofar;
 708 }
 709
 710 template <class T, class... Ts>
 711 size_t estimateSpaceToReserve(size_t sofar, const T& v, const Ts&... vs) {
 712   return estimateSpaceToReserve(sofar + estimateSpaceNeeded(v), vs...);
 713 }
 714
 715 template<class T>
 716 size_t estimateSpaceToReserve(size_t sofar, const T& v) {
 717   return sofar + estimateSpaceNeeded(v);
 718 }
 719
 720 template<class...Ts>
 721 void reserveInTarget(const Ts&...vs) {
 722   getLastElement(vs...)->reserve(estimateSpaceToReserve(0, vs...));
 723 }
 724
 725 template<class Delimiter, class...Ts>
 726 void reserveInTargetDelim(const Delimiter& d, const Ts&...vs) {
 727   static_assert(sizeof...(vs) >= 2, "Needs at least 2 args");
 728   size_t fordelim = (sizeof...(vs) - 2) * estimateSpaceToReserve(0, d);
 729   getLastElement(vs...)->reserve(estimateSpaceToReserve(fordelim, vs...));
 730 }
 731
 732 /**
 733  * Variadic base case: append one element
 734  */
 735 template <class T, class Tgt>
 736 typename std::enable_if<
 737   IsSomeString<typename std::remove_pointer<Tgt>::type>
 738   ::value>::type
 739 toAppendStrImpl(const T& v, Tgt result) {
 740   toAppend(v, result);
 741 }
 742
 743 template <class T, class... Ts>
 744 typename std::enable_if<sizeof...(Ts) >= 2
 745   && IsSomeString<
 746   typename std::remove_pointer<
 747     typename detail::last_element<Ts...>::type
 748   >::type>::value>::type
 749 toAppendStrImpl(const T& v, const Ts&... vs) {
 750   toAppend(v, getLastElement(vs...));
 751   toAppendStrImpl(vs...);
 752 }
 753
 754 template <class Delimiter, class T, class Tgt>
 755 typename std::enable_if<
 756     IsSomeString<typename std::remove_pointer<Tgt>::type>::value>::type
 757 toAppendDelimStrImpl(const Delimiter& /* delim */, const T& v, Tgt result) {
 758   toAppend(v, result);
 759 }
 760
 761 template <class Delimiter, class T, class... Ts>
 762 typename std::enable_if<sizeof...(Ts) >= 2
 763   && IsSomeString<
 764   typename std::remove_pointer<
 765     typename detail::last_element<Ts...>::type
 766   >::type>::value>::type
 767 toAppendDelimStrImpl(const Delimiter& delim, const T& v, const Ts&... vs) {
 768   // we are really careful here, calling toAppend with just one element does
 769   // not try to estimate space needed (as we already did that). If we call
 770   // toAppend(v, delim, ....) we would do unnecesary size calculation
 771   toAppend(v, detail::getLastElement(vs...));
 772   toAppend(delim, detail::getLastElement(vs...));
 773   toAppendDelimStrImpl(delim, vs...);
 774 }
 775 } // folly::detail
 776
 777
 778 /**
 779  * Variadic conversion to string. Appends each element in turn.
 780  * If we have two or more things to append, we it will not reserve
 781  * the space for them and will depend on strings exponential growth.
 782  * If you just append once consider using toAppendFit which reserves
 783  * the space needed (but does not have exponential as a result).
 784  */
 785 template <class... Ts>
 786 typename std::enable_if<sizeof...(Ts) >= 3
 787   && IsSomeString<
 788   typename std::remove_pointer<
 789     typename detail::last_element<Ts...>::type
 790   >::type>::value>::type
 791 toAppend(const Ts&... vs) {
 792   ::folly::detail::toAppendStrImpl(vs...);
 793 }
 794
 795 #ifdef _MSC_VER
 796 // Special case pid_t on MSVC, because it's a void* rather than an
 797 // integral type. We can't do a global special case because this is already
 798 // dangerous enough (as most pointers will implicitly convert to a void*)
 799 // just doing it for MSVC.
 800 template <class Tgt>
 801 void toAppend(const pid_t a, Tgt* res) {
 802   toAppend(uint64_t(a), res);
 803 }
 804 #endif
 805
 806 /**
 807  * Special version of the call that preallocates exaclty as much memory
 808  * as need for arguments to be stored in target. This means we are
 809  * not doing exponential growth when we append. If you are using it
 810  * in a loop you are aiming at your foot with a big perf-destroying
 811  * bazooka.
 812  * On the other hand if you are appending to a string once, this
 813  * will probably save a few calls to malloc.
 814  */
 815 template <class... Ts>
 816 typename std::enable_if<
 817   IsSomeString<
 818   typename std::remove_pointer<
 819     typename detail::last_element<Ts...>::type
 820   >::type>::value>::type
 821 toAppendFit(const Ts&... vs) {
 822   ::folly::detail::reserveInTarget(vs...);
 823   toAppend(vs...);
 824 }
 825
 826 template <class Ts>
 827 void toAppendFit(const Ts&) {}
 828
 829 /**
 830  * Variadic base case: do nothing.
 831  */
 832 template <class Tgt>
 833 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppend(
 834     Tgt* /* result */) {}
 835
 836 /**
 837  * Variadic base case: do nothing.
 838  */
 839 template <class Delimiter, class Tgt>
 840 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppendDelim(
 841     const Delimiter& /* delim */, Tgt* /* result */) {}
 842
 843 /**
 844  * 1 element: same as toAppend.
 845  */
 846 template <class Delimiter, class T, class Tgt>
 847 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppendDelim(
 848     const Delimiter& /* delim */, const T& v, Tgt* tgt) {
 849   toAppend(v, tgt);
 850 }
 851
 852 /**
 853  * Append to string with a delimiter in between elements. Check out
 854  * comments for toAppend for details about memory allocation.
 855  */
 856 template <class Delimiter, class... Ts>
 857 typename std::enable_if<sizeof...(Ts) >= 3
 858   && IsSomeString<
 859   typename std::remove_pointer<
 860     typename detail::last_element<Ts...>::type
 861   >::type>::value>::type
 862 toAppendDelim(const Delimiter& delim, const Ts&... vs) {
 863   detail::toAppendDelimStrImpl(delim, vs...);
 864 }
 865
 866 /**
 867  * Detail in comment for toAppendFit
 868  */
 869 template <class Delimiter, class... Ts>
 870 typename std::enable_if<
 871   IsSomeString<
 872   typename std::remove_pointer<
 873     typename detail::last_element<Ts...>::type
 874   >::type>::value>::type
 875 toAppendDelimFit(const Delimiter& delim, const Ts&... vs) {
 876   detail::reserveInTargetDelim(delim, vs...);
 877   toAppendDelim(delim, vs...);
 878 }
 879
 880 template <class De, class Ts>
 881 void toAppendDelimFit(const De&, const Ts&) {}
 882
 883 /**
 884  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 885  * for all types.
 886  */
 887 template <class Tgt, class... Ts>
 888 typename std::enable_if<
 889   IsSomeString<Tgt>::value && (
 890     sizeof...(Ts) != 1 ||
 891     !std::is_same<Tgt, typename detail::last_element<Ts...>::type>::value),
 892   Tgt>::type
 893 to(const Ts&... vs) {
 894   Tgt result;
 895   toAppendFit(vs..., &result);
 896   return result;
 897 }
 898
 899 /**
 900  * toDelim<SomeString>(SomeString str) returns itself.
 901  */
 902 template <class Tgt, class Delim, class Src>
 903 typename std::enable_if<IsSomeString<Tgt>::value &&
 904                             std::is_same<Tgt, Src>::value,
 905                         Tgt>::type
 906 toDelim(const Delim& /* delim */, const Src& value) {
 907   return value;
 908 }
 909
 910 /**
 911  * toDelim<SomeString>(delim, v1, v2, ...) uses toAppendDelim() as
 912  * back-end for all types.
 913  */
 914 template <class Tgt, class Delim, class... Ts>
 915 typename std::enable_if<
 916   IsSomeString<Tgt>::value && (
 917     sizeof...(Ts) != 1 ||
 918     !std::is_same<Tgt, typename detail::last_element<Ts...>::type>::value),
 919   Tgt>::type
 920 toDelim(const Delim& delim, const Ts&... vs) {
 921   Tgt result;
 922   toAppendDelimFit(delim, vs..., &result);
 923   return result;
 924 }
 925
 926 /*******************************************************************************
 927  * Conversions from string types to integral types.
 928  ******************************************************************************/
 929
 930 namespace detail {
 931
 932 /**
 933  * Finds the first non-digit in a string. The number of digits
 934  * searched depends on the precision of the Tgt integral. Assumes the
 935  * string starts with NO whitespace and NO sign.
 936  *
 937  * The semantics of the routine is:
 938  *   for (;; ++b) {
 939  *     if (b >= e || !isdigit(*b)) return b;
 940  *   }
 941  *
 942  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 943  *  improvements of 20%.
 944  */
 945   template <class Tgt>
 946   const char* findFirstNonDigit(const char* b, const char* e) {
 947     for (; b < e; ++b) {
 948       auto const c = static_cast<unsigned>(*b) - '0';
 949       if (c >= 10) break;
 950     }
 951     return b;
 952   }
 953
 954   // Maximum value of number when represented as a string
 955   template <class T> struct MaxString {
 956     static const char*const value;
 957   };
 958
 959   bool str_to_bool(StringPiece* src);
 960
 961   template <class Tgt>
 962   Tgt digits_to(const char* b, const char* e);
 963
 964   extern template unsigned char digits_to<unsigned char>(const char* b,
 965                                                          const char* e);
 966   extern template unsigned short digits_to<unsigned short>(const char* b,
 967                                                            const char* e);
 968   extern template unsigned int digits_to<unsigned int>(const char* b,
 969                                                        const char* e);
 970   extern template unsigned long digits_to<unsigned long>(const char* b,
 971                                                          const char* e);
 972   extern template unsigned long long digits_to<unsigned long long>(
 973       const char* b, const char* e);
 974 #if FOLLY_HAVE_INT128_T
 975   extern template unsigned __int128 digits_to<unsigned __int128>(const char* b,
 976                                                                  const char* e);
 977 #endif
 978
 979 }                                 // namespace detail
 980
 981 /**
 982  * String represented as a pair of pointers to char to unsigned
 983  * integrals. Assumes NO whitespace before or after.
 984  */
 985 template <class Tgt>
 986 typename std::enable_if<
 987   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 988   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 989   Tgt>::type
 990 to(const char * b, const char * e) {
 991   return detail::digits_to<Tgt>(b, e);
 992 }
 993
 994 /**
 995  * String represented as a pair of pointers to char to signed
 996  * integrals. Assumes NO whitespace before or after. Allows an
 997  * optional leading sign.
 998  */
 999 template <class Tgt>
1000 typename std::enable_if<
1001   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
1002   Tgt>::type
1003 to(const char * b, const char * e) {
1004   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral",
1005                     to<std::string>("b: ", intptr_t(b), " e: ", intptr_t(e)));
1006   if (!isdigit(*b)) {
1007     if (*b == '-') {
1008       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
1009       FOLLY_RANGE_CHECK_BEGIN_END(result <= 0, "Negative overflow.", b, e);
1010       return result;
1011     }
1012     FOLLY_RANGE_CHECK_BEGIN_END(*b == '+', "Invalid lead character", b, e);
1013     ++b;
1014   }
1015   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
1016   FOLLY_RANGE_CHECK_BEGIN_END(result >= 0, "Overflow", b, e);
1017   return result;
1018 }
1019
1020 /**
1021  * Parsing strings to integrals. These routines differ from
1022  * to<integral>(string) in that they take a POINTER TO a StringPiece
1023  * and alter that StringPiece to reflect progress information.
1024  */
1025
1026 /**
1027  * StringPiece to integrals, with progress information. Alters the
1028  * StringPiece parameter to munch the already-parsed characters.
1029  */
1030 template <class Tgt>
1031 typename std::enable_if<
1032   std::is_integral<Tgt>::value
1033   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
1034   Tgt>::type
1035 to(StringPiece * src) {
1036
1037   auto b = src->data(), past = src->data() + src->size();
1038   for (;; ++b) {
1039     FOLLY_RANGE_CHECK_STRINGPIECE(b < past,
1040                                   "No digits found in input string", *src);
1041     if (!isspace(*b)) break;
1042   }
1043
1044   auto m = b;
1045
1046   // First digit is customized because we test for sign
1047   bool negative = false;
1048   /* static */ if (std::is_signed<Tgt>::value) {
1049     if (!isdigit(*m)) {
1050       if (*m == '-') {
1051         negative = true;
1052       } else {
1053         FOLLY_RANGE_CHECK_STRINGPIECE(*m == '+', "Invalid leading character in "
1054                                       "conversion to integral", *src);
1055       }
1056       ++b;
1057       ++m;
1058     }
1059   }
1060   FOLLY_RANGE_CHECK_STRINGPIECE(m < past, "No digits found in input string",
1061                                 *src);
1062   FOLLY_RANGE_CHECK_STRINGPIECE(isdigit(*m), "Non-digit character found", *src);
1063   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
1064
1065   Tgt result;
1066   /* static */ if (!std::is_signed<Tgt>::value) {
1067     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
1068   } else {
1069     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
1070     if (negative) {
1071       result = -t;
1072       FOLLY_RANGE_CHECK_STRINGPIECE(is_non_positive(result),
1073                                     "Negative overflow", *src);
1074     } else {
1075       result = t;
1076       FOLLY_RANGE_CHECK_STRINGPIECE(is_non_negative(result), "Overflow", *src);
1077     }
1078   }
1079   src->advance(m - src->data());
1080   return result;
1081 }
1082
1083 /**
1084  * StringPiece to bool, with progress information. Alters the
1085  * StringPiece parameter to munch the already-parsed characters.
1086  */
1087 template <class Tgt>
1088 typename std::enable_if<
1089   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
1090   Tgt>::type
1091 to(StringPiece * src) {
1092   return detail::str_to_bool(src);
1093 }
1094
1095 namespace detail {
1096
1097 /**
1098  * Enforce that the suffix following a number is made up only of whitespace.
1099  */
1100 inline void enforceWhitespace(const char* b, const char* e) {
1101   for (; b != e; ++b) {
1102     FOLLY_RANGE_CHECK_BEGIN_END(isspace(*b),
1103                                 to<std::string>("Non-whitespace: ", *b),
1104                                 b, e);
1105   }
1106 }
1107
1108 }  // namespace detail
1109
1110 /**
1111  * String or StringPiece to integrals. Accepts leading and trailing
1112  * whitespace, but no non-space trailing characters.
1113  */
1114 template <class Tgt>
1115 typename std::enable_if<
1116   std::is_integral<Tgt>::value,
1117   Tgt>::type
1118 to(StringPiece src) {
1119   Tgt result = to<Tgt>(&src);
1120   detail::enforceWhitespace(src.data(), src.data() + src.size());
1121   return result;
1122 }
1123
1124 /*******************************************************************************
1125  * Conversions from string types to floating-point types.
1126  ******************************************************************************/
1127
1128 /**
1129  * StringPiece to double, with progress information. Alters the
1130  * StringPiece parameter to munch the already-parsed characters.
1131  */
1132 template <class Tgt>
1133 inline typename std::enable_if<
1134   std::is_floating_point<Tgt>::value,
1135   Tgt>::type
1136 to(StringPiece *const src) {
1137   using namespace double_conversion;
1138   static StringToDoubleConverter
1139     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
1140          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
1141          0.0,
1142          // return this for junk input string
1143          std::numeric_limits<double>::quiet_NaN(),
1144          nullptr, nullptr);
1145
1146   FOLLY_RANGE_CHECK_STRINGPIECE(!src->empty(),
1147                                 "No digits found in input string", *src);
1148
1149   int length;
1150   auto result = conv.StringToDouble(src->data(),
1151                                     static_cast<int>(src->size()),
1152                                     &length); // processed char count
1153
1154   if (!std::isnan(result)) {
1155     src->advance(length);
1156     return result;
1157   }
1158
1159   for (;; src->advance(1)) {
1160     if (src->empty()) {
1161       throw std::range_error("Unable to convert an empty string"
1162                              " to a floating point value.");
1163     }
1164     if (!isspace(src->front())) {
1165       break;
1166     }
1167   }
1168
1169   // Was that "inf[inity]"?
1170   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
1171         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
1172     if (src->size() >= 8 &&
1173         toupper((*src)[3]) == 'I' &&
1174         toupper((*src)[4]) == 'N' &&
1175         toupper((*src)[5]) == 'I' &&
1176         toupper((*src)[6]) == 'T' &&
1177         toupper((*src)[7]) == 'Y') {
1178       src->advance(8);
1179     } else {
1180       src->advance(3);
1181     }
1182     return std::numeric_limits<Tgt>::infinity();
1183   }
1184
1185   // Was that "-inf[inity]"?
1186   if (src->size() >= 4 && toupper((*src)[0]) == '-'
1187       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
1188       && toupper((*src)[3]) == 'F') {
1189     if (src->size() >= 9 &&
1190         toupper((*src)[4]) == 'I' &&
1191         toupper((*src)[5]) == 'N' &&
1192         toupper((*src)[6]) == 'I' &&
1193         toupper((*src)[7]) == 'T' &&
1194         toupper((*src)[8]) == 'Y') {
1195       src->advance(9);
1196     } else {
1197       src->advance(4);
1198     }
1199     return -std::numeric_limits<Tgt>::infinity();
1200   }
1201
1202   // "nan"?
1203   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
1204         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
1205     src->advance(3);
1206     return std::numeric_limits<Tgt>::quiet_NaN();
1207   }
1208
1209   // "-nan"?
1210   if (src->size() >= 4 &&
1211       toupper((*src)[0]) == '-' &&
1212       toupper((*src)[1]) == 'N' &&
1213       toupper((*src)[2]) == 'A' &&
1214       toupper((*src)[3]) == 'N') {
1215     src->advance(4);
1216     return -std::numeric_limits<Tgt>::quiet_NaN();
1217   }
1218
1219   // All bets are off
1220   throw std::range_error("Unable to convert \"" + src->toString()
1221                          + "\" to a floating point value.");
1222 }
1223
1224 /**
1225  * Any string, const char*, or StringPiece to double.
1226  */
1227 template <class Tgt>
1228 typename std::enable_if<
1229   std::is_floating_point<Tgt>::value,
1230   Tgt>::type
1231 to(StringPiece src) {
1232   Tgt result = Tgt(to<double>(&src));
1233   detail::enforceWhitespace(src.data(), src.data() + src.size());
1234   return result;
1235 }
1236
1237 /*******************************************************************************
1238  * Integral to floating point and back
1239  ******************************************************************************/
1240
1241 /**
1242  * Checked conversion from integral to floating point and back. The
1243  * result must be convertible back to the source type without loss of
1244  * precision. This seems Draconian but sometimes is what's needed, and
1245  * complements existing routines nicely. For various rounding
1246  * routines, see <math>.
1247  */
1248 template <class Tgt, class Src>
1249 typename std::enable_if<
1250   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
1251   ||
1252   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
1253   Tgt>::type
1254 to(const Src & value) {
1255   Tgt result = Tgt(value);
1256   auto witness = static_cast<Src>(result);
1257   if (value != witness) {
1258     throw std::range_error(
1259       to<std::string>("to<>: loss of precision when converting ", value,
1260 #ifdef FOLLY_HAS_RTTI
1261                       " to type ", typeid(Tgt).name()
1262 #else
1263                       " to other type"
1264 #endif
1265                       ).c_str());
1266   }
1267   return result;
1268 }
1269
1270 /*******************************************************************************
1271  * Enum to anything and back
1272  ******************************************************************************/
1273
1274 template <class Tgt, class Src>
1275 typename std::enable_if<
1276   std::is_enum<Src>::value && !std::is_same<Src, Tgt>::value, Tgt>::type
1277 to(const Src & value) {
1278   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
1279 }
1280
1281 template <class Tgt, class Src>
1282 typename std::enable_if<
1283   std::is_enum<Tgt>::value && !std::is_same<Src, Tgt>::value, Tgt>::type
1284 to(const Src & value) {
1285   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
1286 }
1287
1288 } // namespace folly
1289
1290 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
1291 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
1292 // to avoid defining this global macro name in other files that include Conv.h.
1293 #ifndef FOLLY_CONV_INTERNAL
1294 #undef FOLLY_RANGE_CHECK
1295 #undef FOLLY_RANGE_CHECK_BEGIN_END
1296 #undef FOLLY_RANGE_CHECK_STRINGPIECE
1297 #undef FOLLY_RANGE_CHECK_STRINGIZE
1298 #undef FOLLY_RANGE_CHECK_STRINGIZE2
1299 #endif