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 /**
 796  * Special version of the call that preallocates exaclty as much memory
 797  * as need for arguments to be stored in target. This means we are
 798  * not doing exponential growth when we append. If you are using it
 799  * in a loop you are aiming at your foot with a big perf-destroying
 800  * bazooka.
 801  * On the other hand if you are appending to a string once, this
 802  * will probably save a few calls to malloc.
 803  */
 804 template <class... Ts>
 805 typename std::enable_if<
 806   IsSomeString<
 807   typename std::remove_pointer<
 808     typename detail::last_element<Ts...>::type
 809   >::type>::value>::type
 810 toAppendFit(const Ts&... vs) {
 811   ::folly::detail::reserveInTarget(vs...);
 812   toAppend(vs...);
 813 }
 814
 815 template <class Ts>
 816 void toAppendFit(const Ts&) {}
 817
 818 /**
 819  * Variadic base case: do nothing.
 820  */
 821 template <class Tgt>
 822 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppend(
 823     Tgt* /* result */) {}
 824
 825 /**
 826  * Variadic base case: do nothing.
 827  */
 828 template <class Delimiter, class Tgt>
 829 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppendDelim(
 830     const Delimiter& /* delim */, Tgt* /* result */) {}
 831
 832 /**
 833  * 1 element: same as toAppend.
 834  */
 835 template <class Delimiter, class T, class Tgt>
 836 typename std::enable_if<IsSomeString<Tgt>::value>::type toAppendDelim(
 837     const Delimiter& /* delim */, const T& v, Tgt* tgt) {
 838   toAppend(v, tgt);
 839 }
 840
 841 /**
 842  * Append to string with a delimiter in between elements. Check out
 843  * comments for toAppend for details about memory allocation.
 844  */
 845 template <class Delimiter, class... Ts>
 846 typename std::enable_if<sizeof...(Ts) >= 3
 847   && IsSomeString<
 848   typename std::remove_pointer<
 849     typename detail::last_element<Ts...>::type
 850   >::type>::value>::type
 851 toAppendDelim(const Delimiter& delim, const Ts&... vs) {
 852   detail::toAppendDelimStrImpl(delim, vs...);
 853 }
 854
 855 /**
 856  * Detail in comment for toAppendFit
 857  */
 858 template <class Delimiter, class... Ts>
 859 typename std::enable_if<
 860   IsSomeString<
 861   typename std::remove_pointer<
 862     typename detail::last_element<Ts...>::type
 863   >::type>::value>::type
 864 toAppendDelimFit(const Delimiter& delim, const Ts&... vs) {
 865   detail::reserveInTargetDelim(delim, vs...);
 866   toAppendDelim(delim, vs...);
 867 }
 868
 869 template <class De, class Ts>
 870 void toAppendDelimFit(const De&, const Ts&) {}
 871
 872 /**
 873  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 874  * for all types.
 875  */
 876 template <class Tgt, class... Ts>
 877 typename std::enable_if<
 878   IsSomeString<Tgt>::value && (
 879     sizeof...(Ts) != 1 ||
 880     !std::is_same<Tgt, typename detail::last_element<Ts...>::type>::value),
 881   Tgt>::type
 882 to(const Ts&... vs) {
 883   Tgt result;
 884   toAppendFit(vs..., &result);
 885   return result;
 886 }
 887
 888 /**
 889  * toDelim<SomeString>(SomeString str) returns itself.
 890  */
 891 template <class Tgt, class Delim, class Src>
 892 typename std::enable_if<IsSomeString<Tgt>::value &&
 893                             std::is_same<Tgt, Src>::value,
 894                         Tgt>::type
 895 toDelim(const Delim& /* delim */, const Src& value) {
 896   return value;
 897 }
 898
 899 /**
 900  * toDelim<SomeString>(delim, v1, v2, ...) uses toAppendDelim() as
 901  * back-end for all types.
 902  */
 903 template <class Tgt, class Delim, class... Ts>
 904 typename std::enable_if<
 905   IsSomeString<Tgt>::value && (
 906     sizeof...(Ts) != 1 ||
 907     !std::is_same<Tgt, typename detail::last_element<Ts...>::type>::value),
 908   Tgt>::type
 909 toDelim(const Delim& delim, const Ts&... vs) {
 910   Tgt result;
 911   toAppendDelimFit(delim, vs..., &result);
 912   return result;
 913 }
 914
 915 /*******************************************************************************
 916  * Conversions from string types to integral types.
 917  ******************************************************************************/
 918
 919 namespace detail {
 920
 921 /**
 922  * Finds the first non-digit in a string. The number of digits
 923  * searched depends on the precision of the Tgt integral. Assumes the
 924  * string starts with NO whitespace and NO sign.
 925  *
 926  * The semantics of the routine is:
 927  *   for (;; ++b) {
 928  *     if (b >= e || !isdigit(*b)) return b;
 929  *   }
 930  *
 931  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 932  *  improvements of 20%.
 933  */
 934   template <class Tgt>
 935   const char* findFirstNonDigit(const char* b, const char* e) {
 936     for (; b < e; ++b) {
 937       auto const c = static_cast<unsigned>(*b) - '0';
 938       if (c >= 10) break;
 939     }
 940     return b;
 941   }
 942
 943   // Maximum value of number when represented as a string
 944   template <class T> struct MaxString {
 945     static const char*const value;
 946   };
 947
 948   bool str_to_bool(StringPiece* src);
 949
 950   template <class Tgt>
 951   Tgt digits_to(const char* b, const char* e);
 952
 953   extern template unsigned char digits_to<unsigned char>(const char* b,
 954                                                          const char* e);
 955   extern template unsigned short digits_to<unsigned short>(const char* b,
 956                                                            const char* e);
 957   extern template unsigned int digits_to<unsigned int>(const char* b,
 958                                                        const char* e);
 959   extern template unsigned long digits_to<unsigned long>(const char* b,
 960                                                          const char* e);
 961   extern template unsigned long long digits_to<unsigned long long>(
 962       const char* b, const char* e);
 963 #if FOLLY_HAVE_INT128_T
 964   extern template unsigned __int128 digits_to<unsigned __int128>(const char* b,
 965                                                                  const char* e);
 966 #endif
 967
 968 }                                 // namespace detail
 969
 970 /**
 971  * String represented as a pair of pointers to char to unsigned
 972  * integrals. Assumes NO whitespace before or after.
 973  */
 974 template <class Tgt>
 975 typename std::enable_if<
 976   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 977   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 978   Tgt>::type
 979 to(const char * b, const char * e) {
 980   return detail::digits_to<Tgt>(b, e);
 981 }
 982
 983 /**
 984  * String represented as a pair of pointers to char to signed
 985  * integrals. Assumes NO whitespace before or after. Allows an
 986  * optional leading sign.
 987  */
 988 template <class Tgt>
 989 typename std::enable_if<
 990   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
 991   Tgt>::type
 992 to(const char * b, const char * e) {
 993   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral",
 994                     to<std::string>("b: ", intptr_t(b), " e: ", intptr_t(e)));
 995   if (!isdigit(*b)) {
 996     if (*b == '-') {
 997       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
 998       FOLLY_RANGE_CHECK_BEGIN_END(result <= 0, "Negative overflow.", b, e);
 999       return result;
1000     }
1001     FOLLY_RANGE_CHECK_BEGIN_END(*b == '+', "Invalid lead character", b, e);
1002     ++b;
1003   }
1004   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
1005   FOLLY_RANGE_CHECK_BEGIN_END(result >= 0, "Overflow", b, e);
1006   return result;
1007 }
1008
1009 /**
1010  * Parsing strings to integrals. These routines differ from
1011  * to<integral>(string) in that they take a POINTER TO a StringPiece
1012  * and alter that StringPiece to reflect progress information.
1013  */
1014
1015 /**
1016  * StringPiece to integrals, with progress information. Alters the
1017  * StringPiece parameter to munch the already-parsed characters.
1018  */
1019 template <class Tgt>
1020 typename std::enable_if<
1021   std::is_integral<Tgt>::value
1022   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
1023   Tgt>::type
1024 to(StringPiece * src) {
1025
1026   auto b = src->data(), past = src->data() + src->size();
1027   for (;; ++b) {
1028     FOLLY_RANGE_CHECK_STRINGPIECE(b < past,
1029                                   "No digits found in input string", *src);
1030     if (!isspace(*b)) break;
1031   }
1032
1033   auto m = b;
1034
1035   // First digit is customized because we test for sign
1036   bool negative = false;
1037   /* static */ if (std::is_signed<Tgt>::value) {
1038     if (!isdigit(*m)) {
1039       if (*m == '-') {
1040         negative = true;
1041       } else {
1042         FOLLY_RANGE_CHECK_STRINGPIECE(*m == '+', "Invalid leading character in "
1043                                       "conversion to integral", *src);
1044       }
1045       ++b;
1046       ++m;
1047     }
1048   }
1049   FOLLY_RANGE_CHECK_STRINGPIECE(m < past, "No digits found in input string",
1050                                 *src);
1051   FOLLY_RANGE_CHECK_STRINGPIECE(isdigit(*m), "Non-digit character found", *src);
1052   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
1053
1054   Tgt result;
1055   /* static */ if (!std::is_signed<Tgt>::value) {
1056     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
1057   } else {
1058     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
1059     if (negative) {
1060       result = -t;
1061       FOLLY_RANGE_CHECK_STRINGPIECE(is_non_positive(result),
1062                                     "Negative overflow", *src);
1063     } else {
1064       result = t;
1065       FOLLY_RANGE_CHECK_STRINGPIECE(is_non_negative(result), "Overflow", *src);
1066     }
1067   }
1068   src->advance(m - src->data());
1069   return result;
1070 }
1071
1072 /**
1073  * StringPiece to bool, with progress information. Alters the
1074  * StringPiece parameter to munch the already-parsed characters.
1075  */
1076 template <class Tgt>
1077 typename std::enable_if<
1078   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
1079   Tgt>::type
1080 to(StringPiece * src) {
1081   return detail::str_to_bool(src);
1082 }
1083
1084 namespace detail {
1085
1086 /**
1087  * Enforce that the suffix following a number is made up only of whitespace.
1088  */
1089 inline void enforceWhitespace(const char* b, const char* e) {
1090   for (; b != e; ++b) {
1091     FOLLY_RANGE_CHECK_BEGIN_END(isspace(*b),
1092                                 to<std::string>("Non-whitespace: ", *b),
1093                                 b, e);
1094   }
1095 }
1096
1097 }  // namespace detail
1098
1099 /**
1100  * String or StringPiece to integrals. Accepts leading and trailing
1101  * whitespace, but no non-space trailing characters.
1102  */
1103 template <class Tgt>
1104 typename std::enable_if<
1105   std::is_integral<Tgt>::value,
1106   Tgt>::type
1107 to(StringPiece src) {
1108   Tgt result = to<Tgt>(&src);
1109   detail::enforceWhitespace(src.data(), src.data() + src.size());
1110   return result;
1111 }
1112
1113 /*******************************************************************************
1114  * Conversions from string types to floating-point types.
1115  ******************************************************************************/
1116
1117 /**
1118  * StringPiece to double, with progress information. Alters the
1119  * StringPiece parameter to munch the already-parsed characters.
1120  */
1121 template <class Tgt>
1122 inline typename std::enable_if<
1123   std::is_floating_point<Tgt>::value,
1124   Tgt>::type
1125 to(StringPiece *const src) {
1126   using namespace double_conversion;
1127   static StringToDoubleConverter
1128     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
1129          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
1130          0.0,
1131          // return this for junk input string
1132          std::numeric_limits<double>::quiet_NaN(),
1133          nullptr, nullptr);
1134
1135   FOLLY_RANGE_CHECK_STRINGPIECE(!src->empty(),
1136                                 "No digits found in input string", *src);
1137
1138   int length;
1139   auto result = conv.StringToDouble(src->data(),
1140                                     static_cast<int>(src->size()),
1141                                     &length); // processed char count
1142
1143   if (!std::isnan(result)) {
1144     src->advance(length);
1145     return result;
1146   }
1147
1148   for (;; src->advance(1)) {
1149     if (src->empty()) {
1150       throw std::range_error("Unable to convert an empty string"
1151                              " to a floating point value.");
1152     }
1153     if (!isspace(src->front())) {
1154       break;
1155     }
1156   }
1157
1158   // Was that "inf[inity]"?
1159   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
1160         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
1161     if (src->size() >= 8 &&
1162         toupper((*src)[3]) == 'I' &&
1163         toupper((*src)[4]) == 'N' &&
1164         toupper((*src)[5]) == 'I' &&
1165         toupper((*src)[6]) == 'T' &&
1166         toupper((*src)[7]) == 'Y') {
1167       src->advance(8);
1168     } else {
1169       src->advance(3);
1170     }
1171     return std::numeric_limits<Tgt>::infinity();
1172   }
1173
1174   // Was that "-inf[inity]"?
1175   if (src->size() >= 4 && toupper((*src)[0]) == '-'
1176       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
1177       && toupper((*src)[3]) == 'F') {
1178     if (src->size() >= 9 &&
1179         toupper((*src)[4]) == 'I' &&
1180         toupper((*src)[5]) == 'N' &&
1181         toupper((*src)[6]) == 'I' &&
1182         toupper((*src)[7]) == 'T' &&
1183         toupper((*src)[8]) == 'Y') {
1184       src->advance(9);
1185     } else {
1186       src->advance(4);
1187     }
1188     return -std::numeric_limits<Tgt>::infinity();
1189   }
1190
1191   // "nan"?
1192   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
1193         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
1194     src->advance(3);
1195     return std::numeric_limits<Tgt>::quiet_NaN();
1196   }
1197
1198   // "-nan"?
1199   if (src->size() >= 4 &&
1200       toupper((*src)[0]) == '-' &&
1201       toupper((*src)[1]) == 'N' &&
1202       toupper((*src)[2]) == 'A' &&
1203       toupper((*src)[3]) == 'N') {
1204     src->advance(4);
1205     return -std::numeric_limits<Tgt>::quiet_NaN();
1206   }
1207
1208   // All bets are off
1209   throw std::range_error("Unable to convert \"" + src->toString()
1210                          + "\" to a floating point value.");
1211 }
1212
1213 /**
1214  * Any string, const char*, or StringPiece to double.
1215  */
1216 template <class Tgt>
1217 typename std::enable_if<
1218   std::is_floating_point<Tgt>::value,
1219   Tgt>::type
1220 to(StringPiece src) {
1221   Tgt result = Tgt(to<double>(&src));
1222   detail::enforceWhitespace(src.data(), src.data() + src.size());
1223   return result;
1224 }
1225
1226 /*******************************************************************************
1227  * Integral to floating point and back
1228  ******************************************************************************/
1229
1230 /**
1231  * Checked conversion from integral to floating point and back. The
1232  * result must be convertible back to the source type without loss of
1233  * precision. This seems Draconian but sometimes is what's needed, and
1234  * complements existing routines nicely. For various rounding
1235  * routines, see <math>.
1236  */
1237 template <class Tgt, class Src>
1238 typename std::enable_if<
1239   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
1240   ||
1241   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
1242   Tgt>::type
1243 to(const Src & value) {
1244   Tgt result = Tgt(value);
1245   auto witness = static_cast<Src>(result);
1246   if (value != witness) {
1247     throw std::range_error(
1248       to<std::string>("to<>: loss of precision when converting ", value,
1249 #ifdef FOLLY_HAS_RTTI
1250                       " to type ", typeid(Tgt).name()
1251 #else
1252                       " to other type"
1253 #endif
1254                       ).c_str());
1255   }
1256   return result;
1257 }
1258
1259 /*******************************************************************************
1260  * Enum to anything and back
1261  ******************************************************************************/
1262
1263 template <class Tgt, class Src>
1264 typename std::enable_if<
1265   std::is_enum<Src>::value && !std::is_same<Src, Tgt>::value, Tgt>::type
1266 to(const Src & value) {
1267   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
1268 }
1269
1270 template <class Tgt, class Src>
1271 typename std::enable_if<
1272   std::is_enum<Tgt>::value && !std::is_same<Src, Tgt>::value, Tgt>::type
1273 to(const Src & value) {
1274   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
1275 }
1276
1277 } // namespace folly
1278
1279 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
1280 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
1281 // to avoid defining this global macro name in other files that include Conv.h.
1282 #ifndef FOLLY_CONV_INTERNAL
1283 #undef FOLLY_RANGE_CHECK
1284 #undef FOLLY_RANGE_CHECK_BEGIN_END
1285 #undef FOLLY_RANGE_CHECK_STRINGPIECE
1286 #undef FOLLY_RANGE_CHECK_STRINGIZE
1287 #undef FOLLY_RANGE_CHECK_STRINGIZE2
1288 #endif