deps/v8/src/conversions.cc

   1 // Copyright 2011 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <limits.h>
   6 #include <stdarg.h>
   7 #include <cmath>
   8
   9 #include "src/v8.h"
  10
  11 #include "src/assert-scope.h"
  12 #include "src/char-predicates-inl.h"
  13 #include "src/conversions-inl.h"
  14 #include "src/conversions.h"
  15 #include "src/dtoa.h"
  16 #include "src/factory.h"
  17 #include "src/list-inl.h"
  18 #include "src/strtod.h"
  19 #include "src/utils.h"
  20
  21 #ifndef _STLP_VENDOR_CSTD
  22 // STLPort doesn't import fpclassify into the std namespace.
  23 using std::fpclassify;
  24 #endif
  25
  26 namespace v8 {
  27 namespace internal {
  28
  29
  30 namespace {
  31
  32 // C++-style iterator adaptor for StringCharacterStream
  33 // (unlike C++ iterators the end-marker has different type).
  34 class StringCharacterStreamIterator {
  35  public:
  36   class EndMarker {};
  37
  38   explicit StringCharacterStreamIterator(StringCharacterStream* stream);
  39
  40   uint16_t operator*() const;
  41   void operator++();
  42   bool operator==(EndMarker const&) const { return end_; }
  43   bool operator!=(EndMarker const& m) const { return !end_; }
  44
  45  private:
  46   StringCharacterStream* const stream_;
  47   uint16_t current_;
  48   bool end_;
  49 };
  50
  51
  52 StringCharacterStreamIterator::StringCharacterStreamIterator(
  53     StringCharacterStream* stream) : stream_(stream) {
  54   ++(*this);
  55 }
  56
  57 uint16_t StringCharacterStreamIterator::operator*() const {
  58   return current_;
  59 }
  60
  61
  62 void StringCharacterStreamIterator::operator++() {
  63   end_ = !stream_->HasMore();
  64   if (!end_) {
  65     current_ = stream_->GetNext();
  66   }
  67 }
  68 }  // End anonymous namespace.
  69
  70
  71 double StringToDouble(UnicodeCache* unicode_cache,
  72                       const char* str, int flags, double empty_string_val) {
  73   // We cast to const uint8_t* here to avoid instantiating the
  74   // InternalStringToDouble() template for const char* as well.
  75   const uint8_t* start = reinterpret_cast<const uint8_t*>(str);
  76   const uint8_t* end = start + StrLength(str);
  77   return InternalStringToDouble(unicode_cache, start, end, flags,
  78                                 empty_string_val);
  79 }
  80
  81
  82 double StringToDouble(UnicodeCache* unicode_cache,
  83                       Vector<const uint8_t> str,
  84                       int flags,
  85                       double empty_string_val) {
  86   // We cast to const uint8_t* here to avoid instantiating the
  87   // InternalStringToDouble() template for const char* as well.
  88   const uint8_t* start = reinterpret_cast<const uint8_t*>(str.start());
  89   const uint8_t* end = start + str.length();
  90   return InternalStringToDouble(unicode_cache, start, end, flags,
  91                                 empty_string_val);
  92 }
  93
  94
  95 double StringToDouble(UnicodeCache* unicode_cache,
  96                       Vector<const uc16> str,
  97                       int flags,
  98                       double empty_string_val) {
  99   const uc16* end = str.start() + str.length();
 100   return InternalStringToDouble(unicode_cache, str.start(), end, flags,
 101                                 empty_string_val);
 102 }
 103
 104
 105 // Converts a string into an integer.
 106 double StringToInt(UnicodeCache* unicode_cache,
 107                    Vector<const uint8_t> vector,
 108                    int radix) {
 109   return InternalStringToInt(
 110       unicode_cache, vector.start(), vector.start() + vector.length(), radix);
 111 }
 112
 113
 114 double StringToInt(UnicodeCache* unicode_cache,
 115                    Vector<const uc16> vector,
 116                    int radix) {
 117   return InternalStringToInt(
 118       unicode_cache, vector.start(), vector.start() + vector.length(), radix);
 119 }
 120
 121
 122 const char* DoubleToCString(double v, Vector<char> buffer) {
 123   switch (fpclassify(v)) {
 124     case FP_NAN: return "NaN";
 125     case FP_INFINITE: return (v < 0.0 ? "-Infinity" : "Infinity");
 126     case FP_ZERO: return "0";
 127     default: {
 128       SimpleStringBuilder builder(buffer.start(), buffer.length());
 129       int decimal_point;
 130       int sign;
 131       const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1;
 132       char decimal_rep[kV8DtoaBufferCapacity];
 133       int length;
 134
 135       DoubleToAscii(v, DTOA_SHORTEST, 0,
 136                     Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
 137                     &sign, &length, &decimal_point);
 138
 139       if (sign) builder.AddCharacter('-');
 140
 141       if (length <= decimal_point && decimal_point <= 21) {
 142         // ECMA-262 section 9.8.1 step 6.
 143         builder.AddString(decimal_rep);
 144         builder.AddPadding('0', decimal_point - length);
 145
 146       } else if (0 < decimal_point && decimal_point <= 21) {
 147         // ECMA-262 section 9.8.1 step 7.
 148         builder.AddSubstring(decimal_rep, decimal_point);
 149         builder.AddCharacter('.');
 150         builder.AddString(decimal_rep + decimal_point);
 151
 152       } else if (decimal_point <= 0 && decimal_point > -6) {
 153         // ECMA-262 section 9.8.1 step 8.
 154         builder.AddString("0.");
 155         builder.AddPadding('0', -decimal_point);
 156         builder.AddString(decimal_rep);
 157
 158       } else {
 159         // ECMA-262 section 9.8.1 step 9 and 10 combined.
 160         builder.AddCharacter(decimal_rep[0]);
 161         if (length != 1) {
 162           builder.AddCharacter('.');
 163           builder.AddString(decimal_rep + 1);
 164         }
 165         builder.AddCharacter('e');
 166         builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
 167         int exponent = decimal_point - 1;
 168         if (exponent < 0) exponent = -exponent;
 169         builder.AddDecimalInteger(exponent);
 170       }
 171     return builder.Finalize();
 172     }
 173   }
 174 }
 175
 176
 177 const char* IntToCString(int n, Vector<char> buffer) {
 178   bool negative = false;
 179   if (n < 0) {
 180     // We must not negate the most negative int.
 181     if (n == kMinInt) return DoubleToCString(n, buffer);
 182     negative = true;
 183     n = -n;
 184   }
 185   // Build the string backwards from the least significant digit.
 186   int i = buffer.length();
 187   buffer[--i] = '\0';
 188   do {
 189     buffer[--i] = '0' + (n % 10);
 190     n /= 10;
 191   } while (n);
 192   if (negative) buffer[--i] = '-';
 193   return buffer.start() + i;
 194 }
 195
 196
 197 char* DoubleToFixedCString(double value, int f) {
 198   const int kMaxDigitsBeforePoint = 21;
 199   const double kFirstNonFixed = 1e21;
 200   const int kMaxDigitsAfterPoint = 20;
 201   DCHECK(f >= 0);
 202   DCHECK(f <= kMaxDigitsAfterPoint);
 203
 204   bool negative = false;
 205   double abs_value = value;
 206   if (value < 0) {
 207     abs_value = -value;
 208     negative = true;
 209   }
 210
 211   // If abs_value has more than kMaxDigitsBeforePoint digits before the point
 212   // use the non-fixed conversion routine.
 213   if (abs_value >= kFirstNonFixed) {
 214     char arr[100];
 215     Vector<char> buffer(arr, arraysize(arr));
 216     return StrDup(DoubleToCString(value, buffer));
 217   }
 218
 219   // Find a sufficiently precise decimal representation of n.
 220   int decimal_point;
 221   int sign;
 222   // Add space for the '\0' byte.
 223   const int kDecimalRepCapacity =
 224       kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 1;
 225   char decimal_rep[kDecimalRepCapacity];
 226   int decimal_rep_length;
 227   DoubleToAscii(value, DTOA_FIXED, f,
 228                 Vector<char>(decimal_rep, kDecimalRepCapacity),
 229                 &sign, &decimal_rep_length, &decimal_point);
 230
 231   // Create a representation that is padded with zeros if needed.
 232   int zero_prefix_length = 0;
 233   int zero_postfix_length = 0;
 234
 235   if (decimal_point <= 0) {
 236     zero_prefix_length = -decimal_point + 1;
 237     decimal_point = 1;
 238   }
 239
 240   if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
 241     zero_postfix_length = decimal_point + f - decimal_rep_length -
 242                           zero_prefix_length;
 243   }
 244
 245   unsigned rep_length =
 246       zero_prefix_length + decimal_rep_length + zero_postfix_length;
 247   SimpleStringBuilder rep_builder(rep_length + 1);
 248   rep_builder.AddPadding('0', zero_prefix_length);
 249   rep_builder.AddString(decimal_rep);
 250   rep_builder.AddPadding('0', zero_postfix_length);
 251   char* rep = rep_builder.Finalize();
 252
 253   // Create the result string by appending a minus and putting in a
 254   // decimal point if needed.
 255   unsigned result_size = decimal_point + f + 2;
 256   SimpleStringBuilder builder(result_size + 1);
 257   if (negative) builder.AddCharacter('-');
 258   builder.AddSubstring(rep, decimal_point);
 259   if (f > 0) {
 260     builder.AddCharacter('.');
 261     builder.AddSubstring(rep + decimal_point, f);
 262   }
 263   DeleteArray(rep);
 264   return builder.Finalize();
 265 }
 266
 267
 268 static char* CreateExponentialRepresentation(char* decimal_rep,
 269                                              int exponent,
 270                                              bool negative,
 271                                              int significant_digits) {
 272   bool negative_exponent = false;
 273   if (exponent < 0) {
 274     negative_exponent = true;
 275     exponent = -exponent;
 276   }
 277
 278   // Leave room in the result for appending a minus, for a period, the
 279   // letter 'e', a minus or a plus depending on the exponent, and a
 280   // three digit exponent.
 281   unsigned result_size = significant_digits + 7;
 282   SimpleStringBuilder builder(result_size + 1);
 283
 284   if (negative) builder.AddCharacter('-');
 285   builder.AddCharacter(decimal_rep[0]);
 286   if (significant_digits != 1) {
 287     builder.AddCharacter('.');
 288     builder.AddString(decimal_rep + 1);
 289     int rep_length = StrLength(decimal_rep);
 290     builder.AddPadding('0', significant_digits - rep_length);
 291   }
 292
 293   builder.AddCharacter('e');
 294   builder.AddCharacter(negative_exponent ? '-' : '+');
 295   builder.AddDecimalInteger(exponent);
 296   return builder.Finalize();
 297 }
 298
 299
 300 char* DoubleToExponentialCString(double value, int f) {
 301   const int kMaxDigitsAfterPoint = 20;
 302   // f might be -1 to signal that f was undefined in JavaScript.
 303   DCHECK(f >= -1 && f <= kMaxDigitsAfterPoint);
 304
 305   bool negative = false;
 306   if (value < 0) {
 307     value = -value;
 308     negative = true;
 309   }
 310
 311   // Find a sufficiently precise decimal representation of n.
 312   int decimal_point;
 313   int sign;
 314   // f corresponds to the digits after the point. There is always one digit
 315   // before the point. The number of requested_digits equals hence f + 1.
 316   // And we have to add one character for the null-terminator.
 317   const int kV8DtoaBufferCapacity = kMaxDigitsAfterPoint + 1 + 1;
 318   // Make sure that the buffer is big enough, even if we fall back to the
 319   // shortest representation (which happens when f equals -1).
 320   DCHECK(kBase10MaximalLength <= kMaxDigitsAfterPoint + 1);
 321   char decimal_rep[kV8DtoaBufferCapacity];
 322   int decimal_rep_length;
 323
 324   if (f == -1) {
 325     DoubleToAscii(value, DTOA_SHORTEST, 0,
 326                   Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
 327                   &sign, &decimal_rep_length, &decimal_point);
 328     f = decimal_rep_length - 1;
 329   } else {
 330     DoubleToAscii(value, DTOA_PRECISION, f + 1,
 331                   Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
 332                   &sign, &decimal_rep_length, &decimal_point);
 333   }
 334   DCHECK(decimal_rep_length > 0);
 335   DCHECK(decimal_rep_length <= f + 1);
 336
 337   int exponent = decimal_point - 1;
 338   char* result =
 339       CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1);
 340
 341   return result;
 342 }
 343
 344
 345 char* DoubleToPrecisionCString(double value, int p) {
 346   const int kMinimalDigits = 1;
 347   const int kMaximalDigits = 21;
 348   DCHECK(p >= kMinimalDigits && p <= kMaximalDigits);
 349   USE(kMinimalDigits);
 350
 351   bool negative = false;
 352   if (value < 0) {
 353     value = -value;
 354     negative = true;
 355   }
 356
 357   // Find a sufficiently precise decimal representation of n.
 358   int decimal_point;
 359   int sign;
 360   // Add one for the terminating null character.
 361   const int kV8DtoaBufferCapacity = kMaximalDigits + 1;
 362   char decimal_rep[kV8DtoaBufferCapacity];
 363   int decimal_rep_length;
 364
 365   DoubleToAscii(value, DTOA_PRECISION, p,
 366                 Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
 367                 &sign, &decimal_rep_length, &decimal_point);
 368   DCHECK(decimal_rep_length <= p);
 369
 370   int exponent = decimal_point - 1;
 371
 372   char* result = NULL;
 373
 374   if (exponent < -6 || exponent >= p) {
 375     result =
 376         CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
 377   } else {
 378     // Use fixed notation.
 379     //
 380     // Leave room in the result for appending a minus, a period and in
 381     // the case where decimal_point is not positive for a zero in
 382     // front of the period.
 383     unsigned result_size = (decimal_point <= 0)
 384         ? -decimal_point + p + 3
 385         : p + 2;
 386     SimpleStringBuilder builder(result_size + 1);
 387     if (negative) builder.AddCharacter('-');
 388     if (decimal_point <= 0) {
 389       builder.AddString("0.");
 390       builder.AddPadding('0', -decimal_point);
 391       builder.AddString(decimal_rep);
 392       builder.AddPadding('0', p - decimal_rep_length);
 393     } else {
 394       const int m = Min(decimal_rep_length, decimal_point);
 395       builder.AddSubstring(decimal_rep, m);
 396       builder.AddPadding('0', decimal_point - decimal_rep_length);
 397       if (decimal_point < p) {
 398         builder.AddCharacter('.');
 399         const int extra = negative ? 2 : 1;
 400         if (decimal_rep_length > decimal_point) {
 401           const int len = StrLength(decimal_rep + decimal_point);
 402           const int n = Min(len, p - (builder.position() - extra));
 403           builder.AddSubstring(decimal_rep + decimal_point, n);
 404         }
 405         builder.AddPadding('0', extra + (p - builder.position()));
 406       }
 407     }
 408     result = builder.Finalize();
 409   }
 410
 411   return result;
 412 }
 413
 414
 415 char* DoubleToRadixCString(double value, int radix) {
 416   DCHECK(radix >= 2 && radix <= 36);
 417
 418   // Character array used for conversion.
 419   static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
 420
 421   // Buffer for the integer part of the result. 1024 chars is enough
 422   // for max integer value in radix 2.  We need room for a sign too.
 423   static const int kBufferSize = 1100;
 424   char integer_buffer[kBufferSize];
 425   integer_buffer[kBufferSize - 1] = '\0';
 426
 427   // Buffer for the decimal part of the result.  We only generate up
 428   // to kBufferSize - 1 chars for the decimal part.
 429   char decimal_buffer[kBufferSize];
 430   decimal_buffer[kBufferSize - 1] = '\0';
 431
 432   // Make sure the value is positive.
 433   bool is_negative = value < 0.0;
 434   if (is_negative) value = -value;
 435
 436   // Get the integer part and the decimal part.
 437   double integer_part = std::floor(value);
 438   double decimal_part = value - integer_part;
 439
 440   // Convert the integer part starting from the back.  Always generate
 441   // at least one digit.
 442   int integer_pos = kBufferSize - 2;
 443   do {
 444     double remainder = std::fmod(integer_part, radix);
 445     integer_buffer[integer_pos--] = chars[static_cast<int>(remainder)];
 446     integer_part -= remainder;
 447     integer_part /= radix;
 448   } while (integer_part >= 1.0);
 449   // Sanity check.
 450   DCHECK(integer_pos > 0);
 451   // Add sign if needed.
 452   if (is_negative) integer_buffer[integer_pos--] = '-';
 453
 454   // Convert the decimal part.  Repeatedly multiply by the radix to
 455   // generate the next char.  Never generate more than kBufferSize - 1
 456   // chars.
 457   //
 458   // TODO(1093998): We will often generate a full decimal_buffer of
 459   // chars because hitting zero will often not happen.  The right
 460   // solution would be to continue until the string representation can
 461   // be read back and yield the original value.  To implement this
 462   // efficiently, we probably have to modify dtoa.
 463   int decimal_pos = 0;
 464   while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
 465     decimal_part *= radix;
 466     decimal_buffer[decimal_pos++] =
 467         chars[static_cast<int>(std::floor(decimal_part))];
 468     decimal_part -= std::floor(decimal_part);
 469   }
 470   decimal_buffer[decimal_pos] = '\0';
 471
 472   // Compute the result size.
 473   int integer_part_size = kBufferSize - 2 - integer_pos;
 474   // Make room for zero termination.
 475   unsigned result_size = integer_part_size + decimal_pos;
 476   // If the number has a decimal part, leave room for the period.
 477   if (decimal_pos > 0) result_size++;
 478   // Allocate result and fill in the parts.
 479   SimpleStringBuilder builder(result_size + 1);
 480   builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
 481   if (decimal_pos > 0) builder.AddCharacter('.');
 482   builder.AddSubstring(decimal_buffer, decimal_pos);
 483   return builder.Finalize();
 484 }
 485
 486
 487 double StringToDouble(UnicodeCache* unicode_cache, Handle<String> string,
 488                       int flags, double empty_string_val) {
 489   Handle<String> flattened = String::Flatten(string);
 490   {
 491     DisallowHeapAllocation no_gc;
 492     String::FlatContent flat = flattened->GetFlatContent();
 493     DCHECK(flat.IsFlat());
 494     // ECMA-262 section 15.1.2.3, empty string is NaN
 495     if (flat.IsOneByte()) {
 496       return StringToDouble(unicode_cache, flat.ToOneByteVector(), flags,
 497                             empty_string_val);
 498     } else {
 499       return StringToDouble(unicode_cache, flat.ToUC16Vector(), flags,
 500                             empty_string_val);
 501     }
 502   }
 503 }
 504
 505
 506 bool IsNonArrayIndexInteger(String* string) {
 507   const int kBufferSize = 64;
 508   const int kUint32MaxChars = 11;
 509   uint16_t buffer[kBufferSize];
 510   int offset = 0;
 511   const int length = string->length();
 512   if (length == 0) return false;
 513   // First iteration, check for minus, 0 followed by anything else, etc.
 514   int to = std::min(offset + kUint32MaxChars, length);
 515   {
 516     String::WriteToFlat(string, buffer, offset, to);
 517     bool negative = false;
 518     if (buffer[offset] == '-') {
 519       negative = true;
 520       ++offset;
 521       if (offset == to) return false;  // Just '-' is bad.
 522     }
 523     if (buffer[offset] == '0') {
 524       return to == 2 && negative;  // Match just '-0'.
 525     }
 526     // Process positive integers.
 527     if (!negative) {
 528       uint64_t acc = 0;
 529       for (; offset < to; ++offset) {
 530         uint64_t digit = buffer[offset] - '0';
 531         if (digit > 9) return false;
 532         acc = 10 * acc + digit;
 533       }
 534       // String is consumed.  Evaluate what we have.
 535       if (offset == length) {
 536         return acc >
 537                static_cast<uint64_t>(std::numeric_limits<uint32_t>::max());
 538       }
 539     }
 540   }
 541   // Consume rest of string.  If we get here, we're way out of uint32_t bounds
 542   // or negative.
 543   int i = offset;
 544   while (true) {
 545     for (; offset < to; ++offset, ++i) {
 546       if (!IsDecimalDigit(buffer[i])) return false;
 547     }
 548     if (offset == length) break;
 549     // Read next chunk.
 550     to = std::min(offset + kBufferSize, length);
 551     String::WriteToFlat(string, buffer, offset, to);
 552     i = 0;
 553   }
 554   return true;
 555 }
 556 } }  // namespace v8::internal