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