folly/Conv.h

   1 /*
   2  * Copyright 2012 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 <type_traits>
  34 #include <limits>
  35 #include <string>
  36 #include <tuple>
  37 #include <stdexcept>
  38 #include <typeinfo>
  39
  40 #include "double-conversion.h"   // V8 JavaScript implementation
  41
  42 #define FOLLY_RANGE_CHECK(condition, message)                           \
  43   ((condition) ? (void)0 : throw std::range_error(                      \
  44     (__FILE__ "(" + std::to_string((long long int) __LINE__) + "): "    \
  45      + (message)).c_str()))
  46
  47 namespace folly {
  48
  49 /*******************************************************************************
  50  * Integral to integral
  51  ******************************************************************************/
  52
  53 /**
  54  * Checked conversion from integral to integral. The checks are only
  55  * performed when meaningful, e.g. conversion from int to long goes
  56  * unchecked.
  57  */
  58 template <class Tgt, class Src>
  59 typename std::enable_if<
  60   std::is_integral<Src>::value && std::is_integral<Tgt>::value,
  61   Tgt>::type
  62 to(const Src & value) {
  63   /* static */ if (std::numeric_limits<Tgt>::max()
  64                    < std::numeric_limits<Src>::max()) {
  65     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
  66                       "Overflow");
  67   }
  68   /* static */ if (std::is_signed<Src>::value &&
  69                    (!std::is_signed<Tgt>::value || sizeof(Src) > sizeof(Tgt))) {
  70     FOLLY_RANGE_CHECK(value >= std::numeric_limits<Tgt>::min(),
  71                       "Negative overflow");
  72   }
  73   return static_cast<Tgt>(value);
  74 }
  75
  76 /*******************************************************************************
  77  * Floating point to floating point
  78  ******************************************************************************/
  79
  80 template <class Tgt, class Src>
  81 typename std::enable_if<
  82   std::is_floating_point<Tgt>::value && std::is_floating_point<Src>::value,
  83   Tgt>::type
  84 to(const Src & value) {
  85   /* static */ if (std::numeric_limits<Tgt>::max() <
  86                    std::numeric_limits<Src>::max()) {
  87     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
  88                       "Overflow");
  89     FOLLY_RANGE_CHECK(value >= -std::numeric_limits<Tgt>::max(),
  90                       "Negative overflow");
  91   }
  92   return boost::implicit_cast<Tgt>(value);
  93 }
  94
  95 /*******************************************************************************
  96  * Anything to string
  97  ******************************************************************************/
  98
  99 namespace detail {
 100
 101 template <class T> struct IsSomeString {
 102   enum { value = std::is_same<T, std::string>::value
 103          || std::is_same<T, fbstring>::value };
 104 };
 105
 106 template <class T>
 107 const T& getLastElement(const T & v) {
 108   return v;
 109 }
 110
 111 template <class T, class... Ts>
 112 typename std::tuple_element<
 113   sizeof...(Ts),
 114   std::tuple<T, Ts...> >::type const&
 115   getLastElement(const T& v, const Ts&... vs) {
 116   return getLastElement(vs...);
 117 }
 118
 119 } // namespace detail
 120
 121 /*******************************************************************************
 122  * Conversions from integral types to string types.
 123  ******************************************************************************/
 124
 125 /**
 126  * Returns the number of digits in the base 10 representation of an
 127  * uint64_t. Useful for preallocating buffers and such. It's also used
 128  * internally, see below. Measurements suggest that defining a
 129  * separate overload for 32-bit integers is not worthwhile.
 130  */
 131
 132 inline uint32_t digits10(uint64_t v) {
 133   uint32_t result = 1;
 134   for (;;) {
 135     if (LIKELY(v < 10)) return result;
 136     if (LIKELY(v < 100)) return result + 1;
 137     if (LIKELY(v < 1000)) return result + 2;
 138     if (LIKELY(v < 10000)) return result + 3;
 139     // Skip ahead by 4 orders of magnitude
 140     v /= 10000U;
 141     result += 4;
 142   }
 143 }
 144
 145 /**
 146  * Copies the ASCII base 10 representation of v into buffer and
 147  * returns the number of bytes written. Does NOT append a \0. Assumes
 148  * the buffer points to digits10(v) bytes of valid memory. Note that
 149  * uint64 needs at most 20 bytes, uint32_t needs at most 10 bytes,
 150  * uint16_t needs at most 5 bytes, and so on. Measurements suggest
 151  * that defining a separate overload for 32-bit integers is not
 152  * worthwhile.
 153  *
 154  * This primitive is unsafe because it makes the size assumption and
 155  * because it does not add a terminating \0.
 156  */
 157
 158 inline uint32_t uint64ToBufferUnsafe(uint64_t v, char *const buffer) {
 159   auto const result = digits10(v);
 160   // WARNING: using size_t or pointer arithmetic for pos slows down
 161   // the loop below 20x. This is because several 32-bit ops can be
 162   // done in parallel, but only fewer 64-bit ones.
 163   uint32_t pos = result - 1;
 164   while (v >= 10) {
 165     // Keep these together so a peephole optimization "sees" them and
 166     // computes them in one shot.
 167     auto const q = v / 10;
 168     auto const r = static_cast<uint32_t>(v % 10);
 169     buffer[pos--] = '0' + r;
 170     v = q;
 171   }
 172   // Last digit is trivial to handle
 173   buffer[pos] = static_cast<uint32_t>(v) + '0';
 174   return result;
 175 }
 176
 177 /**
 178  * A single char gets appended.
 179  */
 180 template <class Tgt>
 181 void toAppend(char value, Tgt * result) {
 182   *result += value;
 183 }
 184
 185 /**
 186  * Everything implicitly convertible to const char* gets appended.
 187  */
 188 template <class Tgt, class Src>
 189 typename std::enable_if<
 190   std::is_convertible<Src, const char*>::value
 191   && detail::IsSomeString<Tgt>::value>::type
 192 toAppend(Src value, Tgt * result) {
 193   // Treat null pointers like an empty string, as in:
 194   // operator<<(std::ostream&, const char*).
 195   const char* c = value;
 196   if (c) {
 197     result->append(value);
 198   }
 199 }
 200
 201 /**
 202  * Strings get appended, too.
 203  */
 204 template <class Tgt, class Src>
 205 typename std::enable_if<
 206   detail::IsSomeString<Src>::value && detail::IsSomeString<Tgt>::value>::type
 207 toAppend(const Src& value, Tgt * result) {
 208   result->append(value);
 209 }
 210
 211 /**
 212  * and StringPiece objects too
 213  */
 214 template <class Tgt>
 215 typename std::enable_if<
 216    detail::IsSomeString<Tgt>::value>::type
 217 toAppend(StringPiece value, Tgt * result) {
 218   result->append(value.data(), value.size());
 219 }
 220
 221 /**
 222  * There's no implicit conversion from fbstring to other string types,
 223  * so make a specialization.
 224  */
 225 template <class Tgt>
 226 typename std::enable_if<
 227    detail::IsSomeString<Tgt>::value>::type
 228 toAppend(const fbstring& value, Tgt * result) {
 229   result->append(value.data(), value.size());
 230 }
 231
 232 /**
 233  * int32_t and int64_t to string (by appending) go through here. The
 234  * result is APPENDED to a preexisting string passed as the second
 235  * parameter. For convenience, the function also returns a reference
 236  * to *result. This should be efficient with fbstring because fbstring
 237  * incurs no dynamic allocation below 23 bytes and no number has more
 238  * than 22 bytes in its textual representation (20 for digits, one for
 239  * sign, one for the terminating 0).
 240  */
 241 template <class Tgt, class Src>
 242 typename std::enable_if<
 243   std::is_integral<Src>::value && std::is_signed<Src>::value
 244   && detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 245 toAppend(Src value, Tgt * result) {
 246   typedef typename std::make_unsigned<Src>::type Usrc;
 247   char buffer[20];
 248   if (value < 0) {
 249     result->push_back('-');
 250     result->append(buffer, uint64ToBufferUnsafe(-uint64_t(value), buffer));
 251   } else {
 252     result->append(buffer, uint64ToBufferUnsafe(value, buffer));
 253   }
 254 }
 255
 256 /**
 257  * As above, but for uint32_t and uint64_t.
 258  */
 259 template <class Tgt, class Src>
 260 typename std::enable_if<
 261   std::is_integral<Src>::value && !std::is_signed<Src>::value
 262   && detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 263 toAppend(Src value, Tgt * result) {
 264   char buffer[20];
 265   result->append(buffer, buffer + uint64ToBufferUnsafe(value, buffer));
 266 }
 267
 268 /**
 269  * All small signed and unsigned integers to string go through 32-bit
 270  * types int32_t and uint32_t, respectively.
 271  */
 272 template <class Tgt, class Src>
 273 typename std::enable_if<
 274   std::is_integral<Src>::value
 275   && detail::IsSomeString<Tgt>::value && sizeof(Src) < 4>::type
 276 toAppend(Src value, Tgt * result) {
 277   typedef typename
 278     std::conditional<std::is_signed<Src>::value, int64_t, uint64_t>::type
 279     Intermediate;
 280   toAppend<Tgt>(static_cast<Intermediate>(value), result);
 281 }
 282
 283 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
 284 // std::underlying_type became available by gcc 4.7.0
 285
 286 /**
 287  * Enumerated values get appended as integers.
 288  */
 289 template <class Tgt, class Src>
 290 typename std::enable_if<
 291   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 292 toAppend(Src value, Tgt * result) {
 293   toAppend(
 294       static_cast<typename std::underlying_type<Src>::type>(value), result);
 295 }
 296
 297 #else
 298
 299 /**
 300  * Enumerated values get appended as integers.
 301  */
 302 template <class Tgt, class Src>
 303 typename std::enable_if<
 304   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 305 toAppend(Src value, Tgt * result) {
 306   /* static */ if (Src(-1) < 0) {
 307     /* static */ if (sizeof(Src) <= sizeof(int)) {
 308       toAppend(static_cast<int>(value), result);
 309     } else {
 310       toAppend(static_cast<long>(value), result);
 311     }
 312   } else {
 313     /* static */ if (sizeof(Src) <= sizeof(int)) {
 314       toAppend(static_cast<unsigned int>(value), result);
 315     } else {
 316       toAppend(static_cast<unsigned long>(value), result);
 317     }
 318   }
 319 }
 320
 321 #endif // gcc 4.7 onwards
 322
 323 /*******************************************************************************
 324  * Conversions from floating-point types to string types.
 325  ******************************************************************************/
 326
 327 /** Wrapper around DoubleToStringConverter **/
 328 template <class Tgt, class Src>
 329 typename std::enable_if<
 330   std::is_floating_point<Src>::value
 331   && detail::IsSomeString<Tgt>::value>::type
 332 toAppend(
 333   Src value,
 334   Tgt * result,
 335   double_conversion::DoubleToStringConverter::DtoaMode mode,
 336   unsigned int numDigits) {
 337   using namespace double_conversion;
 338   DoubleToStringConverter
 339     conv(DoubleToStringConverter::NO_FLAGS,
 340          "infinity", "NaN", 'E',
 341          -6,  // decimal in shortest low
 342          21,  // decimal in shortest high
 343          6,   // max leading padding zeros
 344          1);  // max trailing padding zeros
 345   char buffer[256];
 346   StringBuilder builder(buffer, sizeof(buffer));
 347   switch (mode) {
 348     case DoubleToStringConverter::SHORTEST:
 349       conv.ToShortest(value, &builder);
 350       break;
 351     case DoubleToStringConverter::FIXED:
 352       conv.ToFixed(value, numDigits, &builder);
 353       break;
 354     default:
 355       CHECK(mode == DoubleToStringConverter::PRECISION);
 356       conv.ToPrecision(value, numDigits, &builder);
 357       break;
 358   }
 359   const size_t length = builder.position();
 360   builder.Finalize();
 361   result->append(buffer, length);
 362 }
 363
 364 /**
 365  * As above, but for floating point
 366  */
 367 template <class Tgt, class Src>
 368 typename std::enable_if<
 369   std::is_floating_point<Src>::value
 370   && detail::IsSomeString<Tgt>::value>::type
 371 toAppend(Src value, Tgt * result) {
 372   toAppend(
 373     value, result, double_conversion::DoubleToStringConverter::SHORTEST, 0);
 374 }
 375
 376 /**
 377  * Variadic conversion to string. Appends each element in turn.
 378  */
 379 template <class T, class... Ts>
 380 typename std::enable_if<sizeof...(Ts) >= 2
 381   && detail::IsSomeString<
 382   typename std::remove_pointer<
 383     typename std::tuple_element<
 384       sizeof...(Ts) - 1, std::tuple<Ts...>
 385       >::type>::type>::value>::type
 386 toAppend(const T& v, const Ts&... vs) {
 387   toAppend(v, detail::getLastElement(vs...));
 388   toAppend(vs...);
 389 }
 390
 391 /**
 392  * Variadic base case: do nothing.
 393  */
 394 template <class Tgt>
 395 typename std::enable_if<detail::IsSomeString<Tgt>::value>::type
 396 toAppend(Tgt* result) {
 397 }
 398
 399 /**
 400  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 401  * for all types.
 402  */
 403 template <class Tgt, class... Ts>
 404 typename std::enable_if<detail::IsSomeString<Tgt>::value, Tgt>::type
 405 to(const Ts&... vs) {
 406   Tgt result;
 407   toAppend(vs..., &result);
 408   return result;
 409 }
 410
 411 /*******************************************************************************
 412  * Conversions from string types to integral types.
 413  ******************************************************************************/
 414
 415 namespace detail {
 416
 417 /**
 418  * Finds the first non-digit in a string. The number of digits
 419  * searched depends on the precision of the Tgt integral. Assumes the
 420  * string starts with NO whitespace and NO sign.
 421  *
 422  * The semantics of the routine is:
 423  *   for (;; ++b) {
 424  *     if (b >= e || !isdigit(*b)) return b;
 425  *   }
 426  *
 427  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 428  *  improvements of 20%.
 429  */
 430   template <class Tgt>
 431   const char* findFirstNonDigit(const char* b, const char* e) {
 432     for (; b < e; ++b) {
 433       auto const c = static_cast<unsigned>(*b) - '0';
 434       if (c >= 10) break;
 435     }
 436     return b;
 437   }
 438
 439   // Maximum value of number when represented as a string
 440   template <class T> struct MaxString {
 441     static const char*const value;
 442   };
 443
 444
 445 /*
 446  * Lookup tables that converts from a decimal character value to an integral
 447  * binary value, shifted by a decimal "shift" multiplier.
 448  * For all character values in the range '0'..'9', the table at those
 449  * index locations returns the actual decimal value shifted by the multiplier.
 450  * For all other values, the lookup table returns an invalid OOR value.
 451  */
 452 // Out-of-range flag value, larger than the largest value that can fit in
 453 // four decimal bytes (9999), but four of these added up together should
 454 // still not overflow uint16_t.
 455 constexpr int32_t OOR = 10000;
 456
 457 __attribute__((aligned(16))) constexpr uint16_t shift1[] = {
 458   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 459   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 460   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 461   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 462   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 463   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
 464   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 465   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 466   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 467   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 468   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 469   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 470   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 471   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 472   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 473   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 474   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 475   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 476   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 477   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 478   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 479   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 480   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 481   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 482   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 483   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 484 };
 485
 486 __attribute__((aligned(16))) constexpr uint16_t shift10[] = {
 487   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 488   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 489   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 490   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 491   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 492   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 493   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 494   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 495   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 496   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 497   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 498   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 499   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 500   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 501   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 502   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 503   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 504   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 505   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 506   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 507   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 508   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 509   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 510   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 511   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 512   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 513 };
 514
 515 __attribute__((aligned(16))) constexpr uint16_t shift100[] = {
 516   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 517   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 518   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 519   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 520   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 521   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 522   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 523   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 524   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 525   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 526   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 527   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 528   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 529   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 530   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 531   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 532   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 533   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 534   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 535   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 536   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 537   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 538   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 539   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 540   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 541   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 542 };
 543
 544 __attribute__((aligned(16))) constexpr uint16_t shift1000[] = {
 545   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 546   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 547   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 548   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 549   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 550   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 551   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 552   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 553   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 554   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 555   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 556   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 557   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 558   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 559   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 560   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 561   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 562   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 563   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 564   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 565   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 566   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 567   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 568   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 569   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 570   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 571 };
 572
 573 /**
 574  * String represented as a pair of pointers to char to unsigned
 575  * integrals. Assumes NO whitespace before or after, and also that the
 576  * string is composed entirely of digits. Tgt must be unsigned, and no
 577  * sign is allowed in the string (even it's '+'). String may be empty,
 578  * in which case digits_to throws.
 579  */
 580   template <class Tgt>
 581   Tgt digits_to(const char * b, const char * e) {
 582
 583     static_assert(!std::is_signed<Tgt>::value, "Unsigned type expected");
 584     assert(b <= e);
 585
 586     const size_t size = e - b;
 587
 588     /* Although the string is entirely made of digits, we still need to
 589      * check for overflow.
 590      */
 591     if (size >= std::numeric_limits<Tgt>::digits10 + 1) {
 592       // Leading zeros? If so, recurse to keep things simple
 593       if (b < e && *b == '0') {
 594         for (++b;; ++b) {
 595           if (b == e) return 0; // just zeros, e.g. "0000"
 596           if (*b != '0') return digits_to<Tgt>(b, e);
 597         }
 598       }
 599       FOLLY_RANGE_CHECK(size == std::numeric_limits<Tgt>::digits10 + 1 &&
 600                         strncmp(b, detail::MaxString<Tgt>::value, size) <= 0,
 601                         "Numeric overflow upon conversion");
 602     }
 603
 604     // Here we know that the number won't overflow when
 605     // converted. Proceed without checks.
 606
 607     Tgt result = 0;
 608
 609     for (; e - b >= 4; b += 4) {
 610       result *= 10000;
 611       const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 612       const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 613       const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 614       const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 615       const auto sum = r0 + r1 + r2 + r3;
 616       assert(sum < OOR && "Assumption: string only has digits");
 617       result += sum;
 618     }
 619
 620     switch (e - b) {
 621       case 3: {
 622         const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 623         const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 624         const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 625         const auto sum = r0 + r1 + r2;
 626         assert(sum < OOR && "Assumption: string only has digits");
 627         return result * 1000 + sum;
 628       }
 629       case 2: {
 630         const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 631         const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 632         const auto sum = r0 + r1;
 633         assert(sum < OOR && "Assumption: string only has digits");
 634         return result * 100 + sum;
 635       }
 636       case 1: {
 637         const int32_t sum = shift1[static_cast<size_t>(b[0])];
 638         assert(sum < OOR && "Assumption: string only has digits");
 639         return result * 10 + sum;
 640       }
 641     }
 642
 643     assert(b == e);
 644     FOLLY_RANGE_CHECK(size > 0, "Found no digits to convert in input");
 645     return result;
 646   }
 647
 648
 649   bool str_to_bool(StringPiece * src);
 650
 651 }                                 // namespace detail
 652
 653 /**
 654  * String represented as a pair of pointers to char to unsigned
 655  * integrals. Assumes NO whitespace before or after.
 656  */
 657 template <class Tgt>
 658 typename std::enable_if<
 659   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 660   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 661   Tgt>::type
 662 to(const char * b, const char * e) {
 663   return detail::digits_to<Tgt>(b, e);
 664 }
 665
 666 /**
 667  * String represented as a pair of pointers to char to signed
 668  * integrals. Assumes NO whitespace before or after. Allows an
 669  * optional leading sign.
 670  */
 671 template <class Tgt>
 672 typename std::enable_if<
 673   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
 674   Tgt>::type
 675 to(const char * b, const char * e) {
 676   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral");
 677   if (!isdigit(*b)) {
 678     if (*b == '-') {
 679       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
 680       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow.");
 681       return result;
 682     }
 683     FOLLY_RANGE_CHECK(*b == '+', "Invalid lead character");
 684     ++b;
 685   }
 686   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
 687   FOLLY_RANGE_CHECK(result >= 0, "Overflow.");
 688   return result;
 689 }
 690
 691 /**
 692  * Parsing strings to integrals. These routines differ from
 693  * to<integral>(string) in that they take a POINTER TO a StringPiece
 694  * and alter that StringPiece to reflect progress information.
 695  */
 696
 697 /**
 698  * StringPiece to integrals, with progress information. Alters the
 699  * StringPiece parameter to munch the already-parsed characters.
 700  */
 701 template <class Tgt>
 702 typename std::enable_if<
 703   std::is_integral<Tgt>::value
 704   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 705   Tgt>::type
 706 to(StringPiece * src) {
 707
 708   auto b = src->data(), past = src->data() + src->size();
 709   for (;; ++b) {
 710     FOLLY_RANGE_CHECK(b < past, "No digits found in input string");
 711     if (!isspace(*b)) break;
 712   }
 713
 714   auto m = b;
 715
 716   // First digit is customized because we test for sign
 717   bool negative = false;
 718   /* static */ if (std::is_signed<Tgt>::value) {
 719     if (!isdigit(*m)) {
 720       if (*m == '-') {
 721         negative = true;
 722       } else {
 723         FOLLY_RANGE_CHECK(*m == '+', "Invalid leading character in conversion"
 724                           " to integral");
 725       }
 726       ++b;
 727       ++m;
 728     }
 729   }
 730   FOLLY_RANGE_CHECK(m < past, "No digits found in input string");
 731   FOLLY_RANGE_CHECK(isdigit(*m), "Non-digit character found");
 732   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
 733
 734   Tgt result;
 735   /* static */ if (!std::is_signed<Tgt>::value) {
 736     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 737   } else {
 738     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 739     if (negative) {
 740       result = -t;
 741       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow");
 742     } else {
 743       result = t;
 744       FOLLY_RANGE_CHECK(result >= 0, "Overflow");
 745     }
 746   }
 747   src->advance(m - src->data());
 748   return result;
 749 }
 750
 751 /**
 752  * StringPiece to bool, with progress information. Alters the
 753  * StringPiece parameter to munch the already-parsed characters.
 754  */
 755 template <class Tgt>
 756 typename std::enable_if<
 757   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 758   Tgt>::type
 759 to(StringPiece * src) {
 760   return detail::str_to_bool(src);
 761 }
 762
 763 namespace detail {
 764
 765 /**
 766  * Enforce that the suffix following a number is made up only of whitespace.
 767  */
 768 inline void enforceWhitespace(const char* b, const char* e) {
 769   for (; b != e; ++b) {
 770     FOLLY_RANGE_CHECK(isspace(*b), to<std::string>("Non-whitespace: ", *b));
 771   }
 772 }
 773
 774 }  // namespace detail
 775
 776 /**
 777  * String or StringPiece to integrals. Accepts leading and trailing
 778  * whitespace, but no non-space trailing characters.
 779  */
 780 template <class Tgt>
 781 typename std::enable_if<
 782   std::is_integral<Tgt>::value,
 783   Tgt>::type
 784 to(StringPiece src) {
 785   Tgt result = to<Tgt>(&src);
 786   detail::enforceWhitespace(src.data(), src.data() + src.size());
 787   return result;
 788 }
 789
 790 /*******************************************************************************
 791  * Conversions from string types to floating-point types.
 792  ******************************************************************************/
 793
 794 /**
 795  * StringPiece to double, with progress information. Alters the
 796  * StringPiece parameter to munch the already-parsed characters.
 797  */
 798 template <class Tgt>
 799 inline typename std::enable_if<
 800   std::is_floating_point<Tgt>::value,
 801   Tgt>::type
 802 to(StringPiece *const src) {
 803   using namespace double_conversion;
 804   static StringToDoubleConverter
 805     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
 806          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
 807          0.0,
 808          // return this for junk input string
 809          std::numeric_limits<double>::quiet_NaN(),
 810          nullptr, nullptr);
 811
 812   FOLLY_RANGE_CHECK(!src->empty(), "No digits found in input string");
 813
 814   int length;
 815   auto result = conv.StringToDouble(src->data(), src->size(),
 816                                        &length); // processed char count
 817
 818   if (!std::isnan(result)) {
 819     src->advance(length);
 820     return result;
 821   }
 822
 823   for (;; src->advance(1)) {
 824     if (src->empty()) {
 825       throw std::range_error("Unable to convert an empty string"
 826                              " to a floating point value.");
 827     }
 828     if (!isspace(src->front())) {
 829       break;
 830     }
 831   }
 832
 833   // Was that "inf[inity]"?
 834   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
 835         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
 836     if (src->size() >= 8 &&
 837         toupper((*src)[3]) == 'I' &&
 838         toupper((*src)[4]) == 'N' &&
 839         toupper((*src)[5]) == 'I' &&
 840         toupper((*src)[6]) == 'T' &&
 841         toupper((*src)[7]) == 'Y') {
 842       src->advance(8);
 843     } else {
 844       src->advance(3);
 845     }
 846     return std::numeric_limits<Tgt>::infinity();
 847   }
 848
 849   // Was that "-inf[inity]"?
 850   if (src->size() >= 4 && toupper((*src)[0]) == '-'
 851       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
 852       && toupper((*src)[3]) == 'F') {
 853     if (src->size() >= 9 &&
 854         toupper((*src)[4]) == 'I' &&
 855         toupper((*src)[5]) == 'N' &&
 856         toupper((*src)[6]) == 'I' &&
 857         toupper((*src)[7]) == 'T' &&
 858         toupper((*src)[8]) == 'Y') {
 859       src->advance(9);
 860     } else {
 861       src->advance(4);
 862     }
 863     return -std::numeric_limits<Tgt>::infinity();
 864   }
 865
 866   // "nan"?
 867   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
 868         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
 869     src->advance(3);
 870     return std::numeric_limits<Tgt>::quiet_NaN();
 871   }
 872
 873   // "-nan"?
 874   if (src->size() >= 4 &&
 875       toupper((*src)[0]) == '-' &&
 876       toupper((*src)[1]) == 'N' &&
 877       toupper((*src)[2]) == 'A' &&
 878       toupper((*src)[3]) == 'N') {
 879     src->advance(4);
 880     return -std::numeric_limits<Tgt>::quiet_NaN();
 881   }
 882
 883   // All bets are off
 884   throw std::range_error("Unable to convert \"" + src->toString()
 885                          + "\" to a floating point value.");
 886 }
 887
 888 /**
 889  * Any string, const char*, or StringPiece to double.
 890  */
 891 template <class Tgt>
 892 typename std::enable_if<
 893   std::is_floating_point<Tgt>::value,
 894   Tgt>::type
 895 to(StringPiece src) {
 896   Tgt result = to<double>(&src);
 897   detail::enforceWhitespace(src.data(), src.data() + src.size());
 898   return result;
 899 }
 900
 901 /*******************************************************************************
 902  * Integral to floating point and back
 903  ******************************************************************************/
 904
 905 /**
 906  * Checked conversion from integral to flating point and back. The
 907  * result must be convertible back to the source type without loss of
 908  * precision. This seems Draconian but sometimes is what's needed, and
 909  * complements existing routines nicely. For various rounding
 910  * routines, see <math>.
 911  */
 912 template <class Tgt, class Src>
 913 typename std::enable_if<
 914   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
 915   ||
 916   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
 917   Tgt>::type
 918 to(const Src & value) {
 919   Tgt result = value;
 920   auto witness = static_cast<Src>(result);
 921   if (value != witness) {
 922     throw std::range_error(
 923       to<std::string>("to<>: loss of precision when converting ", value,
 924                       " to type ", typeid(Tgt).name()).c_str());
 925   }
 926   return result;
 927 }
 928
 929 /*******************************************************************************
 930  * Enum to anything and back
 931  ******************************************************************************/
 932
 933 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
 934 // std::underlying_type became available by gcc 4.7.0
 935
 936 template <class Tgt, class Src>
 937 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
 938 to(const Src & value) {
 939   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
 940 }
 941
 942 template <class Tgt, class Src>
 943 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
 944 to(const Src & value) {
 945   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
 946 }
 947
 948 #else
 949
 950 template <class Tgt, class Src>
 951 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
 952 to(const Src & value) {
 953   /* static */ if (Src(-1) < 0) {
 954     /* static */ if (sizeof(Src) <= sizeof(int)) {
 955       return to<Tgt>(static_cast<int>(value));
 956     } else {
 957       return to<Tgt>(static_cast<long>(value));
 958     }
 959   } else {
 960     /* static */ if (sizeof(Src) <= sizeof(int)) {
 961       return to<Tgt>(static_cast<unsigned int>(value));
 962     } else {
 963       return to<Tgt>(static_cast<unsigned long>(value));
 964     }
 965   }
 966 }
 967
 968 template <class Tgt, class Src>
 969 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
 970 to(const Src & value) {
 971   /* static */ if (Tgt(-1) < 0) {
 972     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
 973       return static_cast<Tgt>(to<int>(value));
 974     } else {
 975       return static_cast<Tgt>(to<long>(value));
 976     }
 977   } else {
 978     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
 979       return static_cast<Tgt>(to<unsigned int>(value));
 980     } else {
 981       return static_cast<Tgt>(to<unsigned long>(value));
 982     }
 983   }
 984 }
 985
 986 #endif // gcc 4.7 onwards
 987
 988 } // namespace folly
 989
 990 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
 991 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
 992 // to avoid defining this global macro name in other files that include Conv.h.
 993 #ifndef FOLLY_CONV_INTERNAL
 994 #undef FOLLY_RANGE_CHECK
 995 #endif
 996
 997 #endif /* FOLLY_BASE_CONV_H_ */