folly/Conv.h

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