folly/Conv.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include <folly/Conv.h>
  17 #include <array>
  18
  19 namespace folly {
  20 namespace detail {
  21
  22 namespace {
  23
  24 /**
  25  * Finds the first non-digit in a string. The number of digits
  26  * searched depends on the precision of the Tgt integral. Assumes the
  27  * string starts with NO whitespace and NO sign.
  28  *
  29  * The semantics of the routine is:
  30  *   for (;; ++b) {
  31  *     if (b >= e || !isdigit(*b)) return b;
  32  *   }
  33  *
  34  *  Complete unrolling marks bottom-line (i.e. entire conversion)
  35  *  improvements of 20%.
  36  */
  37 inline const char* findFirstNonDigit(const char* b, const char* e) {
  38   for (; b < e; ++b) {
  39     auto const c = static_cast<unsigned>(*b) - '0';
  40     if (c >= 10) {
  41       break;
  42     }
  43   }
  44   return b;
  45 }
  46
  47 // Maximum value of number when represented as a string
  48 template <class T>
  49 struct MaxString {
  50   static const char* const value;
  51 };
  52
  53 template <> const char *const MaxString<uint8_t>::value = "255";
  54 template <> const char *const MaxString<uint16_t>::value = "65535";
  55 template <> const char *const MaxString<uint32_t>::value = "4294967295";
  56 #if __SIZEOF_LONG__ == 4
  57 template <> const char *const MaxString<unsigned long>::value =
  58   "4294967295";
  59 #else
  60 template <> const char *const MaxString<unsigned long>::value =
  61   "18446744073709551615";
  62 #endif
  63 static_assert(sizeof(unsigned long) >= 4,
  64               "Wrong value for MaxString<unsigned long>::value,"
  65               " please update.");
  66 template <> const char *const MaxString<unsigned long long>::value =
  67   "18446744073709551615";
  68 static_assert(sizeof(unsigned long long) >= 8,
  69               "Wrong value for MaxString<unsigned long long>::value"
  70               ", please update.");
  71
  72 #if FOLLY_HAVE_INT128_T
  73 template <> const char *const MaxString<__uint128_t>::value =
  74   "340282366920938463463374607431768211455";
  75 #endif
  76
  77 /*
  78  * Lookup tables that converts from a decimal character value to an integral
  79  * binary value, shifted by a decimal "shift" multiplier.
  80  * For all character values in the range '0'..'9', the table at those
  81  * index locations returns the actual decimal value shifted by the multiplier.
  82  * For all other values, the lookup table returns an invalid OOR value.
  83  */
  84 // Out-of-range flag value, larger than the largest value that can fit in
  85 // four decimal bytes (9999), but four of these added up together should
  86 // still not overflow uint16_t.
  87 constexpr int32_t OOR = 10000;
  88
  89 FOLLY_ALIGNED(16) constexpr uint16_t shift1[] = {
  90   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
  91   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
  92   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
  93   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
  94   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
  95   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
  96   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
  97   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
  98   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
  99   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 100   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 101   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 102   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 103   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 104   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 105   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 106   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 107   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 108   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 109   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 110   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 111   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 112   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 113   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 114   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 115   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 116 };
 117
 118 FOLLY_ALIGNED(16) constexpr uint16_t shift10[] = {
 119   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 120   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 121   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 122   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 123   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 124   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 125   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 126   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 127   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 128   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 129   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 130   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 131   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 132   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 133   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 134   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 135   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 136   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 137   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 138   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 139   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 140   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 141   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 142   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 143   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 144   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 145 };
 146
 147 FOLLY_ALIGNED(16) constexpr uint16_t shift100[] = {
 148   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 149   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 150   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 151   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 152   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 153   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 154   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 155   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 156   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 157   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 158   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 159   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 160   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 161   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 162   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 163   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 164   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 165   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 166   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 167   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 168   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 169   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 170   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 171   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 172   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 173   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 174 };
 175
 176 FOLLY_ALIGNED(16) constexpr uint16_t shift1000[] = {
 177   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 178   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 179   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 180   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 181   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 182   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 183   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 184   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 185   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 186   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 187   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 188   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 189   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 190   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 191   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 192   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 193   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 194   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 195   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 196   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 197   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 198   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 199   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 200   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 201   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 202   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 203 };
 204
 205 struct ErrorString {
 206   const char* string;
 207   bool quote;
 208 };
 209
 210 // Keep this in sync with ConversionError::Code in Conv.h
 211 constexpr const std::array<ErrorString, ConversionError::NUM_ERROR_CODES>
 212     kErrorStrings{{
 213         {"Success", true},
 214         {"Empty input string", true},
 215         {"No digits found in input string", true},
 216         {"Integer overflow when parsing bool (must be 0 or 1)", true},
 217         {"Invalid value for bool", true},
 218         {"Non-digit character found", true},
 219         {"Invalid leading character", true},
 220         {"Overflow during conversion", true},
 221         {"Negative overflow during conversion", true},
 222         {"Unable to convert string to floating point value", true},
 223         {"Non-whitespace character found after end of conversion", true},
 224         {"Overflow during arithmetic conversion", false},
 225         {"Negative overflow during arithmetic conversion", false},
 226         {"Loss of precision during arithmetic conversion", false},
 227     }};
 228
 229 // Check if ASCII is really ASCII
 230 using IsAscii = std::
 231     integral_constant<bool, 'A' == 65 && 'Z' == 90 && 'a' == 97 && 'z' == 122>;
 232
 233 // The code in this file that uses tolower() really only cares about
 234 // 7-bit ASCII characters, so we can take a nice shortcut here.
 235 inline char tolower_ascii(char in) {
 236   return IsAscii::value ? in | 0x20 : std::tolower(in);
 237 }
 238
 239 inline bool bool_str_cmp(const char** b, size_t len, const char* value) {
 240   // Can't use strncasecmp, since we want to ensure that the full value matches
 241   const char* p = *b;
 242   const char* e = *b + len;
 243   const char* v = value;
 244   while (*v != '\0') {
 245     if (p == e || tolower_ascii(*p) != *v) { // value is already lowercase
 246       return false;
 247     }
 248     ++p;
 249     ++v;
 250   }
 251
 252   *b = p;
 253   return true;
 254 }
 255
 256 } // anonymous namespace
 257
 258 ConversionError makeConversionError(
 259     ConversionError::Code code,
 260     const char* input,
 261     size_t inputLen) {
 262   assert(code >= 0 && code < kErrorStrings.size());
 263   const ErrorString& err = kErrorStrings[code];
 264   if (code == ConversionError::EMPTY_INPUT_STRING && inputLen == 0) {
 265     return ConversionError(err.string, code);
 266   }
 267   std::string tmp(err.string);
 268   tmp.append(": ");
 269   if (err.quote) {
 270     tmp.append(1, '"');
 271   }
 272   if (input && inputLen > 0) {
 273     tmp.append(input, inputLen);
 274   }
 275   if (err.quote) {
 276     tmp.append(1, '"');
 277   }
 278   return ConversionError(tmp, code);
 279 }
 280
 281 ConversionResult<bool> str_to_bool(StringPiece* src) {
 282   auto b = src->begin(), e = src->end();
 283   for (;; ++b) {
 284     if (b >= e) {
 285       return ConversionResult<bool>(ConversionError::EMPTY_INPUT_STRING);
 286     }
 287     if (!std::isspace(*b)) {
 288       break;
 289     }
 290   }
 291
 292   bool result;
 293   size_t len = e - b;
 294   switch (*b) {
 295     case '0':
 296     case '1': {
 297       result = false;
 298       for (; b < e && isdigit(*b); ++b) {
 299         if (result || (*b != '0' && *b != '1')) {
 300           return ConversionResult<bool>(ConversionError::BOOL_OVERFLOW);
 301         }
 302         result = (*b == '1');
 303       }
 304       break;
 305     }
 306     case 'y':
 307     case 'Y':
 308       result = true;
 309       if (!bool_str_cmp(&b, len, "yes")) {
 310         ++b;  // accept the single 'y' character
 311       }
 312       break;
 313     case 'n':
 314     case 'N':
 315       result = false;
 316       if (!bool_str_cmp(&b, len, "no")) {
 317         ++b;
 318       }
 319       break;
 320     case 't':
 321     case 'T':
 322       result = true;
 323       if (!bool_str_cmp(&b, len, "true")) {
 324         ++b;
 325       }
 326       break;
 327     case 'f':
 328     case 'F':
 329       result = false;
 330       if (!bool_str_cmp(&b, len, "false")) {
 331         ++b;
 332       }
 333       break;
 334     case 'o':
 335     case 'O':
 336       if (bool_str_cmp(&b, len, "on")) {
 337         result = true;
 338       } else if (bool_str_cmp(&b, len, "off")) {
 339         result = false;
 340       } else {
 341         return ConversionResult<bool>(ConversionError::BOOL_INVALID_VALUE);
 342       }
 343       break;
 344     default:
 345       return ConversionResult<bool>(ConversionError::BOOL_INVALID_VALUE);
 346   }
 347
 348   src->assign(b, e);
 349
 350   return ConversionResult<bool>(result);
 351 }
 352
 353 /**
 354  * StringPiece to double, with progress information. Alters the
 355  * StringPiece parameter to munch the already-parsed characters.
 356  */
 357 template <class Tgt>
 358 ConversionResult<Tgt> str_to_floating(StringPiece* src) {
 359   using namespace double_conversion;
 360   static StringToDoubleConverter
 361     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
 362          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
 363          0.0,
 364          // return this for junk input string
 365          std::numeric_limits<double>::quiet_NaN(),
 366          nullptr, nullptr);
 367
 368   if (src->empty()) {
 369     return ConversionResult<Tgt>(ConversionError::EMPTY_INPUT_STRING);
 370   }
 371
 372   int length;
 373   auto result = conv.StringToDouble(src->data(),
 374                                     static_cast<int>(src->size()),
 375                                     &length); // processed char count
 376
 377   if (!std::isnan(result)) {
 378     // If we get here with length = 0, the input string is empty.
 379     // If we get here with result = 0.0, it's either because the string
 380     // contained only whitespace, or because we had an actual zero value
 381     // (with potential trailing junk). If it was only whitespace, we
 382     // want to raise an error; length will point past the last character
 383     // that was processed, so we need to check if that character was
 384     // whitespace or not.
 385     if (length == 0 || (result == 0.0 && std::isspace((*src)[length - 1]))) {
 386       return ConversionResult<Tgt>(ConversionError::EMPTY_INPUT_STRING);
 387     }
 388     src->advance(length);
 389     return ConversionResult<Tgt>(result);
 390   }
 391
 392   auto* e = src->end();
 393   auto* b =
 394       std::find_if_not(src->begin(), e, [](char c) { return std::isspace(c); });
 395
 396   // There must be non-whitespace, otherwise we would have caught this above
 397   assert(b < e);
 398   size_t size = e - b;
 399
 400   bool negative = false;
 401   if (*b == '-') {
 402     negative = true;
 403     ++b;
 404     --size;
 405   }
 406
 407   result = 0.0;
 408
 409   switch (tolower_ascii(*b)) {
 410     case 'i':
 411       if (size >= 3 && tolower_ascii(b[1]) == 'n' &&
 412           tolower_ascii(b[2]) == 'f') {
 413         if (size >= 8 && tolower_ascii(b[3]) == 'i' &&
 414             tolower_ascii(b[4]) == 'n' && tolower_ascii(b[5]) == 'i' &&
 415             tolower_ascii(b[6]) == 't' && tolower_ascii(b[7]) == 'y') {
 416           b += 8;
 417         } else {
 418           b += 3;
 419         }
 420         result = std::numeric_limits<Tgt>::infinity();
 421       }
 422       break;
 423
 424     case 'n':
 425       if (size >= 3 && tolower_ascii(b[1]) == 'a' &&
 426           tolower_ascii(b[2]) == 'n') {
 427         b += 3;
 428         result = std::numeric_limits<Tgt>::quiet_NaN();
 429       }
 430       break;
 431
 432     default:
 433       break;
 434   }
 435
 436   if (result == 0.0) {
 437     // All bets are off
 438     return ConversionResult<Tgt>(ConversionError::STRING_TO_FLOAT_ERROR);
 439   }
 440
 441   if (negative) {
 442     result = -result;
 443   }
 444
 445   src->assign(b, e);
 446
 447   return ConversionResult<Tgt>(result);
 448 }
 449
 450 template ConversionResult<float> str_to_floating<float>(StringPiece* src);
 451 template ConversionResult<double> str_to_floating<double>(StringPiece* src);
 452
 453 /**
 454  * This class takes care of additional processing needed for signed values,
 455  * like leading sign character and overflow checks.
 456  */
 457 template <typename T, bool IsSigned = std::is_signed<T>::value>
 458 class SignedValueHandler;
 459
 460 template <typename T>
 461 class SignedValueHandler<T, true> {
 462  public:
 463   ConversionError::Code init(const char*& b) {
 464     negative_ = false;
 465     if (!std::isdigit(*b)) {
 466       if (*b == '-') {
 467         negative_ = true;
 468       } else if (UNLIKELY(*b != '+')) {
 469         return ConversionError::INVALID_LEADING_CHAR;
 470       }
 471       ++b;
 472     }
 473     return ConversionError::SUCCESS;
 474   }
 475
 476   ConversionError::Code overflow() {
 477     return negative_ ? ConversionError::NEGATIVE_OVERFLOW
 478                      : ConversionError::POSITIVE_OVERFLOW;
 479   }
 480
 481   template <typename U>
 482   ConversionResult<T> finalize(U value) {
 483     T rv;
 484     if (negative_) {
 485       rv = -value;
 486       if (UNLIKELY(rv > 0)) {
 487         return ConversionResult<T>(ConversionError::NEGATIVE_OVERFLOW);
 488       }
 489     } else {
 490       rv = value;
 491       if (UNLIKELY(rv < 0)) {
 492         return ConversionResult<T>(ConversionError::POSITIVE_OVERFLOW);
 493       }
 494     }
 495     return ConversionResult<T>(rv);
 496   }
 497
 498  private:
 499   bool negative_;
 500 };
 501
 502 // For unsigned types, we don't need any extra processing
 503 template <typename T>
 504 class SignedValueHandler<T, false> {
 505  public:
 506   ConversionError::Code init(const char*&) {
 507     return ConversionError::SUCCESS;
 508   }
 509
 510   ConversionError::Code overflow() {
 511     return ConversionError::POSITIVE_OVERFLOW;
 512   }
 513
 514   ConversionResult<T> finalize(T value) {
 515     return ConversionResult<T>(value);
 516   }
 517 };
 518
 519 /**
 520  * String represented as a pair of pointers to char to signed/unsigned
 521  * integrals. Assumes NO whitespace before or after, and also that the
 522  * string is composed entirely of digits (and an optional sign only for
 523  * signed types). String may be empty, in which case digits_to returns
 524  * an appropriate error.
 525  */
 526 template <class Tgt>
 527 inline ConversionResult<Tgt> digits_to(const char* b, const char* const e) {
 528   using UT = typename std::make_unsigned<Tgt>::type;
 529   assert(b <= e);
 530
 531   SignedValueHandler<Tgt> sgn;
 532
 533   auto err = sgn.init(b);
 534   if (UNLIKELY(err != ConversionError::SUCCESS)) {
 535     return ConversionResult<Tgt>(err);
 536   }
 537
 538   size_t size = e - b;
 539
 540   /* Although the string is entirely made of digits, we still need to
 541    * check for overflow.
 542    */
 543   if (size > std::numeric_limits<UT>::digits10) {
 544     // Leading zeros?
 545     if (b < e && *b == '0') {
 546       for (++b;; ++b) {
 547         if (b == e) {
 548           return ConversionResult<Tgt>(Tgt(0)); // just zeros, e.g. "0000"
 549         }
 550         if (*b != '0') {
 551           size = e - b;
 552           break;
 553         }
 554       }
 555     }
 556     if (size > std::numeric_limits<UT>::digits10 &&
 557         (size != std::numeric_limits<UT>::digits10 + 1 ||
 558          strncmp(b, MaxString<UT>::value, size) > 0)) {
 559       return ConversionResult<Tgt>(sgn.overflow());
 560     }
 561   }
 562
 563   // Here we know that the number won't overflow when
 564   // converted. Proceed without checks.
 565
 566   UT result = 0;
 567
 568   for (; e - b >= 4; b += 4) {
 569     result *= 10000;
 570     const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 571     const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 572     const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 573     const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 574     const auto sum = r0 + r1 + r2 + r3;
 575     if (sum >= OOR) {
 576       goto outOfRange;
 577     }
 578     result += sum;
 579   }
 580
 581   switch (e - b) {
 582   case 3: {
 583     const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 584     const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 585     const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 586     const auto sum = r0 + r1 + r2;
 587     if (sum >= OOR) {
 588       goto outOfRange;
 589     }
 590     result = 1000 * result + sum;
 591     break;
 592   }
 593   case 2: {
 594     const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 595     const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 596     const auto sum = r0 + r1;
 597     if (sum >= OOR) {
 598       goto outOfRange;
 599     }
 600     result = 100 * result + sum;
 601     break;
 602   }
 603   case 1: {
 604     const int32_t sum = shift1[static_cast<size_t>(b[0])];
 605     if (sum >= OOR) {
 606       goto outOfRange;
 607     }
 608     result = 10 * result + sum;
 609     break;
 610   }
 611   default:
 612     assert(b == e);
 613     if (size == 0) {
 614       return ConversionResult<Tgt>(ConversionError::NO_DIGITS);
 615     }
 616     break;
 617   }
 618
 619   return sgn.finalize(result);
 620
 621 outOfRange:
 622   return ConversionResult<Tgt>(ConversionError::NON_DIGIT_CHAR);
 623 }
 624
 625 template ConversionResult<char> digits_to<char>(const char*, const char*);
 626 template ConversionResult<signed char> digits_to<signed char>(
 627     const char*,
 628     const char*);
 629 template ConversionResult<unsigned char> digits_to<unsigned char>(
 630     const char*,
 631     const char*);
 632
 633 template ConversionResult<short> digits_to<short>(const char*, const char*);
 634 template ConversionResult<unsigned short> digits_to<unsigned short>(
 635     const char*,
 636     const char*);
 637
 638 template ConversionResult<int> digits_to<int>(const char*, const char*);
 639 template ConversionResult<unsigned int> digits_to<unsigned int>(
 640     const char*,
 641     const char*);
 642
 643 template ConversionResult<long> digits_to<long>(const char*, const char*);
 644 template ConversionResult<unsigned long> digits_to<unsigned long>(
 645     const char*,
 646     const char*);
 647
 648 template ConversionResult<long long> digits_to<long long>(
 649     const char*,
 650     const char*);
 651 template ConversionResult<unsigned long long> digits_to<unsigned long long>(
 652     const char*,
 653     const char*);
 654
 655 #if FOLLY_HAVE_INT128_T
 656 template ConversionResult<__int128> digits_to<__int128>(
 657     const char*,
 658     const char*);
 659 template ConversionResult<unsigned __int128> digits_to<unsigned __int128>(
 660     const char*,
 661     const char*);
 662 #endif
 663
 664 /**
 665  * StringPiece to integrals, with progress information. Alters the
 666  * StringPiece parameter to munch the already-parsed characters.
 667  */
 668 template <class Tgt>
 669 ConversionResult<Tgt> str_to_integral(StringPiece* src) {
 670   using UT = typename std::make_unsigned<Tgt>::type;
 671
 672   auto b = src->data(), past = src->data() + src->size();
 673
 674   for (;; ++b) {
 675     if (UNLIKELY(b >= past)) {
 676       return ConversionResult<Tgt>(ConversionError::EMPTY_INPUT_STRING);
 677     }
 678     if (!std::isspace(*b)) {
 679       break;
 680     }
 681   }
 682
 683   SignedValueHandler<Tgt> sgn;
 684   auto err = sgn.init(b);
 685
 686   if (UNLIKELY(err != ConversionError::SUCCESS)) {
 687     return ConversionResult<Tgt>(err);
 688   }
 689   if (std::is_signed<Tgt>::value && UNLIKELY(b >= past)) {
 690     return ConversionResult<Tgt>(ConversionError::NO_DIGITS);
 691   }
 692   if (UNLIKELY(!isdigit(*b))) {
 693     return ConversionResult<Tgt>(ConversionError::NON_DIGIT_CHAR);
 694   }
 695
 696   auto m = findFirstNonDigit(b + 1, past);
 697
 698   auto tmp = digits_to<UT>(b, m);
 699
 700   if (UNLIKELY(!tmp.success())) {
 701     return ConversionResult<Tgt>(
 702         tmp.error == ConversionError::POSITIVE_OVERFLOW ? sgn.overflow()
 703                                                         : tmp.error);
 704   }
 705
 706   auto res = sgn.finalize(tmp.value);
 707
 708   if (res.success()) {
 709     src->advance(m - src->data());
 710   }
 711
 712   return res;
 713 }
 714
 715 template ConversionResult<char> str_to_integral<char>(StringPiece* src);
 716 template ConversionResult<signed char> str_to_integral<signed char>(
 717     StringPiece* src);
 718 template ConversionResult<unsigned char> str_to_integral<unsigned char>(
 719     StringPiece* src);
 720
 721 template ConversionResult<short> str_to_integral<short>(StringPiece* src);
 722 template ConversionResult<unsigned short> str_to_integral<unsigned short>(
 723     StringPiece* src);
 724
 725 template ConversionResult<int> str_to_integral<int>(StringPiece* src);
 726 template ConversionResult<unsigned int> str_to_integral<unsigned int>(
 727     StringPiece* src);
 728
 729 template ConversionResult<long> str_to_integral<long>(StringPiece* src);
 730 template ConversionResult<unsigned long> str_to_integral<unsigned long>(
 731     StringPiece* src);
 732
 733 template ConversionResult<long long> str_to_integral<long long>(
 734     StringPiece* src);
 735 template ConversionResult<unsigned long long>
 736 str_to_integral<unsigned long long>(StringPiece* src);
 737
 738 #if FOLLY_HAVE_INT128_T
 739 template ConversionResult<__int128> str_to_integral<__int128>(StringPiece* src);
 740 template ConversionResult<unsigned __int128> str_to_integral<unsigned __int128>(
 741     StringPiece* src);
 742 #endif
 743
 744 } // namespace detail
 745 } // namespace folly