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